Кpиптогpафия от папиpуса до компьютеpа

       

Вскрытие шифров перестановки


Сначала возьмем тот пример шифровки двойной перестановки, что изложен выше. Пусть имеется шифровка АЗЮЖЕ СШГГООИПЕР, которая так укладывается в таблицу 4 х 4:



1 2 3 4
1 A З Ю Ж
2 E   С Ш
3 Г T О О
4 И П E P

Рассматривая маловероятные сочетания букв, легко найти истинную последовательность столбцов. Так, сочетание ГТ в 3 строке шифровки указывает на то, что после 1 столбца вряд ли следует 2 столбец. Рассчитаем статистически, какой столбец скорее всего следует за 1. Для этого воспользуемся таблицей логарифмов вероятностей биграмм русского текста, приведенной в приложении. Вероятность следования одного столбца за другим равна произведению вероятностей биграмм в строках этих столбцов. Поскольку в таблице даны логарифмы биграмм, то их достаточно суммировать, а потом выбрать сочетание столбцов с максимальной вероятностью. Для вероятностей следования за первым столбцом 2, 3 и 4 имеем выражения:
    

р (1-2) =р(A3)   р(Е )   р(ГТ) р(ИП)=7+9+0+5=21
     р (1-3) =р(АЮ) р(ЕС) р(ГО) р(ИЕ)=6+8+8+8=30
     р (1-4 )=р(АЖ) р(ЕШ) р(ГО) р(ЯР)=7+5+8+7=27

В нашем случае наиболее вероятно, что после столбца 1 следует столбец 3. Для такой небольшой таблицы шифрования, которую имеем, можно перебрать все варианты перестановок - их всего лишь 24. В случае большого числа столбцов целесообразно оценить вероятности пар сочетаний разных столбцов и решить оптимизационную задачу, которая укажет перестановку столбцов, дающую фрагменты естественного текста с большей вероятностью. В нашем случае наилучший результат достигается при расстановке столбцов (2413), что примерно вдвое по вероятностной оценке достовернее ближайшей к ней по вероятности расстановки (4132). После того, как столбцы шифровки расставлены, не составит труда правильно расставить и ее строки по смыслу фрагментов текста:

  2 4 1 3
1 З Ж A Ю
2   Ш E С
3 T О Г О
4 П P И E
<
Текст в ней уже читается и, расставив строки в порядке (4123), получим расшифровку ПРИЕЗЖАЮ ШЕСТОГО.

Теперь обратимся к приведенному выше примеру шифра решетки:
3 Т П  
О Ж Ш Р
Е И Г А
Е С Ю О
Неужели его так трудно взломать, как это утверждают некоторые авторы математических изданий? В этой шифровке видимо содержится 2 слова, если учитывать, что она длиной 16 букв, а одно слово русского языка содержит в среднем 7 букв и имеется пробел. Расшифровку проще начать с биграммы СТ.

Предположение 1. Предположим, что наиболее частая биграмма в русском языке СТ входит в одно из слов текста. Так как Т расположена в решетке выше С, это значит, что между ними произошел поворот решетки таким образом:

  **** *Т**
  **** ****
  **** ****
  *С** ****
     
  0' 90'
С учетом того, что эти буквы принадлежат различным прорезям решетки, получаем такой вид разгаданных частей таблиц:

  **?? *Т** **П* ??** **??
  **?? О*** ***Р ??** **??
  Е*** **?? ??** ***А ***
  *С** **?? ??** **Ю* * **
           
  0' 90' 180' 270'  
Проверим правильность этого предположения чтением, заменяя еще не ясные буквы точками: ..ЕСТО..ПР....АЮ. Это очень похоже на фрагменты текста. Пометив в решетке клетку буквы С цифрой 1, обозначим с учетом поворота клетку буквы Т цифрой 2.

Предположение 2. При составлении решеток прорези обычно размещают так, чтобы их было по одной в каждой колонке и каждом столбце, что гарантирует хаотичное и равномерное заполнение квадрата буквами. В этом случае имеется всего два варианта: 1234 и 123'4', изображенных на следующем макете решетки:

  * * 3' 4
  * * 3 4'
  2 * * *
  * 1 * *
Второй вариант 123'4' не подходит, так как не покрывает весь квадрат при поворотах, и остается 1234, что дает ШЕСТОГОПРИЕЗЖАЮ. Сообщение уже ясно, хотя расшифровка начата с неправильного поворота решетки. С учетом этого замечания получим сообщение: ПРИЕЗЖАЮ ШЕСТОГО.
     Реальные шифры этого типа вскрываются еще проще. При поворотах происходят заметные смещения решетки по месту, которые весьма помогают при анализе выделить буквы, относящиеся к одному повороту. Выделив буквы, смещенные в одном направлении, получают прорезанные клетки трафарета. Если же текст сообщения имеет достаточно большую длину, то задача вскрытия шифра решетки резко упрощается из-за этой особенности. Использование ЭВМ для реконструкции решетки по вероятностям чередования букв в тексте позволяет полностью автоматизировать этот увлекательный процесс логического анализа. Однако наилучшая атака на этот шифр получается, если отгадывать вероятное слово текста, как ПРИБУДУ, ПРИЕДУ, ПРИБЫВАЮ, ПРИЛЕТАЮ, ПРИЛЕЧУ и тому подобное, так как обычно лексика сообщения примерно известна.


Содержание раздела