Алгоритм безопасной передачи данных между пользователями в сети
жүктеу/скачать 1,65 Mb. Pdf көрінісі
|
Кузьмин А.А. ПМИб-1401
| 1.3.2.2 Алгоритм шифрования RSA
RSA – криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. RSA является первым алгоритмом шифрования с открытым ключом. Название системы происходит от первых букв фамилий ее авторов – Рональд Ривест, Ади Шамир и Леонард Адлеман – трех ученых из Массачусетского технологического института. После изучения опубликованной в 1976 году статьи Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии», которая заложила основы криптографии с открытым ключом, Ривест, Шамир и Адлеман приступили к поискам математической функции, которая позволяла бы реализовать модель системы, описанной в статье. После работы над более чем 40 возможными вариантами, ученым удалось обнаружить алгоритм, основывающийся на том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел. Для шифрования используется простая операция возведения в степень по модулю N. Для расшифрования необходимо вычислить функцию Эйлера от числа N, для этого необходимо знать разложение числа N на простые множители (в этом состоит задача факторизации). В криптографической системе RSA открытый и закрытый ключи состоят из пары целых чисел. Закрытый ключ хранится в секрете, а открытый сообщается другому участнику, или где-то публикуется[15]. Система базируется на следующих фактах: При известных числах b и d вычисление числа a из сравнения (2.1) По составному модулю n – это простая задача; 23 Вычисление неизвестного числа b при известных числах d и a из сравнения по составному модулю n (2.2) является трудной задачей; Если известно, что p и q простые числа и n = pq, то вычислить n легко, а найти разложение n на простые множители трудно; Если известно разложение n = pq на простые множители, то задача вычисления числа b из уравнения (2.3) выполнима. Теоретической основой криптосистемы RSA является теорема Эйлера: для любых натуральных и взаимно простых чисел n и a справедливо равенство (2.4) Здесь есть функция Эйлера – количество взаимно простых с n натуральных чисел от 1 до n. Из теории чисел известно, что если p и q простые числа, а n = pq, то (2.5) Кроме того, из теоремы Эйлера следует, что если некоторое число e взаимно просто с , то уравнение (2.6) или иначе (2.7) однозначно разрешается относительно d. Решение легко определяется расширенным алгоритмом Евклида. Итак, если известно, что 24 (2.8) а x – передаваемая информация, то справедливо равенство (2.9) Фактически, последнее соотношение является основой для формулировки системы RSA. жүктеу/скачать 1,65 Mb. Достарыңызбен бөлісу:
|