Вскрытие шифра простой замены

Сначала мы рассмотрим способ, которым не надо вскрывать шифр простой замены - способ полного перебора всех вариантов. Букве A открытого текста можно сопоставить любую из 26 латинских букв, букве B - любую из оставшихся 25, букве C - любую из оставшихся 24, и так далее. Поэтому число всевозможных алфавитов простой замены равно

26252423...321,

что для удобства обозначается в математических текстах 26!, а читается "двадцать шесть факториал". Это огромное число, больше чем 10 в 26-й степени (обычно записывается 10²⁶), так что даже компьютер, способный каждую секунду проверять тысячу миллионов (т.е. 10⁹) алфавитов, будет вынужден затратить на эту задачу несколько сотен миллионов лет. Ясно, что метод полного перебора, дающий удовлетворительные результаты с шифром Юлия Цезаря (в нем всего 25 вариантов), здесь совершенно непригоден.

Практический метод вскрытия шифра такого типа состоит в следующем:

1. Составьте таблицу частот знаков, встречающихся в шифрованном тексте, т.е. подсчитайте, сколько раз там встречается каждая из букв A,B,C,...,X,Y,Z.

2. Попробуйте определить, какой знак в шифрованном тексте соответствует пробелу. Если шифрованное сообщение не очень короткое, то сделать это просто, так как пробелы и другие символы пунктуации составляют от 15% до 20% знаков обычного английского текста, причем большая часть этих символов приходится на собственно пробелы. Весьма вероятно, что наиболее частый знак шифрованного текста как раз соответствует пробелу. Более того, если это предположение справедливо, то знаки, соответствующие пробелам, должны встречаться в шифрованном тексте через каждые несколько букв, без значительных промежутков между ними.

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

4. Попробуйте определить шифрованные обозначения для некоторых часто встречающихся букв, таких как E,T,A,I,O и N. Вместе они обычно составляют более 40% всего текста, причем в большинстве текстов буква E значительно опережает остальные по частоте встречаемости. На этом этапе большим подспорьем будет таблица частот встречаемости знаков английского языка. Такая таблица приводится здесь (см. Таблицу 2.4); еще одна таблица, построенная на основе гораздо более объемной выборки, содержится в главе 7. Каждая из них подойдет для вскрытия шифра простой замены. Эти таблицы следует трактовать только как подсказки: если для частых букв их частоты мало меняются от выборки к выборке, то частоты редких букв несут мало информации. В приведенной ниже таблице частот знаков английского языка для каждой из букв J,X и Z приведена частота 1 на 1000 знаков, но в конкретном тексте из 1000 знаков каждая из этих букв может встретиться несколько раз, а может и вовсе отсутствовать. Подобные замечания справедливы для частот знаков большинства языков.

5. Когда таким образом будут восстановлены некоторые фрагменты слов, ищите короткие слова, в которых неизвестны одна-две буквы. Например, если буквы T и E уже известны, и если слово длиной три знака с неизвестной буквой между буквами T и E, то это, скорее всего, слово THE, а неизвестная буква, соответственно, H. Дальше можно расставить такие слова, как THIS, THAT, THERE и THEN, получая новые соответствия между знаками открытого и шифрованного текстов.

6. Завершите вскрытие шифра, используя грамматическую и контекстную информацию.

Таблица 2.4 Таблица частот встречаемости знаков английского языка на 1000 знаков текста (на основе подборки стихотворений, рассказов и научных текстов)

Пример 2.2

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

Шифрованный текст имеет вид:

MJZYB LGESE CNCMQ YGXYS PYZDZ PMYGI IRLLC

PAYCK YKGWZ MCWZK YFRCM ZYVCX XZLZP MYXLG

WYTJS MYGPZ YWCAJ MYCWS ACPZY XGLYZ HSWBN

ZYXZT YTGRN VYMJC POYMJ SMYCX YMJZL ZYSLZ

YMTZP MQYMJ LZZYB ZGBNZ YCPYS YLGGW YMJZP

YMJZL ZYCKY SPYZD ZPKYI JSPIZ YMJSM YMJZL

ZYSLZ YMTGY GXYMJ ZWYTC MJYMJ ZYKSW ZYECL

MJVSQ YERMY MJCKY CKYKG

Решение

(1) Сначала составим таблицу частот встречаемости знаков (см. Таблицу 2.5)

Таблица 2.5

(2) Поскольку буква Y встречается 49 раз в тексте из 265 знаков, то есть гораздо чаще других (на нее приходится примерно 18% текста), то можно сделать вывод, что знак Y шифрованного текста соответствует знаку пробела . Следом за Y по частоте идут буквы Z и M, поэтому отметим их как хорошие кандидатуры на место букв E и T, либо T и E.

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

 1          2         3  4     5         6       7 

MJZáBLGESECNCMQáGXáSPáZDZPMáGIIRLLCPAáCK

     8          9         10       11    12    13    14  

KGWZMCWZKáFRCMZáVCXXZLZPMáXLGWáTJSMáGPZáWCAJM

   15      16     17      18    19      20     21  22    23  

CWSACPZáXGLáZHSWBNZáXZTáTGRNVáMJCPOáMJSMáCXáMJZLZ

24     25       26      27    28 29  30    31     32   33

SLZáMTZPMQáMJLZZáBZGBNZáCPáSáLGGWáMJZPáMJZLZáCK

34    35      36     37     38    39   40  41   42    43 

SPáZDZPKáIJSPIZáMJSMáMJZLZáSLZáMTGáGXáMJZWáTCMJ

 44   45       46      47   48   49  50

MJZáKSWZáECLMJVSQáERMáMJCKáCKáKG

В полученном тексте большое количество коротких слов, а средняя длина слова лежит в интервале от 4 до 5, да и само распределение длин слов в целом выглядит более-менее подходящим для обычного языка. Таким образом, наше предположение, что буква Y соответствует пробелу, получает подтверждение.

(4) При рассмотрении коротких слов выясняется следующее:

• Слово длины 1 только одно (номер 29), состоит из буквы S, поэтому можно предположить, что это либо A, либо I^*).

• Слов длины 2 встретилось всего 10; одно из них (CK) встретилось трижды, под номерами 33 и 49, а два встречаются по два раза - GX под номерами 3 и 41, и SP под номерами 4 и 34.

• Слов длины 3 всего 11, из них два встретились по два раза: MJZ под номерами 1 и 44, и SLZ под номерами 24 и 39.

(5) Поскольку мы уже сделали предположение, что знаки M и Z соответствуют буквам E и T (либо T и E), то триграф MJZ превращается либо в E?T, либо в T?E. Поскольку он встретился дважды, то весьма вероятно, что это слово THE, так что знаки M,J и Z - это, соответственно, буквы T,H и E. В шифрованном тексте есть еще несколько слов, содержащих знаки M,Z и J, в том числе:

(23) MJZLZ, которое превращается в THE?E, так что знак L соответствует R или S;

(26) MJLZZ, которое превращается в TH?EE, откуда следует, что L - это R;

(42) MJZW, которое превращается в THE?, поэтому знак W соответствует M или N;

(37) MJSM, которое превращается в THAT, если знак S соответствует букве A, и в THIT, если S соответствует I.

Отсюда делаем вывод, что знаку L соответствует буква R, знаку S соответствует буква A, а знаку W - буква M или буква N.

Поскольку слово 26 - это THREE^*), то стоит проверить, не является ли слово под номером 25 числительным. В шифрованном виде оно выглядит как MTZPMQ, и благодаря уже известным буквам записывается в открытом виде как T?E?T?, что весьма похоже на TWENTY^**). Если это предположение верно, то знаки T,P и Q - это, соответственно, буквы W,N и Y, и тем самым для знака W устраняется неопределенность - это буква M.

(6) Нами уже установлены открытые эквиваленты для девяти символов шифрованного текста: J,L,M,P,Q,S,W,Y и Z. Им отвечают в открытом тексте, соответственно, H,R,T,N,Y,A,M, пробел и E. Эти девять знаков вместе покрывают более 60% текста, поэтому снова выпишем текст, проставляя открытые эквиваленты уже известных знаков шифрованного текста и ставя точки () там, где буквы открытого текста еще не установлены.

Проделав это, можно установить еще несколько соответствий между знаками открытого и шифрованного текстов. Слово 30, уже частично дешифрованное как R..M, содержит в середине пару одинаковых знаков, и таким образом, это может быть только ROOM, поэтому знак G соответствует букве O открытого текста. Следовательно, слово под номером 50 (в шифрованном тексте KG) в открытом виде теперь выглядит как .O, и поэтому знак K соответствует либо S, либо D, так как нам уже известно, что это не N и не T. Слова под номерами 48 и 49 (MJCK и CK) частично дешифрованы как TH.S и .S, и отсюда мы делаем вывод, что знак C - это буква I. Поскольку знаки C и G встретились в шифрованном тексте 18 и 14 раз соответственно, то они должны отвечать частым буквам. Поэтому буквы I и O сюда хорошо подходят, что вы уже заметили из сказанного выше.

Подставляя I,O и S вместо C,G и K в частично восстановленный текст, получим:

 1          2         3  4     5         6       7 

MJZáBLGESECNCMQáGXáSPáZDZPMáGIIRLLCPAáCK

THEá.RO.A.I.IT.áO.áANáE.ENTáO...RRIN.áIS

     8          9         10       11    12    13    14  

KGWZMCWZKáFRCMZáVCXXZLZPMáXLGWáTJSMáGPZáWCAJM

SOMETIMESá..ITEá.I..ERENTá.ROMá.HATáONEáMI.HT

   15      16     17      18    19      20     21  22    23  

CWSACPZáXGLáZHSWBNZáXZTáTGRNVáMJCPOáMJSMáCXáMJZLZ

IMA.INEá.ORáE.AM..Eá.E.áWO...áTHIN.áTHATáI.áTHERE

24     25       26      27    28 29  30    31     32   33

SLZáMTZPMQáMJLZZáBZGBNZáCPáSáLGGWáMJZPáMJZLZáCK

AREáTWENTYáTHREEá.EO..EáINáAáROOMáTHENáTHEREáIS

34    35      36     37     38    39   40  41   42    43 

SPáZDZPKáIJSPIZáMJSMáMJZLZáSLZáMTGáGXáMJZWáTCMJ

ANáE.ENSá..AN.EáTHATáTHEREáAREáTWOáO.áTHEMá.ITH

 44   45       46      47   48   49  50

MJZáKSWZáECLMJVSQáERMáMJCKáCKáKG

THEáSAMEá.IRTH.A.á..TáTHISáISáSO

Теперь оставшиеся буквы легко восстанавливаются. Полностью алфавит расшифрования (если обозначить пробел знаком ^) выглядит так:

AáBáCáDáEáFáGáHáIáJáKáLáMáNáOáPáQáRáSáTáUáVáWáXáYáZ

GáPáIáVáBáQáOáXáCáHáSáRáTáLáKáNáYáUáAáWá.áDáMáFá^áE

Алфавит зашифрования, которым пользуется отправитель, для получения шифрованного текста из открытого, является, конечно же, его инверсией:

AáBáCáDáEáFáGáHáIáJáKáLáMáNáOáPáQáRáSáTáUáVáWáXáYáZ

SáEáIáVáZáXáAáJáCá.áOáNáWáPáGáBáFáLáKáMáRáDáTáHáQáY

Как для шифра простой замены, так и для системы Юлия Цезаря алфавиты зашифрования и расшифрования, в общем случае, будут различны. Причем для шифра Юлия Цезаря они будут одинаковы только для значения сдвига, равного 13. Для шифра простой замены этого можно добиться, если сгруппировать большую часть букв (если не все) попарно, так чтобы внутри каждой пары буквы при шифровании переходили друг в друга, а остальные не изменялись. Некоторые шифр‑машины, в том числе "Энигма" и "Хагелин", автоматически вырабатывают подобные взаимно-обратные алфавиты, так что процессы зашифрования и расшифрования для них идентичны. Это удобно для пользователя, но одновременно снижает стойкость системы. В шифре простой замены на базе 26-буквенного алфавита число возможных алфавитов замены сокращается с 10²⁶ до менее чем 10¹³ (детальные подсчеты можно найти в M2). Хотя и это число остается очень большим, но с криптоаналитической точки зрения это существенное уменьшение стойкости. Несмотря на это, подобные взаимно-обратные шифры простой замены время от времени применяются, в основном частными лицами, чтобы не дать возможность посторонним лицам прочесть содержимое своих дневников. Например, философ Людвиг Виттгенштейн во время войны 1914-1918 годов, будучи в австрийской армии, шифровал свой дневник подобным образом.

Анализируя приведенный выше пример, отметим, что в шифрованном тексте отсутствует знак U, а букв J и Z нет в открытом тексте. Z используется в нем вместо пробела, и в шифрованном тексте превращается в Y, а буква J является открытым эквивалентом знака U шифрованного текста, и отсутствует в исходном сообщении, которое выглядит так:

THEáPROBABILITYáOFáANáEVENTáOCCURRINGáIS

SOMETIMESáQUITEáDIFFERENTáFROMáWHATáONEáMIGHT

IMAGINEáFORáEXAMPLEáFEWáWOULDáTHINKáTHATáIFáTHERE

AREáTWENTYáTHREEáPEOPLEáINáAáROOMáTHENáTHEREáIS

ANáEVENSáCHANCEáTHATáTHEREáAREáTWOáOFáTHEMáWITH

THEáSAMEáBIRTHDAYáBUTáTHISáISáSO^*) .

Дешифрование этой криптограммы было частично основано на предположении, что частоты встречаемости отдельных знаков, в особенности пробела, E, T, A, O, I и N, будут близки к значениям, которые логично ожидать для фрагмента текста заданного объема, написанного на "типичном" английском языке. Тем не менее, иногда может встретиться отрывок из "нетипичного" источника, такого как узкоспециализированный научный текст. В нем могут довольно часто встречаться слова, которых вы не найдете в повести или в газете, и обычная частотная характеристика букв оказывается искаженной. Проводились исследования текстов различных стилей, таких как художественные произведения, газетные статьи, научные публикации, религиозные тексты, философские трактаты и т.д., объемом в несколько миллионов знаков на английском и некоторых других языках; для них опубликованы частоты встречаемости знаков и слов. Инициатором этой работы был Университет имени Брауна (США); эти таблицы опубликованы в [2.2]. Такие данные необходимы для стилистического анализа (например, при попытке установить автора для текстов, чье авторство неизвестно или является спорным) и других литературных исследований. Знание вероятной темы криптограммы - неоценимое подспорье для криптоаналитика. Если, например, ему известно, что данное письмо послано одним физиком - специалистом по высоким энергиям другому такому же специалисту, то в тексте могут присутствовать такие слова, как ПРОТОН, ЭЛЕКТРОН и КВАРК. Поиск таких слов может существенно уменьшить объем работы по дешифрованию сообщения. Если использовать необычные слова и избегать общеупотребительных, то это тоже может отразиться на частотах встречаемости букв, что, в свою очередь, может как помочь криптоаналитику, так и помешать ему. Известен один курьезный случай, когда автор написал повесть, состоящую из более чем 50000 слов без единой буквы E, однако это было сделано намеренно: он подвязал букву E на своей пишущей машинке, чтобы не было возможности ее использовать. Это - пример удивительного мастерства. Здесь я привел в качестве иллюстрации одно предложение из этой книги:

Upon this basis I am going to show you how a bunch of bright young folks did find a champion; a man with boys and girls of his own; a man of so dominating and happy individuality that Youth is drawn to him as is a fly to a sugar bowl. (см. [2.3]).

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