ДИПЛОМНАЯ РАБОТА на тему Применение алгоритма RSA при шифровании. Применение алгоритма rsa при шифровании потоков данных

• Название: Применение алгоритма rsa при шифровании потоков данных
• Дата: 18.12.2022
• Размер: 1.17 Mb.
• Имя файла: ДИПЛОМНАЯ РАБОТА на тему Применение алгоритма RSA при шифровании.doc
• Тип: Диплом; #851138
• страница: 6 из 7

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

В настоящее время известны детерминированные алгоритмы различ­ной сложности для доказательства простоты чисел. Мы остановимся по­дробнее на одном из них, предложенном в 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) алгоритма.

Сумма Якоби



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



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

,

где и - некоторый корень кубический из 1.

В 1984 г. было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел на квадраты простых чисел. В результате, например, выбрав число и взяв равным произведению простых чисел с условием, что делится на , получим