В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 13 Алгоритм RSA Схема Райвеста–Шамира–Адлемана (Rivest–Shamir–Adleman — RSA), по- жалуй, наиболее популярная криптосистема с открытым ключом (во всяком случае это самая известная криптосистема с открытым ключом). Алгоритм RSA обеспечивает как цифровое подписывание, так и шифрование, что дела- ет его весьма универсальным средством. Кроме того, в основу RSA положе- на проблема выделения множителей больших чисел, которая на протяжении последних тысячелетий занимала лучшие умы человечества, а потому была подвергнута самому тщательному исследованию. 13.1 Введение Алгоритм RSA во многом схож с алгоритмом Диффи–Хеллмана (см. гла- ву 12, “Алгоритм Диффи–Хеллмана”), хотя между ними существует принци- пиальное различие. Алгоритм Диффи–Хеллмана (или сокращенно DH) осно- ван на использовании односторонней функции: предполагая, что p и g пуб- лично известны, мы можем найти g x (mod p ) по заданному x , но не можем найти x по заданному g x (mod p ) . Алгоритм RSA, в свою очередь, основан на использовании односторонней функции с лазейкой (trapdoor one-way func- tion) . Зная публично известные n и e , мы можем найти m e (mod n ) по задан- ному m , но не наоборот. При этом, зная, как n раскладывается на множители, выполнить обратную операцию очень легко. Разложение числа n на множи- тели и есть той самой “лазейкой”. Если мы знаем эту информацию, то можем легко выполнить обратное действие, а если не знаем, то не можем. Нали- чие лазейки позволяет применять RSA как для шифрования, так и в схеме цифровой подписи. Алгоритм RSA изобретен Рональдом Райвестом (Ronald Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adle- man) и впервые опубликован в 1978 году [80]. 245 |