Криптосистемы с открытым ключом. Алгоритм шифрования RSA

     Для этого можно случайным образом  выбирать число  , и проверять для него выполнимость соотношений

                                    

.                          (12)

     Если  при выбранном  эти соотношения выполняются, то, согласно следствию из теоремы 2, можно утверждать, что число простое. Если же эти условия нарушаются, нужно выбрать другое значение и повторять эти операции до тех пор, пока такое число не будет обнаружено.

     Предположим, что построенное число  действительно является простым. Зададимся вопросом, сколь долго придётся перебирать числа , пока не будет найдено такое, для которого будут выполнены условия (12). Заметим, что для простого числа первое условие (12), согласно малой теореме Ферма, будет выполняться всегда. Те же числа , для которых нарушается второе условие (12), удовлетворяют сравнению . Как известно, уравнение в поле вычетов имеет не более решений. Одно из них . Поэтому на промежутке имеется не более чисел, для которых не выполняются условия (12). Это означает, что, выбирая случайным образом числа на промежутке , при простом можно с вероятностью большей, чем , найти число , для которого будут выполнены условия теоремы 2, и тем доказать, что действительно является простым числом.

     Заметим, что построенное таким способом простое число  будет удовлетворять неравенству , т. е. будет записываться вдвое большим количеством цифр, чем исходное простое число . Заменив теперь число на найденное простое число и повторив с этим новым все указанные выше действия, можно построить еще большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз, можно построить простые числа нужной величины.

     Обсудим теперь некоторые теоретические  вопросы, возникающие в связи  с нахождением числа  , удовлетворяющего неравенствам , и такого, что - простое число. Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия , содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии. Опенка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю. В. Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии не превосходит , где - некоторая достаточно большая абсолютная постоянная.

     Таким образом, в настоящее время никаких  теоретических гарантий для существования  простого числа  не существует. Тем не менее, опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии встречаются достаточно близко к её началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел с условием, что число также простое, т. е. простым является уже первый член прогрессии.

     Очень важен в связи с описываемым  методом построения простых чисел  также вопрос о расстоянии между  соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором число составное, можно следующее значение взять равным и действовать так далее, пока не будет найдено простое число . И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число . Перебор чисел до того момента, как мы наткнемся на простое число окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами и в натуральном ряде доказано лишь, что , что, конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера (1936 г.), что , дающая вполне приемлемую опенку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно.

     В качестве итога обсуждения в этом пункте подчеркнём следующее: если принять  на веру, что наименьшее простое  число, а также расстояние между  соседними простыми числами в прогрессии при оцениваются величиной , то описанная схема построения больших простых чисел имеет полиномиальную опенку сложности. Кроме того, несмотря на отсутствие теоретических опенок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно. На обычном персональном компьютере без особых затрат времени строятся таким способом простые числа порядка .

     Конечно, способ конструирования простых  чисел для использования в  схеме RSA должен быть массовым, а сами простые числа должны быть в каком-то смысле хорошо распределёнными. Это вносит ряд дополнительных осложнений в работу алгоритмов.

     Наконец, отметим, что существуют методы построения больших простых чисел, использующие не только простые делители , но и делители чисел . В основе их лежит использование последовательностей целых чисел, удовлетворяющих линейным рекуррентным уравнениям различных порядков. Отметим, что последовательность , члены которой присутствуют в формулировке малой теоремы Ферма, составляет решение рекуррентного уравнения первого порядка . 

     2.3 Проверка большого числа на простоту

     Есть  некоторое отличие в постановках  задач предыдущего и настоящего пунктов. Когда мы строим простое число , мы обладаем некоторой дополнительной информацией о нем, возникающей в процессе построения. Например, такой информацией является знание простых делителей числа . Эта информация иногда облегчает доказательство простоты .

     В этом пункте мы предполагаем лишь, что нам задано некоторое число , например, выбранное случайным образом на каком-то промежутке, и требуется установить его простоту, или доказать, что оно является составным. Эту задачу за полиномиальное количество операций решает указанный в п. 3 алгоритм Миллера. Однако, справедливость полученного с его помощью утверждения зависит от недоказанной расширенной гипотезы Римана. Если число выдержало испытания алгоритмом 5 для 100 различных значений параметра , то, по-видимому, можно утверждать, что оно является простым с вероятностью большей, чем . Эта вероятность очень близка к единице, однако всё же оставляет некоторую тень сомнения на простоте числа . В дальнейшем в этом пункте мы будем считать, что заданное число является простым, а нам требуется лишь доказать это.

     В настоящее время известны детерминированные  алгоритмы различной сложности для доказательства простоты чисел. Мы остановимся подробнее на одном из них, предложенном в 1983 г. в совместной работе Адлемана. Померанца и Рамели. Для доказательства простоты или непростоты числа этот алгоритм требует арифметических операций. Здесь - некоторая положительная абсолютная постоянная. Функция хоть и медленно, но всё же возрастает с ростом , поэтому алгоритм не является полиномиальным. Но всё же его практические реализации позволяют достаточно быстро тестировать числа на простоту. Существенные усовершенствования и упрощения в первоначальный вариант алгоритма были внесены в работах X. Ленстры и А. Коена. Мы будем называть описываемый ниже алгоритм алгоритмом Адлемана - Ленстры.

     В основе алгоритма лежит использование  сравнений типа малой теоремы Ферма, но в кольцах целых чисел круговых полей, т. е. полей. порождённых над полем числами - корнями из 1. Пусть - простое нечётное число и — первообразный корень по модулю , т. е. образующий элемент мультипликативной группы поля , которая пиклична. Для каждого целого числа , не делящегося на , можно определить его индекс, , называемый также дискретным логарифмом, с помощью сравнения . Рассмотрим далее два простых числа , с условием, что делится на , но не делится на .

     Следующая функция, определённая на множестве  целых чисел.

                         

является  характером по модулю и порядок этого характера равен .

     Сумма

называется  суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.

     Теорема 3. Пусть - нечетное простое число, . Тогда в кольце выполняется сравнение

.

     Если  при каких-либо числах сравнение из теоремы 3 нарушается. можно утверждать, что составное число. В противном случае, если сравнение выполняется, оно даёт некоторую информацию о возможных простых делителях числа . Собрав такую информацию для различных , в конце концов, удаётся установить, что имеет лишь один простой делитель и является простым.

     В случае легко проверить, что сравнение из теоремы 3 равносильно хорошо известному в элементарной теории чисел сравнению

, (13)

где - так называемый символ Якоби. Хорошо известно также, что последнее сравнение выполняется не только для простых , но и для любых целых , взаимно простых с . Заметим также, что для вычисления символа Якоби существует быстрый алгоритм, основанный на законе взаимности Гаусса и. в некотором смысле, подобный алгоритму Евклида вычисления наибольшего общего делителя. Следующий пример показывает. каким образом выполнимость нескольких сравнений типа (13) даёт некоторую информацию о возможных простых делителях числа .

     Пример (X. Ленстра). Пусть — натуральное число, . для которого выполнены сравнения

                                             

,        (14)

а кроме  того с некоторым целым числом имеем

                                                

.                                            (15)

     Как уже указывалось, при простом сравнения (14) выполняются для любого , взаимно простого с , а сравнение (15) означает, что есть первообразный корень по модулю . Количество первообразных корней равно , т. е. достаточно велико. Таким образом, число с условием (15) при простом может быть найдено достаточно быстро с помощью случайного выбора и последующей проверки (15).

     Докажем, что из выполнимости (14-15) следует, что  каждый делитель числа удовлетворяет одному из сравнений

                                          

или .                   (16)

Не уменьшая общности, можно считать, что  - простое число. Введем теперь обозначения , где и - нечётные числа. Из (15) и сравнения следует, что . Далее, согласно (14). выполняются следующие сравнения

,

означающие (в силу того, что символ Якоби  может равняться лишь -1 или +1), что

.

При это равенство означает, что при , и, следовательно, . Если же , то имеем   и . Этим (16) доказано.

     Информация  такого рода получается и в случае произвольных простых чисел и с указанными выше свойствами.

     Опишем схему алгоритма Адлемана - Ленстры для проверки простоты :

   1 выбираются различные простые числа и различные простые нечётные такие, что

      1) для каждого все простые делители числа содержатся 
среди и не делятся на квадрат простого числа;

1)  .

2. для каждой пары выбранных чисел , проводятся тесты, подобные сравнению из теоремы 3. Если не удовлетворяет какому-либо из 
   этих тестов - оно составное. В противном случае
3. определяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители . А именно, каждый простой делитель числа должен удовлетворять сравнению вида

,  .

   4) проверяется, содержит ли найденное множество делители . Если при этом делители не обнаружены, утверждается, что - простое 
число.

       Если  число  составное, оно обязательно имеет простой делитель , меньший , который сам содержится среди возможных остатков. Именно на этом свойстве основано применение пункта 4) алгоритма.

       Сумма Якоби