Российские стандарты ЭЦП ГОСТ Р 34.10.94,

DSA

RSA

Известные алгоритмы ЭП

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

Недостатки алгоритма цифровой подписи RSА.

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

Для обеспечения криптостойкости цифровой подписи RSА по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 10¹⁸, необходимо использовать при вычислениях N, D и Е целые числа не менее 2⁵¹² (или около 10¹⁵⁴) каждое, что требует больших вычислительных затрат, превышающих на 20...30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.

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

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

Название ЕGSА происходит от слов Е_ Gаmаl_ Signaturе Аlgorithm (алгоритм цифровой подписи Эль Гамаля).

Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа, - задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

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

Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10³⁰⁸ или ~2¹⁰²⁴) и G (~10¹⁵⁴ или ~2⁵¹²), которые не являются секретными.

Отправитель выбирает случайное целое число X,

1 < Х < (Р-1), и вычисляет Y =G^X mod Р.

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

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

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

2) m = h(М), 1 < m < (Р-1), и генерирует случайное целое число К,

3) 1 < К < (Р-1), такое, что К и (Р-1) являются взаимно простыми.

4) Затем отправитель вычисляет целое число а: а = G^K mod Р

5) Применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения m = (Х * а + К * b) (mod (Р-1))

6) Пара чисел (а, b) образует цифровую подпись S: S=(а,b),проставляемую под документом М.

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

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

9) Затем получатель вычисляет значение А = Y^a a^b (mod Р) и признает сообщение М подлинным, только если А = G^m (mod Р).

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

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

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

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

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

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

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

Алгоритм DSA (Digital Signature Algorithm) был разработан в 1981 г. и с тех пор используется как стандарт США для электронной цифровой подписи — Digital Signature Standard (DSS). Согласно определению стандарта DSS, алгоритм DSA предусматривает применение в качестве хэш-функции алгоритма SHA. Заметим, что параметры алгоритма не засекречены.

В основу DSA легли алгоритмы Эль-Гамаля и RSA.

DSA базируется на применении больших простых чисел одинаковой размерности (от 512 бит) — G и P. Среди его параметров присутствует и простое число q размерностью 160 бит — делитель числа (P — 1). Что же касается секретного ключа Ks, то он представляет собой целое число, случайно выбираемое из диапазона

[1, Kp = G^Ks mod P].

Дата добавления: 2014-01-06