Формальные модели шифров

Для того чтобы иметь возможность доказывать в крипто­графии точные результаты, нужны математические модели основных исследуемых объектов, к которым относятся в пер­вую очередь шифр и открытый текст. Введем сначала алгеб­раическую модель шифра (шифрсистемы), предложенную К.Шенноном. С моделями открытых тек­стов мы познакомимся ниже.

Как мы уже знаем, криптография защищает информацию с помощью шифрования – процедуры, использующей некое обратимое преобразование. При этом преобразование откры­того текста в шифрованный называется зашифрованием, а обратный процесс – расшифрованием. Шифрование предполагает наличие множества обратимых преобразований. Вы­бор преобразования из указанного множества для зашифро­вания данного сообщения осуществляется с помощью ключа. Имеется однозначное соответствие между множеством клю­чей и множеством преобразований.

Выбор ключа естественным образом определяет функ­цию (вообще говоря, многозначную), отображающую множе­ство возможных открытых текстов в множество возможных шифрованных текстов. Способ вычисления значения этой функции для произвольного аргумента будем называть пра­вилом зашифрования. Выбранный ключ будем называть клю­чом зашифрования. Требование однозначности расшифрова­ния определяет обратную функцию, отображающую множе­ство возможных (при выбранном ключе) шифрованных тек­стов в множество возможных открытых текстов. Способ вы­числения значения этой функции для произвольного аргумен­та будем называть правилом расшифрования. Ключ, опреде­ляющий выбор правила расшифрования, будем называть клю­чом расшифрования.

Формализуем сказанное.

Пусть X,K,Y – конечные множества возможных от­крытых текстов, ключей и шифрованных текстов соответст­венно; Е_k: Х —> Y – правило зашифрования на ключе k Î К. Множество {Е_k : k Î К} обозначим через Е, а мно­жество {Е_k(х): хÎX}– через Е_k(X). Пусть D_k :Е_k (X) —> Х – правило расшифрования на ключе k Î К, и D – множество {D_k : k Î K}.

Здесь и далее мы будем предполагать, что если k Î К представляется в виде k=(k_kз, k_kр), где k_з – ключ зашифро­вания, a k_р – ключ расшифрования (причем k_з¹k_р), то Е_k понимается как функция Е_kз , a D_k – как функция D_kр.

Определение 1. Шифром (шифрсистемой) назовем со­вокупность

å_А=(X,K,Y,E,D)

введенных множеств, для которых выполняются следующие свойства:

1) для любых х Î Х и k Î К выполняется равенство

D_k (Е_k (х)) = х;

2)Y= È Е_k (X).

kÎK

Неформально, шифр – это совокупность множеств воз­можных открытых текстов (то, что шифруется), возможных ключей (то, с помощью чего шифруется), возможных шифр-текстов (то, во что шифруется), правил зашифрования и правил расшифрования.

Отметим, что условие 1) отвечает требованию однознач­ности расшифрования. Условие 2) означает, что любой эле­мент у Î Y может быть представлен в виде Е_k(х) для под­ходящих элементов х Î Х и k Î К . Отметим также, что в общем случае утверждение "для любых k Î К и у Î Е_k(X) выполняется равенство E_k(D_k(y)) = у" является неверным.

Легко проверить, что из условия 1) следует свойство инъективности функции Е_k. Другими словами, если х₁, х₂ Î Х , причем х₁ ¹ х₂, то при любом k Î К выполняется неравен­ство Е_k (х₁) ¹Е_k (х₂).

По сути дела определение 1 вводит математическую мо­дель, отражающую основные свойства реальных шифров. В силу этого мы будем отождествлять реальный шифр с его мо­делью å_А, которую будем назвать алгебраической моделью шифра. Для подавляющего большинства известных шифров несложно составить такую модель, как это будет видно из дальнейшего.

Введем теперь вероятностную модель шифра. Следуя К. Шеннону, определим априорные распределения вероятностей Р(Х), Р(К) на множествах Х и К соответст­венно. Тем самым для любого х Î Х определена вероятность р_Х(х) Î Р(Х) и для любого k Î К – вероятность р_К(k) Î Р(К), причем выполняются равенства

и

В тех случаях, когда нам требуется знание распределений Р(Х) и Р(К), мы будем пользоваться вероятностной моде­лью å_В, состоящей из пяти множеств, связанных условиями 1) и 2) определения 1, и двух вероятностных распределений:

å_В = (X, К, Y, Е, D, Р(Х), Р(К)).

Забегая вперед, отметим, что вероятностные характери­стики шифров используются лишь в криптоанализе – разделе криптографии, посвященном решению задач вскрытия (или взлома) шифров.

В большинстве случаев множества Х и Y представляют собой объединения декартовых степеней некоторых мно­жеств А и В соответственно, так что для некоторых нату­ральных L и L₁,

Множества А и В называют соответственно алфавитом открытого текста и алфавитом шифрованного текста. Другими словами, открытые и шифрованные тексты записы­ваются привычным образом в виде последовательностей букв.

Введем шифр простой замены в алфавите А.

Определение 2. Пусть K Í S(A), где S(A) – симметрическая

группа подстановок множества А. Для любого ключа kÎK, открытого текста х=(х₁,...,х_m) и шифрованного текста у =(у₁,..., у_m) прави­ла зашифрования и расшифрования шифра простой замены в алфавите А определяются формулами:

Е_k(х)= (k(х₁),...,k(х_m)),

D_k(y)= (k ^-1(у₁),..., k ^-1(у_m)),

где k ^-1 – подстановка, обратная к k.

В более общей ситуации для шифра простой замены

причем |А|=|В|, а К представляет собой множество биекций множества А на множество В. Правила зашифрования и расшифрования определяются для

k Î К, х Î X, у Î Y (и обратной к k биекции k ^-1) формула­ми (1).

Определим еще один шифр, называемый шифром пере­становки.

Определение 3. Пусть Х = Y = А^L и пусть К Í S_L, где S_L – симметрическая группа подстановок множества {l,2,...,L}. Для любого ключа k, открытого текста х=(х₁,...,х_L) и шифрованного текста у=(у₁,...,у_L) пра­вила зашифрования и расшифрования шифра перестановки определяются формулами:

Е_k(х)= (х_k(1)),...,х_k(L))),

D_k(y)= (у_k-1₍₁₎),...,у_k-1_(L))),

где k ^-1 – подстановка, обратная к k.

Шифры, введенные определениями 2 и 3, являются пред­ставителями двух наиболее важных классов симметричных шифров, а именно шифров замены и шифров перестановки, которые будут подробно рассматриваться ниже. Другими симметричными шифрами являются композиции (или после­довательные применения) некоторых шифров замены и шиф­ров перестановки.

Приведем пример асимметричного шифра. В следующем определении шифра RSA мы будем пользо­ваться общепринятыми в алгебре терминологией и обозначе­ниями.

Определение 4. Пусть п = pq, где р и q – простые числа. Пусть Х = Y = Z_n – кольцо вычетов по модулю п. Положим

К= {(п,р, q, а, b): а,b Î Z_{n ,} п =pq, ab º 1(modj(n))},

где j –функция Эйлера. Представим ключ k Î К в виде k=(k_з,k_р), где k_з=(n,b) и k_р=(n,p,q,a) –ключи за­шифрования и расшифрования соответственно. Правила зашифрования и расшифрования шифра RSA определим для

х Î Х и у Î Y формулами:

Е_kз(х) = х^b mod п, D_kр (у) = у^а mod п. (2)

Аббревиатура RSA определяется начальными буквами фамилий создателей этого шифра – Rivest, Shamir, Adleman. Корректность формул (2) следует из малой теоремы Ферма.

Введенные определения и термины не исчерпывают пол­ный перечень необходимых нам понятий, которые будут вво­диться далее по необходимости.