Теория остатков (стр. 7 из 10)
Если показатель степени
в сравнении (2) взаимно прост с 
, то сравнение (2) имеет единственное решение. Для того, чтобы найти его, определим целое число 
, удовлетворяющее условиям 
Такое число существует, поскольку
, и притом единственно. Здесь и далее символом 
будет обозначаться наибольший общий делитель чисел 
и 
. Классическая теорема Эйлера, см. [3], утверждает, что для каждого числа 
, взаимно простого с 
, выполняется сравнение 
и, следовательно, 
Таким образом, в предположении
, единственное решение сравнения (2) может быть найдено в виде 
Если дополнительно предположить, что число
состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения . Действительно, обозначим 
и 
. Тогда делится на 
, а из (2) следует, что 
. Подобно (4), теперь легко находим 
. А кроме того, имеем 
. Получившиеся сравнения в силу 
дают нам (5).Функция (1), принятая в системе RSA, может быть вычислена достаточно быстро. Как это сделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к
функция 
вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства а) и б).Для вычисления функции (1) достаточно знать лишь числа
и . Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число , оно и является ``секретом'' , о котором речь идет в пункте в). Казалось бы, ничего не стоит, зная число , разложить его на простые сомножители, вычислить затем с помощью известных правил значение и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю ее историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до 
, и, деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно 
, находим, что при , записываемом 100 десятичными цифрами, найдется не менее 
простых чисел, на которые придется делить при разложении его на множители. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для разложения числа 
таким способом на простые сомножители потребуется не менее, чем 
лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно. Таким образом, название статьи М. Гарднера вполне оправдано.Авторы схемы RSA предложили выбирать число
в виде произведения двух простых множителей 
и 
, примерно одинаковых по величине. Так как 
то единственное условие на выбор показателя степени
в отображении (1) есть 
Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа
и . Перемножая их, оно находит число 
. Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (3) сообщения организатору этой системы, а организатор легко сможет дешифровывать их с помощью (5).Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (a=01, b=02, ..., z=26, пробел=00) была записана в виде целого числа
, а затем зашифрована с помощью отображения (1) при