Отчетность по лабораторной работе. Задания, выполненные в рабочей тетради согласно варианту (с подробным описанием хода

Задания, выполненные в рабочей тетради согласно варианту (с подробным описанием хода решения).

ЛАБОРАТОРНАЯ работа № 5

Реализация элементов криптосистемы RSA

Цель работы: формирование умений шифрования с использованием метода асимметрического шифрования RSA.

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

RSA относится к так называемым асимметричным алгоритмам, у которых ключ шифрования не совпадает с ключом дешифровки. Один из ключей доступен всем (так делается специально) и называется открытым ключом, другой хранится только у его хозяина и неизвестен никому другому. С помощью одного ключа можно производить операции только в одну сторону. Если сообщение зашифровано с помощью одного ключа, то расшифровать его можно только с помощью другого. Имея один из ключей невозможно (очень сложно) найти другой ключ, если разрядность ключа высока.

Описание RSA

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

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

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

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

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

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

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

ü Шифрование: b = a^e (mod n)

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

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

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

В первом пункте алгоритма RSA сказано, что необходимо выбрать два простых числа p и q. Простой способ - деление предполагаемого простого числа на все числа меньшие его не работоспособен уже с 32-битными числами (требуется очень много времени на выполнение).

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

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

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

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

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

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

5. Если найдется такое k, 0 <= k < s, что a^{2k * t} = -1 (mod N), перейти к пункту 2

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

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

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

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

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

1. Исходные числа a и b

2. Вычислить r - остаток от деления a на b: a=b*q+r

3. Если r = 0, то b - искомое число (наибольший общий делитель), конец

4. Заменить пару чисел <a, b> парой <b, r>, перейти к пункту 2

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

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

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

Алгоритм решения уравнения a * x + b * y = 1

1. Необходимо определить матрицу E =

2. Вычислить r - остаток от деления a на b: a=b*q+r

3. Если r = 0, то второй столбец матрицы дает решение: , конец

4. E = E *

5. Заменить пару чисел <a, b>, парой <b, r>, перейти к пункту 2

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