Генерация ключей защиты. Подбор кода шифрования информации

Криптографическая система Эль-Гамаля

Данная асимметричная криптосистема носит имя ее изобретателя Т. Эль-Гамаля и основана на схеме формирования открытых ключей, предложенной учеными Диффи и Хеллманом. Криптографическая система Эль-Гамаля является альтернативой системе RSA и при равном размере ключей обеспечивает примерно такую же криптостойкость.

В качестве односторонней функции в криптосистеме Эль-Гамаля используется предложенная Диффи и Хеллманом функция дискретного возведения в степень f(x) = a^x mod p, где х - целое положительное число, а р - простое целое положительное число. Даже при очень больших числах р (например, когда их двоичное представление занимает 1024 бит) для данного х легко вычислить значение этой функции.

Обратной к функции дискретного возведения в степень является функция F'(y), которая ставит в соответствие заданному значению f такое значение х, для которого выполняется условие f= a^x mod р.

Задача нахождения такого х называется задачей дискретного логарифмирования (нахождения дискретных логарифмов) и является чрезвычайно сложной. Сложность вычисления дискретных логарифмов существенно повышается, когда число р-1 содержит один большой и простой множитель, например, когда оно представимо в виде p-1=2р', где р'- простое число. При этом условии трудоемкость нахождения дискретного логарифма равна примерно Öр умножений по модулю р. Решение такой задачи является вычислительно неосуществимым при большом размере числа р (например, от 512 бит), а следовательно при указанных условиях, накладываемых на выбор чисел р и а, функция дискретного возведения в степень является односторонней.

В общем случае задача дискретного логарифмирования по трудности решения подобна задаче разложения больших чисел на сомножители, что говорит о примерно одинаковой криптостойкости систем RSA и Эль-Гамаля. Однако следует отметить, что по оценкам математиков, задача разложения произвольного числа длиной в 512 бит на простые множители проще задачи дискретного логарифмирования такого же числа. Поэтому при точном сравнении криптостойкость системы Эль-Гамаля оказывается выше криптостойкости системы RSA.

В отличие от RSA, в криптосистеме Эль-Гамаля способы криптографического закрытия информации и формирования подписи сообщений существенно отличаются друг от друга. Поэтому рассмот­рим эти способы отдельно.

Схема криптографического закрытия небольшого объема передаваемой информации в криптосистеме Эль-Гамаля реализуется довольно просто.

Каждым пользователем выбирается большое простое число р, такое, что разложение числа р-1 содержит по крайней мере один большой простой множитель, а также число а такое, что 0<а<р-1. (Причем число а должно быть выбрано таким, чтобы величина aⁱ mod p принимала в некоторой очередности по одному разу каждое значение из множества чисел {1,2,3,..., р-1 } при i=1,2,3,...,p-1. Такое число а называется первообразным корнем в поле вычетов по модулю р.)

Далее генерируется случайный секретный ключ х (0<х<p) и по закрытому ключу определяется число у=а^x mod p. В качестве открытого ключа принимается совокупность чисел у, а и р.

Пусть необходимо зашифровать информационный блок, представляющий собой симметричный ключ шифрования. Этот блок должен иметь длину, меньшую длины простого модуля р, т.e. число М должно удовлетворять соотношению: 1<=М<р. На практике модуль р выбирается таким, что он превышает размер симметричного ключа шифрования.

Процесс зашифровывания информационного блока М по ключу {у,а,р} выполняется в соответствии со следующим алгоритмом.

1. Сгенерировать случайное число k (0<k<p-1), взаимно простое с (р-1) т.е. НОД(k,р-1)=1.

2. Вычислить: r:=y^k mod p.

3. Вычислить: c₁:= a^k mod p.

4. Вычислить: c₂:=rÅМ, где Å - операция сложения по модулю 2 (операция исключающего ИЛИ).

5. Сформировать криптограмму информационного блока М, состоящую из элементов с₁ и с₂: С={с₁,с₂ }. Изприведенного алгоритма становится понятно, что для расшифровки информационного элемента с₂ необходимо получить число r. С учетом того, что rºy^k mod р, yºa^x mod p, a с₁ º a^k mod р, получаем: r=y^k mod р = а^xk mod р = (a^k)^x mod р = с₁^x mod р.

Соответственно расшифровка криптограммы С выполняется на основе закрытого ключа х в следующей последовательности.

1. Вычислить: r:= c₁^x mod р.

2. Вычислить: М:= c₂År.

При зашифровывании информационного блока М на четвертом шаге алгоритма вместо операции сложения по модулю 2 может использоваться операция умножения: С₂:=rМ. Тогда при расшифровывании криптограммы С на втором шаге алгоритма операцию сложения по модулю 2 следует заменить на операцию деления: M:=c₂/r.

Система цифровой подписи Эль-Гамаля стала национальным стандартом цифровой подписи в США. Кроме того, данная система положена в основу отечественного стандарта цифровой подписи ГОСТ Р 34.10-94.

Все соглашения и требования, касающиеся закрытого и открытого ключей остаются теми же, что и в случае криптографического закрытия информации.

Пусть имеется большое простое число р, такое, что разложе числа р-1 содержит по крайней мере один большой простой множитель, и число а такое, что 0<а<р-1. (Число а нужно выбрать таким, чтобы оно являлось первообразным корнем в поле вычетов по модулю р. Теория чисел дает несложный тест для проверки этого условия).

Каждым пользователем в качестве закрытого ключа принимается случайное число х (0<х<р), а в качестве открытого - совокупность чисел у, а и р. Число у определяется по закрытому ключу как y=a^x mod p.

Cхема формирования и проверки подписи состоит в следующем. Информационный блок М, на основе которого следует сформировать цифровую подпись, должен иметь длину меньше простого модуля р, т.е. число М должно удовлетворять соотношению: 1<=М<р. На практикемодуль р выбирается таким, что он превышает размер эталонной характеристики сообщения, в качестве которой выступает информационный блок М.

Подписью абонента А, сформированной на основе закрытого ключа у и эталонной характеристики М, служит пара чисел r и s, (0<r<p-1 и 0<=s<p-1), которые удовлетворяют соотношению: a^M= y^rr^s mod p, т.е. а^M и y^r r^s дают одинаковый остаток при целочисленном делении на р (другими словами, соотношение a^M =y^rr^s mod p истинно тогда и только тогда, когда а^M - y^rr^s делится на р).

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

Система цифровой подписи Эль-Гамаля основана на том, что только действительный владелец секретного ключа х может выра­ботать пару чисел (r,s), удовлетворяющую уравнению проверки под­писи. Используя значение х, абонент А вырабатывает подпись по следующему алгоритму:

1. Сгенерировать случайное число k (0<k<p-1), взаимно простое с (р-1), т.е. НОД(k,р-1)=1.

2. Вычислить: r:=a^k mod p.

3. Вычислить s из уравнения М=xr+ks mod (p-1).

4. Сформировать подпись как совокупность чисел r и s. Из теории чисел известно, что последнее уравнение имеет решение для s, если НОД(k,р-1)=1. С учетом этого уравнения, а также из равенств

y=a^x mod p и r=a^k mod р

получаем уравнение проверки подписи:

а^M = (a^x)^r (a^k)^s mod р = у^rr^s mod р.

Таким образом, подпись из совокупности чисел r и s формируется на основе эталонной характеристики М и закрытого ключа x, а проверяется с помощью открытого ключа {у,а,р} и текущей характеристики М' полученного сообщения путем проверки выполнения равенства:

A^M = y^rr^s mod p.

Данное равенство истинно тогда и только тогда, когда

(a^м- y^rr^s )mod p=0.

Нахождение пары чисел (r,s) без знания закрытого ключа вычислительно сложно. Различных подписей, соответствующих данному документу может быть чрезвычайно много (заметим, что k может иметь разные значения), но выработать правильную подпись может только владелец секретного ключа. Возможные подписи отличаются значением r, но для данного г найти соответствующее значение s без знания закрытого ключа практически невозможно. Для вычисления закрытого ключа по открытому необходимо решить задачу дискретного логарифмирования, которая является вычислительно сложной.

Особенностью схемы цифровой подписи Эль-Гамаля, как и особенностью метода шифрования по Эль-Гамалю, является генерация случайного числа k.

Открытое распределение ключей

На основе методов шифрования с открытым ключом легко решить задачу выработки общего секретного ключа для сеанса связи любой пары пользователей информационной системы. Еще в 1976 году Диффи и Хеллман предложили для этого протокол открытого распределения ключей. Он подразумевает независимое генерирование каждым из пары связывающихся пользователей своего случайного числа, преобразование его посредством некоторой процедуры, обмен преобразованными числами по открытому каналу и вычисление общего секретного ключа на основе информации, полученной в процессе связи от партнера. Каждый такой ключ существует только в течение одного сеанса связи или даже части его.

Алгоритм открытого распределения ключей Диффи-Хеллмана выглядит так:

Пусть имеются два абонента открытой сети А и В, знающие пару открытых ключей P и D. Кроме того, у А есть секретный ключ Х из интервала (1, N), а у В есть секретный ключ Y из того же интервала.

Абонент А посылает В шифровку своего ключа z’=Dx MOD P, а абонент В посылает А шифровку своего ключа z’’=Dy MOD P.

После этого общий ключ z они вычисляют как z =z’y=z’’x.

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