Составители:
Определение значения М по известным значениям С, К
о
и N т.е.
обращение функции С = М
К
о
(mod N), практически не осуществимо при N
≈2
512
.
Задачу расшифрования криптограммы С можно решить, используя
секретный ключ К
с
, по следующей формуле:
M = D
К
с
(C) = С
К
с
(mod N). (3.11)
Процесс расшифрования можно записать так:
D (E (M)) = M. (3.12)
Подставляя в (3.12) значения (3.10) и (3.11), получаем
(М
К
о
)
К
с
= М (mod N)
или
М
К
о
К
с
= М (mod N). (3.13)
Согласно теореме Эйлера, утверждающей, что если НОД ϕ(N) =1, то
X
ϕ(N)
≡ 1 (mod N)
или в несколько более общей форме
X
nϕ(N)+1
≡ X (mod N). (3.14)
Сравнивая выражения (3.13) и (3.14), получаем
К
о
⋅К
с
= n ⋅ ϕ(N) + 1 или К
о
⋅К
с
≡ 1(mod ϕ(N)).
Поэтому для вычисления секретного ключа К
с
применяют последнее
соотношение. Откуда следует, что если криптограмму
С = М
К
о
(mod N) возвести в степень К
с
, то в результате восстанавливается
исходный открытый текст М, так как
(М
К
о
)
К
с
= М
К
о
К
с
= М
n ϕ(N) + 1
≡ M (mod N).
Таким образом, получатель, который создает криптосистему,
защищает два параметра: секретный ключ К
с
и пару чисел P и Q,
произведение которых даёт модуль N. Одновременно публикует
значения модуля N и открытого ключа К
о
, поэтому противнику
известны только значения К
о
и N. Если бы криптоаналитик смог
разложить число N на множители P и Q, то он узнал бы тройку чисел
(P,Q, K
o
), значение функции Эйлера ϕ(N) = (P – 1) (Q – 1) и определил
значение секретного ключа K
c
.
Однако, как отмечалось выше, разложение большого числа N на
множители вычислительно не осуществимо при длине выбранных P и Q
не менее 100 десятичных знаков.
58
Страницы
- « первая
- ‹ предыдущая
- …
- 54
- 55
- 56
- 57
- 58
- …
- следующая ›
- последняя »
