![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Шифрование с открытым ключом производится следующим образом.
1. Получателем сообщений производится генерация открытого ключа (пара чисел n и e) и закрытого ключа (число d). Для этого:
· выбираются два простых числа p и q;
· определяется первая часть открытого ключа n = pq;
· определяется вторая часть открытого ключа – выбирается небольшое нечетное число e, взаимно простое с числом (заметим, что
);
· определяется закрытый ключ: .
После чего открытый ключ (числа n и e) сообщается всем отправителям сообщений.
2. Отправитель шифрует сообщение (разбивая его, если нужно, на слова длиной менее
разрядов):
,
и отправляет получателю.
3. Получатель расшифровывает сообщение с помощью закрытого ключа d:
.
Теорема 10.4. Шифрование с открытым ключом корректно, то есть в принятых обозначениях .
Доказательство. Очевидно, что . Покажем, что
. Действительно числа d и e взаимно обратны по модулю
, то есть
при некотором k. Если , то по малой теореме Ферма имеем:
.
Если , то сравнение
, очевидно, выполняется. Таким образом,
.
Совершенно аналогично имеем
.
И по следствию к китайской теореме об остатках
.
Поскольку и
, заключаем, что
.
Пример 10.7. Генерация ключей:
10.3.1. p =3, q =11;
10.3.2. n = ;
10.3.3. , e =7;
10.3.4. d = , (
).
Пусть =3,
=1,
=2 (
). Тогда код определяется следующим образом:
;
;
.
При расшифровке имеем:
,
,
.
Шифры с открытым ключом сравнительно просты в реализации, очень практичны (поскольку нет необходимости пересылать по каналам связи закрытый ключ и можно безопасно хранить его в одном месте) и в то же время обладают высочайшей криптостойкостью.
Кажется, что дешифровать сообщение несложно: достаточно разложить открыто опубликованное число n на множители, восстановив числа p и q, и далее можно легко вычислить секретный ключ d.
Однако дело заключается в следующем. В настоящее время известны эффективные алгоритмы определения простоты чисел, которые позволяют за несколько минут подобрать пару очень больших простых чисел (по 100 и больше цифр в десятичной записи). В то же время неизвестны эффективные алгоритмы разложения очень больших чисел на множители. Разложение на множители числа в 200 и больше цифр потребовало бы сотен лет работы самого лучшего суперкомпьютера. При практическом применении шифров с открытым ключом используют действительно большие простые числа (не менее 100 цифр в десятичной записи, а обычно – значительно больше). В результате вскрыть этот шифр оказывается невозможно, если не существует эффективных алгоритмов разложения на множители.
Впрочем, возможность открытия таких алгоритмов существует, хотя этот факт и не доказан строго.
Дата публикования: 2014-11-03; Прочитано: 392 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!