Составители:
Рубрика:
34
3. КРИПТОСИСТЕМА RSA
3.1. Идея криптосистемы
Наиболее широко распространенной системой с открытым ключом
является криптосистема RSA (Rivest, Shamir, Adleman). Идея системы
состоит в том, что очень сложно разложить произведение двух простых
чисел на сомножители, т. е. найти эти сомножители. Сама же идея сис-
темы RSA исключительно проста.
Пусть p и q – два случайно выбранных простых числа (каждое при-
мерно по 100 десятичных разрядов). Обозначим:
n = pq и ϕ(n) = (p –1)(q –1),
где ϕ (n) – функция Эйлера от n.
Случайно выбирается большое число d >>1, такое, что (d, ϕ(n)) = 1,
и вычисляется e, 1 < e < ϕ(n), удовлетворяющее сравнению:
ed ≡ 1 mod ϕ(n).
Числа n, e и d называются соответственно модулем, экспонентой
зашифрования и экспонентой расшифрования соответственно.
Числа n и e образуют открытый ключ, а p, q, ϕ(n) и d секретную
лазейку. При этом секретная лазейка включает в себя взаимозависи-
мые величины. Так, если известно p (и, конечно, n и e), то остальные
числа лазейки вычисляются просто:
q = n/p; ϕ(n) = (p–1)(q–1);
d находится из условия: ed ≡ 1 mod ϕ(n).
Зашифрование обеспечивается возведением числового фрагмента
текста S в степень e по модулю n.
Расшифрование достигается возведением результата предыдущего
шага в степень d.
При зашифровании получаем S
e
≡ C mod n. Здесь C – зашифрован-
ный фрагмент текста.
При расшифровании C
d
= S
ed
= S
1+ϕ(n)k
= S
ϕ(n)k
S ≡ S mod n. (∗)
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
