Шифр RSA (Шифр Ривеста-Шамира-Алдемана)

Одно из требований к выбору р и q заключается в том, что по крайней мере одно из чисел р — 1 или q — 1 должно иметь один большой простой множитель. Размер модуля n должен быть не менее 512 бит. Для ответственных применений системы RSA рекомендуемая длина модуля составляет 1024 бит.)

2.  Затем выбирается целое число е такое, что е < j(n) и НОД(е, j(n)) = 1 и вычисляется d, удовлетворяющее условию

ed = 1 (mod j(n)).

3.  Секретным ключом является тройка чисел р, q, d, которая держится в секрете. (На самом деле хранить в секрете достаточно только число d, поскольку простые числа р и q нужны только на этапе формирования модуля n и вычисления d. После этого числа р и q могут быть уничтожены.)

4.  Пара чисел n, е является открытым ключом, который предоставляется всем абонентам криптосистемы RSA.

5.  Процедура подписывания сообщения М — это возведение числа М в степень d no mod n:

S = M^d (mod n).

Число S есть цифровая подпись, которую может выработать только владелец секретного ключа.

6.  Процедура проверки подписи S, соответствующей сообщению М, — это возведение числа S в целую степень е по mod n:

М' = S^e (mod n).

Если М' = М, то сообщение М признается подписанным пользователем, который предоставил ранее открытый ключ е. Видно, что

S^e = (M^d)^e = M^de = M^j(n)Q+1 = М^j(n)Q М = (M^j(n))^Q M = 1^Q M (mod n),

т. е. составить криптограмму, соответствующую данному открытому ключу и данному сообщению можно только по известному секретному ключу d.

Стойкость криптосистемы RSA основана на сложности разложения модуля на два больших простых множителя. До настоящего времени не найдены практически реализуемые общие способы решения этой задачи при длине модуля 512 бит и более. Однако, для частных видов простых чисел р и q сложность этой задачи резко понижается, поэтому в криптосистеме RSA необходимо выполнить ряд специальных тестов при генерации секретного ключа. Другой особенностью системы RSA является ее мультипликативность:

Е(М₁М₂) = Е(М₁)Е(М₂) (mod n),

что позволяет нарушителю на основе двух подписанных сообщений сформировать подпись третьего сообщения, которое равно М₃ = M₁M₂ (mod n). Поскольку М₃ в подавляющем большинстве случаев не будет представлять собой какого-либо осмысленного текста, то наличие этой особенности не является недостатком. В системе RSA необходимо учитывать также следующую возможность. Выбрав произвольное значение S, можно вычислить значение М' = S^e т. е. произвольное значение можно представить как подпись некоторого сообщения. Такие фиктивные сообщения, естественно, являются случайными. Однако в ряде применений требуется подписывать случайные сообщения. В таких случаях используют следующую схему.

1. К сообщению Т, которое необходимо подписать и передать по открытому каналу, присоединяется заранее условленный двоичный вектор V длиной v = 64 бит:

М ® Т | V.

2. Вырабатывается подпись для сообщения М:

S = M^d (mod n).

3. Значение S направляется приемной стороне.

4. Приемная сторона по значению S вычисляет значения

Если V равно условленному значению, т. е. если выполняется условие V’ = V, то принимается решение, что сообщение Т' подписано владельцем секретного ключа, соответствующего открытому ключу, с помощью которого выполнялась проверка подписи. (Вероятность того, что случайное сообщение может быть принято за подписанное, равна 2^-v.)

Полезным свойством рассматриваемой системы открытого шифрования