Описание алгоритма RSA
В 1978 г. появилась работа, в которой РонРайвест (RonRivest), Ади Шамир (AdiShamir) и Лен Адлеман (LenAdleman) предложили алгоритм с открытым ключом. Схема Райвеста–Шамира–Адлемана (RSA) получила широкое распространение. Опишем процесс шифрования. Исходный текст должен быть переведен в числовую форму, этот метод считается известным. В результате этого текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке [0, N – 1] (о выборе N — см. ниже). Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом x, 0 £ x £ N -1. Каждый абонент вырабатывает свою пару ключей. Для этого он генерирует два больших простых числа p и q, вычисляет произведение N = p · q. Затем он вырабатывает случайное число e, взаимно простое со значением функции Эйлера от числа N, j (N)=(p -1)·(q -1) и находит число d из условия e ∙ d º 1(mod φ (N)). Так как (e, φ (N))=1, то такое число d существует и оно единственно. Пару (N, e) он объявляет открытым ключом и помещает в открытый доступ. Пара (N, d) является секретным ключом. Для расшифрования достаточно знать секретный ключ. Числа p, q, φ (N) в дальнейшем не нужны, поэтому их можно уничтожить. Пользователь A, отправляющий сообщение x абоненту B, выбирает из открытого каталога пару (N, e) абонента B и вычисляет шифрованное сообщение y = xe (mod N). Чтобы получить исходный текст, абонент B вычисляет yd (mod N). Так как e ∙ d º 1(mod φ (N)), т. е. e ∙ d = φ (N)· k +1, где k – целоечисло, то применяя теорему Эйлера, получим: следующее соотношение: Пример 1. Пусть p = 7, q = 17. Тогда N = 7∙ 17 = 119, φ (N)=96. Выбираем значение е: e < 96, НОД (e, 96) =1. Пусть в нашем случае e = 5. Находим d: d =1/ e (mod 96). Получаем d = 77, так как 77∙ 5 = 4∙ 96 + 1. Открытый ключ (119, 5), личный ключ (119, 77). Пусть х = 19. Для зашифрования число 19 возводим в 5-ю степень по модулю 119, тогда имеем 195 = 2 476 099 и остаток от деления 2 476 099 на 119 равен 66. Итак, y = 195 mod 119 = 66. Прирасшифрованииполучим x =667mod119=19. Как шифрование, так и расшифрование в RSA предполагают использование операции возведения целого числа в целую степень по модулю N. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю N, то промежуточные значения окажутся огромными. Здесь можно воспользоваться свойствами арифметики в классах вычетов (a mod N)·(b mod N) mod N =(a·b) mod N. Таким образом, можно рассмотреть промежуточные результаты по модулю N. Это делает вычисления практически выполнимыми.
|
.
