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

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

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

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

Е (N), НОД (Е, (N)) =1

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

D < N, Е * D ≡ 1 (mod  (N)).

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

Обобщенная схема формирования и проверки цифровой подписи RSА показана на рисунке 6.3.3.1.

Рисунок 6.3.3.1 - Обобщённая схема цифровой подписи RSA

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

m = h(М).

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

S = m^D (mod N).

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

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

m' = S^E (mod N).

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

m = h(М).

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

S^E (mod N) = h(М),

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

Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют "идентификатором" подписавшего.

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

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

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

Пример

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

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

причем

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

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

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

Тогда злоумышленник может легко вычислить подпись S₃ для документа М₃, даже не зная секретного ключа 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г. НИСТ США обосновал перед комиссией Конгресса США выбор алгоритма цифровой подписи Эль-Гамаля в качестве основы для национального стандарта.

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

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

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

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

Y =G^X mod Р.

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

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

m = h(М), 1<m<(Р-1),

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

а = G^K mod Р

и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число 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 Р = Y = 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 = (6* 8+9* b)(mod 10)

или

9* b= -43(mod 10).

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

m = 5,

а затем вычисляет два числа:

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

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

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

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

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

1. При заданном уровне стойкости алгоритма цифровой подписи целые числа, участвующие в вычислениях, имеют запись на 25% короче, что уменьшает сложность вычислений почти в два раза и позволяет заметно сократить объем используемой памяти.
2. При выборе модуля Р достаточно проверить, что это число является простым и что у числа (Р-1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).
3. Процедура формирования подписи по схеме Эль-Гамаля не позволяет вычислять цифровые подписи под новыми сообщениями без знания секретного ключа (как в RSА).

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