Алгоритм RSA был предложен в 1977 году и стал первым полноценным алгоритмом асимметричного шифрования и электронной цифровой подписи. Алгоритм назван по первым буквам фамилий авторов – Рональд Райвест (Ronald Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman). Стойкость алгоритма основывается на вычислительной сложности задачи факторизации (разложения на множители) больших чисел и задачи дискретного логарифмирования.
Криптосистема основана на теореме Эйлера, которая гласит, что для любых взаимно простых чисел M и n (M<n) выполняется соотношение:
| M (n)1(mod n), | (2.14) |
где (n) - функция Эйлера. Эта функция равна количеству натуральных чисел меньших n, которые взаимно просты с n. По определению, (1) 1. Также доказано, что для любых двух натуральных взаимно простых чисел a и b выполняется равенство (a b) (a) (b).
Алгоритм строится следующим образом. Пусть M – блок сообщения, 0≤M<n. Он шифруется в соответствии с формулой: (2.14)
В этом случае e – открытый ключ получателя. Тогда соответствующий ему секретный ключ d должен быть таким, что
| MCd (mod n)(M e) d (mod n) M ed (mod n). | (2.15) | ||
| Как уже отмечалось, теорема Эйлера | утверждает, | что | |
| M (n)1 (mod n) или, что то же самое, | M k (n)1 | M (mod n), где k – | |
натуральный множитель. Сопоставив данное выражение c выражением (2.15) получаем, что e и d должны быть связаны соотношением:
| edk (n)1 | ed 1(mod(n)). | (2.16) |
| Теперь предположим, что n | pq,где p и q – простые числа, |
причем p q. Нетрудно показать, что для простого числа p 1 функция Эйлера будет равна (p) p 1. Тогда, учитывая, что p и q – простые и не равны друг другу (а значит, они и взаимно простые), будет справедливо равенство:
| (pq)(p)(q)(p 1)(q 1). | (2.17) |
Рассмотрим теперь алгоритм RSA «по шагам». Первым этапом является генерация ключей.
1) Выбираются два больших простых числа p и q, p q.
2) Вычисляется модуль n: n = p q. Обратите внимание, что для криптосистемы RSA модуль n является частью открытого ключа и должен меняться при смене ключевой пары.
| 3) | Случайным образом выбирается число d, такое что |
| 1 d (p 1)(q 1)и НОД(d, (p-1)(q-1))=1. | |
| 4) | Вычисляется значение e такое что: |
1 e (p 1) (q 1)
e d 1 mod((p 1)(q 1))
Доказано, что для случая, когда НОД(d, (p-1)(q-1))=1 такое e существует и единственно.
В результате выполнения данных вычислений имеем открытый ключ, представленный парой чисел (n, e) и секретный ключ d.
Шифрование производится следующим образом.
Отправителю известен открытый ключ получателя – (n,e). Пусть M –секретное сообщение,которое надо зашифровать M < n. Криптограмма вычисляется по формуле:
| CM e mod n | (2.18) |
| Криптограмма C передается получателю. Владелец секретного | |
| ключа d может расшифровать сообщение по формуле (2.22). | |
| MCd mod n | (2.19) |
Рассмотрим теперь схему построения э лектронной цифровой подписи. Сообщение M подписывается с использованием секретногоключа d (но для генерации подписи используется уже ключевая пара отправителя):
| SM d mod n | (2.20) |
| Отправитель передает получателю подписанное сообщение, т. е. пару значений (M,S). Проверка ЭЦП по открытому ключу (n,e) производится так: | |
| M ' S e mod n. | (2.21) |
Совпадение значений M и M' служит доказательством того, что сообщение получено от владельца соответствующего секретного ключа и не было изменено в процессе передачи.
Как видно, сами преобразования относительно просты. Основную сложность при реализации алгоритма RSA представляет этап генерации ключей. В частности, простые числа p и q выбираются такими, что:
- одно из них должно быть меньше другого на несколько порядков;
- (p-1) и (q-1) должны иметь как можно меньший НОД;
- хотя бы одно из чисел (p-1), (q-1) должно иметь в разложении большой простой множитель (например, (p-1) = 2t, где t – простое).
Точное определение, является ли большое число простым или нет, во многих случаях является вычислительно сложной задачей. Поэтому, как правило, используются «псевдопростые» тесты, которые позволяют с достаточно большой вероятностью отбросить числа не являющиеся простыми. Один из таких тестов основан на малой теореме Ферма, которая гласит, что если p – простое число и 1 x<p, то x p 11 mod p. Проверив«кандидата»в простые числа с несколькими x,выбираемыми в соответствии со специальными требованиями,можно с большой вероятностью выяснить, является ли он простым.
Нахождение наибольшего общего делителя и определение значения e на шаге 4) алгоритма генерации ключей производится в соответствии с алгоритмом Евклида и обобщенным алгоритмом Евклида [7,9,12].
3.4.4 Криптографическая система Эль-Гамаля
В 1984 году американским исследователем египетского происхождения Тахером Эль-Гамалем (Taher Elgamal) были опубликованы алгоритмы шифрования с открытым ключом и ЭЦП, получившие его имя. Криптографическая система Эль-Гамаля использует ту же математическую основу, что и рассмотренная ранее схема распределения ключей Диффи-Хеллмана: в качестве односторонней функции в этой криптосистеме используется возведение в степень по модулю большого простого числа.
Алгоритм шифрования строится следующим образом. Выбирается большое простое число р такое, что разложение
числа (р-1) содержит большой простой множитель, а также число а такое, что 1 < а < (p-1) и a – первообразный корень по модулю p.
Получатель сообщения генерирует ключевую пару: случайным образом выбирает секретный ключ x (0 < x < р) и вычисляет открытый ключ y a x mod p.
Для шифрования сообщения М (0 ≤ М < р), отправитель должен выполнить следующие действия.
1. Выбратьслучайноечисло k такое,что 1 < k < p-1, НОД(k,р-1)=1.
2. Вычислить вспомогательное значение ryk mod p.
3. Рассчитать значение криптограммы, состоящее из двух час
тей: c 1 ak mod p, с 2 rM mod p.
Надо отметить, что в [10] приводится вариация данного алгоритма, где вторая часть криптограммы рассчитывается как
с 2' r M,где – побитное сложение по модулю 2.
Рассмотрим процесс расшифровки. Для того, чтобы по c2 определить M, получателю потребуется рассчитать значение r. С учетом того, что ему известен секретный ключ x и значение c1 это становится возможным: c 1 x (ak) x r mod p. Тогда M c 2 r 1 c 2 (c 1 x) 1 mod p. Или для варианта со сложением по модулю 2: M c 2' c 1 x mod p.
При использовании шифра Эль-Гамаля требуется, чтобы выбираемое в процессе шифрования число k, каждый раз менялось. В противном случае, если сообщения М и М' предназначены одному получателю, и нарушитель смог узнать одно из них, то ему не составит труда рассчитать и второе. Пусть, например, нарушитель знает сообщение M, соответствующие ему криптограммы c1 и c2, и криптограммы c1' и с2'. Из-за того, что k и ключи не менялись, будут совпадать r и r', c1 и с1'. М' нарушитель может рассчитать как:
| Mcr 1mod p; | M ' c ' r 1 | c | ' Mc 1 mod p. | (2.22) | |
| Рассмотрим теперь | предложенный | Эль-Гамалем | алгоритм | ||
электронной цифровой подписи. Надо отметить,что он получил широкое распространение и на его базе был разработан американский стандарт ЭЦП DSA (англ. «Digital Signature Algorithm»).
Как и при шифровании, стороны согласуют параметры a и p. После этого, отправитель выбирает секретный ключ x и рассчитывает открытый ключ y a x mod p.
| Подписываемое сообщение M должно удовлетворять условию | |||
| 0 | M < p. Подписью абонента | служит пара чисел r и s (0r < p, | |
| 0 | s < p),которые удовлетворяют соотношению: | ||
| aMyr r s mod p | (2.23) |
Получатель, знающий сообщение и открытый ключ, может проверить выполнение этого равенства. Но только владелец секретного ключа x может правильно рассчитать значения r и s. Для этого он выполняет следующие действия.
1. Выбирает случайное число k: 1 < k < p-1, НОД(k,р-1)=1.
2. Вычисляет rak mod p.
3. Вычисляет s из уравнения Mxrks mod(p 1). Это уравнение получено, основываясь на доказанном в теории числе утверждении: если p – простое, a – целое, 1<a<p (в этом случае, a и p будут и xy mod(p1)для любых целых не отрицательных x, y.
Таким образом, s (M xr) k 1mod(p 1). При выполнении условия НОД(k,р-1)=1, s существует и единственно.
Отправитель передает сообщение с подписью (M,r,s) получателю, который, пользуясь соотношением (2.23), может проверить ЭЦП.
При применении алгоритма ЭЦП Эль-Гамаля, также как и в случае шифрования, недопустимо использовать одно и то же значение k для подписи двух разных сообщений.
