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

\.Замкнутость: произведение подстановок %i%2 является подстановкой:

7Г: 1711(712(0).

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

(711712)713=1(23)

Ъ.Существование нейтрального элемента: постановка i, определяемая как i(t)=t, 0<t<m, является нейтральным элементом SYM(Zm) по операции умножения: 17Г=7г1 для V7rGSYM(Zm).

А.Существование обратного: для любой подстановки 7Г существует единственная обратная подстановка 7Г\ удовлетворяющая усло-

7Г7Г=7Г7Г=1.

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

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

k=(po,pi,...,pn-i,-), Рп SYM(ZJ, 0<n<oo

Подстановка, определяемая ключом к, является криптографическим преобразованием Tk, при помощи которого осуществляется преобразование п-граммы исходного текста (хо ,xi ,.-,Xn-i) в л-грамму шифрованного текста (уо ,yi ,...,yn-i):

yi=/?(Xi), 0<i<n

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

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

1. Исходный текст шифруется посимвольно. Шифрования л-граммы (хо ,xi ,..,Xn-i) и ее префикса (хо ,xi ,..,X5-i) связаны соотношениями

T;t(xo ,xi ,..,Xn.i)=(yo ,yi ,...,yn-i)

T;t(xo ,xi ,..,x,.i)=(yo ,yi ,...,y.-i)

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

Подстановка Цезаря

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

Определение. Подмножество C={Ck- 0<A:<m} симметрической группы SYM(Zm), содержащее т подстановок

Cyfc: jG+) (mod m), Q<k < m,

называется подстановкой Цезаря. Умножение коммутативно, CkCj=CjCk=Cj+k, Со - идентичная подстановка, а обратной к Скявляется Ck=Cm-k, где 0<к<т. Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки Сз.

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

Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая л-грамму исходного текста (хо, Xi ,..,Xn-i) в л-грамму шифрованного текста (уо ,yi ,...,yn-i) в соответствии с правилом

yi=C;fc(Xi), 0<i<n.

Например, ВЫШЛИТЕ НОВЫЕ УКАЗАНИЯ посредством подстановки Сз преобразуется в еюыолхиврсеюивцнгкгрлб.

Таблица 1.

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

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

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

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

Многоалфавитные системы. Системы одноразового использования.

Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных.

Многоалфавитная подстановка определяется ключом т={Щ, 7Г2, "О? содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением.

Пусть {К]". 0<i<n} - независимые случайные переменные с одинаковым распределением вероятностей, принимающие значения на множестве Zm

РклКо, к,, „.i)=(fco, h, K.,)]={\lmf

Система одноразового использования преобразует исходный текст

, Xi, Xn-l)

В шифрованный текст

Y=(Yo, Ух, Упл)

при помощи подстановки Цезаря

Yi=Cfi(Xi)=(i+Xi) (mod т) i=0...n-l (1)

Для такой системы подстановки используют также термин "одноразовая лента" и "одноразовый блокнот". Пространство ключей К системы одноразовой подстановки является вектором рангов {Ко, Ki, Kn-i) и содержит т" точек.

Рассмотрим небольшой пример шифрования с бесконечным ключом. В качестве ключа примем текст

"БЕСКОНЕЧНБШКЛЮЧ....".

Зашифруем с его помощью текст "ШИФР НЕРАСКРБ1ВАЕМ". Шифрование оформим в таблицу:

ШИФРУЕМЫЙТЕКСТ 24 8 20 16 19 5 12 27 9 32 18 5 10 17 18

БЕСКОНЕЧНЫЙКЛЮЧ 1 5 17 10 14 13 5 23 13 27 9 32 10 11 30

ЩРДЪАТТССЦЪЫДФЬП 25 13 4 26 О 18 17 17 22 26 27 4 20 28 15

Исходный текст невозможно восстановить без ключа.

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

п-граммой называется последовательность из п символов алфавита.