Алгоритм RSA. Жданов О.Н - 6 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

6
но знать секретный ключ. Числа p, q,
(
)
N
ϕ
в дальнейшем не нужны, поэтому
их можно уничтожить.
Пользователь A, отправляющий сообщение x абоненту B, выбирает из от-
крытого каталога пару (N, e) абонента B и вычисляет шифрованное сообщение
(
)
mod
e
yx N= . Чтобы получить исходный текст, абонент B вычисляет
(
)
mod
d
yN. Так как mod1( ( ))ed N⋅≡ ϕ , т. е. ( ) 1ed N k
ϕ
⋅
=⋅+, где k – целое, то
применяя теорему Эйлера, получим: следующее соотношение:
() 1 ()
mod() ( ) ( )
Nk N
deded k
yx xx x xx N
ϕ⋅+ ϕ
≡≡≡ ≡ ⋅≡ .
Пример 1. Пусть p = 7, q = 17. Тогда N = 7·17 = 119, ( ) 96.N
ϕ
= Выбираем
значение е: 96, ( , 96) 1ee<=. Пусть в нашем случае e = 5. Находим d:
mod1/ ( 96)de= . Получаем d = 77, так как 77·5 = 4·96 + 1. Открытый ключ
(119,5), личный ключ (119,77). Пусть х = 19. Для зашифрования число 19 возво-
дим в 5-ю степень по модулю 119, тогда имеем 19
5
= 2 476 099 и остаток от де-
ления 2 476 099 на 119 равен 66. Итак, y = 19
5
mod 119 = 66, а расшифрование
x = 66
7
mod 119 = 19.
О вычислениях
Как шифрование, так и расшифрование в RSA предполагают использова-
ние операции возведения целого числа в целую степень по модулю N. Если воз-
ведение в степень выполнять непосредственно с целыми числами и только по-
том проводить сравнение по модулю N, то промежуточные значения окажутся
огромными. Здесь можно воспользоваться свойствами арифметики в классах
вычетов
mod mod mod mod()() ()aNbN NabN⋅=. Таким образом, можно рас-
смотреть промежуточные результаты по модулю N. Это делает вычисления
практически выполнимыми.
О стойкости RSA
Безопасность алгоритма RSA основана на трудоемкости разложения на
множители больших чисел. Современное состояние технических средств раз-
ложения на множители таково, что число, содержащее 193 десятичных знака,
факторизовано в 2005 г. Следовательно, выбираемое N должно быть больше.
Большинство общепринятых алгоритмов вычисления простых чисел p и q носят
вероятностный характер.
О выборе чисел p и q
Для работы алгоритма RSA нужны простые числа. Наиболее приемлемым
является генерация случайных чисел и последующая проверка их на простоту.
Существуют вероятностные тесты, определяющие с заданной степенью досто-
верности факт простоты числа. Возникает вопрос, что произойдет, если числа
окажутся составными? Можно свести вероятность такого события до приемле-
мого минимума, используя тесты на простоту
. Кроме того, если такое событие

Страницы