Криптография

kIlka(kilka@linkin-park.ru) и AssassiN(vault13@mailgate.ru)

Спецвыпуск Xakep, номер #041

---

Для тех, кому есть что скрывать

...С каждого заметного угла смотрело лицо черноусого. С дома напротив – тоже. СТАРШИЙ БРАТ СМОТРИТ НА ТЕБЯ – говорила подпись... (Джордж Оруэлл "1984")

Вступление

Скрыть свои намерения от окружающих всегда приятно, а иногда даже необходимо. Когда они в твоей голове, это не трудно. Но что если они мирно покоятся на твоем харде? Замуровать комп в стену? Тоже метод. Но как же юзать CD? Немного проще зашифровать личную информацию.

Ты помнишь, как все начиналось

Люди начали задумываться об этом, с тех пор как приспособились записывать свои мысли. Развитая криптография существовала в Древней Греции. Использовалась банальная перестановка букв в тексте и замена букв другими буквами алфавита (или специальными символами) по определенному алгоритму. Этот способ использовал Юлий Цезарь. Он применял подстановку, где буквы сдвигались циклически на три позиции вправо.

В иных методах буквы послания заменялись парой цифр. Алфавит записывался в матрицу 5x5 - так называемый "квадрат Полибия". Подобный принцип "шифрования" до сих пор применяется в таблице ASCII.

Одно из слабых мест этих методов – низкая сопротивляемость частотному анализу. К примеру, зная частоту появления букв алфавита в тексте, можно найти соответствие между символами в послании и в шифре. Чтобы снизить подверженность алгоритма такому способу дешифрации, были разработаны методы шифрования пропорциональной замены. Букву заменяли несколькими символами. Их количество было пропорционально частоте появления буквы в послании.

Шифры с ключом

Однако если одно и то же сообщение повторяется несколько раз (возможно, с незначительными изменениями), то противник может догадаться о его содержании и разгадать шифр. Следующим шагом в эволюции криптографии стало появление шифров с ключами. Теперь текст "шифровки" стал зависеть не только от содержания послания, но и от значения ключа – определенной последовательности букв или цифр, определяющей способ шифрования/дешифрации. Рассмотрим пример метода, в котором ключ используется для перестановки символов определенным образом. Его суть проще всего понять на конкретном примере. Допустим, нам жизненно необходимо зашифровать фразу "ДОЛОЙ СТАРШЕГО БРАТА".

Шифрование с использованием ключа

Для этого сначала выберем ключ шифровки, который должен быть известен только нам и получателю (в нашем случае это "КОРОВА"). Теперь секретную фразу запишем без пробелов по столбцам в таблицу 6x3 (длина ключа – 6 символов, длина сообщения – 18 символов). Далее над столбцами матрицы напишем ключевое слово, тем самым сопоставив каждому столбцу букву алфавита. А затем отсортируем столбцы по алфавиту. Осталось только записать шифр фразы (строки полученной таблицы): "АОДОШТТБОЙЕААРЛСГР".

Еще один простой пример – применение к посланию и ключу операции XOR (побитовое исключающее ИЛИ). Дешифрация очень проста – она состоит в повторном применении XOR’а (т.к. если a = b XOR c, то и b = a XOR c).

Шифрование операцией XOR

Вроде бы, отличный алгоритм! Но если, как в примере, мы будем использовать ключ длиной всего 3 байта, то у нас возникнут проблемы. При современном быстродействии компьютеров разгадать такой шифр - не проблема. Другое дело, если ключ имеет длину, равную длине послания, и каждый символ в нем равновероятен (выбирается случайным образом). Такой алгоритм носит название одноразовой гаммы Вернама. Можно показать математически, что одноразовая гамма Вернама обладает абсолютной теоретико-информационной стойкостью. Это значит, что даже противник, обладающий неограниченными ресурсами (временными, вычислительными), не может "расколоть" этот шифр.

Однако, как нетрудно заметить, и такой шифр неидеален. Необходимо каждый раз передавать объемистый ключ по защищенному каналу. Поэтому при создании современных криптографических схем стараются достигнуть компромисса между сложностью алгоритма и его криптостойкостью. Исходя из того, что предполагаемый противник ограничен в ресурсах, можно сказать, что такой подход оправдывает себя. Действительно, много ли разницы между шифром, который можно дешифровать за тысячу лет, и шифром, который вообще нельзя дешифровать?

Сеть Файстеля и DES

Самое время поговорить о каком-нибудь современном криптоалгоритме. Пожалуй, самым известным алгоритмом, использующим один ключ, являются DES (Data Encription Standart). До недавнего времени он был официальным американским стандартом для защиты линий связи и компьютерных данных. История его принятия в этом качестве не менее интересна, чем сам алгоритм. Поговаривают, что NSA (National Security Agency) предполагала, что будут существовать лишь аппаратные реализации DES (то есть, что он будет реализован лишь в специальных микросхемах). Однако NSA и NBS (National Bureau of Standarts) не договорились. И в итоге опубликованное описание алгоритма оказалось настолько полным, что можно было без труда выполнить и программную реализацию. Так алгоритм стал доступен широким массам трудящихся =).

Один раунд шифрования в сети Файстеля

Основой для DES послужил разработанный инженерами IBM алгоритм Люцифер. Люцифер основывался на принципе, предложенном Хорстом Файстелем и получившем название сеть Файстеля. В сущности, сеть Файстеля базируется все на том же XOR’е (то есть представляет собой гаммирование). Хитрость - в выборе гаммы. Легче всего понять алгоритм из рисунка. Блок данных определенной длины (для DES это 64 бита) делится на две части (равные или нет, зависит от типа сети – сбалансированной или нет соответственно). Правая часть Rj ставится на место левой. Левая же часть XOR’ится с Fj. Fj – функция гаммирования, зависящая от Rj и Kj (исходный ключ преобразуется на j шаге в Kj). В алгоритме таких шагов (называемых раундами) может быть несколько. DES состоит из 16 раундов. Длина его ключа – 64 бита, правда, реально работают лишь 56 (8 используются для проверки четности). Еще одна интересная особенность DES – его симметричность. Для дешифровки используется тот же алгоритм, что и для шифрования. Это связано с симметрией последовательности Kj. Среди 2^56 возможных ключей DES существуют 80 так называемых слабых. Однако определение того, является ли ключ слабым, элементарно. И все же ключ длиной в 56 бит по нынешним меркам коротковат. Поэтому многие сейчас используют тройное шифрование при помощи DES с различными ключами – тройной DES. Американцы же в 2001 году приняли новый стандарт AES на базе алгоритма Rijndael. Длина ключа Rijndael варьируется от 128 до 256 битов.

Еще один алгоритм, базирующийся на сбалансированной сети Файстеля – RC6. Однако в нем наблюдается некоторое отступление от традиционной схемы. Блок делится не на 2 половинки, а на 4 куска. Изменяемые и неизменяемые части чередуются. Размер блока и ключа, а также число раундов могут меняться в широких пределах. Этот алгоритм, как и Rijndael, участвовал в конкурсе при принятии AES.

Криптосистемы с открытым ключом и RSA

До сих пор мы рассматривали криптографические схемы, использующие только один ключ (из-за этого их часто называют симметричными криптосистемами или криптосистемами с секретным ключом). Их общим недостатком является необходимость передачи ключа по защищенному каналу. Этого недостатка лишены системы шифрования с открытым ключом, первые теоретические наброски которых появились в 70-х годах 20 века. В них, в отличие от традиционных методов шифрования, используется не один, а два ключа – открытый (public key) и секретный (secret key). Одной из наиболее известных криптосистем такого рода является криптосистема RSA. Поразительно, что, несмотря на полную открытость алгоритма, практически невозможно за разумное время дешифровать сообщение. Это связано с тем, что в настоящее время разработаны эффективные алгоритмы нахождения больших простых чисел, и вместе с тем не создан достаточно быстрый алгоритм разложения произведения двух простых чисел на множители.

Рассмотрим механизм работы RSA. Пусть у нас ведут переговоры две личности: kIlka и AssassiN. Каждый имеет свой открытый (известный всем) и секретный (хранящийся в тайне) ключи, которые мы будем обозначать P и S соответственно с индексами K и A в зависимости от обладателя. Пусть Н – множество всевозможных посланий. Каждый ключ задает перестановку множества Н. Через PA() и SA() обозначим перестановки, соответствующие ключам AssassiN'а. Ключи таковы, что справедливы следующие равенства: M = SA(PA(M)); M = PA(SA(M)).

Шифрование алгоритмом RSA

Предположим, что kIlka пишет AssassiN'y секретное сообщение. Сначала он узнает PA, потом зашифровывает сообщение M и отправляет адресату результат C = PA(M). AssassiN получает шифровку C, а потом восстанавливает сообщение M = SA(C).

В общих чертах схема построения пары ключей для криптосистемы RSA выглядит так:

1. Выбираются два БОЛЬШИХ простых числа r и h (примерно 100 десятичных цифр в каждом).
2. Вычисляется n=r*h.
3. Выбирается небольшое нечетное число е, взаимно простое с t=(r-1)*(h-1).
4. Вычисляется d=(e^-1) mod t.

P(M) = (M^e) mod n – преобразование, соответствующее открытому ключу, S = (M^d) mod n – преобразование, соответствующее секретному ключу.

Суть в том, что только AssassiN может вычислить функцию SA() за разумное время, так как только он знает число d. Конечно, злоумышленник может разложить известное ему число n на множители r и h и тем самым определить d. Но существующие ныне алгоритмы будут пыхтеть над разложением n очень долго. Кстати, если кого-то интересует математически строгое обоснование корректности RSA, то найти его можно в [2].

Цифровая подпись

Интересным свойством криптосистем с открытым ключом (и в частности - криптосистемы RSA) является то, что они позволяют не только шифровать сообщения, но и создавать так называемые "цифровые подписи" (digital signature), удостоверяющие авторство и правдивость сообщения.

RSA-алгоритм создания цифровой подписи

Вот как это происходит. AssassiN пишет ответ M kIlk'е, далее вычисляет цифровую подпись E=SA(M) и отсылает пару (M,E) kIlk'е, который, в свою очередь, получает пару (M,E) и убеждается в подлинности послания, проверив равенство M=PA(E). Таким образом можно подписывать, например, банковские поручения, а если нужно сохранить секретность, то пару (M,E) следует тоже зашифровать.

Очевидно, генерируемая таким образом цифровая подпись избыточна – размер ее пропорционален размеру сообщения, а ведь необходимо время на ее создание, пересылку вместе с секретной информацией и дешифрацию. Поэтому для создания цифрового росчерка применяют однонаправленную хеш-функцию. Такая функция (обозначим ее H()) преобразуют сообщения в достаточно короткие "образы". Причем не существует двух различных сообщений A и B, для которых H(A) = H(B) (это предположение верно в разумных пределах, естественно; например, у 128-битной хеш-функции будет 2^128 вариантов хеша, учитывая, что сообщений существует больше, то разумно предположить: существуют некие сообщения M1 и M2, такие, что H(M1) = H(M2) - прим. ред.). AssassiNу достаточно зашифровать с помощью SA() не все сообщение M, а лишь H(M).

Однако и криптографические схемы с открытым ключом не лишены недостатков. Главный из них – невозможность достоверно определить, кому принадлежит открытый ключ. Злоумышленник может перехватить открытый ключ твоего товарища, а вместо него прислать свой. Тогда с дешифровкой у него проблем не возникнет. Для борьбы с такими умниками используется так называемый центр доверия. Образно говоря, это некий чрезвычайно честный человек, имеющий свой открытый ключ. Он может выдавать страждущим справки, подписанные его цифровой подписью, что их открытые ключи принадлежат действительно им.

Под занавес хочется сказать несколько слов о слабых местах криптографических систем. В последнее время в подавляющем большинстве компьютерных программ, использующих криптографию, применяются алгоритмы, надежность которых доказана математически. Но все же конкретная реализация может иметь слабое место, а иногда и не одно. Хранение ключей или незашифрованных данных на жестком диске для лучшей сохранности, утюги и паяльники злоумышленников и тому подобные глупости могут свести на нет всю математическую надежность криптоалгоритма... Вот и я для лучшей защищенности моего PGP диска пойду долбить стенку. С CD как-нибудь разберусь. Думаю, цемент M-500 будет в самый раз =).

Шифры Виженера как обобщение шифра Цезаря

В современной криптографии шифры, подобные шифру Цезаря, объединяются в одну группу, именуемую шифрами Виженера. В криптоалгоритмах такого рода ключом является последовательность символов некоторой длины n. Этот ключ записывается с повторением под секретным посланием, а затем две полученные последовательности суммируются по модулю m (в случае латинского алфавита m=26). В итоге получаем формулу: S(j)=P(j)+K(j) (mod m). Здесь K(j) – буква ключа, находящаяся на (j mod n)-ом месте.

Дополнительная информация по теме

Книги и статьи:

1. Клод Шеннон "Теория связи в секретных системах";
2. Т.Кормен, Ч.Лейзерзон, Р.Ривест "Алгоритмы: построение и анализ";
3. Брюс Шнайер "Криптография: протоколы, алгоритмы и исходные тексты на языке C";
4. Хорст Файстель "Криптография и компьютерная безопасность".

Все эти книги, за исключением [2], есть в виде pdf-файлов в Сети. Они, а также куча других полезных вещей, лежат здесь: www.cryptography.ru; www.enlight.ru/crypto/; www.ssl.stu.neva.ru/psw/crypto.html.

"Криптография бывает двух типов: криптография, которая помешает читать ваши файлы вашей младшей сестре, и криптография, которая помешает читать ваши файлы дядям из правительства". Брюс Шнайер.

В средневековье криптографией пользовались в основном военные и представители церкви.

Современная наука о шифрах называется криптологией и включает в себя криптографию и криптоанализ.

Если ваш шифр надежен главным образом потому, что никто не знает, как он работает, то он не надежен вовсе.

Долгое время люди не очень доверяли DES. Ходили слухи, что NSA внесло в проект IBM изменения, позволившие правительству легко взламывать DES. Однако сейчас достоверно известно, что это не так.

Современное законодательство США позволяет NSA контролировать экспорт криптографических систем.

Разрешенный к экспорту вариант алгоритма RC4, длина ключа которого составляет 40 бит, используется в SSL. К сожалению, он может быть довольно легко вскрыт.

В 1978 авторами RSA было опубликовано число-шифр и назначено вознаграждение тому, кто первый дешифрует его. Задача была решена лишь спустя 17 лет при помощи распределенных вычислений через интернет.

Математики относят функции, подобные SA(), к специальному классу – функции с секретом (trapdoor functions).

Еще один алгоритм шифрования с открытым ключом – DSA (Digital Signature Algorithm) – может быть использован лишь для создания цифровой подписи.


Источник