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

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

ОГЛАВЛЕНИЕ

Следующая >>

чае должно быть кратно длине лозунга. Слодовательно, вычислив
наибольший общий делитель всех таких расстояний, мы получим
рабочую гипотезу о длине ключа.
Исследуем расстояния между повторениями биграммы WX в при­
веденном выше шифротексте. Некоторые из расстояний между по­
вторениями этого буквосочетания равны 9, 21, 66 и 30. Отдельные
совпадения могут возникнуть случайно, в то время как остальные
содержат информацию о длине ключевого слова. Вычислим попар­
ные наибольшие общие делители этих чисел.
НОД (30,66) = 6,
НОД (3,9) = НОД (9,66) = НОД (9,30) = НОД (21,66) = 3.
Маловероятно, что ключевое слово состоит из трех букв, так что бу­
дем считать, что расстояния 9 и 21 попали случайно, а длина ключа
равна 6.
Возьмем теперь каждую шестую букву шифротекста и приме­
ним частотный анализ, как мы уже делали, взламывая шифр сдвига,
3.4' Шифр Виоюенера

и определим первую букву ключа. Преимущество гистограмм в ча­
стотном анализе здесь очевидно, поскольку наивный перебор всех
возможных 26 ключей не сможет дать убедительного результата.
Действительно, даже если каждая шестая буква шифротекста бу­
дет угадана, получить осмысленный текст мы не сможем. Так что
метод гистограмм более продуктивен в этой ситуации.
На рисунке 3.3 дано сравнение частот повторяемости каждой
шестой буквы, начиная с первой, со среднестатистической. Изучая
эти гистограммы, мы отмечаем возможные замены букв «а», «е» и
«t» естественного языка, и делаем вывод, что они сдвинуты на 2.
Следовательно, первая буква ключа — «о>, поскольку именно она
обеспечивает такой сдвиг.




QR S Т и V W X Y Z
ABCDEFGHI J К LMNO
(б)

Рис. 3.3. Сравнение повторяемости каждой шестой буквы, начиная с пер­
вой, в примере шифра Виженера со среднестатистической

Применим аналогичный анализ для каждой шестой буквы, на­
чиная со второй. Соответствующие гистограммы изображены на
рис. 3.4. Используя ту же технику, мы видим, что гистограмма (б)
«сдвинута» относительно диаграммы (а) на 17 позиций, что соот­
ветствует букве «л>, стоящей на втором месте ключевого слова.
Продолжая в том же духе, найдем оставшиеся четыре буквы
ключа и обнаружим, что лозунг — это «crypto». Теперь можно про­
честь исходный текст:
Глава 3. Исторические шифры


Scrooge was better than his word. He did it all, and infinitely more;
and to Tiny Tim, who did not die, he was a second father. He became
as good a friend, as good a master, and as good a man, as the good old
city knew, or any other good old city, town, or borough, in the good
old world. Some people laughed to see the alteration in him, but he let
them laugh, and little heeded them; for he was wise enough to know
that nothing ever happened on this globe, for good, at which some
people did not have their fill of laughter in the outset; and knowing
that such as these would be blind anyway, he thought it quite as well
that they should wrinkle up their eyes in grins, as have the malady
in less attractive forms. His own heart laughed: and that was quite
enough for him.
He had no further intercourse with Spirits, but lived upon the Total
Abstinence Principle, ever afterwards; and it was always said of him,
that he knew how to keep Christmas well, if any man alive possessed
the knowledge. May that be truly said of us, and all of us! And so,
as Tiny Tim observed, God bless Us, Every One!

12n




12n




ABCDEFGHI JKLMNOPQRSTUVWXYZ
(6)
Р и с . 3.4. Сравнение повторяемости каждой шестой буквы, начиная со вто­
рой, в примере шифра Виженера со среднестатистической

Отрывок взят из произведения Чарльза Диккенса «Рождествен­
ская песнь в прозе. Святочный рассказ с привидениями».
3.5. Перестановочные шифры

3.5. Перестановочные шифры
Идеи, лежащие в основе шифра замены, движут и современными
криптографами, разрабатывающими симметричные алгоритмы. Поз­
же мы увидим, что в шифрах DES и Rijndael присутствуют ком­
поненты, называемые S-блоками, которые являются простыми под­
становками. Другие составляющие современных симметричных ши­
фров основываются на перестановках.
Перестановочные шифры активно применялись в течение не­
скольких столетий. Здесь мы опишем один из самых простейших,
который легко поддается взламыванию.
Фиксируется симметрическая группа Sn и какой-то ее элемент
а Е Sn- Именно перестановка а является секретным ключом. Пред­
положим, что
/ 1 2 3 4 5\ ,
а={ ]= 1243 G 55
\ 2 4 1 3 5у
и зашифруем с ее помощью открытый текст:
Once upon а time there was a little girl called Snow White.
Разобьем текст на части по 5 букв:
опсеи ponat imeth erewa salit egirl calle dsnow white.
Затем переставим буквы в них в соответствии с нашей перестановкой:
соепи npaot eitmh eewra Isiat iergl Iclae ndosw iwthe.
Убрав теперь промежутки между группами, чтобы скрыть значение
п, получим шифротекст
coenunpaoteitmheewralsiatiergllclaendoswiwthe.
Перестановочный шифр поддается взлому атакой с выбором откры­
того текста в предположении, что участвующая в шифровании ис­
пользованная симметрическая группа (т. е. параметр п) не слишком
велика. Ц,ля этого нужно навязать отправителю шифрованных со­
общений нужный нам открытый текст и получить его в зашифро­
ванном виде. Предположим, например, что нам удалось подсунуть
алфавит
abcdefghijklmnopqrstuvwxyz
и получить его шифрованную версию
CADBEHFIGJMKNLORPSQTWUXVYZ.
Глава 3. Исторические шифры

Сопоставляя открытый текст и криптограмму, получаем переста­
новку
/ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . \
\2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 ...у
После короткого анализа полученной информации мы обнаружива­
ем повторяюш;иеся серии перестановок: каждые пять чисел пере­
ставляются одинаково. Таким образом, можно сделать вывод, что
п = 5, и восстановить ключ, взяв первые пять столбцов этой таблицы.


3.6. Одноразовый шифр-блокнот
Во время Первой Мировой Войны криптологи активно использо­
вали так называемый одноразовый шифр-блокнот, который часто
называют шифром Вернама. Этот алгоритм подробно изучается в
четвертой главе, а сейчас мы перейдем к другой, не менее интерес­
ной криптосистеме.


3.7. Роторные машины и «Энигма»
С наступлением 1920 года назрела необходимость механизировать
процесс шифрования. Наиболее подходящим для этого типом ши­
фра казался подстановочный. Для механизации процесса шифрова­
ния брался полый диск с нанесенными с двух сторон контактами,
соответствующими алфавитам открытого и шифрованного текста,
причем контакты соединялись между собой по некоторой подста­
новке, называемой коммутацией диска. Эта коммутация определяла
замену букв в начальном угловом положении. При изменении угло­
вого положения диска изменялась и соответствующая замена на со­
пряженную подстановку. Отсюда название механического устрой­
ства — ротор^ или роторная машина.
Предположим, что коммутация диска задает подстановку
abcdefghijklmnopqrs tuvwxyz
TMKGOYDSIPELUAVCRJWXZNHBQF,
которая реализуется в начальном угловом положении. Тогда пер­
вая буква сообщения замещается согласно этому соответствию. Пе­
ред шифрованием второй буквы открытого текста коммутацион­
ный диск поворачивается на одну позицию и получается другое пра­
вило замещения:
3.7. Роторные машины и «Энигма»

abcdefghijklmnopqr stuvwxyz
MKGOYDSIPELUAVCRJWXZNHBQFT
Для третьей буквы используется очередная подстановка:
abcdefghijk Imnopq rstuvwxyz
KGOYDSIPELUAVCRJWXZNHBQFTM
и т. д. Все это дает нам полиалфавитный шифр замены с 26 алфа­
витами.
Наиболее знаменитой из роторных машин была машина «Эниг­
ма», стоявшая на вооружении Германии во время второй мировой
войны. Мы опишем самую простую версию «Энигмы», содержашую
лишь три коммутационных диска, которые реализовывали три из
следуюш;их перестановок:
abcdefghijklmnopqr stuvwxyz
E K M F L G D Q V Z N T O W Y H X U SPA I BR С J
AJDKSIRUXBLHWTMCQGZNPYFVOE
BDFHJLCPRTXVZ N Y E I W G A K M U S QO
ESOVPZJAYQUIRHXLNFTGKDCMWB
VZBRGITYUPSDNHLXAWMJQOFECK
Машины, применяемые в конце войны, имели большее число дисков,
выбираемых из большего набора перестановок. Обратите внимание,
что порядок компоновки дисков в машине суш;ественен. Поэтому
число возможных компоновок дисков в нашем примере равно
5 • 4 • 3 - 60.
При каждом повороте первого ротора соединенное с ним кольцо
попадает в паз второго диска и толкает его. Аналогично пошаговые
итерации третьего ротора контролируются вторым ротором. Оба
кольца подвижны, и их положения тоже формируют часть простран­
ства ключей. Число всех положений двух колец составляет 26^ = 676.
За счет враш;ения дисков конкретная буква текста замеш;алась раз­
ными символами при каждом нажатии на клавишу.
Наконец, р,ля двойной замены букв при каждом шифровании ис­
пользовалась штекерная панель, что увеличивало сложность и доба­
вляло еш;е 10^^ возможных ключей.
Таким образом, в формировании пространства ключей принима­
ли участия коммутации дисков, порядок их компоновки, начальные
угловые положения дисков и положения колец. В результате обш;ее
число секретных ключей доходило до 2^^.
Глава 3. Исторические шифры

Ц^ля контроля соответствия операций шифрования и расшифро­
вания использовался так называемый рефлектор, в качестве которо­
го выступала фиксированная открытая подстановка, заданная таб­
лицей
abcdefghi jк Imnopqrstuvwxyz
YRUHQSLDPXNGOKMIEBFZCWVJAT
На рис. 3.5 приведено схематическое изображение упрощенной ма­
шины «Энигма». Жирными линиями выделен путь, по которому бу­
ква «а» открытого текста заменяется на знак «D» шифротекста. За­
метим, что шифрование и расшифрование должно осуш;ествляться
машинами, находящимися в одном и том же положении. Предполо­
жим теперь, что первый диск провернули на одну позицию, так что
«а» перейдет в «D» под воздействием первого диска, «Ь» в «А», «с» в
«С» и «d» в «В». Вам стоит продумать, куда перейдет «а» открытого
текста при втором шаге шифрования (см. рис. 3.5).
диски
1 2 3 рефлектор
индикаторы клавиатура штекеры




Р и с . 3.5. Упрощенная машина «Энигма»

При эксплуатации «Энигмы» немцы ежедневно меняли следую-
ш;ие установки:
- расположение штекеров,
- коммутационные диски и их компоновку,
- позиции колец,
- начальные угловые положения дисков.
Однако правильнее было бы менять ключ с передачей каждого
нового сообш;ения, поскольку шифрование слишком большого коли­
чества информации с одними и теми же установками — неудачная
практика. Именно этот недосмотр в режиме работы «Энигмы» по­
зволил сотрудникам Блетчлеи Парка раскрыть график передвиже­
ния германских войск. Подчеркнем, что утечка информации про-
S.l. Роторные машины и «Энигма»

изошла ввиду неверной эксплуатации машины, а не из-за слабой
криптостойкости алгоритма.
Режим эксплуатации «Энигмы» во время военных действий вы­
глядел следуюш;им образом. Ежедневно перед отправкой первого
шифрованного сообш;ения менялись и фиксировались на весь день
настройки машины. Выбиралась короткая последовательность букв,
скажем «а, f, g» (на современном языке это называется сеансовым
ключом)^ которая дважды шифровалась. Полученный шифротекст,
т.е. шестибуквенная последовательность (в нашем примере «G, Н,
К, L, Р, Т»), передавалась в самом начале сообш;ения. Адресат, полу­
чив комбинированный шифротекст, дешифровал сеансовый ключ и
в соответствии с результатом менял настройки машины. После это­
го расшифровывался текст первого сообш;ения. Именно эта схема
использования позволила людям из Блетчлей Парка взломать «Эниг-
му». О подробностях, касаюш;ихся взлома этого шифра, можно про­
честь в книгах, указанных в разделе «Дополнительная литература»
этой главы.
У «Энигмы» было и другое слабое место, известное сотрудни­
кам разведки, которое они так никогда и не использовали. Наличие
этого дополнительного недостатка показывает, что система шифро­
вания «Энигма» нестойка даже в том случае, если эксплуатируется
правильно. По суп1;еству, штекерная панель и композиционные дис­
ки — ортогональные механизмы шифрования, что допускает успеш­
ную атаку на отдельный достаточно большой шифротекст. Расска­
жем о схеме такой атаки.
Допустим, у нас есть большое шифрованное сообш;ение, которое
мы намерены взломать. Сначала мы игнорируем участие штекерной

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

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

ОГЛАВЛЕНИЕ

Следующая >>