Цифровая подпись RSA уязвима к так называемой мультипликативной атаке

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

Пример. Допустим, что злоумышленник может сконструировать три сообщения M₁, M₂ и M₃, у которых хэш-значения

m₁ = h(M₁), m₂ = h(M₂), m₃ = h(M₃),

причем m₃ = m₁ * m₂ (mod N).

Допустим также, что для двух сообщений M₁ и M₂ получены законные подписи

S₁ = m₁^D (mod N) и S₂ = m₂^D (mod N).

Тогда злоумышленник может легко вычислить подпись S₃ для документа M₃, даже не зная секретного ключа D:

S₃ = S₁ * S₂ (mod N).

Действительно,

S₁ * S₂ (mod N) = m₁^D * m₂^D (mod N) = (m₁m₂)^D (mod N) = m₃^D (mod N) = S₃.

Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем. В 1991 г. НИСТ США обосновал перед комиссией Конгресса США выбор алгоритма цифровой подписи Эль Гамаля в качестве основы для национального стандарта.

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

Название EGSA происходит от слов El Gamal Signature Algorithm (алгоритм цифровой подписи Эль Гамаля)

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

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

В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

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

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

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

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

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

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

Алгоритм цифровой подписи DSA (Digital Signature Algorithm) предложен в 1991 г. в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К.Шнорра

(Алгоритм цифровой подписи, определяемый отечественным стандартом цифровой подписи ГОСТ Р 34.10-94 [40]. концептуально близок к алгоритму DSA.)

Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и P – простые числа, L бит каждое (512 £ L £ 1024); q – простое число длиной 160 бит (делитель числа (P –1)). Числа G, P, q являются открытыми и могут быть общими для всех пользователей сети.

Отправитель выбирает случайное целое число X, 1< X< q. Число X является секретным ключом отправителя для формирования электронной цифровой подписи.

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