Криптографическая система RSA

Алгоритм 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 1}1 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. Вычислить вспомогательное значение ry^k mod p.

3. Рассчитать значение криптограммы, состоящее из двух час

тей: c ₁ a^k mod p, с ₂ rM mod p.

Надо отметить, что в [10] приводится вариация данного алгоритма, где вторая часть криптограммы рассчитывается как

с ₂^' r M,где – побитное сложение по модулю 2.

Рассмотрим процесс расшифровки. Для того, чтобы по c₂ определить M, получателю потребуется рассчитать значение r. С учетом того, что ему известен секретный ключ x и значение c₁ это становится возможным: c ₁ ^x (a^k) ^x r mod p. Тогда M c ₂ r ¹ c ₂ (c ₁ ^x) ¹ mod p. Или для варианта со сложением по модулю 2: M c ₂^' c ₁ ^x mod p.

При использовании шифра Эль-Гамаля требуется, чтобы выбираемое в процессе шифрования число k, каждый раз менялось. В противном случае, если сообщения М и М' предназначены одному получателю, и нарушитель смог узнать одно из них, то ему не составит труда рассчитать и второе. Пусть, например, нарушитель знает сообщение M, соответствующие ему криптограммы c₁ и c₂, и криптограммы c₁' и с₂'. Из-за того, что k и ключи не менялись, будут совпадать r и r', c₁ и с₁'. М' нарушитель может рассчитать как:

 

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. Вычисляет ra^k mod p.

3. Вычисляет s из уравнения Mxrks mod(p 1). Это уравнение получено, основываясь на доказанном в теории числе утверждении: если p – простое, a – целое, 1<a<p (в этом случае, a и p будут и xy mod(p1)для любых целых не отрицательных x, y.

Таким образом, s (M xr) k ¹mod(p 1). При выполнении условия НОД(k,р-1)=1, s существует и единственно.

Отправитель передает сообщение с подписью (M,r,s) получателю, который, пользуясь соотношением (2.23), может проверить ЭЦП.

При применении алгоритма ЭЦП Эль-Гамаля, также как и в случае шифрования, недопустимо использовать одно и то же значение k для подписи двух разных сообщений.