Математика и шифры

52

Н. Виленкин

Matematika
и шифры

— То, что изобретено одним человеком, может быть понято другое, — сказал Холмс.

Артур Конан Дойль.
«Пляшушие человеки».

Тарабарская грамота

Издавна люди изискивали способы уберечь сообщения от посторонних глаз. Один древний царь, например, обрил голову гонца, написал на ней послание и отослал к своему союзнику гонца лишь тогда, когда волосы на его голове отросли. Развитие химииало более удобное средство: симпатичесне чернила, записи которых не видны до тех пор, пока бумагу не нагреют или образотают каким-нибудь химикатом. На чаше всего для тайнописи применяют шифры. Ими пользовются дипломаты, стремящиеся сохранить тайны переговоров, военачальники, скрывающие от противника отданные распоряжения, разведчики и т. д. А в древности ими пользовались пираты, отмечая расположение кладов, алхимики, купцы, заговорщики и многое другое.

Сначала шифры были очень несложными. Например, русские дипломаты XV—XVI веков применяли так называемую «тарабарскую грамоту», в котором все гласные буквы оставались неизменными, а согласные заменялись друг на друга по следующей схеме:

б в г дж з к л мн
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
шщц х ф т срп

(в первой строке согласные идут в общичном порядке, а во второй строке — в обратном). Например, вместе «Великий государь» получалось «Ше-

53

ситий чолучамь». Этот шфр очень несложен (можно научиться даже более разговаривать на «тарабарской грамоте»).

Постепенно тайнопись условиялась, но даже шфр, который пользовался в конце XVII века царевна Софья в своей переписке с Василием Голицьным, был весна прост — одно из ее писем было несколько лет тому назад опубликовано в журнале «Наука и жизнь», и многие читатели его расшифровали. Шифрами пользовался и изменник Мазена. Как пишет в позме «Полтава» А. С. Пушкин:

«Во тыме ночной они, как воры,
Ведут свои переговоры,
Измену ценят между собой,
Сладают цфр универсал…»

Каким должен быть шфр

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

Тарабарская грамота относится к шфрамм, в которых каждая буква заменяется определенным знаком — другой буквой, цифрой или изображением. Таким же образом шфровали свои последния чикагские бандиты в расскаZE Конан Дойля «Пляшушие»

*) Впрочем, теперь эти операции можно поручить ЭВМ.

человеки» и права в повести Эдгара По «Золотой жук» (только права применили еще симпатически чернила). Иногда для того, чтобы затруднить чтение шфра, используют избыточные коды — одну и ту же букву обозначают разными знаками. Тогда, даже если противник отгадает значение какого-нибудь знака, он не сможет использовать это при расшифровке другого места текста, так как там та же буква обозначется инчете.

Впрочем, иногда избиточность возникнет естественным путем. Когда специальы по древним языкам стали расшифровывать надписи, сделанные много тысяч лет тому назад карийцами (народом, жившим в Малой Азии), они обнаружили, что число знаков слишком велико для буквенной азбуки. Поэтому они решили, что неокотые знаки означают отдельные буквы, а неокотые — слоги. Однако на этом пути возникли нереодолимые трудности. И только когда советский ученый В. В. Шеворошкин стал смотеть, в каких местности встречались не более трех десятков различных знаков, то есть письменность была все же буквенной. Только в разных местах неокотые буквы изображались по-разному, что и затруднили разгадку карийских надписей.

Шифры и комбинаторика

Поскольку множество знаков, применяемых в данной шфре, является конечным, его элементы можно переумеровать и вместе с ними знаков использовать их номера. Будем для простоты рассматривать шфры, в которых нет избыточности. Тогда число знаков равно числу букв в алфавите, а также таких знаков, как пробел между словами, точка, запятая. Для русского языка можно обойтись 35 знаками: 31 буква (e, é, и b, ѫ не различаются), пробел, точка, запятая, тipe. Если число знаков, использованных при шфро-

54

вани, тоже равно 35, то каждый такой шфр задается взаимно-однозначным отображением одного множества из 35 элементов на другое такое множество. В комбинаторике доказывается, что число таких отображений равно 35!, то есть произведение натуральных чисел от 1 до 35. Это настолько громадное число, что его трудно себе представить, — оно примерно равно $10^{40}$.

Иметь дело с произвольными отображениями $f$ множества букв алфавита и знаков препиниания $A = \{a_1, a_2, \ldots, a_{35}\}$ на множество знаков шфра $B = \{b_1, b_2, \ldots, b_{35}\}$ не слишком удобно: запомнить такое отображение трудно, а хранить при себе таблицу отображения — «ключ» шфра — нежелательно. Лучше имеет какое-нибудь простое правило, позволяющее по $k$ найти $f(k)$. А также правила дают методы математики — ведь нет ничего лучшего для распутивания всяких сложностей, чем использование математических методов.

Шифры и сравнения

Математика издавана примениялась в теории шфров. Еще в конце XVІ века расшифровкой переписки между противниками французского короля Генриха III занимался один из создателей современной алгебры Франса Виет. А английские монархистские заговорщики в XVII вке поражались быстрете, с которой Кромвель проникал в их замыслы. Они думали, что использемые им шфры невозможно разгадать, и считали, что ключи к ним выдал кто-то изучатников заговорора. Лишь после падения ресурблики и воцарения Карла II узнал, что все эти шфры разгадывают один из лучших математков того времени профессор Оксфордского университета Валлис, который считал себя основателем новой науки — критморафии.

Один из методов кодирования заключается в следующем. Разделим колюцо на 35 конгруэнтных частей, занумерумем их и пометим каждую буквой или знаком препиниания (см. рисунок). А теперь выберем какое-нибудь число $a$ («ключевое число» шфра) и повернем колюцо вокруг центра по часовой стрелке так, чтобы каждая часть переместилась на $a$ шагов. Это и задает шфр—отображение множества $A = \{a_1, a_2, \ldots, a_{35}\}$ на множество знаков шфра $B = \{01, 02, \ldots, 35\}$ (перед однозначными числами надо писать 0, иначе неясно, что такое 15 — «пятнадцать» или «один», «пять»).

Например, если $a = 11$, то часть, помеченная числом 01, перейдет в часть, помеченную числом 12, а это значит, что букве «A» при кодировании ответает число 12. Точно так же букве «B» ответает число 14 и так далее.

В результате получается последнее, в котором каждая буква или знак записаны двумя числами числом. Адресау для расшифровки надо разбить полученную последовательность цифр на двухчанные числа, вычесть из каждой ключевое число и заменить полученное число $k$ — номер знака $a_k$ — на букву алфавита или знак препиниания.

Впрочем, на самом деле правил кодирования и раскодирования не столь просты — ведя если $k$ больше, чем 24, то сумма $k + 11$ больше, чем 35, а в множестве $B$ самое больше число равно 35. Но здесь надо вспомнить, что мы писали числа не на прямой, а на колюце, а, как известно, у колюца начала нет и нет конца — за числом 35 идет 1. Иными словами, после числа 35 все повторяется снова. Это значит, что, получив сумму, превосходящий 35, надо вычесть из нее 35. Полученная раз-

55

ность и покажет, в какое число переходит $a_k$. Например, $a_{27}$ (буква «ы») переходит не в число 38, а в 03, $a_{32}$ («пробел») — в 08 и так далее. Таким образом,

$$f(a_k) = \begin{cases} k + 11, & \text{ если } k \leq 24, \\ k - 24, & \text{ если } 25 \leq k \leq 35. \end{cases}$$

А раскодирование делается по следующим формулам:

$$g(n) = \begin{cases} a_{n-11}, & \text{ если } 12 \leq n \leq 35, \\ a_{n+24}, & \text{ если } 1 \leq n \leq 11. \end{cases}$$

Правило кодирования можно записать более компактно, если сложение понимать в особом смысле.

Разобъем все цельные числа на классы, отнеся к одному классу числа, дающие одинаковые остатки при делении на 35. Например, в один и тот же класс попадут числа—32,3,38,73, так как все они при делении на 35 дают в остатке 3. Общий вид чисел этого класса $3+35k$, где $k$ целое число. Обозначим через $Z_{35}$ множество таких классов. Число различных классов равно 35 (при делении на 35 получается остатки 0, 1, 2, …, 34), и их можно обозначать теми же цифрами, что и соответствующие остатки, только писать сверху черточку. Например, 5 означает не число 5, а класс, содержащий это число, то есть множество чисел {…, — 30, 5, 40, 75, …}. В частности, 0 означает класс, содержащий число 35.

Теперь уже можно написать, что $27 + 11 = 3$, то есть, прибавляя 11 к числом класса $27$, мы получаем числа из класса 3. Значит, если номерами кодируемых букв и знаками шфра считать классы из $Z_{35}$, то формульы кодирования и раскодирования можно записать так:

$$f(a_k) = \bar{k} + 11,$$
$$g(n) = a_{n-11}.$$

Такая «арithmetic» остатков полезна и во многих других вопросах. Пусть, например, сейчас минутная стрелка показывает 25 минут. Каким будет ее положение через 176 минут? Что бы ответить на этот вопрос, достаточно заметить, что через каждые 60 минут стрелка возвращается в исходное положение. Поэтому надо найти остаток от деления суммы 25 + 176 = 201 на 60. Получим, что этот остаток равен 21. Значит, стрелка будет показывать 21 минуту.

Для облегчения сложения и вычитания в арithmetic остатков при делении на $m$ надо составить таблицу сложения. С этой целью берут общную таблицу сложения и заменют каждое число его остатком при делении на $m$.

Такую arithmetic обусловно называют arithmeticкой по modulo $m$, а числа, имеющие одинаковые остатки при делении на $m$, называют сравнимыми по modulo $m$. Если $a$ и $b$ сравнимыми по modulo $m$, то пишут

$$a \equiv b \pmod{m}.$$

Например,

$$215 \equiv 40 \pmod{7},$$

так как $k$ и 215, и 40 при делении на 7 дают остаток 5.

Если уже известно, что шфр получен прибавлением одного и того же числа к номерам букв, то его можно разгадать, угадав значение хотя одной буквы, а еще лучше — несколько буквы. Например, если известно, что в письме речь идет о Москве и в нем часто встречается сочетание «УХШСЙЗ», то легко догадаться, что при шфровании номер каждой буквы увеличивается на 7.

Более сложный шфр получается, если заменить сложение умножением. Будем, например, умножать номера всех букв на 2. Конечно, если произведение окажется больше 35, надо заменять его остатком от деления на 35. Например, буква «Ч» получит при шфровке номер 13, так как номер буквы «Ч» равен 24, а при делении 24·2 = 48 на 35 получается остаток 13. Это преобразование запутаннее, чем сложение, и можно опасаться, что разные буквы при кодировании перейдут в одну и ту же букву. Но, к счастью, в данном случае этого не произойдет — код невырожен. Доказательство этого утверждения основано на том, что произведение двух чисел делится на 2 лишь в случае, когда один из множителей четен. А если бы мы попробали умножать номера букв не на 2, а на 5 (делитель числа 35), то получился бы выроженный код (проверьте это сам!). Интересные коды получаются при замене умножения возвредением в сте-