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

ЕКРЕТ

). ЭТО НЕ Т

К

О

НО, Т

К

ТО

О

ЕРИ

Ь И

П

И

Ь ТЕРПЕНИЕМ,

КОРО Т

В

У

Е

Ь

Н

ТЬ И УМЕТЬ

МО

ТО

ТЕ

ЬНО.

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

Это упражнение должно было научить тебя нескольким полезным вещам, а именно:

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

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

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

4. Наконец, в шифрограммах нежелательно употреблять короткие слова: предлоги, союзы, частицы, встречающиеся в обычных текстах много раз. Это всё – первые подсказки для криптоаналитика, при помощи которых он сможет взломать шифр. Сообщение вполне может быть понятным без предлогов и частиц: «Прибыть пункт распределения завтра десять тридцать». Попробуй зашифровать эту фразу каким-нибудь шифром простой подстановки, а потом применить к ней метод частотного анализа, и ты увидишь, насколько это сложнее.

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

Неделя 2. Шифр многоалфавитной замены

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

Во-первых, давай считать пробел символом. Да, с математической точки зрения пробел – это такой же символ, как и любой другой. Я специально использую слово «символ», а не «буква», чтобы не путать. Итак, все буквы, цифры, пунктуационные знаки и даже пробел являются символами. Но главное – это понять, что пробел – не отсутствие символа, а отдельный символ. В предложении «ЭТА ФРАЗА СОДЕРЖИТ 3 °СИМВОЛОВ» действительно содержится 30 символов: 24 буквы, 2 цифры и 4 пробела.

Во-вторых, давай в дальнейшем для шифрования использовать только заглавные буквы русского алфавита и пробел, причём будем считать пары букв «Е» и «Ё», а также «Ъ» и «Ь» неразличимыми. Теперь в наших текстах и шифрограммах символ «Е» будет обозначать как букву «Е», так и букву «Ё», а символ «Ъ» будет обозначать буквы «Ъ» «Ь». Таким образом, весь алфавит теперь состоит из следующих символов:

Пробел А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Э Ю Я

Примечательность этого алфавита в том, что в нём содержится ровно 32 символа.

С каждым из этих символов мы сопоставим число от 0 до 31, которое назовём кодом. То есть «пробел» будет иметь код 0, буква «А» – код 1 и так далее – до буквы «Я», которой мы присвоим код 31.

После этого надо научиться складывать и вычитать особым образом (математики называют такие операции сложением и вычитанием с вычетами). Итак, у нас есть только тридцать два числа – от 0 до 31. Мы хотим складывать и вычитать при помощи этих чисел, и никакие другие числа нам использовать нельзя. Очень просто, например, сложить 5 и 8, поскольку получится 13. Но как быть, если нам надо сложить, скажем, 23 и 17? Обычная арифметика подсказывает, что 23 + 17 = 40, но у нас нет чисел, которые больше 31. Как быть? Всё просто. Если полученный результат больше 31, надо вычесть из него общее количество чисел, то есть 32. Другими словами, по правилам нашей новой арифметики (немного странной на первый взгляд) получается, что 23 + 17 = 40–32 = 8.

То же самое с вычитанием. Легко вычесть из 15, скажем, 12, поскольку получится 3. А как вычесть из меньшего числа большее, например, из 10–27? Тут тоже просто. Если из меньшего числа требуется вычесть большее, то сначала к меньшему надо прибавить 32. Таким образом: 10–27 = 10 + 32–27 = 15.

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

Мы узнали об этой новой арифметике для того, чтобы использовать её правило сложения для шифрования, а правило вычитания – для расшифровки. Ведь у каждой буквы есть числовой код от 0 до 31. При таком шифровании буквы открытого текста складываются со специально выбранными буквами (эти выбранные буквы называются «ключом» или «паролем»). Расшифровывают сообщение, вычитая из букв зашифрованного текста буквы ключа.

Если в качестве ключа взять какую-нибудь одну букву, то получится шифр одноалфавитной замены, который мы как раз изучали на прошлой неделе.

Давай попробуем зашифровать слово «БЕСПОРЯДОК» при помощи ключа «С». Начнём с первой буквы, «Б». Её код – 2, а код буквы «С» – 18. Если сложить буквы Б и С, то есть 2 и 18, то получится 20, а это буква «У». Далее, буква «Е», её код – 6. Опять складываем: 6 + 18 = 24, и это буква Ч. Продолжая так дальше, мы получаем слово «УЧГБАВРХАЭ». Расшифровывать это слово нужно при помощи вычитания. Берём букву «У» и её код 20, вычитаем из него код буквы «С»: 20–18 = 2, и получается буква «Б». Ну и так далее…

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

Как же выбираются эти буквы для шифрования? Как я уже сказал, для этого используется ключевое слово, ключ или пароль. Его длина определяет длину цикла многоалфавитной замены, то есть количество используемых алфавитов. А буквы ключа применяются для шифрования при помощи описанных выше правил арифметики вычетов. Давай рассмотрим пример. Пусть в качестве ключа используется слово «КЛЮЧ», тогда первая буква открытого текста шифруется через букву «К», вторая – через букву «Л» и так далее, а пятая буква открытого текста опять шифруется при помощи буквы «К».

Например:

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

«ЪЭЖНЩРЖЧТМАКЫМЮВКЫМЛП».

Уверен, что его не сможет разгадать никто из твоих друзей. Никто даже и браться за такое не будет.