6.2. Алгоритм создание эцп и стандарты.

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

1. Сжатие с помощью хеш-функции,

2. Шифрование хеш-свертки с помощью одного из методов асимметричного шифрования, например, RSA или ElGamal с использованием закрытого ключа.

Рис. Схема вычисления электронно- цифровой подписи.

Напомним, что хеш-функции обеспечивают преобразования файла F произвольной длины в строку фиксированной длины h(F) (128 бит для MD5 или 160 бит для SHA-1). Полученная строка, рассматриваемое как 128 или 160-битовое число, может быть за одну операцию возведения в степень (если используется RSA) преобразовано в 512 или 1024 битовое число Enc(h(F)) (длина результата зависит от длины ключа RSA, поскольку результат возведения в степень нормируется по модулю числа N, являющегося ключом RSA). Полученное значение называется электронно-цифровой подписью документа F.

Отметим свойства ЭЦП, важные с точки зрения безопасности:

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

2. Длина свертки (128 бит или более) достаточно велика, что исключить полный перебор вариантов ( ).

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

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

Стандарты электронно-цифоровой подписи.

На сегодняшний день придумано и реализовано достаточно много алгоритмов цифровой подписи:

• алгоритм подписи на основе RSA;

• Алгоритм цифровой подписи Эль-Гамаля (El Gamal Signature Algorithm);

• алгоритм DSA, предложен в 1991г. в США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Основан на усовершенствованной схеме Эль-Гамаля.

• Старый российский стандарт электронно-цифровой подписи ГОСТ Р34.10-94, концептуально близок к алгоритму DSA. Различие между этими стандартами заключается в использовании параметров ЭЦП разного порядка, что приводит к получению более безопасной подписи при использовании российского стандарта.

• Новый российский стандарт ГОСТ Р 34.10-2001, основан на использовании эллиптических кривых.

Электронно-цифровая подпись на основе метода Эль-Гамаля.

Пусть заданы простое число p – характеристика поля Галуа, порождающий элемент g<p, секретный ключ x, 1< x < p-1, сообщение M и случайное число k, взаимно простое с p-1. Схема построения ЭЦП для сообщения М является следующей:

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

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

3. Потом отправитель вычисляет целое число .

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

m = Х * а + К * b (mod (Р-1)) .

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

S=(а,b) ,

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

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

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

m = h(М) ,

т.е. хэширует принятое сообщение М.

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

А = Y^a a^b (mod Р)

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

А = G^m (mod Р) .

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

Y^a a^b (mod Р) = G^m (mod Р) .

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

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

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

Y = G^X mod Р = 2⁸ mod 11 = 3 .

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

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

а = G^K mod Р = 2⁹ mod 11 = 6 ,

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

m = Х * а + К * b (mod(Р-1)).

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

5 = 8 * 6 + 9 * b (mod 10)

или

9 * b = -43 (mod 10) .

Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3. Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для сообщения М : m = 5, а затем вычисляет два числа:

Y^aa^b (mod Р) = 3⁶ * 6³ (mod 11) = 10 (mod 11);

G^m (mod Р) = 2⁵ (mod 11) = 10 (mod 11).

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

Следует отметить, что схема Эль Гамаля является характерным примером подхода, который допускает пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSА:

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

2. При выборе модуля Р достаточно проверить, что это число является простым и что у числа (Р-1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).

3. Процедура формирования подписи по схеме Эль Гамаля не позволяет вычислять цифровые подписи под новыми сообщениями без знания секретного ключа (как в RSА).

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