Шифры сложной замены

Одноалфавитные (простые) и многоалфавитные (сложные) замены.

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

Рис. 1.26. Классификация шифров замены по типу преобразования.

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

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

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

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

Рис. 1.27. Таблица Виженера, выделены строки, соответствующие ключевому слову «white»

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

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

Для каждой буквы открытого текста берут шифр-алфавит из таблицы Виженера, определяемый соответствующим символом ключа. Открытому тексту соответствует первая буквенная строка таблицы. Каждой букве ключа соответствует та строка таблицы, которая начинается с этой буквы (на рис. 1.27 выделены строки, соответствующие ключу «white»). Таким образом, буквы открытого текста следует искать в первой строке таблицы, а буквы ключа — в ее первом столбце. Буква шифротекста лежит на пересечении столбца, определяемого буквой открытого текста, и строки, определяемой буквой ключа (рис. 1.28).

Рис. 1.28. Пример шифрования с помощью таблицы Виженера.

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

В этом примере видны достоинства шифра Виженера: несмотря на то, что открытый текст содержит расположенные подряд повторяющиеся символы («ss», «tt»), в шифре им соответствуют разные буквы. Действительно, шифр Виженера маскирует естественные частоты появления символов в тексте (рис. 1.29) — график частот шифра Виженера ближе к случайному равномерному распределению (расположен более «горизонтально»).

Рис. 1.29. Маскировка естественных частот символов в шифре Виженера.

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

В отличие от шифра Цезаря в схеме Виженера сдвиг не является постоянной величиной, он определяется символами ключа. Пусть {<а_п} — последовательность символов исходного текста, {с_п} — последовательность символов шифротекста, а {ЙД — ключевая последовательность, 0 < й. < N — 1, i = = 0,…, п, п — длина исходного текста.

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

Шифрование по таблице Виженера аналогично преобразованию а расшифрование — преобразованию.

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

Криптоанализ шифра Виженера. Пусть М — длина ключевого слова. Если ключевое слово короче шифруемого текста, то ключевое слово будет последовательно повторяться, поэтому М — период ключевой последовательности.

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

Описанное свойство дает возможность применить частотный анализ для каждой группы символов криптограммы, соответствующих определенной букве ключа. Такие группы символов называют группами периода. Первую группу периода составляют 1, М + 1, 2М + 1, …, rM + 1 символы, вторую группу периода — 2, М + 2, 2М + 2,…, гМ + 2 символы и т. д. Число групп периода равно длине ключа М.

Частотный анализ символов, составляющих группу периода, позволяет криптоаналитику определить величину смещения нормативного алфавита для каждой группы, т. е. ключ шифрования. Такой метод криптоанализа может быть эффективен, если длина криптограммы п превышает 20М (п > 20М), М — длина ключа.

Обычно криптоанализ шифра Виженера проводится в два этана. На первом этапе определяется число М, на втором этапе — само ключевое слово.

Для определения периода ключевой последовательности М применяются:

• • тест Казиски (1863 г.), основанный на том, что два одинаковых отрезка открытого текста, отстоящих друг от друга на расстоянии, кратном М, будут зашифрованы одинаково. В силу этого в криптограмме ищутся повторяющиеся фрагменты достаточной длины (> 3), случайное появление которых в шифротексте маловероятно, а затем определяются расстояния d_v d_v… между одинаковыми фрагментами. Мдолжно оказаться среди делителей d = НОД (d_v d_v …). Чем больше повторяющихся фрагментов имеется в шифротексте, тем более вероятно, что М совпадет с d
• • автокорреляционный метод. Текст криптограммы выписывается в строку, под ним выписываются строки, в которых текст сдвинут влево на одну, две, три, четыре и т. д. позиции (t = 1,2,3,…). Затем для каждой строки подсчитывается число позиций, в которых символ совпал с символом исходной строки в той же позиции (с, = с_/+,), и вычисляются автокорреляционные коэффициенты, равные отношению числа совпадений к длине строки. Для t, кратных периоду ключевой последовательности, автокорреляционные коэффициенты должны быть заметно больше, чем для сдвигов, не кратных периоду;
• • для проверки правильности выбора значения М может быть использован метод индекса совпадения, введенный в практику в 1920 г. американским криптологом и криптоаналитиком У. Фридманом (William Frederick Friedman), впервые успешно применившим вероятностно-статистические методы в криптологии. Для каждой группы периода X_rt= 1,М вычисляется значение статистики — индекса совпадения 1_С(Х_г):

где/, i = 0,N — I — число появлений буквы а- шифр-алфавита А мощностью N в последовательности Х_г Для случайной последовательности символов значение индекса соответствия будет составлять около 1 /N 0,030.

для русского языка), в то время как для осмысленных текстов его значение существенно выше (~ 0,055 для русского языка). Поскольку шифр Цезаря, которым зашифрованы символы группы периода, не меняет частотных характеристик текста, заметная разница значений I_c(X_t) для осмысленных текстов и случайных последовательностей позволяет в большинстве случаев установить точное значение периода ключевой последовательности М в шифре Виженера.

На втором этапе требуется найти само ключевое слово, т. е. определить сдвиги b_t, t= 1,…, М для каждой из групп периода. Это можно сделать визуально, используя гистограммы частот символов каждой из групп периода. Для решения задачи может быть использована статистика — взаимный индекс совпадения MI_c(X_t, X'):

где /₀,/, …,/_v_₁ и /о,/, — частоты вхождений букв алфавита А в группы периода X_t и X' соответственно. При нулевом сдвиге между группами периода взаимный индекс совпадения М1_С близок к индексу совпадения в естественном языке, ненулевые относительные сдвиги дают более низкие значения. Используя изложенный метод, можно связать системой уравнений относительные сдвиги различных групп периода. В результате останется 33 (для русского языка) варианта для ключевого слова, из которых можно выбрать наиболее предпочтительный вариант, если ключевое слово является осмысленным. Этот метод будет эффективным для небольших значений М, поскольку для хороших сближений индексов совпадения требуются тексты достаточно большой длины.

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

Пример 1.7

Имеется криптограмма, полученная шифром Виженера. Известно, что нормативный алфавит и шифр-алфавит состоят из букв русского языка, буквы «е» и «ё» нс различаются, знаки пунктуации и пробелы в тексте удалены. Мощность алфавита N = 32. Требуется определить исходный текст и ключ шифрования.

Текст криптограммы:

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

ищшчряьршхдоьхюэщчтяйьъшвлрщкбчнхпаелщштгпэшыовцхбъьбъюэжчна;

йтыещрщюшиймйьреьыйвчьнтяйэьцялуакйгэкмиещщэъыыашзеюъшцищ;

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

ржлсэсцудиыъькмчаышкыйшоорэущкъоыьф".

Определим период ключевой последовательности, используя тест Казиски. В тексте будем искать повторы трехбуквенных и более длинных последовательностей, случайное повторение которых считается маловероятным.

Найдены повторяющиеся фрагменты: «ъхэщщжтаы» — два повтора, расстояние между повторами d_i = 325 символов; «кэиж» — два повтора, d₂ = 45; «ьаш» — два повтора, б/₃ = 15; «юбш» — два повтора, d_A = 270. Наибольший общий делитель этих чисел d = НОД (d_v d_v d_y d_A) = НОД (325, 45, 15, 270) = 5. Скорее всего, период ключевой последовательности М = 5.

Проверим эту гипотезу методом индекса совпадений. Сформируем группы периода (табл. 1.5).

Таблица 1.5

Группы периода.

Подсчитаем индексы совпадений для каждой группы периода, воспользовавшись формулой (1.5) (табл. 1.6).

Для случайного текста значение индекса совпадения будет близко к 1 /N = = 1/32 = 0,3 125. Как очевидно из табл. 1.6, полученные статистики значительно больше этого значения. Таким образом, можно сделать вывод о том, что период ключевой последовательности М = 5 выбран правильно.

Определим теперь сдвиги алфавитов групп периода Х₍ относительно первой группы. Сдвиги можно определить визуально: для этого сопоставим частоты появления символов в двух группах, выделив наиболее часто встречающиеся символы (рис. 1.30).

Таблица 1.6

Расчет индекса совпадений.

Группа периода.									*3.
Алфавит.
а.
в.
г.
д.
е.
ж.
и.
й.
к.
л.								ПО.
м.
н.
О.
п.
р
с.
т.
У.
ф.
X.
Ц
ч.
ш.
Щ.
ъ.
ы.			И.
ь.
э.
ю.
я.
ЕЛЛ- 1).
т (т — 1).	13 110.		12 882.		12 882.		12 882.		12 882.
т	0,0485.		0,0605.		0,0517.		0,0567.		0,0472.

Рис. 1.30. Сопоставление частот символов групп периода 1 и 2

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

На рис. 1.30 такой «провал» в алфавите первой группы периода X, наблюдается, начиная с буквы «э» (код 29), а в алфавите второй группы периода Х₂ — начиная с буквы «г» (код 3). Таким образом, букву «г» второго шифр-алфавита надо «совместить» с буквой «э» первого шифр-алфавита. Иными словами, алфавит группы Х₂ надо циклически сдвинуть вправо на 26 позиций.

Циклический сдвиг алфавита нижней группы периода вправо дает положительное значение сдвига, а влево — отрицательное.

Величина сдвига алфавита группы Х₂ относительно алфавита группы X, периода s₂ = 26. Проведем проверку полученного результата с помощью индекса взаимного совпадения, воспользовавшись формулой (1.6). На рис. 1.31 отображены частоты символов / группы Х₂ с учетом сдвига s₂ = 26.

Рис. 1.31. Частоты символов Х₂ с учетом сдвига Взяв значения / для группы X, из табл. 1.6 и значения т₁ для групп X, и Х₂ из табл. 1.5, получаем MI_C(X_V Х₂) = 752/13 110 = 0,057. Очевидно, значение статистики MI_C(X_V Х₂) достаточно высоко, что свидетельствует о правильном выборе сдвига.

Если сдвиг определен неверно, значение этой статистики будет значительно ниже и находится в районе 0,03. Обычно совмещения начал «провалов» даст правильное значение сдвига, однако если статистика не подтверждает результат, можно попробовать взять значения сдвига ±1 от полученного или проверить «совмещение» пиковых значений частот.

Определим значения s₃, s₄ и s₅ для групп X, и X_:i, X, и Х₄, X, и Х₅. На рис. 1.32 показаны направления сдвигов алфавитов групп Х₂—Х₅ относительно X,. Получаем: s₃ = 15, s₄ = -1, s₅ = 28.

На рис. 1.33 показаны частоты символов шифр-алфавитов с учетом сдвигов, тогда получаем MI_C(X_V Х₃) = 714/13 110 = 0,055, MI_C(X_V Х_л) = 699/13 110 = = 0,053, MI_C(X_V Х₅) = 639/13 110 = 0,049. Сдвиги s, определены верно.

Зная значения относительных сдвигов s_t алфавитов групп Х₍ относительно группы X, можно определить сдвиги g_t алфавитов групп периода X, относительно алфавита открытого текста:

Рис. 1.32. Определение сдвигов шифр-алфавитов.

Рис. 1.33. Частоты символов Х₍ с учетом сдвига.

Теперь осталось определить сдвиг g, алфавита первой группы периода относительно алфавита открытого текста. Зная gj и используя полученные соотношения для g, можно определить все символы ключевого слова.

Поскольку число различных вариантов значений сдвига g, невелико — N, можно определить gj (и ключ) перебором. Для этого рассматривают все возможные варианты первого символа ключа (от «а» до «я»), следующие символы определяют по формулам для g, (операции выполняются по модулю iV), исходя из текущего значения первого символа (табл. 1.7).

Таблица 1.7

Подбор ключевого слова.

Поскольку известно, что ключ является осмысленным словом, его определение не составляет труда. Среди всех вариантов ключа имеется только один осмысленный: это вариант, определяемый сдвигом g, = 10, — «крыло».

Теперь, используя формулу (1.4), получаем исходный текст: «оназаглянулавсоседнююкомнатуздесьстоялписьменныйстол…».

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

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