Математика и криптография. Тайны шифров и логическое мышление - Роман Душкин

Это описание рассказывает о сути невзламываемой системе шифрования. Вот она вся как есть:

1. Для шифрования текста необходимо воспользоваться операцией XOR.

2. Ключ должен быть такой же длины, как и шифруемый открытый текст.

3. Ключ должен состоять из случайного набора символов.

4. Ни один ключ не должен использоваться более одного раза. Никогда! Ни при каких условиях!

Эти четыре простых правила дают абсолютную защиту.

Давай подробнее разберём, что происходит и почему необходимо неукоснительно соблюдать эти правила, чтобы шифр невозможно было взломать.

Правило первое на самом деле не такое уж абсолютное. Дело в том, что, как мы уже видели, операция XOR даёт очень простой и быстрый способ получения из двух букв новой. Но точно так же можно воспользоваться и любой другой таблицей подстановки — например, той, что приведена в описании второй недели, то есть шифром сдвига. Да и вообще можно составить любую таблицу многоалфавитной замены, где способ замены будет определяться буквой ключа. Главное, чтобы она была удобна и однозначна. Мне кажется удобной именно таблица для операции XOR.

Второе правило говорит о том, что длина ключа должна быть равна длине шифруемого сообщения. Это просто объяснить. Если длина ключа будет меньше длины шифруемого сообщения, то ключ будет повторяться при шифровании. А как взламывать шифрограммы с периодическим ключом, мы уже изучили на второй неделе. Да, если ключ будет достаточно длинным, взломать сообщение будет сложно. Но возможно.

Третье правило: ключ должен быть абсолютно случаен. Нельзя использовать в качестве ключа какой-либо осмысленный текст. Это было понятно из описания попыток горе-аналитика взломать шифрограмму слова «КАТАПУЛЬТА». Если бы это слово было зашифровано при помощи другого осмысленного слова, то в процессе перебора криптоаналитик наткнулся бы на такой осмысленный ключ и сделал резонный вывод, что он получил расшифровку. Кроме того, если использовать осмысленный ключ (даже и такой же длины, как и шифруемое сообщение), тайное послание превратится в банальный шифр многоалфавитной замены, к которому применим частотный анализ. Более того, не придется задумываться о длине ключа, поскольку надо будет анализировать частоты пар символов.

Наконец, главное правило: никогда, ни при каких условиях один и тот же ключ нельзя использовать дважды. Это очень важно. Всё дело в том, что если криптоаналитик получит два сообщения, зашифрованные одним и тем же ключом, каким бы длинным он ни был, то оба этих сообщения будут очень быстро взломаны. Можно просто применить к ним обоим операцию XOR, и тогда, насколько ты помнишь её свойства, секретный ключ просто взаимоуничтожится, и получится зашифрованное сообщение, состоящее из двух осмысленных текстов. А это очень легко взламывается частотным анализом. Дело тут даже не в операции XOR. Любая таблица многоалфавитной замены предполагает обратную операцию. Просто операция XOR обратна сама для себя, поэтому она так удобна.

Как происходит такое шифрование? У двух людей, которые желают обмениваться секретными данными этим абсолютно надёжным способом, должны быть специальные одинаковые блокноты с ключами. На каждой странице такого блокнота написаны случайные символы. Когда первый человек посылает второму секретное сообщение, он зашифровывает его при помощи ключа на первой странице блокнота. Второй человек, получив сообщение, расшифровывает его при помощи такого же ключа на первой странице его блокнота. После этого и первый и второй вырывают первую страницу блокнота и уничтожают её (лучше всего сжечь и смешать пепел; если просто выкинуть страницу с ключом в мусорное ведро, то она может быть найдена зловредным криптоаналитиком, и тогда всё пропало). Далее всё повторяется. Каждый раз после использования ключа с очередной страницы эта страница уничтожается. Потому-то метод и называется одноразовым блокнотом.

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

Теперь я расскажу тебе, почему этот способ шифрования не используется так широко. Если ты подумаешь, то поймёшь, что проблема заключается в передаче ключа. Одноразовый ключ должен быть заранее создан и получен теми двумя лицами, которые должны обмениваться секретной информацией. Это сделать не так сложно, если их действительно всего двое. А представь, к примеру, штаб, которому необходимо обмениваться секретной информацией с сотнями разведчиков по всему миру. Одноразовые блокноты не должны повторяться у разных людей. То есть для каждого разведчика надо создать свой блокнот, как-то передать его, а потом время от времени обновлять, когда блокнот заканчивается. Это связано с очень большими расходами и риском раскрыть свою агентурную сеть.

Передавать же секретный ключ по открытым каналам связи, как ты понимаешь, нельзя. Это должна быть надёжная передача, а пока не придумали ничего надёжнее, чем передача из рук в руки. Впрочем, существует метод скрытой передачи по открытому каналу. Но он связан с серьёзной математикой, и его описание выходит за рамки этой книги. К тому же он всё равно остаётся довольно громоздким и проблематичным. Так что мы изучим его в другой раз. Но и этот метод полностью не решает проблемы распределения ключей (запомни, кстати, этот термин).

Но возможно, ты можешь передать секретные ключи одному или нескольким своим коллегам по секретной переписке. Тогда я сейчас научу тебя генерировать такие ключи. И ты поймёшь, что это тоже непросто и связано с большим расходом времени и сил.

Вспомни, как мы научились кодировать все буквы алфавита при помощи пяти двоичных цифр (нулей и единиц). Для каждой буквы нужно пять двоичных цифр, то есть пять бит информации. Как получить случайные пять бит? Да очень просто. Для этого надо воспользоваться пятью монетками. Возьми пять монет разного достоинства (чтобы различать их): 10 копеек, 50 копеек, 1 рубль, 2 рубля и 5 рублей (или какие-то еще). Орёл обозначает 0, решка обозначает 1. Брось пять монет и запиши результат по порядку от 10 копеек до 5 рублей. Таким способом ты получишь один символ. Если все монеты выпадут орлом (это соответствует 00000, то есть пробел), то не используй этот символ.

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

На этом наше путешествие в мир криптографии и криптоаналитики заканчивается. Но я затрону ещё две интересные темы, которые останутся тебе в качестве домашнего задания (про них не будет знать тот, с кем ты переписывался всё лето). А в самом конце книги я перечислю, что интересного можно почитать на тему криптографии, если ты заинтересовался этой областью прикладной науки.

Вот тебе первое домашнее задание. Придумай шифр «одноалфавитной» подстановки, но не как обычно, для каждой буквы, а по одному символу для пары букв. Возьми уже знакомый алфавит из тридцати двух символов и составь таблицу размером 32 × 32. Строки и столбцы таблицы обозначь символами нашего алфавита. А в каждой ячейке придумай замену паре символов в виде какого-нибудь экзотического знака.