Подстановка Цезаря.
Методы защиты электронной информации
Определение. Ключом подстановки k для Zm называется последовательность элементов симметрической группы Zm: Буква шифрованного текста yi является функцией только i-й компоненты ключа pi и i-й буквы исходного текста xi. Например, «ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ» посредством подстановки C3 преобразуется в «еюыолхиврсеюивцнгкгрлб». Набор всех подстановок называется симметрической группой Zm и будет… Читать ещё >
Подстановка Цезаря. Методы защиты электронной информации (реферат, курсовая, диплом, контрольная)
Перестановкой набора целых чисел (0,1,…, N-1) называется его переупорядочение. Для того чтобы показать, что целое i перемещено из позиции i в позицию (i), где 0 (i) < n, будем использовать запись.
=((0), (1),…, (N-1)).
??? ??? ?? (0,1,…, N-1) ??? n≠1*2*…*(N-1)*N. ??? ??? ??? ??? ??? (???) ??? S={s0,s1, …, sN-1}, ??? ?? n ???, ?? …
: S S.
: si s (i), 0 i < n.
Будем говорить, что в этом смысле является перестановкой элементов S. И, наоборот, автоморфизм S соответствует перестановке целых чисел (0,1,2,., n-1).
Криптографическим преобразованием T для алфавита Zm называется последовательность автоморфизмов:
T={T (n):1n<}.
T (n): Zm, nZm, n, 1n<
Каждое T (n) является, таким образом, перестановкой n-грамм из Zm, n.
Поскольку T (i) и T (j) могут быть определены независимо при ij, число криптографических преобразований исходного текста размерности n равно (mn)!. Оно возрастает непропорционально при увеличении m и n: так, при m=33 и n=2 число различных криптографических преобразований равно 1089! Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.
Практическая реализация криптографических систем требует, чтобы преобразования {Tk: kK} были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).
Определение. Подстановкой на алфавите Zm называется автоморфизм Zm, при котором буквы исходного текста t замещены буквами шифрованного текста (t):
Zm Zm;: t (t).
Набор всех подстановок называется симметрической группой Zm и будет в дальнейшем обозначаться как SYM (Zm).
Утверждение. SYM (Zm) c операцией произведения является группой, т. е. операцией, обладающей следующими свойствами:
1. Замкнутость: произведение подстановок 12 является подстановкой:
: t1(2(t)).
- 2. Ассоциативность: результат произведения 123 не зависит от порядка расстановки скобок:
- (12)3=1(23)
- 3. Существование нейтрального элемента: постановка i, определяемая как i (t)=t, 0t
i=i.
SYM (Zm).
4. Существование обратного: для любой подстановки существует единственная обратная подстановка -1, удовлетворяющая условию:
_1=_1=i.
Число возможных подстановок в симметрической группе Zm называется порядком SYM (Zm) и равно m! .
Определение. Ключом подстановки k для Zm называется последовательность элементов симметрической группы Zm:
k=(p0,p1,…, pn-1,…), pnSYM (Zm), 0n<
Подстановка, определяемая ключом k, является криптографическим преобразованием Tk, при помощи которого осуществляется преобразование n-граммы исходного текста (x0, x1 ,., xn-1) в n-грамму шифрованного текста (y0, y1 ,…, yn-1):
yi=p (xi), 0i.
где 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.
Подстановка Цезаря является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок.
Определение. Подмножество Cm={Ck: 0k.
Ck: j (j+k) (mod m), 0k < m,.
CkCj=CjCk=Cj+k.
Ck-1=Cm-k.
Умножение коммутативно, C0 — идентичная подстановка, где 0.
Подстановка определяется по таблице замещения, содержащей пары соответствующих букв «исходный текст — шифрованный текст». Для C3 подстановки приведены в Табл. 1. Стрелка () означает, что буква исходного текста (слева) шифруется при помощи C3 в букву шифрованного текста (справа).
Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1 ,., xn-1) в n_грамму шифрованного текста (y0, y1 ,…, yn-1) в соответствии с правилом.
yi=Ck (xi), 0i.
Например, «ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ» посредством подстановки C3 преобразуется в «еюыолхиврсеюивцнгкгрлб».
Таблица 1.
Аг. | Йм. | Тх. | Ыю. |
Бд. | Кн. | Уц. | Ья. |
Ве. | Ло. | Фч. | Э_. |
Гж. | Мп. | Хш. | Юа. |
Дз. | Нр | Цщ. | Яб. |
Еи. | Ос. | Чъ. | _в. |
Жй. | Пт. | Шы. | |
Зк. | Ру. | Щь. | |
Ил. | Сф. | Ъэ. |
При своей несложности система легко уязвима. Если злоумышленник имеет:
- 1) шифрованный и соответствующий исходный текст или
- 2) шифрованный текст выбранного злоумышленником исходного текста,
то определение ключа и дешифрование исходного текста тривиальны.
Более эффективны обобщения подстановки Цезаря — шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.