Введение в криптографию

       

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


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

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

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

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

1.Замкнутость: произведение подстановок p1p2 является подста­новкой:

p: tàp1(p2(t)).

2.Ассоциативность: результат произведения p1p2p3 не зависит от порядка расстановки скобок:

(p1p2)p3=p1(p2p3)

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

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

pp?1=p?1p=i.

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

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

k=(p0,p1,...,pn-1,...), pnÎSYM(Zm), 0£n<¥

Подстановка, определяемая ключом k, является крипто­гра­фи­ческим преобразованием Tk, при помощи которого осуществляется преоб­разование n-граммы исходного текста (x0 ,x1 ,..,xn-1) в n-грамму шифрованного текста (y0 ,y1 ,...,yn-1):

yi=p(xi),   0£i<n

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

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

1. Исходный текст шифруется посимвольно. Шифрования n-граммы (x0 ,x1 ,..,xn-1) и ее префикса (x0 ,x1 ,..,xs-1) связаны соотношениями

Tk(x0 ,x1 ,..,xn-1)=(y0 ,y1 ,...,yn-1)

Tk(x0 ,x1 ,..,xs-1)=(y0 ,y1 ,...,ys-1)

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



Содержание раздела