Введение в криптографию
[an error occurred while processing this directive]

Система шифрования RSA


В дальнейшем мы будем предполагать, что читатель знаком с элементарными фактами теории чисел. Тех же, кто хотел бы ознакомиться с ними или напомнить себе эти факты, мы отсылаем к книге [].

Пусть и натуральные числа. Функция , реализующая схему RSA, устроена следующим образом

(1)

Для дешифрования сообщения достаточно решить сравнение

(2)

При некоторых условиях на и это сравнение имеет единственное решение .

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента обозначается и равняется количеству целых чисел на отрезке от до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того, для любых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.

Если показатель степени в сравнении () взаимно прост с , то сравнение () имеет единственное решение. Для того, чтобы найти его, определим целое число , удовлетворяющее условиям

(3)

Такое число существует, поскольку , и притом единственно. Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера, см. [], утверждает, что для каждого числа , взаимно простого с , выполняется сравнение

и, следовательно,

(4)

Таким образом, в предположении , единственное решение сравнения () может быть найдено в виде

(5)

Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение () будет выполняться и без предположения . Действительно, обозначим и . Тогда делится на , а из () следует, что . Подобно (), теперь легко находим . А кроме того, имеем . Получившиеся сравнения в силу дают нам ().

Функция (), принятая в системе RSA, может быть вычислена достаточно быстро. Как это сделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к функция вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции () будут выполнены указанные выше свойства а) и б).




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]