ВУЗ:
Составители:
Рис. 3.3. Процесс расшифрования и аутентификации
Рассмотренная криптосистема является семантически стойкой и неде-
лимой. В частности, неделимость обеспечивается тем, что значение g
u
по-
дается на вход функции хэширования. Если этого не сделать, то возможна
атака, подобная атаке на шифр Эль-Гамаля.
Эффективность предложенной схемы по существу та же, что и у шиф-
ра Эль-Гамаля, т.е. для зашифрования требуются две операции возведения
в степень, а для расшифрования – одна. Тем самым для больших сообще-
ний скорость шифрования будет определяться скоростью работы симмет-
ричного шифра и алгоритма вычисления кода аутентификации сообщения.
3.3.3. КРИПТОСИСТЕМА РИВЕСТА–ШАМИРА–АДЛЕМАНА
В настоящее время наиболее развитым методом криптографической
защиты информации с известным ключом является RSA, названный так по
начальным буквам фамилий ее изобретателей (Rivest, Shamir и Adleman) и
представляющую собой криптосистему, стойкость которой основана на
сложности решения задачи разложения числа на простые сомножители..
Перед тем как приступить к изложению концепции метода RSA, необходи-
мо определить некоторые термины.
Под простым числом будем понимать такое число, которое делится
только на единицу и на само себя. Взаимно простыми числами будем назы-
вать такие числа, которые не имеют ни одного общего делителя, кроме
единицы.
Под результатом операции i mod j будем считать остаток от целочис-
ленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала
сгенерировать открытый и секретный ключи, выполнив следующие шаги:
•
выберем два очень больших простых числа p и q;
•
определим n как результат умножения p на q (n = p × q);
•
выберем большое случайное число, которое назовем 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}:
Страницы
- « первая
- ‹ предыдущая
- …
- 54
- 55
- 56
- 57
- 58
- …
- следующая ›
- последняя »
