Шифрование с открытым ключом

Шифрование с открытым ключом производится следующим образом.

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 цифр в десятичной записи, а обычно – значительно больше). В результате вскрыть этот шифр оказывается невозможно, если не существует эффективных алгоритмов разложения на множители.

Впрочем, возможность открытия таких алгоритмов существует, хотя этот факт и не доказан строго.