История криптологии. Немного о шифре простой замены

История криптологии. Немного о шифре простой замены

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

1. Арабы vs Шифр простой одно алфавитной замены.

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

Документально подтверждено, что, помимо информации государственной важности, чиновники зашифровывали также сведения о налогах и другие конфиденциальные данные, т. е. применение криптографии было обыденным делом. Во многие руководства для чиновников (например, в “Adab al-Kuttab” или «Руководство для секретарей») вошли разделы, посвящённые способам шифрования, большая часть которых основана на шифрах одноалфавитной замены. Напомню, шифром простой одноалфавитной замены называется любой шифр замены, шифроалфавит которого единственен и может состоять из любых символов.

Однако, наряду с использованием шифров арабские учёные добились успехов и в их взломе. Это было обусловлено не только развитием математики, лингвистики и статистки (в которых арабские учёные добились впечатляющих успехов на фоне европейских коллег), но и популярностью и востребованностью религиозного образования. В основных медресе, основанных в Басре, Куфе и Багдаде, теологи тщательно изучали содержащиеся в Коране откровения Муххамеда. В частности, теологи интересовались установлением хронологии откровений, что стало возможным благодаря изучению частоты появления определённых слов в каждом откровении. А т. к. некоторые слова появились только на определённых стадиях развития исламского мира, то такой способ был достаточно эффективным. Но арабские учёные не остановились на изучении частот отдельных слов, а стали анализировать и отдельные буквы. Это было необходимым условием проверки согласованности отдельных текстов с лингвистическим стилем Муххамеда. В ходе такой проверки было установлено, что отдельные буквы встречаются чаще других: так в арабском языке наиболее распространёнными буквами являются a и l.

Это наблюдение привело к первому значительному прорыву в криптоанализе. Кто первым догадался, что изменение частоты появления букв может быть использовано в целях взлома шифров, неизвестно. Но одно из наиболее ранних описаний данного метода датировано IX веком и принадлежит перу крупнейшего учёного Абу Юсуф Якуб ибн Исхак фс-Сабах ибн Умран ибн Исмаил аль-Кинди, самый известный (из порядка 290 работ по различным дисциплинам) труд которого назвался «Рукопись по дешифрованию криптографических сообщений».

Теперь перейдём собственно к методу криптоанализа, придуманному аль-Кинди. Прежде всего, для дешифрования необходимо взять достаточно большой кусок эталонного текста и подсчитать частоту появления каждой буквы. Причём текст по стилистике должен быть максимально приближен к предполагаемой стилистике зашифрованного сообщения. Это связано с тем, что, например, в каком-нибудь научном тексте частота буквы ф будет больше, чем в литературном произведении из-за частого употребления таких слов, как дифференциал, дифракция и т. д. Весь принцип данного метода построен на том, что в языке каждая буква встречается с некоторой достаточно устойчивой частотой, которую можно определить из эталонного текста. Усреднённая частота встречи каждой буквы в некоторых языках показана на схеме 1 (обратите внимание на то, что здесь относительная частота для некоторых языков показана с учётом пробела).

Схема 1 - средняя частота букв в различных языках

2. Практический пример

В качестве примера разберём пример с дешифрованием следующего сообщения: сата эи фиеич ъёюр саъэиу бичэасчм ед ёыя сшиафи щиуъацд ег ср вёцик чбжиъэиу чсжаъеаэда чажвля ъиафи гед щичшмхаэга щиося бяб эабифвя афи ектишд щажав ситик таю исшася щжиувас эа щжгюэяээиа шэишд

При внимательном рассмотрении можно заметить, что число различных букв в нём – 28, буквы распределены по тексту более-менее нормально, т. е. нет скоплений отдельных символов. Значит, есть все основание полагать, что перед нами сообщение, зашифрованное с помощью шифра замены. Попробуем применить для расшифровки изученный метод IX века. Для этого воспользуемся программой уже XXI века.

Нелирическое отступление или краткая повесть о CryptoTool 2.

Рассмотрим работу одной очень интересной и полезной (с моей точки зрения) для обучения криптографии программы, а именно CryptoTool 2. Скачать её можно вот отсюда http://www. cryptool. org/ . Детально на интерфейсе я останавливаться не буду - всё достаточно просто. Итак, для выполнения частотного анализа нам необходимо перетащить на «рабочий стол» проекта две иконки - Frequency Test (вкладка инструментов Cryptoanalysis слева) и TextInput (вкладка Tools). Каждая иконка символизирует модуль с определённым набором функций. Так предназначение первого модуля, думаю, понятно, второй модуль служит «поставщиком» текста. Обратите внимание на иконки вверху каждого модуля. Они символизируют ввод/вывод, а различие в цвете обусловлено различным форматом ввода/вывода. Пока остановимся на формате System. String (тем, кто знают C# или любой С-подобный названия покажутся знакомыми), который представляет (кто бы мог подумать) из себя строковый формат, каждый его элемент – это символ в двухбайтовой кодировке Unicode (всё как в C#, на котором и написана данная программа). Теперь соединим вывод TextInput и ввод Frequency Test и почти всё готово для получения долгожданной гистограммы. Осталось вставить текст в модуль ввода, это делается с помощью двойного клика мышкой и ввода текста в открывшемся окне (в итоге должно получиться нечто, похожее на рисунок 1). А также необходимо щёлкнуть правой кнопкой по модулю Frequency Test и выбрать count, что необходимо для обработки русских букв, т. к. по умолчанию используется английский алфавит (дальше научимся его менять). Будьте внимательны, т. к. в этом случае будут подсчитываться все символы, в т. ч. знаки препинания и пробелы.

Рисунок 2 - рабочее пространство в CryptoTool 2

На этом можно приступать к проведению опыта. Для этого нажимаем на кнопку Play и два раза щёлкаем по Frequency Test и любуемся на рисунок 3 - гистограмма в CryptoTool 2

Видим выбросы, образованные пробелом и буквами «и» и «а». Теперь посмотрим на эталонное распределение - самыми часто встречающимися буквами являются «О» и «Е». Можно предположить, что в шифроалфавите эти буквы соответствуют 2-м самым часто встречающимся буквам в тексте – «и» и «а». Попробуем заменить. Я буду пользоваться для замены программой Штирлиц IV (там есть удобная опция: правка -> ручная замена), но это можно осуществить в любом текстовом редакторе. Итак, после замены у нас получилось следующее: рисунок 4 - режим ручной замены в программе Штирлиц IV

Внимательно медитируем на картинку и замечаем слово «ЕфО» => в шифроалфавите букве «Г» соответствует буква «ф», заменяем (здесь и далее заменённые буквы - прописные). Медитируем дальше и видим «ъОЕГО», схема соответствия алфавитов пополнилась заменой «ъ» - «М». Мы всё ближе и ближе к цели – смотрим на первую и последнюю строчку – там есть два предлога «эО» и «эЕ». Если отбросить чисто лингвистические рассуждения и посмотреть на таблицу распределения букв по частоте, то увидим, что наиболее вероятные кандидаты – буквы «Т» и «Н», что согласуется и с лингвистическими соображениями. Осталось правильно выбрать букву, для чего посмотрим на «сУМэОу» слово в конце первой строки. Видим, что здесь присутствует буква «э», причём она стоит после буквы «М» - учитывая, что сочетание двух букв (биграмма) «МН» более вероятно, чем «МТ» (как и комбинация …УМНО… встречается гораздо чаще, чем …УМТО…), предположим, что здесь всё-таки употребляется буква «Н».

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

Рисунок 5 - режим ручной замены в программе Штирлиц IV

Далее нам необходимо рассматривать слова, в которых уже много «разгаданных» букв. В частности, хорошим кандидатом представляется слово в последней строке – «щжгюНяННОЕ». Кандидатов на замену буквы «я» два – это буква «Ё» и «А» (суффиксы енн/ённ, онн, анн). Определится нам поможет слово «бяб» в начале 6-й строки, исключающее возможность замены буквы «я» на «Ё». Это слово вместе со следующим определяют очередную возможную замену «б» - «К». А слово «НЕКОГвА» – «в» - «Д». Пора определиться и с первым словом: частота символа «с» в данном тексте – 5,61, что соответствует по эталонному распределению (с учётом уже совершённых замен) букве «Т», т. е. очень вероятно, что первое слово «ТЕБЕ», но вполне вероятно, что и «СЕБЕ». Для того чтобы определиться, необходимо посмотреть на другие слова, в частности, на последнее слово первой строки, откуда следует «с» - «Т» и «у» - «Й». Итак, имеем следующий почти расшифрованный текст: рисунок 6 - режим ручной замены в программе Штирлиц IV

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

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

3. На этот раз просто заключение

Как, вы смогли заметить, криптология основана не только на математике, но и во многом на лингвистике. Знание особенностей языка для проведения успешного криптоанализа просто необходимо.

Тем, кому это понравилось, предлагаю в качестве упражнения выполнить ряд несложных заданий:

1.Дешифровать сообщение до конца;

2.Разобраться с CryptoTool и приспособить её для автоматического расшифрования такого класса шифров;

3.Ну и напоследок задание с одного небезызвестного конкурса:

Decrypt please

Ocmln. up.'g. bjf abanfoco odrgne er yd. ypcjt d. p. /,.nnw urp yd. mroy lapy=v

Ydco y. qy, ao, pcyy. b gocbi a ol. jcan t. fxrapew br bry. pirbrmcjw frg aoodayv

WdcbyV Yd. t. f frg ap. nrrtcbi urp co yd. bam. oat. ru ydco t. fxrapev WzdcbyV

В качестве ответа принимается более-менее подробное описание процесса дешифрования. За решение в первых рядах любого задания - +.

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


Карта сайта


Информационный сайт Webavtocat.ru