Криптосистемы
Страница 3
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.
1.3. Подстановка Цезаря
Подстановка Цезаря является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок.
Определение. Подмножество Cm={Ck: 0£k<m} симметрической группы SYM(Zm), содержащее m подстановок
Ck: j®(j+k) (mod m), 0£k < m,
называется подстановкой Цезаря.
Умножение коммутативно, CkCj=CjCk=Cj+k, C0 – идентичная подстановка, а обратной к Cк является Ck-1=Cm-k, где 0<k<m. Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки C3.
Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”. Для C3 подстановки приведены в Табл. 1. Стрелка (à) означает, что буква исходного текста (слева) шифруется при помощи C3 в букву шифрованного текста (справа).
Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1 , ,xn-1) в n‑грамму шифрованного текста (y0 ,y1 , .,yn-1) в соответствии с правилом
yi=Ck(xi), 0£i<n.
Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C3 преобразуется в еюыолхиврсеюивцнгкгрлб.
Аàг
Йàм
Тàх
Ыàю
Бàд
Кàн
Уàц
Ьàя
Вàе
Лàо
Фàч
Эà_
Гàж
Мàп
Хàш
Юàа
Дàз
Нàр
Цàщ
Яàб
Еàи
Оàс
Чàъ
_àв
Жàй
Пàт
Шàы
Зàк
Рàу
Щàь
Иàл
Сàф
Ъàэ
Таблица 1.1: Применение подстановки Цезвря.
При своей несложности система легко уязвима. Если злоумышленник имеет
1) шифрованный и соответствующий исходный текст или
2) шифрованный текст выбранного злоумышленником исходного текста,
то определение ключа и дешифрование исходного текста тривиальны.
Более эффективны обобщения подстановки Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм[2] (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.
1.4.Многоалфавитные системы. Системы одноразового использования
Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных.
Многоалфавитная подстановка определяется ключом p=(p1, p2, .), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением. Пусть {Ki: 0£i<n} – независимые случайные переменные с одинаковым распределением вероятностей,
принимающие значения на множестве Zm
Pкл{(K0, K1, ., Kn-1)=(k0, k1, ., kn-1)}=(1/m)n
Система одноразового использования преобразует исходный текст
X=(X0, x1, ., xn-1)
в шифрованный текст
Y=(Y0, y1, ., yn-1)
при помощи подстановки Цезаря
Yi=CKi(xi)=(Ki+Xi) (mod m) i=0 .n-1 (1)
Для такой системы подстановки используют также термин “одноразовая лента” и “одноразовый блокнот”. Пространство ключей К системы одноразовой подстановки является вектором рангов (K0, K1, ., Kn-1) и содержит mn точек.
Рассмотрим небольшой пример шифрования с бесконечным ключом. В качестве ключа примем текст
“БЕСКОНЕЧНЫЙ_КЛЮЧ ”.
Зашифруем с его помощью текст “ШИФР_НЕРАСКРЫВАЕМ”. Шифрование оформим в таблицу:
ШИФРУЕМЫЙ_ТЕКСТ
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
0
18
17
17
22
26
27
4
20
28
15