Составители:
каждый из которых содержит двоичное значение, меньшее некоторого
заданного числа N. Это значит, что длина блока должна быть меньше
или равна log
2
(N).
Трудность факторизации больших чисел и трудность вычисления
дискретных логарифмов определяют надежность алгоритма RSA. В
данной криптосистеме открытый ключ К
о
, секретный ключ К
с
,
сообщение М и криптограмма С принадлежат множеству целых чисел
Z
N
= {0, 1, 2. …, N-1}, (3.5)
N = P ⋅ Q, (3.6)
где N – модуль, P и Q являются случайными большими взаимно
простыми числами. Их выбирают равной длины и хранят в секрете для
обеспечения максимальной безопасности.
Множество Z
N
с операциями сложения и умножения по модулю N
образует арифметику по модулю N.
Открытый ключ К
о
выбирают случайным образом так, чтобы
выполнялись условия
1 < K
о
≤ ϕ(N), HOД (К
о
, ϕ(N)) = 1 (3.7)
ϕ(N) = (P – 1) (Q – 1), (3.8)
где ϕ(N) – функция Эйлера, которая указывает количество
положительных целых чисел в интервале от 1 до N, которые взаимно
просты с N.
Кроме того, открытый ключ К
о
и функция Эйлера ϕ(N) также должны
быть взаимно простыми.
Затем, используя расширенный алгоритм Евклида [17], вычисляют
секретный ключ К
с
такой, что
К
с
⋅К
о
≡ 1(mod ϕ(N)) или К
с
= К
о
-1
(mod (P – 1) (Q – 1)). (3.9)
Данное вычисление возможно, поскольку получатель знает пару
простых чисел (P, Q) и может легко найти ϕ(N), при этом К
с
и N должны
быть взаимно простыми. Задачу зашифрования открытого текста М в
криптограмму С можно решить, используя открытый ключ K
o
, по
следующей формуле:
С = Е
К
о
(М) = М
К
о
(mod N). (3.10)
57
Страницы
- « первая
- ‹ предыдущая
- …
- 53
- 54
- 55
- 56
- 57
- …
- следующая ›
- последняя »
