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

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA. Обобщенная схема формирования и проверки цифровой подписи RSA показана на рисунке 6.1.

Криптосистему формирует отправитель (автор) электрон­ных доку­ментов. Для этого вычисляет два больших простых числа p и q, затем находит их произведение n = p · q и значение функции Эйлера

j(n)=(p -1)(q -1).

Далее он вычисляет пару ключей (секретный ключ d и открытый ключ e) из условий:

e £j(n), НОД (e, (j(n)) =1 и

d < n, e · d = 1 mod j (n).

 

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

 

Рисунок 6.1. Схема формирования и проверки цифровой подписи RSA

 

Допустим, что отправитель хочет подписать сообщение M перед его отправкой. Сначала сообщение M (блок информации, файл, …) сжимают с помощью хэш-функции h (·) в целое число m = h (M). Затем вычисляют циф­ровую подпись s под электронным докумен­том M, используя хэш-значение m и секретный ключ d:                 

s = m^d mod n.

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

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

m ´= s^e mod n.

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

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

s^e mod n = h (M),

то получатель признает пару (M, s) подлинной. Доказано, что толь­ко обладатель секретного ключа d может сформировать цифровую подпись s по документу M, а определить секретное число d по открытому числу e не легче, чем разложить модуль n на множи­тели.

Можно строго математически доказать, что результат проверки циф­ровой подписи s будет положительным только в том случае, если при вычислении s был использован секретный ключ d, соответствующий отк­рытому ключу e. Поэтому s называют «идентификатором подписавшего».

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

1. При вычислении модуля n, ключей e и d для системы цифровой подписи RSA необходимо проверять большое количе­ство дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фаль­сификацию цифровой подписи со стороны того, кто обнаружит та­кое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.

2. Для обеспечения криптостойкости цифровой подписи RSA по от­ношению к попыткам фальсификации на уровне, напри­мер, националь­ного стандарта США, не­обходимо использовать при вычисле­ниях n, d и e целые числа не менее 2⁵¹² (или около 10¹⁵⁴) каж­дое, что требует больших вычислительных затрат, превышающих на 20-30% вычислительные затраты других алгоритмов циф­ровой подписи при сохранении того же уровня криптостойкости.

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