Вопросы и задачи
Чем отличаются понятия «шифрование» и «кодирование»?
Что такое ключ?
Как называется наука, изучающая методы шифрования?
Что такое симметричный шифр? Какая проблема возникает при использовании симметричного шифра, если участники переписки находятся в разных странах?
Что такое несимметричные шифры? На чем основана их надежность?
Что такое криптостойкость алгоритма? Какой алгоритм считается криптостойким?
Зашифруйте с помощью шифра Цезаря со сдвигом 6 высказывание «ЛЮДИ ОХОТНО ВЕРЯТ ТОМУ, ЧЕМУ ЖЕЛАЮТ ВЕРИТЬ».
(Ответ: «СДКО ФЫФШУФ ИЛЦЕШ ШФТЩ, ЭЛТЩ МЛСЖДШ ИЛЦОШВ»).
*Попытайтесь расшифровать сообщение, закодированное шифром Цезаря с неизвестным сдвигом: «ХШЖНПУТ ФКХКОЙКТ». Для этого можно написать программу. (Ответ: «РУБИКОН ПЕРЕЙДЕН», сдвиг 5)
Используя шифр Виженера с ключом «ЛЕНА», зашифруйте сообщение «НЕЛЬЗЯ ОБИЖАТЬ ГОСТЯ».
(Ответ: «ШКШЬТД ОМНУАЭБ ГЩЦЯЯ»)
10.5. Хэширование и пароли
В современных информационных системах часто используется вход по паролю. Если при этом где-то хранить пароли всех пользователей, система становится очень ненадежной, потому что «утечка» паролей позволит сразу получить доступ к данным. С другой стороны, кажется, что пароли обязательно где-то нужно хранить, иначе пользователи не смогут войти в систему. Однако, это не совсем так. Можно хранить не пароли, а некоторые числа, полученные в результате обработки паролей. Простейший вариант - сумма кодов символов, входящих в пароль. Для пароля «А123» такая сумма равна
215 = 65 (код «А») + 49 (код «1») + 50 (код «2») + 51 (код «3»).
Фактически мы определили функцию H(M), которая сообщение M любой длины превращает в короткий код m заданной длины. Такая функция называются хэш-функцией (от англ. hash - «мешанина», «крошить»), а само полученное число - хэш-кодом, хэш-суммой или просто хэшем исходной строки. Важно, что зная хэш-код, невозможно восстановить исходный пароль! В этом смысле хэширование - это необратимое шифрование.
Итак, вместо пароля «А123» мы храним число 215. Когда пользователь вводит пароль, мы считаем сумму кодов символов этого пароля и разрешаем вход в систему только тогда, когда она равна 215. И вот здесь возникает проблема: существует очень много паролей, для которых наша хэш-функция дает значение 215, например, «В023». Такая ситуация - совпадение хэш-кодов различных исходных строк - называется коллизией (англ. collision - «столкновение»). Коллизии будут всегда - ведь мы «сжимаем» длинную цепочку байт до числа. Казалось бы, ничего хорошего не получилось: если взломщик узнает хэш-код, то, зная алгоритм его получения, он сможет легко подобрать пароль с таким же хэшем и получить доступ к данным. Однако, это произошло потому, что мы выбрали плохую хэш-функцию.
Математики разработали надежные (но очень сложные) хэш-функции, обладающие особыми свойствами:
хэш-код очень сильно меняется при малейшем изменении исходных данных;
при известном хэш-коде m невозможно за приемлемое время найти сообщение M с таким хэш-кодом (H(M) = m );
при известном сообщении M невозможно за приемлемое время найти сообщение Ml с таким же хэш-кодом (H(M) = H(Mj)).
Здесь выражение «невозможно за приемлемое время» (или «вычислительно невозможно») означает, что эта задача решается только перебором вариантов (других алгоритмов не существует), а количество вариантов настолько велико, что на решение уйдут сотни и тысячи лет. Поэтому даже если взломщик получил хэш-код пароля, он не сможет за приемлемое время получить сам пароль (или пароль, дающий такой же хэш-код).
Чем длиннее пароль, тем больше количество вариантов. Кроме длины, для надежности пароля важен используемый набор символов. Например, очень легко подбираются пароли, состоящие только из цифр. Если же пароль состоит из 10 символов и содержит латинские буквы (заглавные и строчные) и цифры, перебор вариантов (англ. brute force - метод «грубой силы») со скоростью 10 млн. паролей в секунду займет более 2000 лет.
Надежные пароли должны состоять не менее чем из 7-8 символов; пароли, состоящие из 15 символов и более взломать методом «грубой силы» практически невозможно. Нельзя использовать пароли типа «12345», «qwerty», свой день рождения, номер телефона. Плохо, если пароль представляет собой известное слово, для этих случаев взломщики используют подбор по словарю. Сложнее всего подобрать пароль, который представляет собой случайный набор заглавных и строчных букв, цифр и других знаков4.
Сегодня для хэширования в большинстве случаев применяют алгоритмы MD5, SHA1 и российский алгоритм, изложенный в ГОСТ Р 34.11 94 (он считается одним из самых надежных). В криптографии хэш-коды чаще всего имеют длину 128, 160 и 256 бит.
Хэширование используется также для проверки правильности передачи данных. Различные контрольные суммы, используемые для проверки правильности передачи данных, - это не что иное, как хэш-коды .
? Вопросы и задачи
Что такое хэширование? хэш-функция? хэш-код?
Какую хэш-функцию вы используете, когда начинаете искать слово в словаре?
Что такое коллизии? Почему их должно быть как можно меньше?
Какие требования предъявляются к хэш-функциям, которые используются при хранении паролей?
Что значит «вычислительно невозможно»?
Взломщик узнал хэш-код пароля администратора сервера. Сможет ли он получить доступ к секретным данным на сервере?
Какие свойства пароля влияют на его надежность?
Как выбрать надежный пароль?
Какие алгоритмы хэширования сейчас чаще всего применяются?
*Предложите какой-нибудь свой метод хэширования. Подумайте, как часто при его использовании могут происходить коллизии.
10.6. Современные алгоритмы шифрования
Государственным стандартом шифрования в России является алгоритм, зарегистрированный как ГОСТ 28147-89. Он является блочным шифром, то есть шифрует не отдельные символы, а 64-битные блоки. В алгоритме предусмотрено 32 цикла преобразования данных с 256-битным ключом, за счет этого он очень надёжен (обладает высокой криптостойкостью). На современных компьютерах раскрытие этого шифра путем перебора ключей («методом грубой силы») займет не менее сотен лет, что делает такую атаку бессмысленной. В США используется аналогичный блочный шифр AES.
В Интернете популярен алгоритм RSA, названный так по начальным буквам фамилий его авторов - Р. Райвеста (R. Rivest), А. Шамира (A. Shamir) и Л. Адлемана (L. Adleman). Это алгоритм с открытым ключом, стойкость которого основанный на использовании свойств простых чисел. Для его взлома нужно разложить очень большое число на простые сомножители. Эту задачу сейчас умеют решать только перебором вариантов. Поскольку количество вариантов огромно, для раскрытия шифра требуется много лет работы современных компьютеров.
Для применения алгоритм RSA требуется построить открытый и секретный ключи следующим образом.
Выбрать два больших простых числа,p и q.
Найти их произведение n = p • q и значение р = (p -1) • (q -1) .
Выбрать число e (1 < e < р), которое не имеет общих делителей с р.
Найти число d, которое удовлетворяет условию d • e = kp +1 для некоторого целого k.
Пара значений (e,n) - это открытый ключ RSA (его можно свободно публиковать), а пара (d,n) - это секретный ключ.
Передаваемое сообщение нужно сначала представить в виде последовательности чисел в интервале от 0 до n - 1. Для шифрования используют формулу
y = xe mod n,
где x - число исходного сообщения, (e,n) - открытый ключ, y - число закодированного сообщения, а запись xe mod n обозначает остаток от деления xe на n. Расшифровка сообщения выполняется по формуле
x = yd mod n.
Это значит, что зашифровать сообщение может каждый (открытый ключ общеизвестен), а прочитать его - только тот, кто знает секретный показатель степени d.
Для лучшего понимания мы покажем работу алгоритма RSA на простом примере. Возьмем p = 3 и q = 7 , тогда находим n = p • q = 21 и ф = (p -1) • (q -1) = 12. Выберем e = 5 , тогда равенство d • e = kty +1 выполняется, например, при d = 17 (и k = 7 ). Таким образом, мы получили открытый ключ (5,21) и секретный ключ (17,21).
Зашифруем сообщение «123» с помощью открытого ключа (5,21). Получаем 1 ^ 15 mod 21 = 1, 2 ^ 25 mod 21 = 11, 3 ^ 35 mod 21 = 12, то есть зашифрованное сообщение состоит из чисел 1, 11 и 12. Зная секретный ключ (17,21), можно его расшифровать:
1 ^ 117 mod 21 = 1, 11 ^ 1117 mod 21 = 2, 12 ^ 1217 mod 21 = 3. Мы получили исходное сообщение.
Конечно, вы заметили, что при шифровании и расшифровке приходится вычислять остаток от деления очень больших чисел (например, 1217) на n. Оказывается, само число 1217 в этом случае находить не нужно. Достаточно записать в обычную целочисленную переменную, например, x, единицу, а потом 17 раз выполнить преобразование x = 12-x mod 21. После этого в переменной x будет значение 1217 mod 21 = 3. Попробуйте доказать правильность этого алгоритма.
Для того, чтобы расшифровать сообщение, нужно знать секретный показатель степени d. А для этого, в свою очередь, нужно найти сомножители p и q, такие что n = p • q . Если n велико, это очень сложная задача, ее решение перебором вариантов на современном компьютере займет сотни лет. В 2009 году группа ученых из разных стран в результате многомесячных расчетов на сотнях компьютеров смогла расшифровать сообщение, зашифрованное алгоритмом RSA с 768- битным ключом. Поэтому сейчас надежными считаются ключи с длиной 1024 бита и более. Если будет построен работающий квантовый компьютер, взлом алгоритма RSA будет возможен за очень небольшое время.
При использовании симметричных шифров всегда возникает проблема: как передать ключ, если канал связи ненадежный? Ведь получив ключ, противник сможет расшифровать все дальнейшие сообщения. Для алгоритма RSA этой проблемы нет, сторонам достаточно обменяться открытыми ключами, которые можно показывать всем желающим.
У алгоритма RSA есть еще одно достоинство: его можно использовать для цифровой подписи сообщений. Она служит для доказательства авторства документов, защиты сообщений от подделки и умышленных изменений.
|
