ВУЗ:
Составители:
шему строить шифр таким способом, чтобы его раскрытие было эквивалентно решению
математической задачи, требующей выполнения объемов вычислений, превосходящих
возможности современных ЭВМ (например, операции с большими простыми числами и
их произведениями).
Принцип применения асимметричного шифрования показан на рис. 6.7. Рассмотрим
наиболее распространенные алгоритмы асимметричного шифрования.
6.4.2.1. Алгоритм RSA
В настоящее время наиболее развитым методом криптографической защиты инфор-
мации с известным ключом является
RSA, названный так по начальным буквам фамилий
ее изобретателей (
Rivest, Shamir и Adleman). Перед тем как приступить к изложению кон-
цепции метода
RSA, необходимо определить некоторые термины.
Под
простым числом будем понимать такое число, которое делится только на 1 и на
само себя. Взаимно простыми числами будем называть такие числа, которые не имеют ни
одного общего делителя, кроме 1.
Под
результатом операции i mod j будем считать остаток от целочисленного деле-
ния
i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и
секретный ключи, выполнив следующие шаги.
Выберем два очень больших простых числа
p и q,
Определим
n как результат умножения p на q (n = pq).
Выберем большое случайное число, которое назовем
d. Это число должно быть вза-
имно простым с
m результатом умножения (р – 1) (q – 1).
Определим такое число
e, для которого является истинным следующее соотношение
(
e d) mod (m) = 1 или e = (1 mod (m))/d.
Открытым ключом будут числа
e и n, а секретным ключом – числа d и n.
Теперь, чтобы зашифровать данные по известному ключу {
e, n}, необходимо сде-
лать следующее:
−
разбить шифруемый текст на блоки, каждый из которых может быть представлен
в виде числа
М(i) = 0, 1, …, n – 1;
−
зашифровать текст, рассматриваемый как последовательность чисел М(i) по
формуле
С(i) = (М(i)
e
) mod n.
Чтобы расшифровать данные, используя секретный ключ {
d, n}, необходимо выпол-
нить следующие вычисления:
М(i) = (С(i)
d
) mod n. В результате получится множество
чисел
М(i), которые представляют собой исходный текст.
Пример. Применим метод RSA для шифрования сообщения «ГАЗ». Для простоты
будем использовать очень маленькие числа (на практике используются намного большие
числа).
Выберем
p = 3 и q = 11.
Определим
n = 3 ⋅ 11 = 33.
Найдем (
p – 1) (q – 1) = 20. Следовательно, в качестве d выберем любое число, кото-
рое является взаимно простым с 20, например
d = 3.
Выберем число
е. В качестве такого числа может быть взято любое число, для кото-
рого удовлетворяется соотношение (
e × 3) mod 20 = 1, например 7.
Представим шифруемое сообщение как последовательность целых чисел в диапазо-
не 0…32. Пусть буква
А изображается числом 1, буква Г – числом 4, а буква З – числом 9.
Тогда сообщение можно представить в виде последовательности чисел 4 1 9. Зашифруем
сообщение, используя ключ {7, 33}:
C
1
= (4
7
) mod 33 = 16384 mod 33 = 16,
C
2
= (1
7
) mod 33 = 1 mod 33 = 1,
C
3
= (9
7
) mod 33 = 4782969 mod 33 = 15.
Шифртекст: «16 1 15».
Попытаемся расшифровать сообщение {16, 1, 15}, полученное в результате зашиф-
рования по известному ключу, на основе секретного ключа {3, 33}:
М
1
= (16
3
) mod 33 = 4096 mod 33 = 4,
М
2
= (1
3
) mod 33 = 1 mod 33 = 1,
М
3
= (15
3
) mod 33 = 3375 mod 33 = 9.
Таким образом, в результате расшифрования сообщения получено исходное сооб-
щение «ГАЗ».
Криптостойкость алгоритма
RSA основывается на предположении, что исключи-
тельно трудно определить секретный ключ по известному, поскольку для этого необхо-
димо решить задачу о существовании делителей целого числа. Данная задача является
NР-полной и, как следствие этого факта, не допускает в настоящее время эффективного
(полиномиального) решения. Более того, сам вопрос существования эффективных алго-
ритмов решения
NР-полных задач является до настоящего времени открытым. В связи с
этим для чисел, состоящих из 200 цифр (а именно такие числа рекомендуется использо-
Страницы
- « первая
- ‹ предыдущая
- …
- 73
- 74
- 75
- 76
- 77
- …
- следующая ›
- последняя »
