<< Предыдущая

стр. 11
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

фра и знанием статистического распределения букв подлежащего
открытого текста.

Таблица 3.1. Среднестатистические частоты употребления английских букв
Буква Процентное содержание Буква Процентное содержание
n
а 8;2 6J
о
b 7,5
1,5
с 2,8 1,9
p
4,2
d 0,1
q
r
е 12,7 6,0
f 2,2 s 6,3
t 9,0
2,0
g
h u 2,8
6,1
i 7,0 1,0
V

J w 2,4
0,1
к 0,8 0,1
X

1 4,0 2,0
у
m z
2^4 1 ОД


Распределение (встречаемость) букв в английском среднестати­
стическом тексте представлено в табл. 3.1. Соответствующая гисто-
^ Редакцией было принято решение не переводить примеры дешифрования на
русский язык, поскольку в реальной жизни перехваченная шифровка может быть
написана на любом языке. — Прим. перев.
3.2. Шифр сдвига

грамма изображена на рис. 3.1. Как видно из этих данных, наиболее
часто встречающиеся буквы — это «е» и «t».
При взломе шифра полезно знать статистическую информацию и
второго порядка, а именно, частоту встречаемости групп из двух и
трех букв, называемых биграммами и триграммами. Наиболее часто
встречающиеся биграммы представлены в табл. 3.2, а самые попу­
лярные триграммы выписаны в строку в порядке убывания частоты
их использования:
the, ing, and, her, ere, ent, tha, nth, was, eth, for.




abcdefghijklmnopqrstuvwxyz
Рис. 3.1. Относительная встречаемость английских букв

Вооруженные такой статистической информацией, мы готовы
сейчас исследовать и взломать несколько классических шифров.

Таблица 3.2. Частота встречаемости английских биграмм
Биграмма Процентное содержание Биграмма Процентное содержание
th 3,15 he 2,51
an 1,72 in 1,69
er 1.54 re 1,48
es 1.45 on 1.45
ea 1,31 ti 1,28
at 1,24 St 1,21
1 en 1,20 nd 1,18 1


3.2. Шифр сдвига
Коллекцию классических криптосистем открывает один из самых
первых известных типов шифра, называемый шифром сдвига. Про­
цесс шифрования заключается в замене каждой буквы на другую,
отстоянную от исходной на определенное число позиций в алфавите
в зависимости от значения ключа. Так, например, если ключ равен
3, то буква «а» исходного текста в шифровке изображается «D», вме­
сто буквы «Ь» появится «Е» и т. д. Слово «hello» будет представлено
Глава 3. Исторические шифры

шифровкой «KHOOR». Когда этот шифр употребляется с ключом,
равным трем, его часто называют шифром Цезаря, хотя во многих
книгах это название относится к шифру сдвига с любым ключом.
Строго говоря, такое обобщение не совсем допустимо, поскольку
Юлий Цезарь пользовался шифром сдвига именно с ключом 3.
Существует более математизированное описание шифра сдвига,
которым мы будем руководствоваться при дальнейшем обсуждении.
Сначала нужно пронумеровать все буквы алфавита, начиная с О,
т.е. букве «а» присваивается номер О, «Ь» — 1, и т.д. до буквы «z»
под номером 25. Затем мы переписываем исходный текст, заменяя
каждую букву соответствующим номером, и получаем последова­
тельность чисел. Шифротекст возникает после того, как к каждому
числу в этой последовательности прибавляется значение ключа к по
модулю 26, А;, очевидно, — целое число между О и 26. Таким обра­
зом, шифр сдвига можно интерпретировать как поточный шифр с
потоком ключей в виде повторяющейся последовательности
й/ъ hb hb Ш/% й/ъ 1/ъ

гь^ гь^ гь^ Гь^ гь^ Гь^ • • •

Этот поток, естественно, далек от случайного, вследствие чего кри-
птостойкость шифра сдвига крайне низка. Наивный путь атаки
на шифр сдвига состоит в простом переборе возможных значений
ключа до тех пор, пока не получится осмысленный текст. Поскольку
существует ровно 25 вариантов (ключ О не меняет текста), то д^ля
их перебора потребуется не очень много времени, особенно в случае
короткой шифрограммы.
Покажем сейчас, как можно взломать шифр сдвига, опираясь на
статистику подлежащего языка. В случае шифра сдвига такой спо­
соб не является острой необходимостью. Однако позже мы позна­
комимся с шифрами, составленными из нескольких шифров сдвига,
которые применяются поочередно, и тут уж без статистического
подхода не обойтись. Кроме того, приложение этого метода к ши­
фру сдвига иллюстрирует проявление статистики исходного откры­
того текста в соответствующем шифротексте.
Рассмотрим пример шифрограммы.
GB OR, BE AEG GB OR: GUNG VF GUR DHRFGVBA:
JURGURE VVF ABOYRE VA GUR ZVAQ GB FHSSRE
GUR FYVATF NAQ NEEBJF BS BHGENTRBHF SBEGHAR,
BE GB GNXR NEZF NTNVAFG N FRN BS GEBHOYRF,
NAQ OL BCCBFVAT RAQ GURZ? GB OVR: GB FYRRC;
AB ZBER; NAQ OL N FYRRC GB FNL JR RAQ
GUR URNEG-NPUR NAQ GUR GUBHFNAQ ANGHENY FUBPXF
3.2. Шифр сдвига

GUNG SYRFU VF URVE GB, WF N PBAFHZZNGVBA
QRIBHGYL GB OR JVFU'Q, GB QVR, GB FYRRC;
GB FYRRC: CREPUNAPR GB QERNZ: NL, GURERT GUR EHO;
SBE VA GUNG FYRRC BS QRNGU JUNG QERNZF ZNL PRZR
JURA JR UNIR FUHSSYRQ BSS GUVF ZBEGNY PBVY,
ZHFG TVIR HF CNHFR: GURERT GUR ERFCRPG
GUNG ZNXRF PNYNZVGL BS FB YBAT YVSR;

Один из приемов взлома этого образца шифротекста основывается
на том, что шифровка все еще сохраняет относительные длины слов
исходного текста. Например, «N» появляется в нем как однобуквен-
ное слово. Поскольку в английском языке таковыми словами могут
быть лишь «а» и «i», легко предположить, что ключ равен либо 13
(т. к. «N» — тринадцатая буква в алфавите после «А»), либо 5 («N» —
пятая буква после «I»). Отсюда мораль — пробелы между словами в
исходном тексте перед его шифрованием с помощью шифра сдвига
следует убирать. Но даже если игнорировать информацию о длине
слов, мы можем без особого труда вскрыть шифр сдвига, применив
частотный анализ.
Вычислим частоты появления букв в шифротексте и сравним
их со среднестатистическими из табл. 3.1. Полученная информация
представлена на двух гистограммах (рис. 3.2), расположенных друг
над другом. Посмотрев на них, легко убедиться, что гистограм­
ма (б), отражающая статистику букв в шифротексте, очень похожа
на сдвиг гистограммы (а) со среднестатистической информацией.
Заметим, что мы не вычисляли частоты j\jui вычерчивания первой
диаграммы по исходному открытому тексту, поскольку он не был
нам известен. Мы просто воспользовались легко доступной стати­
стической информацией о подлежащем языке.
Сравнивая гистограммы, можно предположить, насколько вто­
рая сдвинута относительно первой. Наиболее употребляемая буква
в английском тексте — это «е». Отмечая большие столбцы во второй
гистограмме, замечаем, что буква «е» исходного текста может быть
заменена на «G», «N», «R» или «В», т.е. ключом может служить одно
из чисел:
2, 9, 13 или 23.
Аналогично, исследуя кандидаттуры на букву «а», получаем, что
возможный ключ равен одному из
1, 6, 13 или 17.
Среди двух серий гипотетических ключей есть только одно совпа-
Глава 3. Исторические шифры

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




ABCDEFGHI JKLMNOPQRSTUVWXYZ
(б)

Рис. 3.2. Сравнение частот появления букв в шифротексте со среднеста­
тистической

То Ье, or not to be: that is the question:
Whether His nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And by opposing end them? To die: to sleep;
No more; and by a sleep to say we end
The heart-ache and the thousand natural shocks
That flesh is heir to, 4is a consummation
Devoutly to be wished. To die, to sleep;
To sleep: perchance to dream: ay, there's the rub;
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil.
Must give us pause: there's the respect
That makes calamity of so long life;
Вы, конечно, узнали знаменитый монолог Гамлета из трагедии
Вильяма Шекспира.
3.3. Шифр замены


3.3. Шифр замены
Основной недостаток шифра сдвига заключается в том, что суще­
ствует слишком мало возможных ключей, всего 25. В целях устра­
нения указанного недостатка был изобретен шифр замены. Чтобы
описать ключ такого шифра, сначала выписывается алфавит, а не­
посредственно под ним — тот же алфавит, но с переставленными
буквами^ Это дает нам правило, по которому буквы открытого тек­
ста замещаются символами шифровки. Например,
abcdefghij к Imnop qrs tuvwxy z
GOYDSIPELUAVCRJWXZNHBQFTMK
Шифрование состоит в замене каждой буквы в открытом тексте на
соответствующую ей нижнюю букву. Чтобы расшифровать шифро-
текст, нужно каждую его букву найти в нижней строке таблицы
и заменить ее соответствующей верхней. Таким образом, крипто­
грамма слова «hello» будет выглядеть как ESVVJ, если пользоваться
приведенным соответствием.
Количество всех возможных ключей такого шифра совпадает
с числом всевозможных перестановок 26 элементов, т.е. порядком
симметрической группы S'265 равным
26! ?^4,03-10^^ ^2^^.
Поэтому, перебирая все возможные ключи с помощью самого со­
временного и быстрого компьютера, мы потратим столько време­
ни, что задача о дешифровании конкретного сообщения перестанет
быть актуальной. Тем не менее, мы можем взломать шифр замены,
опираясь на статистику подлежащего языка, аналогично тому, как
мы вскрыли шифр сдвига.
Если шифр сдвига можно считать поточным шифром, когда шиф-
ротекст получается комбинацией открытого текста с потоком клю­
чей, шифр замены похож на более современный блочный шифр, блок
в котором состоит из одной английской буквы. Блок шифротекста
получается из блока открытого текста в результате применения не­
которого ключа (предположительно, простого), зависящего от ис­
пользуемого алгоритма.
Шифры замены имеют богатую и интересную историю, и как
правило именно они фигурируют во всевозможных детективных исто­
риях. Один из таких шифров описан в рассказе Артура Конан Дойля
^Или любой другой набор различных знаков, например, азбука Морзе. Однако
в этой книге автор ограничивается перестановками стандартного алфавита. —
Прим. перев.
Глава 3. Исторические шифры

«Пляшущие человечки». Интрига детектива замешана на шифре за­
мены, в котором буквы замеш;ались схематично изображенными че­
ловечками в различных положениях. Метод, которым Холмс и Ват-
сон взломали шифр, и есть тот действенный способ, который мы и
возьмем на вооружение, проводя атаку на шифротекст, приведен­
ный ниже.
Мы разберем в деталях пример атаки на криптограмму, кото­
рая предварительно была упрощена по сравнению с оригинальной: в
ней оставлены промежутки между словами подлежащего открытого
текста. Сделано это в целях более наглядной демонстрации метода.
В какой-то момент мы воспользуемся этой информацией, хотя стоит
признаться, что это сильно облегчит нам задачу.
Рассмотрим шифротекст.
XSO MJIWXVL JODIVA STW VAO VY OZJVCO'W LTJDOWX
KVAKOAXJTXIVAW VY SIDS XOKSAVLVDQ lAGZWXJQ.
KVUCZXOJW, KVUUZAIKTXIVAW TAG UIKJVOLOKXJVAIKW
TJO HOLL JOCJOWOAXOG, TLVADWIGO GIDIXTL UOGIT,
KVUCZXOJDTUOW TAG OLOKXJVAIKKVUUOJKO. TWHOLL TW
SVWXIAD UTAQ JOWOTJKS TAG CJVGZKX GONOLVCUOAX
KOAXJOW VY UTPVJ DLVMTL KVUCTAIOW, XSO JODIVA
STW T JTCIGLQ DJVHIAD AZUMOJ VY lAAVNTXINO AOH
KVUCTAIOW. XSO KVUCZXOJ WKIOAKO GOCTJXUOAX STW
KLVWO JOLTXIVAWSICWHIXS UTAQ VY XSOWO
VJDTAIWTXIVAW NIT KVLLTMVJTXINO CJVPOKXW, WXTYY
WOKVAGUOAXW TAG NIWIXIAD lAGZWXJITL WXTYY. IX STW

<< Предыдущая

стр. 11
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>