Аффинная система подстановок Цезаря.

Символы алфавита Z_m можно не только складывать по модулю m, но и умножать по этому модулю. Применяя одновременно операции сложения и умножения по модулю m над элементами множества Z_m, можно получить систему подстановок, называемую аффинной системой подстановок Цезаря. Аффинная система – это одновременное сложение и умножение по mod m над элементами Z_m.

Е_a,b : Z_m ® Z_m

Е_a,b : t ® Е_a,b(t)

Е_a,b(t) = (at + b)mod m;

a, b – целые числа, причем 0 < a, b < m: НОД(a, m) = 1.

Здесь буква, соответствующая t, заменяется на букву, соответствующую (at + b)mod m

такое преобразование взаимно однозначно в том и только в том случае, когда числа a и m являются взаимно простыми.

Например, пусть m = 33, a = 5, b = 3. Тогда наименьший общий делитель НОД(5, 33) = 1, и мы получаем следующее соответствие между числовыми кодами букв:

t
5t+3
t
5t+3
t
5t+3

Преобразуя числа в буквы русского алфавита, получаем следующее соответствие для букв открытого текста и шифртекста:

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

Г

И

Н

Т

Ч

Ъ

_

Е

К

П

Ф

П

Ю

В

З

М

С

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Ъ

Э

Ю

Я

_

Ц

Ы

_

Д

Й

О

У

Ш

Э

А

Ж

Л

Р

Х

Ь

Я

Исходное сообщение:

МОСКОВСКИЙ_ИНСТИТУТ_СТАЛИ_И_СПЛАВОВ,

будет выглядеть следующим образом:

ЮЗЦФЗНЦФКПЯКВЦЫКЫ_ЫЯЦЫГПКЯКЯЦМПГНЗН.

Здесь ключ – это пара чисел a, b.

Криптосистема Хилла.

Алгебраический метод, обобщающий аффинную подстановку Цезаря

Е_a,b : Z_m ® Z_m,

E_a,b(t) = t® at + b(mod m)

для определения n-грамм, был сформулирован Лестером С. Хиллом.

Множество целых Z_m, для которого определены операции сложения, вычитания и умножения по модулю m, является примером кольца. Кольцо R представляет собой алгебраическую систему в которой определены операции сложения, вычитания и умножения пар элементов. Эта алгебраическая система обладает рядом свойств:

• элементы кольца R образуют коммутативную группу относительно операции сложения; кроме того, существуют единичный и обратный элементы относительно операции сложения,

• умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.

Мультипликативное обратное a^-1 элемента a кольца может существовать не всегда. Например, если модуль m = 26, то значе­ния 2^-1(mod 26) и 13^-1(mod 26) не могут существовать.

Если модуль m является простым числом р, то существует обратная величина любого ненулевого элемента t из Z_p (при m = р), поскольку значения

t (mod m), 2t (mod m), 3t (mod m), .... ,(p-1) t (mod m)

различаются, если 1 £ t £ p -1.

Множество Z_p, где р – простое число, является примером алгебраической системы, называемой конечным полем. Ненулевые элементы Z_p образуют мультипликативную группу.

Множество всех n-грамм х = (х₀, х,, х₂,.... x_n-1) с компонентами из кольца Z_m образует векторное пространство Z_m,n над кольцом Z_m. Каждая n-грамма х называется вектором. В векторном про­странстве Z_mn для векторов х определены операции сложения и вычитания по модулю n, а также скалярное умножение вектора на элемент t кольца Z_m . Сложение и скалярное умножение являются операциями, удовлетворяющими коммутативному, ассоциативному и дистрибутивному законам. Вектор х является линейной комбинацией векторов

{х⁽ⁱ⁾: 0 <i < L}, если

х = t₀x⁽⁰⁾ + t₁x⁽¹⁾ +... + t_L-1.,x^(L-¹⁾(mod m).

Линейное преобразование Т является отображением:

T : Z_m,n ® Z_m,n,, T : x ® y, y=T(x),

которое удовлетворяет условию линейности

T = (t´x + s´y)-t´Т(х) + s´Т(у) (mod m) для всех s, t в Z_m и х, у в Z_{m п}.

Линейное преобразование Т может быть представлено матрицей размером n´n вида

причем .

Базисом для векторного пространства является набор векторов из {х⁽ⁱ⁾ : 0 < i < L}, которые линейно независимы и порождают .Каждый базис для содержит n линейно независи­мых векторов Любой набор из n векторов, которые линейно независимы над является базисом.

Пусть является линейным преобразованием, описываемым матрицей, причем .

Если векторы {х⁽ⁱ⁾ 0 < i < n} линейно независимы над , тогда их образы {Т(х⁽ⁱ⁾) : 0 £ i < п} линейно независимы над только в том случае, если определитель матрицы , обозначаемый как det (Т), не делится на любое простое р, которое делит m. В этом случае преобразование называется обратимым (или невырожденным) линейным преобразованием, имеющим обратное преобразование , где l-единичная матрица. Кроме того, также является линейным преобразованием.

Например, когда m = 26 и матрица преобразования

,

то определитель этой матрицы

det(T) = 9 = 1(mod 2),

det(T) = 9 = 9{mod 13).

Поэтому существует обратное преобразование . Нетрудно убедиться, что

удовлетворяет соотношению .

Пусть является линейным преобразованием на с матрицей

Используем это преобразование для определения биграммной подстановки в английском алфавите {ABCDEFGH..XYZ}. Сначала разобьем n-грамму открытого текста на биграммы, причем выберем n кратным 2. Например, 12-грамма PAYMOREMONEY делится на шесть биграмм:

PA YM OR EM ON EY

Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:

.

Преобразование биграмм открытого текста в биграммы , шифртекста осуществляется в соответствии с уравнением

или

где и – вектор столбцов биграмм шифртекста и открытого текста соответственно.

Получаем

,

.

Заменяя в биграммах шифртекста числа на соответствующие буквы согласно таблицы, получаем 12-грамму шифртекста

ТЕ ЕЕ PJ WQ DP GY

Для расшифрования биграмм , шифртекста и восстановления биграмм открытого текста необходимо выполнить обратное преобразование согласно уравнению

В рассмотренном примере матрицы преобразования имели размер 2x2 и шифровались биграммы (пары) букв Хотя буква Е может быть зашифрована по-разному в различных парах исходного сообщения одна и та же пара, например ЕМ будет шифроваться всегда одинаково на протяжении всего исходного текста.

Задание на лабораторную работу

1. Используя алгоритм шифрования данных по системе Цезаря, написать программу шифрования и дешифрования произвольного набора символов на любом языке программирования

2. Используя алгоритм шифрования данных по криптосистеме Хилла, написать программу шифрования и дешифрования произвольного набора символов на любом языке программирования.

Порядок выполнения работы

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

2. написать функцию дешифрования, в которую в качестве параметров передается ключ и символ (или строка символов) зашифрованного текста.

3. написать главную функцию, которая организует ввод/вывод исходного текста и по запросу пользователя шифрует исходный или дешифрует зашифрованный текст.

Оформление отчета

В отчете следует привести краткие теоретические сведения. Кроме того, должны быть представлены: краткая блок-схема, текст программы, шифруемый набор символов, результаты выполнения программы.

Контрольные вопросы

1. В чем заключается суть метода шифрования подстановкой?

2. Чем различаются между собой одноалфавитная и многоалфавитная подстановки?

3. Опишите достоинства аффинной системы подстановок Цезаря?

4. Каким образом формируются биграммы в криптосистеме Хилла?

5. Какое линейное преобразование применяется в криптосистеме Хилла?

Лабораторная работа №3

Шифрование данных методом гаммирования

в симметричных криптосистемах

Цель работы: изучить методы шифрования данных гаммированием и освоить их практическое применение.

Теоретическое введение

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

Процесс дешифрования данных сводится к повторной генерации гаммы шифра при известном ключе и наложении такой гаммы на зашифрованные данные.

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

Ниже рассматриваются наиболее распространенные методы генерации гамм, которые могут быть использованы на практике.

Датчики ПСЧ

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

а) Конгруэнтные датчики

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

Одним из хороших конгруэнтных генераторов является линейный конгруэнтный датчик ПСЧ. Он вырабатывает последовательности псевдослучайных чисел T(i), описываемые соотношением

T(i+1) = (A*T(i)+C) mod m,

где А и С - константы, Т(0) - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик ПСЧ генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений А и С. Значение m обычно устанавливается равным 2n , где n - длина машинного слова в битах. Датчик имеет максимальный период М до того, как генерируемая последовательность начнет повторяться. По причине, отмеченной ранее, необходимо выбирать числа А и С такие, чтобы период М был максимальным. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда С - нечетное, и Аmod 4 = 1.

Для шифрования данных с помощью датчика ПСЧ может быть выбран ключ любого размера. Например, пусть ключ состоит из набора чисел x(j) размерностью b, где j=1, 2, ..., n. Тогда создаваемую гамму шифра G можно представить как объединение непересекающихся множеств H(j).

б) Датчики М-последовательностей

М-последовательности также популярны, благодаря относительной легкости их реализации.

М-последовательности представляют собой линейные рекуррентные последовательности максимального периода, формируемые k-pазpядными генераторами на основе регистров сдвига. На каждом такте поступивший бит сдвигает k предыдущих и к нему добавляется их сумма по модулю 2. Вытесняемый бит добавляется к гамме.

Строго это можно представить в виде следующих отношений:

r₁:=r₀ r₂:=r₁ ... r_k-1:=r_k-2

r₀:=a₀ r₁ a₁ r₂ ... a_k-2 r_k-1

Г_i:= r_k-

Здесь r₀ r₁ ... r_k-1 - k однобитных регистров, a₀ a₁ ... a_k-1 - коэффициенты непpиводимого двоичного полинома степени k-1. Г_i - i-е значение выходной гаммы.

Период М-последовательности, исходя из ее свойств равен 2^k-1.

Другим важным свойством М-последовательности является объем ансамбля, т.е. количество различных М-последовательностей для заданного k. Эта характеристика приведена в таблице:

k
объем ансамбля

Очевидно, что такие объемы ансамблей последовательности неприемлемы.

Поэтому на практике часто используют последовательности Голда, образующиеся суммированием нескольких М-последовательностей. Объем ансамблей этих последовательностей на несколько порядков превосходят объемы ансамблей порождающих М-последовательности. Так, при k=10 ансамбль увеличивается от 1023 (М-последовательности) до 388000.

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

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

Шифрование с помощью датчика ПСЧ является довольно распространенным криптографическим методом. Во многом качество шифра, построенного на основе датчика ПСЧ, определяется не только и не столько характеристиками датчика, сколько алгоритмом получения гаммы. Один из фундаментальных принципов кpиптологической практики гласит: даже сложные шифры могут быть очень чувствительны к простым воздействиям.

Задание на лабораторную работу

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

2. Используя алгоритм шифрования данных методом гаммирования с ПСП на основе М-последовательности, написать программу шифрования и дешифрования произвольного набора символов на любом языке программирования.

Порядок выполнения работы

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

2. функцию шифрования, в которую в качестве параметров передается ключ (очередное число ПСП) и символ (или строка символов) исходного текста.

3. функцию дешифрования, в которую в качестве параметров передается ключ (очередное число ПСП) и символ (или строка символов) зашифрованного текста.

4. главную функцию, которая организует ввод/вывод исходного текста и по запросу пользователя шифрует исходный или дешифрует зашифрованный текст.

Оформление отчета

В отчете следует привести краткие теоретические сведения. Кроме того, должны быть представлены: краткая блок-схема, текст программы, шифруемый набор символов, результаты выполнения программы.

Контрольные вопросы

1. Что понимают под гаммированием?

2. В чем состоит отличие между случайной и псевдослучайной последовательностями чисел?

3. В чем похожи моно и многоалфавитные системы шифрования и системы гаммирования?

4. Что такое период ПСП?

Лабораторная работа №4

Шифрование данных в асимметричной криптосистеме RSA

Цель работы: изучить методы шифрования данных в криптосистеме RSA и освоить их практическое применение.

Теоретическое введение

Алгоритм RSA предложен в 1978 г. тремя авторами: Р. Райвестом, А. Шамиром и А. Адлеманом. Это первый полноценный алгоритм работы с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме цифровой подписи.

Надежность алгоритма RSA основана на трудности факторизации больших чисел и вычисления дискретных логарифмов в конечных полях.

В криптосистеме RSA открытый ключ К_В, секретный ключ k_B, сообщение М и криптограмма С принадлежат множеству целых чисел

Z_N={0,1,2,…,N-1}

где N – модуль:

N=P´Q

В данном случае P и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете.

Множество Z_N с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ К_В выбирают случайным образом так, чтобы выполнялись следующие условия:

где – функция Эйлера.

Функция Эйлера указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.

Второе из указанных условий означает, что открытый ключ К_В и функция Эйлера должны быть взаимно простыми.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ k_B такой, что

или

Это можно осуществить, так как получатель сообщения В знает пару простых чисел P и Q и может легко найти . Заметим, что следует произвести проверку на взаимную простоту k_B и K_B.

Открытый ключ K_B используется для шифрования сообщения, а секретный ключ k_B – для расшифрования.

Шифрование определяет криптограмму С через пару (открытый ключ К_В, сообщение М) в соответствии со следующей формулой:

В качестве алгоритма быстрого вычисления значения С используется ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N.

Определение значения М по известным С, К_В и N практически не осуществимо при .

Однако обратную задачу, т.е. задачу расшифрования криптограммы С можно решить, используя пару (секретный ключ k_B, криптограмма С) по формуле:

.

Подставляя в данную формулу значение для С, получаем:

Величина имеет важное значение в теории Эйлера, которая утверждает, что если НОД(x,N)=1, то

или в несколько более общей форме

.

Учитывая вышесказанное, получаем:

Таким образом, если криптограмму

возвести в степень k_B, то в результате получим исходное открытое сообщение М, так как

Таким образом, получатель В, создавая криптограмму С, защищает два параметра: секретный ключ k_B, пару чисел (P, Q), произведение которых дает значение модуля N.

Противнику известны лишь значения К_В и N. Если бы он смог разложить число N на множители, то, узнав тройку чисел (P, Q, K_B), вычислил значение и вычислил секретный ключ. Однако, разложение достаточно большого числа на множители вычислительно не осуществимо, что и определяет криптостойкость алгоритма RSA.

Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два простых числа p и q

2. Вычисляется их произведение n=(p´q)

3. Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

4. Методом Евклида решается в целых числах уравнение e´d+(p-1)(q-1) ´y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

5. Два числа (e,n) – публикуются как открытый ключ.

6. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

Задание на лабораторную работу

Используя алгоритм шифрования данных в криптосистеме RSA, написать программу шифрования и дешифрования произвольного набора символов на любом языке программирования.

Порядок выполнения работы

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

2. написать функцию дешифрования, в которую в качестве параметров передается ключ и символ (или строка символов) зашифрованного текста.

3. написать главную функцию, которая организует ввод/вывод исходного текста и по запросу пользователя шифрует исходный или дешифрует зашифрованный текст.

4. для написания функций шифрования и дешифрования потребуется проверить два больших числа на взаимную простоту, используя алгоритм Евклида; вычислить число, обратное данному, в поле целых чисел, используя расширенный алгоритм Евклида для вычисления обратных величин; определить возведение в степень большого числа по модулю. Алгоритмы выполнения этих задач приведены в приложении.

Оформление отчета

В отчете следует привести краткие теоретические сведения. Кроме того, должны быть представлены: краткая блок-схема, текст программы, шифруемый набор символов, результаты выполнения программы.

Контрольные вопросы

1. Что понимают под однонаправленной функцией?

2. Какие параметры защищает криптосистема RSA?

3. Какие параметры криптосистемы RSA известны противнику?

4. При каких значениях параметров алгоритма криптосистема RSA станет абсолютно стойкой?

Лабораторная работа №5

Шифрование данных в асимметричных криптосистемах

по схеме Эль-Гамаля

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

Теоретическое введение

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

Безопасность схемы обусловлена сложностью вычисления дискретного логарифма в конечном поле.

Для генерации пары: открытый ключ, секретный ключ, сначала выбирают некоторое большое простое число Р и некоторое большое целое число Q, причем Q<P. Эти два числа распространяются среди группы пользователей.

Затем выбирают случайное число X<P, которое является секретным ключом.

Далее вычисляется открытый ключ Y по формуле:

Y = Q^X mod P.

Для зашифровки сообщения М выбирают случайное целое число К так, что

1 < K < P-1, НОД (K, P-1 )=1

Затем вычисляют числа:

a = Q^K mod P; b = Y^K M mod P

Пара чисел (a, b) является зашифрованным текстом, таким образом, длина зашифрованного текста вдвое больше длины открытых данных.

Для расшифрования вычисляют (*)

Так как ,

то соотношение (*) справедливо.

Пример: Для простоты возьмем небольшие числа. Пусть Р = 11, Q = 2, X = 8.

Вычисляем Y = Q^X mod P = 2⁸ mod 11 = 256 mod 11 = 3

Итак, открытый ключ равен 3.

Пусть сообщение М = 5. Выберем некоторое случайное число К = 9. Убедимся, что НОД(К, Р-1) = 1. Действительно, НОД(9, 10) = 1. Вычисляем пару чисел (a, b).

a = Q^K mod P = 2⁹ mod 11 = 512 mod 11 = 6;

b = Y^KM mod P = 3⁹*5 mod 11 = 19683*5 mod 11 = 9.

Получаем шифртекст (a, b) = (6, 9).

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

Это выражение можно представить в виде: или .

Решая данное сравнение, находим М = 5.

В реальных схемах шифрования необходимо использовать в качестве модуля P большое целое простое число, имеющее в двоичном представлении длину 512…1024 бит.

Задание на лабораторную работу

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

Порядок выполнения работы

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

2. написать функцию дешифрования, в которую в качестве параметров передается ключ и символ (или строка символов) зашифрованного текста.

3. написать главную функцию, которая организует ввод/вывод исходного текста и по запросу пользователя шифрует исходный или дешифрует зашифрованный текст.

4. для написания функций шифрования и дешифрования потребуется проверить два больших числа на взаимную простоту, используя алгоритм Евклида; вычислить число, обратное данному, в поле целых чисел, используя расширенный алгоритм Евклида для вычисления обратных величин; определить возведение в степень большого числа по модулю; решить сравнение вида a´x=b(mod n). Алгоритмы выполнения этих задач приведены в приложении.

Оформление отчета

В отчете следует привести краткие теоретические сведения. Кроме того, должны быть представлены: краткая блок-схема, текст программы, шифруемый набор символов, результаты выполнения программы

Контрольные вопросы

1. Чем обусловлена безопасность схемы Эль-Гамаля?

2. Какие параметры защищает криптосистема Эль-Гамаля ?

3. Какие параметры криптосистемы Эль-Гамаля известны противнику?

4. Насколько отличаются по длине исходный текст и шифртекст в криптосистеме Эль-Гамаля?

Лабораторная работа №6

Алгоритм электронной цифровой подписи

Цель работы: изучить алгоритмы электронной цифровой подписи и освоить их практическое применение.

Теоретическое введение

Алгоритм цифровой подписи RSA

Первой и наиболее известной во всем мире системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г в Массачусетском технологическом институте США.

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

N=P´Q

и значение функции

Далее отправитель вычисляет число Е из условий

и число D из условий

Пара чисел (Е N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.

Допустим, что отправитель хочет подписать сообщение M перед его отправкой. Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хэш-функции в целое число m.

m=h(M)

3aтем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D.

Пара (M,S) предается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.

После приема пары (M,S) получатель вычисляет хэш-значение сообщения М двумя разными способами. Прежде всего, он восстанавливает хэш-значение , применяя криптографическое преобразование подписи S с использованием открытого ключа Е:

Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(М):

m=h(M)

Если соблюдается равенство вычисленных значении т.е.

то получатель признает пару (М, S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители.

Алгоритм цифровой подписи Эль Гамаля (EGSA)

Название ЕGSA происходит от слов El Gamal Signature Algorihm (алгоритм цифровой подписи Эль Гамаля). Идея EGSA основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа, – задача дискретного логарифмирования. Кроме того, Эль- Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSA, связанного с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Рассмотрим подробнее алгоритм цифровой подписи Эль-Гамаля. Для того чтобы генерировать пару ключей (открытый ключ -секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G<Р.

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

Отправитель выбирает случайное целое число Х, 1<Х£(Р-1) и вычисляет

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов

Число X является секретным ключом отправителя для подписания документов и должно храниться в секрете.

Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h( ) в целое число m:

m=h(M), 1<m£(Р-1),

и генерирует случайное целое число К, 1<К<(Р-1), такое что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а

а = G^K modP

и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа X целое число b из уравнения

m = X´a + К´b (mod (Р-1)).

Пара чисел (а,b) образует цифровую подпись S

S=(а,b),

проставляемую под документом М.

Тройка чисел (М,а,b) передается получателю в то время, как пара чисел (X,К) держится в секрете.

После приема подписанного сообщения (М,а,b) получатель должен проверить, соответствует ли подпись S=(а,b) сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число

m=h(M).

Затем получатель вычисляет значение

и признает сообщение М подлинным, если и только если

Иначе говоря, получатель проверяет справедливость соотношения

Следует отметить что выполнение каждой подписи по методу Эль-Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К повторно используемое отправителем, то он сможет раскрыть секретный ключ X отправителя.

Пример.Выберем числа Р = 11 G = 2 и секретный ключ Х=8. Вычисляем значение открытого ключа

Предположим, что исходное сообщение М характеризуется хэш-значением m=5.

Для того чтобы вычислить цифровую подпись для сообщения М имеющего хэш-значение m=5, сначала выберем случайное целое число К=9. Убедимся, что числа К и (Р-1) являются взаимно простыми Действительно

НОД(9,10)=1.

Далее вычисляем элементы а и b подписи

элемент b определяем, используя расширенный алгоритм Евклида:

m = X´a + К´b (mod (Р-1)),

При m=5, a=6, X=3, К=9, Р=11 получаем

5=(6´8+9´b)(mod10)
или 9´b=-43(mod10).

Решение: b=3. Цифровая подпись представ