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

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

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

Во-первых, давай считать пробел символом. Да, с математической точки зрения пробел — это такой же символ, как и любой другой. Я специально использую слово «символ», а не «буква», чтобы не путать. Итак, все буквы, цифры, пунктуационные знаки и даже пробел являются символами . Но главное — это понять, что пробел — не отсутствие символа, а отдельный символ. В предложении «ЭТА ФРАЗА СОДЕРЖИТ 3 °CИМВОЛОВ» действительно содержится 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, и получается буква «Б». Ну и так далее…

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

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

Например:

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

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

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

Есть и более легкий метод шифрования этим способом. Для него требуется одна таблица. Она на следующем развороте.

Пользоваться ею легко. Для шифрования надо найти букву открытого текста в первой строке и букву ключа в первом столбце. Буква шифрограммы находится на пересечении выбранного столбца и строки. Для расшифровки надо найти букву ключа в первом столбце и букву шифрограммы в выбранной строке. Буква открытого текста будет в первой строке полученного столбца. Всё довольно просто.

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

Теперь давай научимся расшифровывать тексты, записанные шифрами многоалфавитной замены. Например, у тебя оказалось зашифрованное послание и ты знаешь, что оно зашифровано именно таким шифром. Как подступиться к расшифровке? Вот простейший метод:

1. Определить длину ключа, то есть длину цикла, в котором меняются алфавиты. Это делается при помощи одного очень хитроумного способа, о котором ты узнаешь чуть позже.

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