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

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

Определение. Подстановкой на алфавите 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)ⁿ