Математика и криптография

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

Но начнём. Вспомни, пожалуйста, тему четвёртой недели, когда мы изучали новую математическую операцию XOR. Сейчас это тебе пригодится. Если требуется, перечитай соответствующую главу и выполни несколько упражнений, применяя операцию XOR к двоичным числам. А теперь продолжай чтение.

Представь, что тебе необходимо зашифровать какую-либо фразу. Пусть это будет простое слово «КАТАПУЛЬТА». В качестве ключа для применения операции XOR пусть используется последовательность символов «ВОАЫДЛАОВЬ». Что получится в результате? Правильно: последовательность «ЗНСЭФЧМУПЩ», которая и будет нашей шифрограммой.

Если криптоаналитик перехватит шифрограмму, у него окажется этот странный текст: «ЗНСЭФЧМУПЩ». Как подойти к расшифровке? Он может последовательно перебирать все возможные ключи, в какой-то момент наткнётся на ключ «АЕРЪГЯКЩШЫ» и при расшифровке получит слово «ИЗВЕРЖЕНИЕ». Дальше он встретит ключ «АКУСРИЛШЭЪ», которому при расшифровке будет соответствовать слово «ИДЕОГРАММА». И так далее.

Очевидно, что так криптоаналитик переберёт все возможные ключи и получит все возможные слова длиной в 10 букв (даже больше, он получит и обрывки фраз длиной в 10 букв). Но какое из них верное? Нет никакой возможности выбрать правильный вариант, поскольку ни один ключ не будет правильным словом — все ключи окажутся случайными наборами символов.

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

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

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

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

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

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

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

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

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

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

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