Операция "Раздолбай"

Моноалфавитные и полиалфавитные шифры. Описание и криптоанализ.

Моноалфавитный шифр

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

Криптоанализ

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

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

Полиалфавитный шифр

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

Шифрование

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

Расшифровка

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

Криптоанализ

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

Метод Касиски

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

Автокорреляционный метод

Автокорреляционный метод состоит в том, что исходный шифротекст (C_1, C_2 ,\ldots, C_L) выписывается в строку, а под ней выписываются строки полученные сдвигом вправо на t=1, 2, 3,\ldots позиций. Для каждого t подсчитывается число n_t индексов i\in[1,L-t] таких, что C_i=C_{i+t}\,. Вычисляются автокорреляционные коэффициенты \gamma_t=n_i/(L-t).

Для чисел t, кратных периоду m, коэффициенты \gamma_t должны быть заметно больше, чем для сдвигов, не кратных периоду.

Метод индекса совпадений

Для последовательности \bold{x}=(x_1,x_2,\ldots,x_L) из букв алфавита из A букв индексом совпадения I_c(\bold{x}) называется вероятность того, что два случайных элемента этой последовательности совпадают. Экспериментально индекс совпадений приближенно равен

I_c(\bold{x})=\frac{\sum\limits_{i=1}^{A} f_i(f_i-1)}{L(L-1)}

где f_i число появлений буквы i в последовательности \bold{x}. Период можно определить по формуле

m\approx\frac{k_p-k_r}{I_c(\bold{x})-k_r+\frac{k_p-I_c(\bold{x})}{L}}

где k_r=1/A, k_p=\sum_{i=1}^{A}p_i^2,~p_i - частота появления буквы i в естественном языке.


Система Orphus

Комментарии (показать)