Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
В своей статье "Новые направления в криптографии" У. Диффи и М. Хеллман заявили: "Сегодня мы находимся накануне революции в криптографии". И они были правы. Своей публикацией они положили начало новому научному направлению. Начался интенсивный поиск односторонних функций с ловушкой с одновременным "прощупыванием" почвы для возможных их приложений. Как и следовало ожидать, на этом пути были взлеты и падения, но за прошедшие со дня публикации упомянутой статьи У. Диффи и М. Хеллмана двадцать лет односторонние функции с ловушкой заняли свое прочное и, пожалуй, наиболее перспективное место в современной криптографии. За это время были
77
ГЛАВА 5 найдены различные процедуры-функции, обладающие свойствами односторонних функций с ловушкой. Особенно продуктивными оказались попытки создания таких процедур в русле возведения чисел в большие степени по большому модулю, а также в русле создания кодов, обнаруживающих и исправляющих ошибки. Примерами алгоритмов, относящихся к первому направлению исследований, могут служить алгоритмы, предложенные Р. Ривестом, А. Шамиром, JI. Адлеманом, Т. Эль-Гамалем и другими [8, 13, 14]. Примерами же алгоритмов, относящихся ко второму направлению, могут служить алгоритмы Мак-Элиса, Нидер-райтера, Габидулина, Крука и других [4].
КРИПТОСИСТЕМА ОТКРЫТОГО ШИФРОВАНИЯ 4J- RSA
Из известных нам криптосистем, базирующихся на односторонних функциях с ловушкой, наибольшую популярность получила криптосистема RSA, относящаяся к первому направлению исследований - направлению возведения чисел в большие степени по модулю, также являющемуся большим числом. Свое название этот алгоритм получил по первым буквам фамилий его создателей (Rivest, Shamir, Adleman). Популярность алгоритма RSA, по-видимому, можно объяснить возможностью довольно элегантной реализации в рамках этого алгоритма как передачи конфиденциальных сообщений, так и организации электронной подписи. Механизм функционирования криптосистемы RSA заключается в следующем [4, 5, 6, 8, 9, 10, 14].
Каждый /-й абонент сети независимо от других абонентов генерирует два больших простых числа q(i) и p(i) и вычисляет число N(i) = = q(i)p{i). Порядок величин q(i) и p(i) определяется двумя соображениями:
- с увеличением этих чисел скорость шифрования, передачи по каналам связи и расшифрования конфиденциальных сообщений уменьшается;
- при прочих равных условиях с увеличением простых чисел q(i) и /;(/) криптостойкость системы RSA растет.
Обычно рекомендуется в качестве q(i) и p(i) выбрать простые числа, состоящие из 150+200 десятичных знаков каждое. Естественно, что эти рекомендации не следует принимать за догму, и в зависимости от эксплуатационной необходимости эти числа могут быть выбраны значительно меньшими, или, наоборот, большими. Более того, как мы убедимся ниже, криптостойкость системы RSA зависит не только от самих величин этих чисел, но и от их характера, и в этом смысле представляется актуальной задача оптимального выбора этих чисел, с тем, чтобы при приемлемых скоростных показателях обеспечить максимально возможный уровень криптостойкости. При выборе и проверке на простоту больших чисел обычно пользуются малой теоремой Ферма,
78 а именно, число S считают простым, если для произвольно выбранного числа M <S имеет место
Ms-] = Imod(S). (4.4)
Хотя условие (4.4) является лишь необходимым, но не достаточным условием, чтобы число S признать простым, тем не менее, после соответствующих допроверок теорема Ферма способствует выбору простых чисел q(i) и p(i). После определения числа /V(Z), Z-й абонент сети вычисляет число Эйлера от аргумента /V(Z), которое при простых </(/) и p(i) определяется по формуле
F(ZV(J)) = (^(I)-I)(P(I)-I). (4.5)
Далее 1-м абонентом выбирается произвольное достаточно большое и взаимно простое с F(N(i)) число e(i), после чего выбирается произвольное число d(i) такое, чтобы имело место
<?(0 • d{i) = lmod(F(A/(0)) (4.6)
(к вопросу о том. насколько правомочна произвольность выбора чисел <7(0 и /;(/), мы вернемся ниже). После того, как 1-м абонентом определены числа <7(/), /?(/), ZV(Z), F(N(i)), <?(') и d(i), он уже готов к приему конфиденциальных сообщений. Для этого он помещает в общедоступный справочник числа /V(Z) и е(і) в качестве открытого ключа шифрования, а число d(i) хранит у себя в качестве секретного ключа расшифрования. Поскольку при известных числах <?(Z) и ZV(Z) знания любого из чисел q(i),p(i) или F{N(i)) достаточно для того, чтобы вычислить число d(i) - секретный ключ расшифрования, то числа q(i), p(i) и F(N(i)) следует хранить в тайне, либо же вообще "уничтожить", поскольку далее они этому абоненту не нужны.
Для передачи конфиденциальных сообщений в адрес Z-го абонента пользователи сети предварительно архивируют передаваемые сообщения с помощью какого-либо общедоступного архиватора, затем полученный архивированный текст делят на фрагменты (если в этом есть необходимость) так, чтобы численное представление каждого из этих фрагментов оказалось меньше числа N(i). Численные представления X каждого из этих фрагментов и есть образы конфиденциальных сообщений, подлежащих передаче в адрес Z-ro абонента. Заметим, что процедура предварительной архивации текстов не является обязательной, хотя она и создает дополнительные сложности для злоумышленников, пытающихся рассекретить систему RSA. Предварительная архивация текстов полезна еще и потому, что в результате архивации исходные тексты уменьшаются, в результате чего уменьшается также число фрагментов, на которые делятся исходные тексты, с тем, чтобы численные представления каждого из этих фрагментов оказались меньше
