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

kIlka и AssassiN

Спецвыпуск Xakep, номер #041, стр. 041-004-1

(vault13@mailgate.ru) (kilka@linkin-park.ru)

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

Эпиграф

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

Вступление

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

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

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

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

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

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

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

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

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

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

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

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