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

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

/> эта вероятность, конечно, еще меньше. Более тонкий анализ с использованием опенок А. Вейля для сумм харак­теров показывает, что вероятность для многочлена не распасться на множители при однократном проходе шагов алгоритма 1-4. не пре­восходит . Здесь постоянная в зависит от .

Если в сравнении (8) заменить простой модуль составным моду­лем , то задача нахождения решений соответствующего сравнения ста­новится намного более сложной. Известные алгоритмы её решения осно­ваны на сведении сравнения к совокупности сравнений (8) по простым модулям — делителям , и. следовательно, они требуют разложения чи­сла то на простые сомножители, что, как уже указывалось, является до­статочно трудоемкой задачей.


3. КАЧЕСТВЕННАЯ ТЕОРИЯ АЛГОРИТМА RSA


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

. (9)

Если же при каком-то это сравнение нарушается, можно утверждать, что - составное. Проверка (9) не требует больших вычислений, это следует из алгоритма 1. Вопрос только в том, как найти для составного целое число , не удовлетворяющее (9). Можно, например, пытаться найти необходимое число , испытывая все целые числа подряд, начиная с 2. Или попробовать выбирать эти числа случайным образом на отрезке .

К сожалению, такой подход не всегда даёт то, что хотелось бы. Име­ются составные числа , обладающие свойством (9) для любого целого с условием . Такие числа называются числами Кармайкла. Рассмотрим, например, число . Так как 560 делится на каждое из чисел 2, 10, 16, то с помощью малой теоремы Ферма легко проверить, что 561 есть число Кармайкла. Можно доказать, что любое из чисел Кармайкла имеет вид , где все простые различны, причем делится на каждую разность . Лишь недавно, была решена проблема о бесконечности множества таких чисел.

В 1976 г. Миллер предложил заменить проверку (9) проверкой несколь­ко иного условия. Если - простое число, , где нечётно, то согласно ма­лой теореме Ферма для каждого с условием хотя бы одна из скобок в произведении

делится на . Обращение этого свойства можно использовать, чтобы от­личать составные числа от простых.

Пусть - нечётное составное число, , где нечётно. Назовем целое число , , «хорошим» для , если нарушается одно из двух условий:

1) не делится на ;

2) или существует целое , , такое, что

.

Из сказанного ранее следует, что для простого числа не существует хороших чисел . Если же составное число, то, как доказал Рабин, их существует не менее .

Теперь можно построить вероятностный алгоритм, отличающий со­ставные числа от простых.

3.1. Алгоритм, доказывающий непростоту числа

  1. Выберем случайным образом число , , и проверим для
    этого числа указанные выше свойства 1) и 2) п.2.

  2. Если хотя бы одно из них нарушается, то число составное.

  3. Если выполнены оба условия 1) и 2) п.2, возвращаемся к шагу 1.

Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей . А вероятность не определить его после повторений не превосходит . т. е. убывает очень быстро.

Миллер предложил детерминированный алгоритм определения состав­ных чисел, имеющий сложность , однако справедливость его ре­зультата зависит от недоказанной в настоящее время так называемой расширенной гипотезы Римана. Согласно этому алгоритму достаточно проверить условия 1) и 2) п.2 для всех целых чисел , . Если при каком-нибудь из указанного промежутка нарушается одно из условий а) или б), число составное. В противном случае оно будет простым или степенью простого числа. Последняя возможность, конечно, легко проверяется.

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

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

В 1952 г. Анкени с помощью расширенной гипотезы Римана доказал, что для каждого простого числа существует квадратичный невычет , удовлетворяющий неравенствам . Константа 70 была со­считана позднее. Именно это утверждение и лежит в основе алгоритма Миллера. В 1957 г. Берджесс доказал существование такого невычета без использования расширенной гипотезы Римана, но с худшей оценкой , справедливой при любом положительном и , большем некоторой границы, зависящей от.

Алгоритм Миллера принципиально отличается от алгоритма 2.1., так как полученное с его помощью утверждение о том, что число - со­ставное, опирается на недоказанную расширенную гипотезу Римана и по­тому может быть неверным. В то время как вероятностный алгоритм 2.1. даёт совершенно правильный ответ для составных чисел. Несмотря на отсутствие оценок сложности, на практике он работает вполне удовле­творительно.

3.2. Нахождение больших простых чисел

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

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

. (10)

Тогда каждый простой делитель числа удовлетворяет сравнению

.

Доказательство. Пусть - простой делитель числа , a - не­который делитель . Из условий (10) следует, что в поле вычетов спра­ведливы соотношения

. (11)

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

Следствие. Если выполнены условия теоремы 2 и , то - простое число.

Действительно, пусть равняется произведению не менее двух про­стых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем . Но тогда . Противоречие и доказывает следствие.

Покажем теперь, как с помощью последнего утверждения, имея боль­шое простое число , можно построить существенно большее простое число . Выберем для этого случайным образом чётное число на про­межутке и положим . Затем проверим число на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что - составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число , выдержавшее испытания алго­ритмом 5 достаточно много раз. В этом случае появляется надежда на то, что - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2.

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

. (12)

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

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

Заметим, что построенное таким способом простое число будет удовлетворять неравенству

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

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

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

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