Криптографические методы защиты информации

Лекции

4. ШИФРЫ ЗАМЕНЫ

 

4.1. Основы шифрования.

4.2. Шифры однозначной замены.

4.3. Полиграммные шифры.

4.4. Омофонические шифры.

4.5. Полиалфавитные шифры.

4.6. Нерегулярные шифры.

Вопросы для самопроверки.

 

4.1. Основы шифрования

 

Сущность шифрования методом замены заключается в следующем [9]. Пусть шифруются сообщения на русском языке и замене подлежит каждая буква этих сообщений. Тогда, букве А исходного алфавита сопоставляется некоторое множество символов (шифрозамен) МА, Б – МБ, …, Я – МЯ. Шифрозамены выбираются таким образом, чтобы любые два множества (МI и МJ, i ≠ j) не содержали одинаковых элементов (МI ∩ МJ = Ø ).

Таблица, приведенная на рис.4.1, является ключом шифра замены. Зная ее, можно осуществить как шифрование, так и расшифрование.

АБ...Я
МАМБ...МЯ

Рис.4.1. Таблица шифрозамен

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

Приведенное выше описание сущности шифров замены относится ко всем их разновидностям за исключением полиалфавитных шифров, в которых для зашифрования разных символов исходного алфавита могут использоваться одинаковые шифрозамены (т.е. МI ∩ МJ ≠ Ø , i ≠ j).

Метод замены часто реализуется многими пользователями при работе на компьютере. Если по забывчивости не переключить на клавиатуре набор символов с латиницы на кириллицу, то вместо букв русского алфавита при вводе текста будут печататься буквы латинского алфавита («шифрозамены»).

Для записи исходных и зашифрованных сообщений используются строго определенные алфавиты. Алфавиты для записи исходных и зашифрованных сообщений могут отличаться. Символы обоих алфавитов могут быть представлены буквами, их сочетаниями, числами, рисунками, звуками, жестами и т.п. В качестве примера можно привести пляшущих человечков из рассказа А. Конан Дойла () и рукопись рунического письма () из романа Ж. Верна «Путешествие к центру Земли».

Шифры замены можно разделить на следующие подклассы (разновидности).

Рис.4.2. Классификация шифров замены

I. Регулярные шифры. Шифрозамены состоят из одинакового количества символов или отделяются друг от друга разделителем (пробелом, точкой, тире и т.п.).

1. Шифры однозначной замены (моноалфавитные, простые подстановочные). Количество шифрозамен для каждого символа исходного алфавита равно 1 (| Мi | = 1 для одного символа).

2. Полиграммные шифры. Аналогичны шифрам однозначной замены за исключением того, что шифрозамене соответствует сразу блок символов исходного сообщения (| Мi | ≥ 1 для блока символов).

3. Омофонические шифры (однозвучные, многозначной замены). Количество шифрозамен для отдельных символов исходного алфавита больше 1 (| Мi | ≥ 1 для одного символа).

4. Полиалфавитные шифры (многоалфавитные). Состоят из нескольких шифров однозначной замены. Выбор варианта алфавита для зашифрования одного символа зависит от особенностей метода шифрования (| Мi | > 1 для одного символа);

II. Нерегулярные шифры. Шифрозамены состоят из разного количество символов, записываемых без разделителей.

 

4.2. Шифры однозначной замены

 

Максимальное количество ключей для любого шифра этого вида не превышает n!, где n – количество символов в алфавите. С увеличением числа n значение n! растет очень быстро (1! = 1, 5! = 120, 10! = 3628800, 15! = 1307674368000). При больших n для приближенного вычисления n! можно воспользоваться формулой Стирлинга

          (4.1)

Шифр Цезаря. Согласно описаниям историка Светония в книге «Жизнь двенадцати цезарей» данный шифр использовался Гаем Юлием Цезарем для секретной переписке со своими генералами (I век до н.э.) [44]. Применительно к русскому языку суть его состоит в следующем. Выписывается исходный алфавит (А, Б, ..., Я), затем под ним выписывается тот же алфавит, но с циклическим сдвигом на 3 буквы влево.

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
ГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВ

Рис.4.3. Таблица шифрозамен для шифра Цезаря

При зашифровке буква А заменяется буквой Г, Б - на Д и т. д. Так, например, исходное сообщение «АБРАМОВ» после шифрования будет выглядеть «ГДУГПСЕ». Получатель сообщения «ГДУГПСЕ» ищет эти буквы в нижней строке и по буквам над ними восстанавливает исходное сообщение «АБРАМОВ».

Ключом в шифре Цезаря является величина сдвига нижней строки алфавита. Количество ключей для всех модификаций данного шифра применительно к алфавиту русского языка равно 33. Существуют различные модификации шифра Цезаря, в частности атбаш и лозунговый шифр.

Атбаш. В Ветхом Завете существует несколько фрагментов из священных текстов, которые зашифрованы с помощью шифра замены, называемого атбаш. Этот шифр состоит в замене каждой буквы другой буквой, которая находится в алфавите на таком же расстоянии от конца алфавита, как оригинальная буква - от начала. Например, в русском алфавите буква А заменяется на Я, буква Б - на Ю и т.д. В оригинальном Ветхом Завете использовались буквы еврейского алфавита. Так, в книге пророка Иеремии (25:26) слово «Бабель» (Вавилон) зашифровано как «Шешах» [44].

Лозунговый шифр. Для данного шифра построение таблицы шифрозамен основано на лозунге (ключе) – легко запоминаемом слове. Вторая строка таблицы шифрозамен заполняется сначала словом-лозунгом (причем повторяющиеся буквы отбрасываются), а затем остальными буквами, не вошедшими в слово-лозунг, в алфавитном порядке. Например, если выбрано слово-лозунг «ДЯДИНА», то таблица имеет следующий вид.

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
ДЯИНАБВГЕЁЖЗЙКЛМОПРСТУФХЦЧШЩЪЫЬЭЮ

Рис.4.4. Таблица шифрозамен для лозунгового шифра

При шифровании исходного сообщения «АБРАМОВ» по приведенному выше ключу шифрограмма будет выглядеть «ДЯПДКМИ».

В качестве лозунга рекомендуется выбирать фразу, в которой содержаться конечные буквы алфавита. В общем случае, количество вариантов нижней строки (применительно к русскому языку) составляет 33! (≥ 1035).

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


123456
1АБВГДЕ
2ЁЖЗИЙК
3ЛМНОПР
4СТУФХЦ
5ЧШЩЪЫЬ
6ЭЮЯ---

Рис.4.5. Таблица шифрозамен для полибианского квадрата

Шифруемая буква заменяется на координаты квадрата (строка-столбец), в котором она записана. Например, если исходное сообщение «АБРАМОВ», то шифрограмма – «11 12 36 11 32 34 13». В Древней Греции сообщения передавались с помощью оптического телеграфа (с помощью факелов). Для каждой буквы сообщения вначале поднималось количество факелов, соответствующее номеру строки буквы, а затем номеру столбца.

Тюремный шифр [43]. Эта звуковая разновидность полибианского квадрата была разработана заключенными. Система состояла из нескольких ударов, обозначающих строки и столбцы в таблице с буквами алфавита. Один удар, а потом еще два соответствовали строке 1 и столбцу 2, т.е. букве Б. Пауза служила разделителем между строками и столбцами. Таким образом, зашифровать исходное сообщение «АБРАМОВ» можно следующим образом.

Атук ___ тук
Бтук ___ тук, тук
Ртук, тук, тук ___ тук, тук, тук, тук, тук, тук
Атук ___ тук
Мтук, тук, тук ___ тук, тук
Отук, тук, тук ___ тук, тук, тук, тук
Втук ___ тук, тук, тук

Рис.4.6. Пример использования тюремного шифра

Шифрующая система Трисемуса (Тритемия). В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием «Полиграфия». В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. На рис.4.7 изображена таблица с ключевым словом «ДЯДИНА».

ДЯИНАБ
ВГЕЁЖЗ
ЙКЛМОП
РСТУФХ
ЦЧШЩЪЫ
ЬЭЮ---

Рис.4.7. Таблица шифрозамен для шифра Трисемуса

Каждая буква открытого сообщения заменяется буквой, расположенной под ней в том же столбце. Если буква находится в последней строке таблицы, то для ее шифрования берут самую верхнюю букву столбца. Например, исходное сообщение «АБРАМОВ», зашифрованное – «ЖЗЦЖУФЙ».

Шифр масонов [43]. В XVIII в. масоны создали шифр, чтобы скрыть от общественности свои коммерческие сделки. Как поведали те, кто прежде состоял в рядах этого общества, масоны пользовались способом засекречивания, весьма похожим на шифр розенкрейцеров. В «решетке» и в углах находятся точки, которыми заменяются буквы:

Рис.4.8. Шифрозамены шифра масонов

Так как клятвы хранить тайну нарушались не раз, большинство Великих лож масонов в США больше не пользуются письменными шифрами, предпочитая передавать устные инструкции во время закрытых ритуалов.

С помощью шифра масонов можно легко расшифровать следующую фразу.

Рис.4.9. Пример использования шифра масонов

Это первый уровень, на котором находятся все впервые вступившие в общество члены: Blue Lodge (рус. «Голубая (Синяя) ложа»).

Одним из существенных недостатков шифров однозначной замены является их легкая вскрываемость. При вскрытии шифрограмм используются различные приемы, которые даже при отсутствии мощных вычислительных средств позволяют добиться положительного результата. Один из таких приемов базируется на том, что в шифрограммах остается информация о частоте встречаемости букв исходного текста. Если в открытом сообщении часто встречается какая-либо буква, то в шифрованном сообщении также часто будет встречаться соответствующий ей символ. Еще в 1412 г. Шихаба ал-Калкашанди в своем труде «Субх ал-Ааша» привел таблицу частоты появления арабских букв в тексте на основе анализа текста Корана. Для разных языков мира существуют подобные таблицы. Так, например, для букв русского алфавита по данным "Национального корпуса русского языка" такая таблица выглядит следующим образом [17].

Таблица 4.1. Частота появления букв русского языка в текстах

№ п/пБукваЧастота, %№ п/пБукваЧастота, %
1О10.9718Ь1.74
2Е8.4519Г1.70
3А8.0120З1.65
4И7.3521Б1.59
5Н6.7022Ч1.44
6Т6.2623Й1.21
7С5.4724Х0.97
8Р4.7325Ж0.94
9В4.5426Ш0.73
10Л4.4027Ю0.64
11К3.4928Ц0.48
12М3.2129Щ0.36
13Д2.9830Э0.32
14П2.8131Ф0.26
15У2.6232Ъ0.04
16Я2.0133Ё0.04
17Ы1.90   

Существуют подобные таблицы для пар букв (биграмм). Например, часто встречаемыми биграммами являются «то», «но», «ст», «по», «ен» и т.д. Другой прием вскрытия шифрограмм основан на исключении возможных сочетаний букв. Например, в текстах (если они написаны без орфографических ошибок) нельзя встретить сочетания «чя», «щы», «ьъ» и т.п.

Для усложнения задачи вскрытия шифров однозначной замены еще в древности перед шифрованием из исходных сообщений исключали пробелы и/или гласные буквы. Другим способом, затрудняющим вскрытие, является шифрование биграммами (парами букв).

 

4.3. Полиграммные шифры

 

Полиграммные шифры замены - это шифры, в которых одна шифрозамена соответствует сразу нескольким символам исходного текста.

Биграммный шифр Порты [43]. Шифр Порты, представленный им в виде таблицы, является первым известным биграммным шифром. Размер его таблицы составлял 20 х 20 ячеек; наверху горизонтально и слева вертикально записывался стандартный алфавит (в нем не было букв J, К, U, W, X и Z). В ячейках таблицы могли быть записаны любые числа, буквы или символы - сам Джованни Порта пользовался символами - при условии, что содержимое ни одной из ячеек не повторялось. Применительно к русскому языку таблица шифрозамен может выглядеть следующим образом.


АБВГДЕ
(Ё)
ЖЗИ
(Й)
КЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
А001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031
Б032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062
В063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093
Г094095096097098099100101102103104105106107108109110111112113114115116117118119120121122123124
Д125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155
Е (Ё)156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
Ж187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
З218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248
И (Й)249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279
К280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310
Л311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341
М342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372
Н373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403
О404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434
П435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465
Р466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496
С497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527
Т528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558
У559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589
Ф590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620
Х621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651
Ц652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682
Ч683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713
Ш714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744
Щ745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775
Ъ776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806
Ы807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837
Ь838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868
Э869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899
Ю900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930
Я931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961

Рис.4.10. Таблица шифрозамен для шифра Порты

Шифрование выполняется парами букв исходного сообщения. Первая буква пары указывает на строку шифрозамены, вторая - на столбец. В случае нечетного количества букв в исходном сообщении к нему добавляется вспомогательный символ («пустой знак»). Например, исходное сообщение «АБ РА МО В», зашифрованное – «002 466 355 093». В качестве вспомогательного символа использована буква «Я».

Шифр Playfair (англ. «Честная игра»). В начале 1850-х гг. Чарлз Уитстон придумал так называемый «прямоугольный шифр». Леон Плейфер, близкий друг Уитстона, рассказал об этом шифре во время официального обеда в 1854 г. министру внутренних дел лорду Пальмерстону и принцу Альберту. А поскольку Плейфер был хорошо известен в военных и дипломатических кругах, то за творением Уитстона навечно закрепилось название «шифр Плейфера».

Данный шифр стал первым буквенным биграммным шифром (в биграммной таблице Порты использовались символы, а не буквы). Он был предназначен для обеспечения секретности телеграфной связи и применялся британскими войсками в Англо-бурской и Первой мировой войнах. Им пользовалась также австралийская служба береговой охраны островов во время Второй мировой войны.

Шифр предусматривает шифрование пар символов (биграмм). Таким образом, этот шифр более устойчив к взлому по сравнению с шифром простой замены, так как затрудняется частотный анализ. Он может быть проведен, но не для 26 возможных символов (латинский алфавит), а для 26 х 26 = 676 возможных биграмм. Анализ частоты биграмм возможен, но является значительно более трудным и требует намного большего объема зашифрованного текста.

Для шифрования сообщения необходимо разбить его на биграммы (группы из двух символов), при этом, если в биграмме встретятся два одинаковых символа, то между ними добавляется заранее оговоренный вспомогательный символ (в оригинале – X, для русского алфавита - Я). Например, «зашифрованное сообщение» становится «за ши фр ов ан но ес оЯ об ще ни еЯ». Для формирования ключевой таблицы выбирается лозунг и далее она заполняется по правилам шифрующей системы Трисемуса. Например, для лозунга «ДЯДИНА» ключевая таблица выглядит следующим образом.

ДЯИНАБ
ВГЕЁЖЗ
ЙКЛМОП
РСТУФХ
ЦЧШЩЪЫ
ЬЭЮ-12

Рис.4.11. Ключевая таблица для шифра Playfair

Затем, руководствуясь следующими правилами, выполняется зашифровывание пар символов исходного текста:

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

2. Если символы биграммы исходного текста встречаются в одном столбце, то они преобразуются в символы того же столбца, находящимися непосредственно под ними. Если символ является нижним в столбце, то он заменяется на первый символ этого же столбца.

3. Если символы биграммы исходного текста находятся в разных столбцах и разных строках, то они заменяются на символы, находящиеся в тех же строках, но соответствующие другим углам прямоугольника.

Пример шифрования.

- биграмма «за» формирует прямоугольник – заменяется на «жб»;

- биграмма «ши» находятся в одном столбце – заменяется на «юе»;

- биграмма «фр» находятся в одной строке – заменяется на «хс»;

- биграмма «ов» формирует прямоугольник – заменяется на «йж»;

- биграмма «ан» находятся в одной строке – заменяется на «ба»;

- биграмма «но» формирует прямоугольник – заменяется на «ам»;

- биграмма «ес» формирует прямоугольник – заменяется на «гт»;

- биграмма «оя» формирует прямоугольник – заменяется на «ка»;

- биграмма «об» формирует прямоугольник – заменяется на «па»;

- биграмма «ще» формирует прямоугольник – заменяется на «шё»;

- биграмма «ни» формирует прямоугольник – заменяется на «ан»;

- биграмма «ея» формирует прямоугольник – заменяется на «ги».

Шифрограмма – «жб юе хс йж ба ам гт ка па шё ан ги».

Для расшифровки необходимо использовать инверсию этих правил, откидывая символы Я (или Х), если они не несут смысла в исходном сообщении.

Шифр Хилла [17, 43]. Первый практически реализуемый способ шифрования с использованием алгебры был придуман в 1929 г. математиком Лестером Хиллом - профессором из Хантер-колледжа в Нью-Йорке, статья которого «Cryptography in an Algebraic Alphabet» была опубликована в журнале «The American Mathematical Monthly».

Каждой букве алфавита сопоставляется число. Для русского алфавита можно использовать простейшую схему: А = 0, Б = 1, ..., Я = 32. Для зашифрования блок исходного сообщения из n букв рассматривается как n-мерный вектор чисел и умножается на матрицу размером n x n по модулю 33. Данная матрица, совместно с кодовой таблицей сопоставления букв алфавита с числами, является ключом зашифрования. Для расшифрования применяется обратная матрица1 по модулю.

Например, для триграммных замен могут использоваться следующие матрицы зашифрования / расшифрования.

6271
22617
131632
26204
281715
133021
матрица
зашифрования
      матрица
расшифрования

Рис.4.12. Матрицы зашифрования / расшифрования

Исходное сообщение «АБРАМОВ», дополненное двумя вспомогательными буквами «яя» (для кратности трем), после сопоставления букв с числами будет выглядеть следующим образом «0 1 17     0 13 15     2 32 32». После перемножения троек чисел на матрицу зашифрования шифрограмма примет следующий вид «11 32 8     3 28 17     17 11 24» (или в буквенном эквиваленте «КЯЗ ГЪР РКЧ»).

АБР - 0 1 17
(6 * 0 + 27 * 1 + 1 * 17) mod 33 = 11   (К)
(13 * 0 + 16 * 1 + 32 * 17) mod 33 = 32   (Я)
(18 * 0 + 17 * 1 + 15 * 17) mod 33 = 8   (З)
АМО - 0 13 15
(6 * 0 + 27 * 13 + 1 * 15) mod 33 = 3   (Г)
(13 * 0 + 16 * 13 + 32 * 15) mod 33 = 28   (Ъ)
(28 * 0 + 17 * 13 + 15 * 15) mod 33 = 17   (Р)
Вяя - 2 32 32
(6 * 2 + 27 * 32 + 1 * 32) mod 33 = 17   (Р)
(13 * 2 + 16 * 32 + 32 * 32) mod 33 = 11   (К)
(28 * 2 + 17 * 32 + 15 * 32) mod 33 = 24   (Ч)

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

КЯЗ - 11 32 8
(2 * 11 + 26 * 32 + 17 * 8) mod 33 = 0   (А)
(26 * 11 + 20 * 32 + 4 * 8) mod 33 = 1   (Б)
(13 * 11 + 30 * 32 + 21 * 8) mod 33 = 17   (Р)
ГЪР - 3 28 17
(2 * 3 + 26 * 28 + 17 * 17) mod 33 = 0   (А)
(26 * 3 + 20 * 28 + 4 * 17) mod 33 = 13   (М)
(13 * 3 + 30 * 28 + 21 * 17) mod 33 = 15   (О)
РКЧ - 17 11 24
(2 * 17 + 26 * 11 + 17 * 24) mod 33 = 2   (В)
(26 * 17 + 20 * 11 + 4 * 24) mod 33 = 32   (я)
(13 * 17 + 30 * 11 + 21 * 24) mod 33 = 32   (я)

В результате будет получен набор чисел «0 1 17     0 13 15     2 32 32», соответствующий исходному сообщению со вспомогательными символами «АБРАМОВяя».


1Обратная матрица - матрица A-1, при умножении на которую, исходная матрица A дает в результате единичную матрицу E.

 

4.4. Омофонические шифры

 

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

Система омофонов. В 1401 г. Симеоне де Крема стал использовать таблицы омофонов для сокрытия частоты появления гласных букв в тексте при помощи более чем одной шифрозамены. Такие шифры позже стали называться шифрами многозначной замены или омофонами2. Они получили развитие в XV веке. В книге «Трактат о шифрах» Леона Баттисты Альберти (итальянский ученый, архитектор, теоретик искусства, секретарь папы Климентия XII), опубликованной в 1466 г., приводится описание шифра замены, в котором каждой букве ставится в соответствие несколько эквивалентов, число которых пропорционально частоте встречаемости буквы в открытом тексте. Так, если ориентироваться на табл.4.1, то число шифрозамен для буквы О должно составлять 110, для буквы Е – 85 и т.д. При этом каждая шифрозамена должна состоять из 3 цифр и их общее количество равно 1000. На рис.4.12 представлен фрагмент таблицы шифрозамен.

№ п/пАБВМОРЯ
1311128175037248064266
2357950194149267189333
16495990199349303374749

20519
427760306469845

32637
524777432554




45678
644


824721





47776




828954





80901




886






110





903

Рис.4.13. Фрагмент таблицы шифрозамен для системы омофонов

При шифровании символ исходного сообщения заменяется на любую шифрозамену из своего столбца. Если символ встречается повторно, то, как правило, используют разные шифрозамены. Например, исходное сообщение «АБРАМОВ» после шифрования может выглядеть «357 990 374 678 037 828 175».

Книжный шифр. [14] Заметным вкладом греческого ученого Энея Тактика в криптографию является предложенный им так называемый книжный шифр, описанный в сочинении «Об обороне укреплённых мест». Эней предложил прокалывать малозаметные дырки в книге или в другом документе над буквами секретного сообщения. Интересно отметить, что в Первой мировой войне германские шпионы использовали аналогичный шифр, заменив дырки на точки, наносимые симпатическими чернилами3 на буквы газетного текста. Описанные способы передачи секретных сообщений (с помощью точек) относяться к стеганографическим методам сокрытия информации.

После Первой мировой войны книжный шифр приобрел иной вид. Шифрозамена для каждой буквы определялась набором цифр, которые указывали на номер страницы, строки и позиции в строке.

           
а) ключ
(4-ый том собрания сочинений Фридриха Шиллера)
б) шифрограмма в) сообщение

Рис.4.14. Пример использования книжного шифра
(кадры из советского сериала «Семьнадцать мнгновений весны»)

 

Количество книг, изданных за всю историю человечества, является величиной ограниченной (по крайней мере, явно меньше, чем 15!). Однако отсутствие полной электронной базы по изданиям делает процедуру вскрытия шифрограмм почти не выполнимой.

Вариантные шифры [43]. Вариантные шифры напоминают полибианский квадрат, но для каждой строки и столбца используется по два буквенных идентификатора. В квадрат (прямоугольник) шифрозамен вначале записывается ключевое слово без повторяющихся букв, а затем дополняется не вошедшими в него буквами по порядку следования в алфавите. Каждой строке и столбцу квадрата ставится в соответствие по две буквы алфавита. Буквы для идентификации строк и столбцов не должны повторяться.


Й
Ц
У
К
Е
Н
Г
Ш
Щ
З
Х
Ъ
Ф ЫДЯИНАБ
В АВГЕЁЖЗ
П РЙКЛМОП
О ЛРСТУФХ
Д ЖЦЧШЩЪЫ
Э ЯЬЭЮ---

Рис.4.15. Пример таблицы шифрозамен вариантного шифра с ключевым словом «ДЯДИНА»

Комбинации букв-идентификаторов строки и столбца дают по восемь шифрозамен для каждой буквы исходного текста. Например, для буквы Д возможны шифрозамены: ФЙ, ЙФ, ФЦ, ЦФ, ЫЙ, ЙЫ, ЫЦ и ЦЫ. Для таблицы шифрозамен, приведенной на рис. 4.15, исходное сообщение «АБРАМОВ» может быть зашифровано как «ЫЗ ЫХ ОЦ ЗФ ГР РЩ АЙ».


2Омофоны (греч. homos - одинаковый и phone - звук) - слова, которые звучат одинаково, но пишутся по-разному и имеют разное значение.

3Симпатические (невидимые) чернила — чернила, записи которыми являются изначально невидимыми и становятся видимыми только при определенных условиях (нагрев, освещение, химический проявитель и т. д.).

 

4.5. Полиалфавитные шифры

 

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

Диск Альберти. В «Трактате о шифрах» Альберти приводит первое точное описание многоалфавитного шифра на основе шифровального диска.

Рис.4.16. Реплика диска Альберти, используемого Конфедерацией во время Гражданской войны в Америке [www.cryptomuseum.com]

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

Таблица Трисемуса. Одним из шифров, придуманных немецким аббатом Трисемусом, стал многоалфавитный шифр, основанный на так называемой «таблице Трисемуса» - таблице со стороной равной n, где n – количество символов в алфавите. В первой строке матрицы записываются буквы в порядке их очередности в алфавите, во второй – та же последовательность букв, но с циклическим сдвигом на одну позицию влево, в третьей – с циклическим сдвигом на две позиции влево и т.д.

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
БВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯА
ВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБ
ГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВ
ДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГ
ЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГД
ЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕ
ЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁ
ЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖ
ИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗ
ЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИ
КЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙ
ЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙК
МНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛ
НОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМ
ОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМН
ПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНО
РСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОП
СТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПР
ТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРС
УФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТ
ФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУ
ХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФ
ЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХ
ЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦ
ШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧ
ЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШ
ЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩ
ЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪ
ЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫ
ЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬ
ЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭ
ЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮ

Рис.4.17. Таблица Трисемуса

Первая строка является одновременно и алфавитом для букв открытого текста. Первая буква текста шифруется по первой строке, вторая буква по второй и так далее. После использования последней строки вновь возвращаются к первой. Так сообщение «АБРАМОВ» приобретет вид «АВТГРУЗ».

Система шифрования Виженера. В 1586 г. французский дипломат Блез Виженер представил перед комиссией Генриха III описание простого, но довольно стойкого шифра, в основе которого лежит таблица Трисемуса.

Перед шифрованием выбирается ключ из символов алфавита. Сама процедура шифрования заключается в следующем. По i-ому символу открытого сообщения в первой строке определяется столбец, а по i-ому символу ключа в крайнем левом столбце – строка. На пересечении строки и столбца будет находиться i-ый символ, помещаемый в шифрограмму. Если длина ключа меньше сообщения, то он используется повторно. Например, исходное сообщение «АБРАМОВ», ключ – «ДЯДИНА», шифрограмма – «ДАФИЪОЁ».

Справедливости ради, следует отметить, что авторство данного шифра принадлежит итальянцу Джованни Батиста Беллазо, который описал его в 1553 г. История «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания» [13]. Беллазо предложил называть секретное слово или фразу паролем (ит. password; фр. parole - слово).

В 1863 г. Фридрих Касиски опубликовал алгоритм атаки на этот шифр, хотя известны случаи его взлома шифра некоторыми опытными криптоаналитиками и ранее. В частности, в 1854 г. шифр был взломан изобретателем первой аналитической вычислительной машины Чарльзом Бэббиджем, хотя этот факт стал известен только в XX в., когда группа ученых разбирала вычисления и личные заметки Бэббиджа [44]. Несмотря на это шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому еще долгое время. Так, известный писатель и математик Чарльз Лютвидж Доджсон (Льюис Кэрролл) в своей статье «Алфавитный шифр», опубликованной в детском журнале в 1868 г., назвал шифр Виженера невзламываемым. В 1917 г. научно-популярный журнал «Scientific American» также отозвался о шифре Виженера, как о неподдающемся взлому [13].

Роторные машины. Идеи Альберти и Беллазо использовались при создании электромеханических роторных машин первой половины ХХ века. Некоторые из них использовались в разных странах вплоть до 1980-х годов. В большинстве из них использовались роторы (механические колеса), взаимное расположение которых определяло текущий алфавит шифрозамен, используемый для выполнения подстановки. Наиболее известной из роторных машин является немецкая машина времен Второй мировой войны «Энигма» [8].

Рис.4.18. Энигма [www.cryptomuseum.com]

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

       
а) четыре последовательно соединённых ротора   б) штыри ротора

Рис.4.19. Роторная система Энигмы [www.cryptomuseum.com]

Шифрующее действие «Энигмы» показано для двух последовательно нажатых клавиш - ток течёт через роторы, «отражается» от рефлектора, затем снова через роторы.

Рис.4.20. Схема шифрования

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

Шифры Тени [43]. Главными развлечениями для американцев тридцатых годов XX века были бульварное чтиво и радио. Для раскрутки своих книжек издательство Street & Smith проспонсировало радиопередачу, ведущим в которой был Тень (англ. Shadow), загадочный рассказчик со зловещим голосом, который в начале каждого выпуска заявлял: «Кто знает, что за зло прячется в сердцах людей? Тень знает!». Успех радиопередачи подтолкнул издательство к решению начать выпускать серию книг, в которой главным героем был бы Тень. Свои услуги предложил Уолтер Гибсон, большой любитель фокусов и головоломок. Под псевдонимом Максвелл Грант он принялся писать роман за романом, да с такой скоростью, что за свою жизнь написал почти 300 книжек о грозе тех, кто нечист помыслами. В новелле «Цепочка смерти» супергерой воспользовался так называемым кодом направления, хотя на самом деле он действует скорее как шифр, чем как код.

Рис.4.21. Таблица шифрозамен и управляющих символов

Управляющие символы в последней строке таблицы служат для изменения кода (выбора шифралфавита) для зашифрования/дешифрования. Линии внутри каждого кружка фактически являются стрелками, подсказывающими адресату, как держать лист бумаги. Символ 1 означает, что лист надо держать как обычно: верх и низ расположены на своих местах, а сообщение читается слева направо. Символ 2 требует поворота на 90° вправо, а символ 3 указывает, что лист бумаги следует перевернуть вверх ногами. Символ 4 обозначает поворот на 90° влево. Эти дополнительные символы могут появляться перед любой строчкой текста, а также в ее середине.

Из нижеприведенного примера можно узнать настоящие имя и фамилию супергероя.

Рис.4.22. Настоящие имя и фамилия Тени

Согласно первому управляющему символу, лист следует держать обычным образом, не поворачивая, и после замены буквы образуют «Lamont Cranston» (Ламонт Крэнстон).

 

4.6. Нерегулярные шифры

 

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

Совмещенный шифр (совмещенная таблица) [43]. Данный шифр применялся еще семейством Ардженти - криптологами, разрабатывавшими шифры для Папы Римского в XVI в. В XX столетии этим способом пользовались коммунисты в ходе гражданской войны в Испании. В начале войны противники фашизма в Испании контролировали большинство крупных городов и защищали свою связь, включая радиопередачи, с помощью различных методов шифрования, в том числе совмещенных шифров.

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

Таблица шифрозамен состоит из 10 столбцов с нумерацией 0, 9, 8, 7, 6, 5, 4, 3, 2 и 1. В начальную строку вписывается ключевое слово без повторяющихся букв. В последующие строки вписываются по десять не вошедших в него букв по порядку следования в алфавите. Строки, за исключением начальной, нумеруются по порядку, начиная с 1.


0987654321

ДЯИНА




1БВГЕЁЖЗЙКЛ
2МОПРСТУФХЦ
3ЧШЩЪЫЬЭЮ--

Рис.4.23. Пример таблицы шифрозамен совмещенного шифра с ключевым словом «ДЯДИНА»

При шифровании буквы исходного сообщения, входящие в ключевое слово, заменяются на одну цифру (номер столбца), остальные – двумя (номера строки и столбца). Например, для приведенной выше таблицы шифрозамен исходное сообщение «АБРАМОВ» будет зашифровано как «610276202919».

При получении шифрограммы адресат знает, что когда появляются цифры 1, 2 или 3, с ними обязательно связана еще одна цифра, поскольку они представляют собой цифровую пару. Так что 35 - это, несомненно, пара, а 53 - нет, ведь в таблице нет строки с номером 5. Перехват такого сообщения третьей стороной даст ей всего лишь ряд цифр, потому что криптоаналитик противника не имеет ни малейшего представления, какие цифры одиночные, а какие входят в состав пар.

 

Вопросы для самопроверки

 

1. В чем заключается основная идея криптографических преобразований шифров замены?

2. Перечислите основные разновидности шифров замены.

3. Дайте характеристику разновидностям шифров замены.

4. Назовите основной недостаток шифра однозначной замены.