Моно- и многоалфавитные подстановки

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

Определение. Подстановкой на алфавите Z_nназывается отображение, при котором буквы исходного текста t замещены буквами шифрованного текста (t):

Z_n Z_n; : tt(t).

 

Кратко рассмотренный ранее шифр Цезаря, является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок.

Определение. Подмножество C_n={C_k: 0≤k<n}, содержащее n подстановок C_k: j→(j+k) (mod n), 0≤k < n, называется подстановкой Цезаря.

Два целых числа n и n' называются сравнимыми по модулю m, если при делении на m они дают одинаковые остатки. Пишут n≡n'(m) или n≡n'(mod m), а число m называют модулем сравнения.

Таким образом, получается разбиение Z на классы чисел, сравнимых между собой по mod m и называемых классами вычетов по mod m.

Каждый класс вычетов имеет вид: {r}m=r+mZ={r+mk | kZ},

Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки C₃.

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”.

Для C₃подстановки приведены в Табл. 2. Т.к 1=4 (mod 3), 2=5 (mod 3) …Стрелка () означает, что буква исходного текста (слева) шифруется при помощи C₃в букву шифрованного текста (справа).

 

Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая исходный текст (x₀,x₁,..,x_n-1) в шифрованный текст (y₀,y₁,...,y_n-1) в соответствии с правилом: y_i=C_k(x_i), 0≤i<n.

Пример 59.Сообщение ИЗУЧАЙТЕ_КРИПТОГРАФИЮ посредством подстановки C₃преобразуется в лкцъгмхивнултсжугчла. ♦

При своей несложности система легко уязвима. Если злоумышленник имеет:

1) шифрованный и соответствующий исходный текст или

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

Более эффективны обобщения подстановки Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

Слабая криптостойкость моноалфавитных подстановок преодолевается с применением многоалфавитных подстановок, которые определяются ключом =(₁, ₂, ...), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением.

Пусть {K_i: 0≤i<n} - независимые случайные переменные с одинаковым распределением вероятностей, принимающие значения на множестве Z_m:

P{(K₀, K₁, ..., K_n-1)=(k₀, k₁, ..., k_n-1)}=(1/m)ⁿ

 

Система одноразового использования преобразует исходный текст: X=(x₀, x₁, ..., x_n-1) в шифрованный текст: Y=(y₀, y₁, ..., y_n-1)

при помощи подстановки Цезаря: y_i=C_Ki(x_i)=(K_i+x_i) (mod m) i=0,1,…n-1.

Для такой системы подстановки используют также термин “одноразовая лента” и “одноразовый блокнот”. Пространство ключей К системы одноразовой подстановки является вектором ранга (K₀, K₁,...,K_n-1) и содержит mn точек.

 

 

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