Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.5.3. Схема RSA

Сообщения в схеме Ривеста-Шамира-Дцельмана (Riyest- Shamir-Adelman -RSA) сначала представляются как целые числа из интервала (0, n-1). Каждый пользователь выбирает собственное значение п и пару положительных целых чисел е и d описанным ниже способом. Пользователь помещает свой ключ шифрования, числовую пару (п, е), в общедоступный каталог. Ключ дешифрования состоит из числовой пары (n, d), в которой d держится в секрете. Шифрование сообщения М и дешифрование шифрованного текста С определяются следующим образом.

                   Шифрование: С = Е(М) = (М)епо модулю n                      (14.32)

                    Дешифрование:   М =D(C)= (C)d по модулю n

Это легко вычислить. Результатом каждой операции являются целые числа из интервала (0, n-1). В схеме RSA п получается в результате перемножения двух больших простых чисел р и q.                        

                                                        n=pq                                                   (14.33)

Несмотря на то что п общедоступно, p иq являются скрытыми из-за большой сложности в разложении п на множители. Затем определяется функция, называемая функцией Эйлера.

                                                                                   (14.34)

Параметр (п) имеет интересное свойство [12]: для любого целого X из интервала (0, n-1) и любого целого k имеет место, следующее соотношение.

                                                                           по модулю n                                   (14.35)

Следовательно, если все остальные арифметические действия выполняются по модулю п, арифметические действия в степени выполняются по модулю . Затем случайным образом выбирается большое целое число d, являющееся взаимно простым с ; это означает, что и d не должны иметь общих делителей, отличных от 1. Это записывается следующим образом.

                                       НОД [, d]= 1                                               (14.36)

В данном случае НОД означает «наибольший общий делитель». Этому условию будет удовлетворять любое простое число, большее наибольшего из (р, q). Далее находится целое е, 0 < е <,

                                  ed по модулю = 1,                                           (14.37)

что, вследствие равенства (14.35), равносильно выбору е и d, которые удовлетворяют следующему условию.

                                   X = Xed  по модулю n                                             (14.38)

Следовательно,

                                 E[D(X)] = D[E(X)]=X                                             (14.39)

и возможно корректное дешифрование. Один из возможных способов взлома шифра при данном ключе (п, е) — это разложить п на множители р и q, вычислить  = (р-1)(q-1) и вычислить d из равенства (14.37). Все это, за исключением разложения п на множители, представляет собой простые действия.

Схема RSA основывается на том, что два больших простых целых числа р и q легко выбрать и перемножить, но гораздо сложнее разложить на множители результат. Следовательно, произведение, как часть ключа шифрования, может быть сделано общедоступным, в то время как множители, которые могут «разоблачить» ключ дешифрования, соответствующий ключу шифрования, остаются скрытыми. Если длина каждого множителя составляет порядка 100 разрядов, умножение может быть выполнено в доли секунды, а изнурительное разложение на множители результата может потребовать миллиарды лет [2].



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.