Криптография
овательности, генерируемой на основе ключа.
Блочные шифры собой последовательность (с возможным повторением и
чередованием) основных методов преобразования, применяемую к блоку (части)
шифруемого текста. Блочные шифры на практике встречаются чаще, чем “чистые”
преобразования того или иного класса в силу их более высокой
криптостойкости. Российский и американский стандарты шифрования основаны
именно на этом классе шифров.
Перестановкой ( набора целых чисел (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):1(n<(}
T(n): Zm,n(Zm,n, 1(n<(
Каждое T(n) является, таким образом, перестановкой n-грамм из Zm,n.
Поскольку T(i) и T(j) могут быть определены независимо при i(j, число
криптографических преобразований исходного текста размерности n равно
(mn)![1]. Оно возрастает непропорционально при увеличении m и n: так, при
m=33 и n=2 число различных криптографических преобразований равно 1089!.
Отсюда следует, что потенциально существует большое число отображений
исходного текста в шифрованный.
Практическая реализация криптографических систем требует, чтобы
преобразования {Tk: k(K} были определены алгоритмами, зависящими от
относительно небольшого числа параметров (ключей).
1.2. Системы подстановок
Определение Подстановкой ( на алфавите Zm называется автоморфизм Zm,
при котором буквы исходного текста t замещены буквами шифрованного текста
((t):
Zm ( Zm; (: t ( ((t).
Набор всех подстановок называется симметрической группой Zm и будет в
дальнейшем обозначаться как SYM(Zm).
Утверждение SYM(Zm) c операцией произведения является группой, т.е.
операцией, обладающей следующими свойствами:
1. Замкнутость: произведение подстановок (1(2 является подстановкой:
(: t((1((2(t)).
1. Ассоциативность: результат произведения (1(2(3 не зависит от
порядка расстановки скобок:
((1(2)(3=(1((2(3)
1. Существование нейтрального элемента: постановка i, определяемая как
i(t)=t, 0(t<(
Подстановка, определяемая ключом k, является криптографическим
преобразованием Tk, при помощи которого осуществляется преобразование n-
граммы исходного текста (x0 ,x1 ,..,xn-1) в n-грамму шифрованного текста
(y0 ,y1 ,...,yn-1):
yi=p(xi), 0(i< m,
называется подстановкой Цезаря.
Умножение коммутативно, CkCj=CjCk=Cj+k, C0 – идентичная подстановка, а
обратной к Cк является Ck-1=Cm-k, где 0< ( .
Например, при r = ( и ключе пользователя 15 8 2 10 11 4 18 рабочий ключ
будет периодической последовательностью:
15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...
Определение. Подстановка Вижинера VIGk определяется как
VIGk : (x0, x1, ..., xn-1) ( (y0, y1, ..., yn-1) = (x0+k, x1+k,. ..,
xn-1+k).
Таким образом:
1) исходный текст x делится на r фрагментов
xi = (xi , xi+r , ..., xi+r(n-1)), 0 ( i < r;
2) i-й фрагмент исходного текста xi шифруется при помощи подстановки
Цезаря Ck :
(xi , xi+r , ..., xi+r(n-1)) ( (yi , yi+r , ..., yi+r(n-1)),
Вариант системы подстановок Вижинера при m=2 называется системой
Вернама (1917 г). В то время ключ k=(k0 ,k1 ,...,kк-1) записывался на
бумажной ленте. Каждая буква исходного переводилась с использованием кода
Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по
модулю 2). Старинный телетайп фирмы AT&T со считывающим устройством Вернама
и оборудованием для шифрования, использовался корпусом связи армии США.
Очень распространена плохая с точки зрения секретности практика
использовать слово или фразу в качестве ключа для того, чтобы k=(k0 ,k1
,...,kк-1) было легко запомнить. В ИС для обеспечения безопасности
информации это недопустимо. Для получения ключей должны использоваться
программные или аппаратные средства случайной генерации ключей.
Пример. Преобразование текста с помощью подстановки Вижинера (r=4)
Исходный текст (ИТ1):
НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ
Ключ: КЛЮЧ
Разобьем исходный текст на блоки по 4 символа:
НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ
и наложим на них ключ (используя таблицу Вижинера):
H+К=Ч, Е+Л=Р и т.д.
Получаем зашифрованный (ЗТ1)
| | скачать работу |
Криптография |