Алгоритм 1

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

2. Выявление шифробозначений, заменяющих гласные и согласные буквы.

3. Выдвижение гипотез о значениях шифробозначений и их проверка. Восстановление истинного значения шифробо­значений.

Сделаем ряд замечаний и уточнений. Если длина текста достаточно велика, то найденные на этапе I частоты окажутся близкими к табулированным значе­ниям частот знаков (соответственно – биграмм или три­грамм). Проведенная на этом этапе работа служит основанием для выдвижения гипотез о значениях шифрвеличин, соответ­ствующих данным шифробозначениям. При этом учитывает­ся, что каждая буква имеет группу предпочтительных связей, которые составляют ее наиболее харак­терную особенность. Как правило, такие гипотезы подтвер­ждаются не полностью. Хорошим критерием при этом явля­ется "читаемость" восстанавливаемого открытого текста. Вы­деление шифробозначений, отвечающих гласным и соглас­ным, основано на характерных свойствах этих букв. Добавим к ним следующие соображе­ния (относимые к большинству европейских языков). Если шифробозначение часто встречается, равномерно располага­ется по шифртексту, в отдельных местах чередуется через 1, 2 или 3 знака, сочетается со средними и редкими (по частоте) шифробозначениями, то это дает основания полагать, что такое шифробозначение скрывает гласную букву. Удвоение гласных в открытом тексте происходит реже, чем согласных. Если некоторое шифробозначение признано гласной, то буква, часто сочетающаяся с ней, скорее всего согласная. В от­крытом тексте чрезвычайно редко встречаются три и более подряд идущие гласные. Четыре и более подряд идущие со­гласные также редки. Важно учитывать также процентное со­отношение чисел гласных и согласных в открытом тексте.

При проверке гипотез о значениях шифробозначений по­лезен поиск в шифртексте слов с характерной структурой, которые часто встречаются в открытом тексте. Для русского языка – это, например, слова сколько, которое, что и т. п. Для английского языка – слова every, that, look, the и т.п. Такие слова выделяются в шифртексте посредством интерва­лов между повторяющимися частыми буквами, характерными сочетаниями гласных и согласных.

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

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

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

Мерой близости служит следующая "целевая функция" f(t), связывающая матрицы D(t) и В:

(1)

Будем исходить из того естественного предположения, что если у – данная криптограмма и D_k– правило расшиф­рования на ключе k данного шифра простой замены, то для истинного ключа k_u значение

должно быть минимальным.

Идея основного шага алгоритма состоит в том, чтобы ис­ходя из некоторого первичного "приближения" k для ключа k_u, основанного, например, на диаграмме частот букв, не­много его изменять неким "разумным" способом, уменьшая значение целевой функции f(t).

Приведем теперь формальное описание алгоритма.

Алгоритм 2

1. Построить начальный вариант ключа k на основе сравне­ния частот знаков криптограммы и открытого текста.

2. Положить v = f(D_k(у)).

3. Положить k'= k.

4. Поменять местами в нижней строке подстановки k' неко­торую пару букв, скажем а и b.

5. Положить v'=f(D_k¢(y)).

6. Если v' < v, то положить k = k', v'=v и перейти к 4.

7. Перейти к шагу 3.

Алгоритм заканчивается, когда условие v'<v не выпол­няется в течение некоторого числа итераций, например 100.

Переход на шаге 4 от k к k', связанный с транспозицией пары символов, имеет под собой следующее основание. На шаге 5 вычисляется величина

где D¹(t) – матрица, полученная из матрицы D(t) путем перестановки в ней столбцов с номерами а и b, а также строк с теми же номерами.

В силу отмеченного свойства на шаге 5 алгоритма не нужно проводить трудоемкую операцию вычисления матри­цы биграмм D_ij(D_k¢(y)) непосредственно по "расшифрован­но­му" тексту D_k¢(y). Достаточно вычислить лишь матрицу D(D_k(у)), а на следующих шагах алгоритма производить в ней одноименные перестановки строк и столбцов.

Выбор транспозиции (a, b) на шаге 4 можно произво­дить, например, следующим естественным образом. Пусть s=(s₁,s₂,...,s_n) – вектор, образованный буквами крипто­граммы, упорядоченными по убыванию частот. Тогда после­довательность транспозиций можно выбрать такой:

(s₁,s₂), (s₂,s₃),…,(s_n-2,s_n-1), (s_n-1,s_n),

(s₁,s₃), (s₂,s₄),…,(s_n-2,s_n),

………………………………

(s₁,s_n).

Алгоритм 2 является достаточно эффективным.

Отметим некоторые особенности вскрытия равнозначных и разнозначных шифров простой замены.

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

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

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

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

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

4.4.3. Блочные шифры простой замены

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

Простейший блочный шифр оперирует с биграммными шифрвеличинами. Одними из первых таких шифров были биграммные шифры Порта и Плейфера. Приведем описание шифра Плейфера, нашедшего широкое применение в начале ХХ века.

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

Буквы биграммы (i, j), i ¹ j (являющейся шифрвеличиной) находятся в данной таблице. При зашифровании биграмма (i, j) заменяется биграммой (k,l), где k и l опреде­ляются в соответствии с правилами 1-3.

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

2. Если i и j лежат в одной строке, то k и l – буквы той же строки, расположенные непосредственно справа от i и j соответственно. При этом если одна из букв – последняя в строке, то считается, что ее "правым соседом" является пер­вая буква той же строки.

3. Аналогично, если i и j лежат в одном столбце, то они заменяются их "соседями снизу".

При зашифровании открытый текст представляется в ви­де последовательности биграмм. Если текст имеет нечетную длину или содержит биграмму, состоящую из одинаковых букв, то в него добавляются "пустышки" следующим образом. "Пустышкой" является некоторая редкая для данного типа текста буква (или знак), которая вставляется между одинаковыми буквами биграммы или добавляется в текст для того, чтобы его длина стала четной. Такие изменения открытoго текста, как правило, не мешают при расшифровании. Проиллюстрируем сказанное следующим примером.

Пример (шифра Плейфера)

Пусть шифр использует прямоугольник размером 5 х 6, в который записан систематически перемешанный русский 30-буквенный алфавит на основе ключевого слова командир:

Зашифруем фразу "автором метода является Уитстон". В качестве "пустышки" будем использовать редкую букву ф. Представим фразу в виде последовательности биграмм:

АВ ТО РО МФ ME ТО ДА ЯВ ЛЯ ЕТ СЯ УИ ТС ТО НФ

(Нам пришлось дважды вставить "пустышку".)

В соответствии со сформулированными правилами получаем шифртекст:

ВП ЗД ЗР ОХ ДБ ЗД КН ЭЕ ТЫ ТШ ШД ЩЖ ЖТ ЗД ОЧ или без пробелов

впздзрохдбздкнэетытшшдщжжтздоч

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

Шифрвеличинами для другого широко известного блоч­ного шифра – шифра Хилла (названного по имени Лестора Хилла) – являются п-граммы открытого текста (п > 1), представленного некоторым числовым кодом (так что алфа­витом открытого текста служит кольцо вычетов по модулю мощности алфавита Z_m).

Правило зашифрования представляет собой линейное преобразование кольца Z_m : если х=(х₁,...,х_n) – n-грамма открытого текста, k =(k_ij) – некоторая обратимая матрица над Z_m (ключ) и y=(y₁,...,y_n) – n-грамма шифртекста, то у=Е_k(х) = k • х. Соответственно х =D_k (у) = k ^-1• у,

где k ^-1– матрица, обратная к матрице k.

Подчеркнем, что матричные операции здесь производятся над кольцом Z_m.

Проиллюстрируем введенное определение примером.

Пример (шифра Хилла)

Положим п = 4 и зашифруем фразу:

без труда не вынешь рыбку из пруда

записанную в 30-буквенном русском алфавите. Условимся о числовом кодировании букв в соответствии с таблицей:

В качестве ключа выберем матрицу

являющуюся обратимой над кольцом Z₃₀. Несложно убедиться в том, что

Запишем открытый текст по столбцам матрицы Т :

и получим шифртекст в виде столбцов матрицы k • Т:

Теперь осталось воспользоваться числовым кодом, чтобы выписать шифртекст в буквенном виде:

токцжишшеюыстщчрбвсцьцтржишш

Замечание. Из соображений удобства в применении по­лучили широкое распространение шифры, для которых пра­вила зашифрования и расшифрования идентичны. Такие шифры называются обратимыми. Шифр Хилла является об­ратимым в том и только том случае, когда k ^-1= k, или иначе: k² = Е, где Е– единичная матрица. Матрица, удовлетво­ряющая этому свойству, называется инволютивной.

Из курса алгебры известен критерий обратимости квад­ратной матрицы над кольцом Z_m.

Теорема. Квадратная матрица М над кольцом Z_m об­ратима тогда и только тогда, когда (çМç,т)=1, то есть определитель çМç взаимно прост с т.

Заметим, что правило зашифрования Е_М (с матрицей М_n´n) в шифрсистеме Хилла является обратимым линейным преобразованием n-мерного модуля

. Такая функция является лишь одним из примеров простого задания обратимого преобразования —> , являющегося, очевидно, биекцией на . Любая же такая биекция потенциально может рас­сматриваться как правило зашифрования блочного шифра простой замены (если п – размер блока), выбираемого некоторым ключом. Поскольку число обратимых линейных преобразований модуля составляет (при n >2, m >2) лишь незначительную часть общего числа рассматриваемых биекций, то же самое можно сказать и о доле, которую составляют (при данном п) шифрсистемы Хилла в множестве возможных блочных шифров простой замены.

Естественным обобщением шифра Хилла является аф­финный блочный шифр, правило зашифрования Е_(А,b)(х) которого определяется формулой:

Е_(А,b)(х)=х×А+ b.

При этом Аявляется "обратимой п х п матрицей, а b– фиксированным п-мерным вектором над Z_m.

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

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

Предположим, что известны п+1 пар блоков открытого текста и соответствующих им блоков шифртекста:

(х₀,у₀),…,(х_n,у_n), х_i, у_iÎ, полученных на одном ключе (A, b). Требуется этот ключ найти.

Для решения поставленной задачи положим:

x⁽ⁱ⁾=х_i – x₀, y⁽ⁱ⁾=y_i – y₀, i=1,…,n.

Тогда x⁽ⁱ⁾ и y⁽ⁱ⁾ оказываются связанными линейным соот­ношениемy⁽ⁱ⁾=х⁽ⁱ⁾А.

Аналогичное соотношение имеет место и для матриц

и :

из которого находим матрицу А в виде произведения

Наконец, вектор b находится, например, по формуле b = y₀ —х₀•А. Естественно, что такое решение корректно лишь в том случае, когда матрица

обратима.

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

Более детальное рассмотрение блочных шифров простой замены будет продолжено в Теме 6.