Схема формирования ЭЦП Эль Гамаля

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

Исследование электронной цифровой подписи (ЭЦП)

 

Цель работы: исследование структуры алгоритма и методики практической реализации (ЭЦП) RSA и Эль-Гамаля.

 

1. Основные положения

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

Одновременно при этом возникает проблема, как аутентификации автора электронного документа, так и самого документа, т.е. установление подлинности автора и отсутствия изменений в полученном электронном сообщении.

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

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

- удостоверяет, что подписанный текст исходит от лица, поставившего подпись;

- не даёт этому самому лицу возможности отказаться от обязательств, связанных с подписанным текстом;

- гарантирует целостность подписанного текста.

ЭЦП представляет собой относительно небольшой объём дополнительной цифровой информации, передаваемой вместе с подписанным текстом.

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

Система ЭЦП включает две процедуры:

- формирование цифровой подписи;

- проверку цифровой подписи.

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

 

Алгоритм электронной цифровой подписи (ЭЦП) RSA

Безопасность системы RSA определяется вычислительной трудностью разложения на множители больших целых чисел. Недостатком алгоритма цифровой подписи RSA является уязвимость её к мультипликативной атаке. Другими словами, алгоритм ЭЦП RSA позволяет хакеру без знания секретного ключа сформировать подписи под теми документами, в которых результат хэширования можно вычислить как произведение результата хэширования уже подписанных документов.

Обобщённая схема формирования и проверки электронной цифровой подписи приведена на рис. 1.

Рис. 1. Схема электронной цифровой подписи RSA

 

1) Определение открытого «е» и секретного «d» ключей (действия отправителя)

- Выбор двух взаимно простых больших чисел р и q

- Определение их произведения n = р*q

- Определение функции Эйлера: φ(п) = (p-1)(q-1)

- Выбор секретного ключа d с учетом условий: 1 < d ≤ φ(п), НОД(d, φ( n) ) =1

- Определение значения открытого ключа e: е< n, e * d ≡ 1 (mod φ(n))

2) Формирование ЭЦП

- Вычисление хэш-значения сообщения М: т = h (M)

- Для получения ЭЦП шифруем хэш-значение m с помощью секретного ключа d и отправляем получателю цифровую подпись S = m^d (mod п) и открытый текст сообщения M

3) Аутентификация сообщения - проверка подлинности подписи

- Расшифровка цифровой подписи S с помощью открытого ключа e и вычисление её хэш-значения m'=S^e (mod п)

- Вычисление хэш-значения принятого открытого текста M

т = h (М)

- Сравнение хэш-значений т и т' если т = т’то цифровая подпись S – достоверна.

Процедуру формирования ЭЦП сообщения М рассмотрим на следующем простом примере:

4) Вычисление хэш-значения сообщения М: m = h(M).

Хешируемое сообщение M представим как последовательность целых чисел 312. В соответствии с приведённым выше алгоритмом формирования ЭЦП RSA выбираем два взаимно простых числа р = 3, q = 11, вычисляем значение п=p*q = 3*11 = 33, выбираем значение секретного ключа d =7 и вычисляем значение открытого ключа е = 3. Вектор инициализации Н₀ выбираем равным 6 (выбирается случайным образом). Хэш-код сообщения M=312 формируется следующим образом:

Н₁ = (M₁ + H₀)² (mod п) = (3 + 6)² (mod 33) = 81 (mod 33) = 15;

H₂ = (М₂ + H₁)² (mod п) =(1 + 15)² (mod 33) = 256 (mod 33) = 25;

Н₃ = (М₃ + H₂)² (mod п) = (2 + 25) ² (mod 33) = 729 (mod 33) = 3; т = 3

Для получения ЭЦП шифруем хэш-значение m с помощью секретного ключа d и отправляем получателю цифровую подпись S = m^d (mod n) и открытый текст сообщения M: S = 3⁷ (mod 33) =2187 (mod 33) = 9

Проверка подлинности ЭЦП

Расшифровка S (т.е. вычисление её хэш-значения т') производится с помощью открытого ключа е.

m'= S^e (mod п) = 9³ (mod 33) =729 (mod 33) = 3

Если сравнение хэш-значений т' и т показывает их равенство, т.е. т = m' то подпись достоверна.

 

Схема формирования ЭЦП Эль Гамаля

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

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

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

1) Определение открытого «у» и секретного «x» ключей (действия отправителя)

- Выбор двух взаимно простых больших чисел р и q, q<p

- Выбор значения секретного ключа х, х <р

- Определение значения открытого ключа у из выражения:

у = q^x (mod р)

2) Формирование ЭЦП

- Вычисление хэш-значения сообщения M: т =h(M)

- Выбор случайного числа k, 0<k< р-1 и НОД (k, р-1) = 1

- Определение значения а из выражения: а = q^k (mod р)

- Определение значения b из выражения:

m = (ха + kb) (mod (р-1))

- Цифровая подпись S = (а, b) и открытый текст сообщения M отправляются получателю.

 

3) Аутентификация сообщения - проверка подлинности подписи (действия получателя)

- Вычисление хэш-значения принятого открытого текста сообщения M

т'=h(M)

- Подпись считается достоверной, если а < р, m = m' и выполняется условие

у^a a^b (mod р) = q^m’ (mod р)

 

4) В качестве процедуры формирования ЭЦП рассмотрим следующий пример (для удобства расчётов в данном примере использованы числа малой разрядности):

- Выбираем простое число р и два случайных числа q и х (q и х<р), р=11, q= 2 и секретный ключ х = 8;

- Вычисляем значение открытого ключа у

у = q^x (mod р) = 2⁸(mod 11) = 3;

- Определяем хэш-значение исходного сообщения М, (312) т = h (M), в данном примере принимаем т = 3(методика определения хэш значения сообщения M описана в алгоритме ЭЦП RSA).

- Выбираем случайное целое число k, взаимно простое с р-1. Принимаем k= 9, НОД(9, 10) = 1.

- Для формирования ЭЦП вычисляем элементы подписи а и b

а = q^k (mod р) = 2⁹ (mod 11) =6.

Элемент b определяем с помощью расширенного алгоритма Евклида из следующего соотношения:

m = (ха + kb) (mod (р-1)); 3= (8*6 + 9*b) (mod 10)) -9*b = -45(mod 10)

b =5.

В данном примере цифровой подписью является пара чисел а = 6, b = 5.

Цифровая подпись S = (а,b) и открытый текст сообщения M отправляются получателю. Для контроля целостности сообщения и достоверности ЭЦП получатель вычисляет хэш-значение m' принятого открытого текста сообщения M. При этом отправитель и получатель использует одну и ту же хэш-функцию h().

Получив подписанное сообщение и открытый ключ у = 3, получатель для проверки подлинности подписи проверяет выполнение условия

у^a a^b (mod р) = q^m’ (mod р)

3⁶*6⁵ (mod 11) = 2³(mod 11)

5668704(mod 11) = 8 (mod 11) 8(mod 11) = 8(mod 11),

так как условие выполняется, то принятое получателем сообщение признаётся подлинным.

Таким образом, процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщения.

Следует иметь ввиду, что каждая подпись по схеме Эль Гамаля требует нового значения k. Случайное значение k должно храниться в секрете.

 

2. Выполнение работы

Задачи лабораторной работы:

1) Разработать приложения формирования ЭЦП RSA и Эль-Гамаля.

2) Привести сравнительную характеристику формирования ЭЦП RSA и Эль-Гамаля. Описать их преимущества и недостатки.

 

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

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

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

3. Назовите и охарактеризуйте методы, реализующие ЭЦП.

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

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

6. Сравните наиболее распространенные стандарты ЭЦП.