Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
74
Основные понятия
Пусть X9K9Y — конечные множества возможных открытых текстов, ключей и шифрованных текстов соответственно; Ejc : X Y — правило зашифрования на ключе
к є К . Множество [Eji : к є К\ обозначим через E, а множество {Ек(х) : х є X] — через Ek (X). Пусть Dk : Ek(X) —> X — правило расшифрования на ключе k є К 9 и D — множество (Dk :к є К}.
Здесь и далее мы будем предполагать, что если к є К представляется в виде к = (к3, А:р ), где к3 — ключ зашифрования, а кр— ключ расшифрования (причем к3 Ф &р), то Ek понимается как функция Ek^ ,a Dk — как функция Dk .
Определение 1. Шифром (шифрсистемой) назовем совокупность
Sa =(X9K9Y9E9D) введенных множеств, для которых выполняются следующие свойства:
1) для любых х є X и к є К выполняется равенство Dk(Ek(X)) = X;
2)Y=\jE,(X).
кеК
Неформально, шифр — это совокупность множеств возможных открытых текстов (то, что шифруется), возможных ключей (то, с помощью чего шифруется), возможных шифр-текстов (то, во что шифруется), правил зашифрования и правил расшифрования.
Отметим, что условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент у є Y может быть представлен в виде Ек(х) для подходящих элементов х є X и к є К . Отметим также, что в
75
І лава 2
общем случае утверждение “для любых к є К и у є Ek (X) выполняется равенство Ek (Dk (у)) = у ” является неверным.
Легко проверить, что из условия 1) следует свойство инъ-ективности функции Ek. Другими словами, если X15X2 є J,
причем X1 Ф X2, то при любом к є К выполняется неравен-
ство ?*(*,)* Ek(X2).
По сути дела определение 1 вводит математическую модель, отражающую основные свойства реальных шифров. В силу этого мы будем отождествлять реальный шифр с его моделью Za , которую будем назвать алгебраической моделью шифра. Для подавляющего большинства известных шифров несложно составить такую модель, как это будет видно из дальнейшего.
Введем теперь вероятностную модель шифра. Следуя К. Шеннону [ШенбЗ], определим априорные распределения вероятностей P(X)5 Р(^) на множествах X и К соответственно. Тем самым для любого х є X определена вероятность рх (х) є P(X) и для любого к є К — вероятность рК (к) є P(AT) , причем выполняются равенства
YiPxW=1 и
дгєЛ' кеК
В тех случаях, когда нам требуется знание распределений P(X) и P(AT), мы будем пользоваться вероятностной моделью , состоящей из пяти множеств, связанных условиями 1) и 2) определения 1, и двух вероятностных распределений:
ZB=(X,K,Y,E,D,T>(X),P(K)).
Забегая вперед, отметим, что вероятностные характеристики шифров используются лишь в криптоанализе — разде-
76
Основные понятия
ле криптографии, посвященном решению задач вскрытия (или взлома) шифров.
В большинстве случаев множества X и Y представляют собой объединения декартовых степеней некоторых множеств А и В соответственно, так что для некоторых натуральных L и Lx
X = (jA', Y = \jB'.
/ = I / = 1
Множества А и В называют соответственно алфавитом открытого текста и алфавитом шифрованного текста. Другими словами, открытые и шифрованные тексты записываются привычным образом в виде последовательностей букв.
Введем шифр простой замены в алфавите А .
L
Определение 2. Пусть X = Y = \^ A1, К с: S(A)f где
/=і
S(A) — симметрическая группа подстановок множества А. Для любого ключа к є К, открытого текста х = (X19-^9X1) и шифрованного текста J = (J1V9Jz) правила зашифрования и расшифрования шифра простой замены в алфавите А определяются формулами:
Ek(x) = (k(xx),...,k(xi)),
где k~x —подстановка, обратная к к.
В более общей ситуации для шифра простой замены
L L
X = \^Al, Y = \^В1, причем |і4|=|і?|, а К представляет
/=і і=і
собой множество биекций множества А на множество В. Правила зашифрования и расшифрования определяются для
77
Ілава 2
к є К, X є X, у gY (и обратной к к биекции к 1) формулами (1).
Определим еще один шифр, называемый шифром перестановки.
Определение 3. Пусть X = Y = A1 и пусть К CiSl, где S1 — симметрическая группа подстановок множества {1,2,...,4 Для любого ключа к, открытого текста x = (xlv..,xz) и шифрованного текста у = (У\9~-9Уі) правша зашифрования и расшифрования шифра перестановки определяются формулами:
Ек(х) = (хк(1)>-,**(?)), AtOO = Ол-і(1),-,^-і(і)Х
где к 1 —подстановка, обратная к к.
Шифры, введенные определениями 2 и 3, являются представителями двух наиболее важных классов симметричных шифров, а именно шифров замены и шифров перестановки, которые будут подробно рассматриваться ниже. Другими симметричными шифрами являются композиции (или последовательные применения) некоторых шифров замены и шифров перестановки.
Приведем пример асимметричного шифра.
В следующем определении шифра RSA мы будем пользоваться общепринятыми в алгебре терминологией и обозначениями (см. Приложение 3).
Определение 4. Пусть п = pq, где р и q — простые числа. Пусть X = Y = Zn — кольцо вычетов по модулю п. Положим
K = {(п,р, q, а, Ь): а,Ь є Zn, п =pq, ab з l (mod$«))},
