Xreferat.com » Рефераты по математике » Применение алгоритма RSA для шифрования потоков данных

Применение алгоритма RSA для шифрования потоков данных

src="http://xreferat.ru/image/54/1306457233_190.gif" alt="" width="1468" height="634" align="ABSMIDDLE" />, т. е. будет записываться вдвое боль­шим количеством цифр, чем исходное простое число . Заменив теперь число на найденное простое число и повторив с этим новым все указанные выше действия, можно построить еще большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятич­ными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз. можно построить простые числа нужной величи­ны.

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

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

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

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

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

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

3.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) .

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

  2. определяется не очень большое множество чисел, с которыми толь­ко и могут быть сравнимы простые делители . А именно, каждый простой делитель числа должен удовлетворять сравнению вида

, .

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

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

Сумма Якоби

определяется для двух характеров модулю . Если характеры имеют порядок , то соответствующая сумма Якоби принадлежит кольцу . Поскольку числа , участвующие в алгоритме, сравнительно невели­ки, то вычисления с суммами Якоби производятся в полях существенно меньшей степени, чем вычисления с суммами Гаусса. Это главная при­чина, по которой суммы Якоби предпочтительнее для вычислений. При выполняется классическое соотношение

связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в терминах сумм Якоби. Так. при и соответствующее сравнение, справедливое для простых , отлич­ных от 2,3,7, принимает вид

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: