Лабораторная работа №7

Тема:«Теория чисел: Простые числа»

Цель работы:

1.Ознакомление со структурой и принципом теории чисел.

2.Вычисления.

3. Составление отчета по лабораторной работе.

Теоритические сведения

Натуральное число называют простым, если оно не имеет других натуральных делителей, кроме и .

Простым числом будет наименьший, отличный от делитель целого .

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

Описание RSA

Алгоритм RSA состоит из следующих пунктов:

1. Выбрать простые числа p и q

2. Вычислить n = p * q

3. Вычислить m = (p - 1) * (q - 1)

4. Выбрать число d взаимно простое с m

5. Выбрать число e так, чтобы (e * d) modm= 1

Числа e и d являются ключами. Шифруемые данные необходимо разбить на блоки - числа от 0 до n - 1. Шифрование и дешифровка данных производятся следующим образом:

• Шифрование: b = a^emod n

• Дешифровка: a = b^d mod n

Алгоритм поиска простых чисел

N - нечетное число. Найти s и t, удовлетворяющие уравнению: N - 1 = 2s * t

Случайным образом выбрать число a, 1 <a<N

Если N делится на a, перейти к пункту 6

Если условие at = 1 (modN) выполняется, перейти к пункту 2

Если найдется такое k, 0 <= k<s, что a2k * t = -1 (modN), перейти к пункту 2

Число N - составное: выбрать другое нечетное число N, перейти к пункту 1

Если для какого-либо числа N проверено m чисел a, то математически доказанная вероятность того, что число является составным будет равняться 4-m (на самом деле вероятность намного меньше этого значения). Исходя из этого, считаю нужным для числа N, состоящего из p бит проверить p различных значений a. Если во время этого не обнаружится, что N - число составное, то вероятно (это моя личная оценка), что число N является простым.

Замечу, что число s не может быть большим количества бит в числе. Числа s и t находятся при помощи двоичного сдвига числа N - 1, пока младший разряд не станет 1. В результате s - количество сдвигов, t - число N - 1 после сдвига.

Нахождение взаимно простых чисел

На шаге 4 алгоритма RSA необходимо найти число d взаимно простое с m, т.е. не имеющее общих делителей с ним, кроме единицы. Число d должно быть меньше m. Для нахождения взаимно простых чисел используется алгоритм Евклида, который находит наибольший общий делитель двух чисел. Если найденный делитель больше единицы, то необходимо выбрать другое число d и повторить проверку.

Алгоритм Евклида

Алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух неотрицательных целых чисел основан на следующих свойствах этой величины. Пусть m и n - одновременно не равные нулю целые неотрицательные числа и пусть n меньше m .

Тогда если n=0, то НОД(m, n)=m, а если n>0, то для чисел m, n и r,

где r - остаток от деления m на n, выполняется равенство НОД (m, n)=НОД(n, r).

Например: НОД(15, 6)=НОД(6, 3)=НОД(3, 0)=3.

При вычислении наибольшего общего делителя с помощью алгоритма Евклида будет выполнено не более 5 * p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b. На практике алгоритм работает очень быстро.

Пример программы реализующий алгоритм Евклида приведен в приложении 2.

Выбрать число e.

В 5 пункте алгоритма RSA предполагается нахождение такого числа e, чтобы (e * d) modm= 1

Нахождения числа е можно организовать двумя способами:

1. Простым перебором, например, так

int p1q1=(p-1)*(p-1);

for (int i=3;i<p1q1;i++) if (((i*d)% p1q1)==1) {e1=i; i=p1q1;}

2. Решение уравнения a * x + b * y = 1

Для этого нужно использовать модифицированный алгоритм Евклида, который работает, только если числа d и m взаимно просты. Вычисление числа e сводится к решению уравнения m * x + d * e = 1 в натуральных числах. Число x не существенно.