Основы шифрованияРефераты >> Криптология >> Основы шифрования
Число перестановок из (0,1, .,N-1) равно n!=1*2* .*(N-1)*N. Введем обозначение s для взаимно-однозначного отображения (гомоморфизма) набора S={s0,s1, .,sN-1}, состоящего из n элементов, на себя.
s: S ® S
s: si ® ss(i), 0 £ i < n
Будем говорить, что в этом смысле s является перестановкой элементов S. И, наоборот, автоморфизм S соответствует перестановке целых чисел (0,1,2, , n-1).
Криптографическим преобразованием T для алфавита Zm называется последовательность автоморфизмов: T={T(n):1£n<¥}
T(n): Zm,n®Zm,n, 1£n<¥
Каждое T(n) является, таким образом, перестановкой n-грамм из Zm,n.
Поскольку T(i) и T(j) могут быть определены независимо при i¹j, число криптографических преобразований исходного текста размерности n равно (mn)![1][1]. Оно возрастает непропорционально при увеличении m и n: так, при m=33 и n=2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.
Практическая реализация криптографических систем требует, чтобы преобразования {Tk: kÎK} были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).
1.2. Системы подстановок
Определение Подстановкой p на алфавите Zm называется автоморфизм Zm, при котором буквы исходного текста t замещены буквами шифрованного текста p(t):
Zm à Zm; p: t à p(t).
Набор всех подстановок называется симметрической группой Zm è будет в дальнейшем обозначаться как SYM(Zm).
Утверждение SYM(Zm) c операцией произведения является группой, т.е. операцией, обладающей следующими свойствами:
1.1.Замкнутость: произведение подстановок p1p2 является подстановкой:
p: tàp1(p2(t)).
2.2.Ассоциативность: результат произведения p1p2p3 не зависит от порядка расстановки скобок:
(p1p2)p3=p1(p2p3)
3.3.Существование нейтрального элемента: постановка i, определяемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Zm) по операции умножения: ip=pi для "pÎSYM(Zm).
4.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) шифрованный и соответствующий исходный текст или