Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Следует отметить, что в криптосистемах Рабина и RSA используются одни и те же модули. Следовательно, на криптосистему Рабина распространяются мерь! предосторожности, касающиеся выбора модулей в криптосистеме RSA.
В заключение отметим, что атака "встреча посередине" позволяет взломать еще один вариант схемы шифрования Рабина. Шифрование, с = m2(mod N).
Расшифровка. Вычисление квадратного корня по модулю N.
Как и в учебной криптосистеме RSA, легкость факторизации небольших исходных сообщений (см. раздел 8.9) в криптосистеме Рабина обеспечивает успем атаки на основе перехвата, описанной в примере 8.3.
Глава 8. Шифрование — асимметричные методы
321
8.12 Криптосистема Эль-Гамаля (учебный вариант)
Эль-Гамаль разработал весьма остроумную криптосистему с открытым ключом [102], использующую однонаправленную функцию Диффи-Хеллмана с секретом. Работа Эль-Гамаля вызвала большой теоретический и практический интерес, который сохраняется до сих пор. В дальнейшей части книги мы рассмотрим два усовершенствованных варианта этой криптосистемы — схему шифрования Эль-Гамаля (глава 13) и криптосистему Эль-Гамаля с доказуемо высокой стойкостью (глава 15).
Одна из причин широкой популярности этой криптосистемы заключается в использовании задачи Диффи-Хеллмана, неразрешимость которой общепризнанна. Считается, что ее сложность эквивалентна сложности задачи о вычислении дискретного логарифма, которая, в свою очередь, является альтернативой задачи о разложении целого числа на простые множители, лежащей в основе криптосистем RSA и Рабина.
Криптосистема Эль-Гамаля описывается алгоритмом 8.3.
Покажем, что система, описанная алгоритмом 8.3, действительно является криптографической, т.е. в результате расшифровки Алиса восстанавливает тот самый исходный текст, который был послан Бобом.
Поскольку
с* = (gk)X = {ff е/е Л (modp),
[формула (8.12.2) действительно позволяет восстановить исходный текст т.
Для деления, выполняемого в формуле (8.12.2), необходимо применить рас->ширенный алгоритм Евклида (алгоритм 4.2), что в общем случае сопровождается (большими затратами, чем умножение. Однако Алиса может избежать деления, использовав следующие вычисления.
т«— C2C1"a:(modp).
^Пегко проверить, что эта схема расшифровки вполне работоспособна, однако слезет иметь в виду, что число —х в этой формуле на самом деле означает число р — 1 — х.
Пример 8.8. В примере 8.1 показано, что число 3 является первообразным корнем по модулю 43. Допустим, Алиса выбирает в качестве своего закрытого ключа число 7. Затем она вычисляет свой открытый ключ:
37 = 37(mod 43).
кПосле этого Алиса оглашает параметры своего открытого ключа (р,д,у) =
322
Часть III. Основные методы криптографии
Алгоритм 83. Криптосистема Эль-Гамаля
Ключ
Для создания ключа Алиса должна выполнить следующие действия.
1. Выбрать случайное простое число р.
2. Вычислить случайный мультипликативный порождающий элемент д б F*.
3. Извлечь случайное целое число х 6 u^p-i и считать его своим закрытым | ключом.
4. Вычислить открытый ключ
у <- ^(modp).
5. Использовать тройку (р, д, у) в качестве параметров открытого ключа и запомнить число х в качестве закрытого ключа.
(* Аналогично протоколу обмена ключами Диффи-Хеллмана системные пользо-а ватели могут использовать общие открытые параметры (р,д). *)
Шифрование
Для того чтобы послать Алисе секретное сообщение т < р, Боб извлекает слу^ чайное целое число к б и вычисляет зашифрованный текст (с\, с2):
{
Cl^(modp), (812
С2 <— jrm(modp).
Расшифровка
Для того чтобы расшифровать зашифрованный текст (ci, сг), Алиса вычисляет формулу
т ^|(modp). (8.12.2)1
ci
Предположим, что Боб шифрует исходное сообщение т — 14. Он извлекает случайный показатель степени, равный 26, и вычисляет следующие значения.
с2 = 15 = З26 (mod 43), с2 = 31 = 3626 х 14(mod3).
В результате возникает зашифрованный текст (15,31).
Для того чтобы расшифровать сообщение (15,31), Алиса находит следующее1 число.
14 = 31/36 = 31/157(mod43).
Глава 8. Шифрование — асимметричные методы
323
Для деления необходимо применить алгоритм 4.2. Однако Алиса не делает этого и вычисляет значение 14 иначе.
14 = 31 х 1542~7 = 31 х 6(mod 43). D
8.13 Уязвимость учебной криптосистемы Эль-Гамаля
Алгоритм шифрования (8.12.1) является вероятностным: он использует случайное число кЕ.ц^р-1. Допустим, что закрытый ключ Алисы х является числом, взаимно простым с числом р — 1. Тогда по теореме 5.2.3 (раздел 5.2.3) открытый ключ Алисы у = 5х(modp), как и число д, является порождающим элементом группы F*. Следовательно, число yfc(modp) пробегает всю группу F*, когда элемент к пробегает группу Zp_i. Поскольку умножение по модулю р является перестановкой над группой F*, для любого исходного сообщения т ? F* число С2 = ykm(modp) пробегает всю группу F*, когда число к пробегает группу Zp_i (теорема 6.6 из раздела 6.2.2). Итак, если к е u%p-i> то с2 6 [/F*. Это означает, что шифрование Эль-Гамаля равномерно распределяет исходное сообщение по всему пространству сообщений. Это — идеальное семантическое свойство алгоритма шифрования.
