Алгоритм безопасной передачи данных между пользователями в сети



Pdf көрінісі
бет11/22
Дата15.04.2023
өлшемі1,65 Mb.
#82715
түріДипломная работа
1   ...   7   8   9   10   11   12   13   14   ...   22
Байланысты:
Кузьмин А.А. ПМИб-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   ...   7   8   9   10   11   12   13   14   ...   22




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет