Криптоаналитическая статистическая атака и система омофонов

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

² определяется число появлений каждой буквы в шифртексте.

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

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

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

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

При шифровании каждая буква алфавита заменяется на трехраз­ряд­ное число. Замены (их еще называют омофонами) представлены числами от 000 до 999. Самые редко встречающиеся буквы получают по одному числу для замены, остальные – по несколько чисел, одно из которых выби­рается случайным равновероятным образом при шифровании данной бук­вы. Число чисел для замены каждой буквы берется пропорционально час­тоте её появления. При шифровании буквы исходного сообщения, выбира­ется одна из ее замен, то есть каждая буква исходного алфавита шифруется тремя цифрами и шифртекст в три раза длиннее исходного текста.

Например, английская буква Е встречается в 3 раза чаще буквы L и в 123 раза чаще букв J и Z, а русская буква Е встречается в 36 раз чаще, чем буква Ф. Тогда в английском алфавите буквы J и Z для замены получа­ют по одному числу, а буква Е заменяется на выбранное случайным обра­зом одно из 123 трехзначных чисел из назначенных ей в таблице замен.

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

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

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

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

При r -алфавитной подстановке символ х₀ исходного сообщения за­ме­няется символом из алфавита В₀, символ х₁ – символом из алфави­та B₁ и так далее, символ х_r-1 заменяется символом из алфавита B_r-1, символ х_r  заменяется символом снова из алфавита В₀ и т.д.

Пример многоалфавитной подстановки (r =4):

Входной символ     х₀ х₁ х₂ х₃ х₄ х₅ х₆ х₇ х₈ х₉

Алфавит подстановки B₀ B₁ B₂ B₃ B₀ B₁ B₂ B₃ B₀ B₁

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

Многоалфавитные шифры замены предложил и ввел в практику крип­тографии Леон Батист Альберти, который также был известным архи­тектором и теоретиком искусства. Его книга "Трак­тат о шифре", написан­ная в 1566 г., представляла собой первый в Европе научный труд по крип­тологии. Криптологи всего мира почитают Альберти основоположником криптологии. Он же впервые выдвинул идею повторного шифрования, ко­то­рая в виде идеи многократного шифрования лежит в основе всех совре­менных шифров с секретным ключом. Кроме шифра многоалфа­витной замены Альберти также подробно описал устройства для его реализации.

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

Шифр Гронсфельда

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

Шифртекст получают аналогично, как в шифре Цезаря, но отсчитывают по алфавиту не третью букву (как это делается в шифре Цезаря), а выбирают ту букву, которая смещена по алфавиту на соответствующую цифру ключа. Напри­мер, применяя в качестве ключа группу из четырех начальных цифр числа е (основания натуральных логарифмов), а именно 2718, получаем для исходного сообщения ВОСТОЧНЫЙ ЭКС­ПРЕСС следующий шифртекст:

Чтобы зашифровать первую букву сообщения В, исполь­зуя первую цифру ключа 2, нужно отсчитать вторую по порядку букву от В, получает­ся первая буква шифртекста Д.

Следует отметить, что шифр Гронсфельда вскрывается относитель­но легко, если учесть, что в числовом ключе каждая цифра имеет только де­сять значений, а значит, имеется лишь де­сять вариантов прочтения каж­дой буквы шифртекста. С другой стороны, шифр Грон­сфельда допускает дальнейшие модификации, улучшающие его стой­кость, в частности двой­ное шифрование разными числовыми ключами. Этот шифр представляет собой по существу ча­стный случай системы шифрования Вижинера, кото­рый проанализировал и объединил предложенные Тритемием, Белазом и Портом подходы, по существу не внеся в них ничего оригинального.