Сис­те­мы под­ста­но­вок

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

Z_m à Z_m; p: t à p(t).

Набор всех подстановок называется симметрической группой Z_m è будет в дальнейшем обозначаться как SYM(Z_m).

Утверждение SYM(Z_m) c операцией произведения является группой, т.е. операцией, обладающей следующими свойствами:

Замкнутость: произведение подстановок p₁p₂ является подста­новкой:

p: tàp₁(p₂(t)).

Ассоциативность: результат произведения p₁p₂p₃ не зависит от порядка расстановки скобок:

(p₁p₂)p₃=p₁(p₂p₃)

Существование нейтрального элемента: постановка i, опре­деляемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Z_m) по операции умножения: ip=pi для "pÎSYM(Z_m).

Существование обратного: для любой подстановки p существует единственная обратная подстановка p^-1, удовлетворя­ющая условию

pp^‑1=p^‑1p=i.

Число возможных подстановок в симметрической группе Z_m называется порядком SYM(Z_m) и равно m!.

Определение. Ключом подстановки k для Z_m называется последовательность элементов симметрической группы Z_m:

k =(p ₀, p ₁,..., p _n-1,...), p _nÎSYM(Z_m), 0£n<¥

Подстановка, определяемая ключом k, является крипто­гра­фи­ческим преобразованием T _k, при помощи которого осуществляется преоб­разование n -граммы исходного текста (x₀,x₁,..,x_n-1) в n -грамму шифрованного текста (y₀,y₁,...,y_n-1):

y_i= p (x_i), 0£i<n

где n – произвольное (n=1,2,..). T _k называется моноалфавитной под­ста­новкой, если p неизменно при любом i, i=0,1,..., в противном случае T _k называется многоалфавитной подстановкой.

Примечание. К наиболее существенным особенностям подста­новки T _k относятся следующие:

1. Исходный текст шифруется посимвольно. Шифрования n -граммы (x₀,x₁,..,x_n-1) и ее префикса (x₀,x₁,..,x _{s -1}) связаны соотношениями

T _k (x₀,x₁,..,x_n-1)=(y₀,y₁,...,y_n-1)

T _k (x₀,x₁,..,x _{s -1})=(y₀,y₁,...,y _{s -1})

2. Буква шифрованного текста y_i является функцией только i-й компоненты ключа p_i и i-й буквы исходного текста x _i.