Описание алгоритма RSA

Методические указания и задания для выполнения лабораторных

Работ по теме «Алгоритм RSA».

К методическим указаниям прилагаются следующие файлы:

1. Программа «BCalc».

2. Программа «PS».

3. Варианты заданий к выполнению лабораторных работ.

4. Таблица простых чисел от 3 до . Формат файла: каждое простое число занимает 4 байта. Числа записаны в файле подряд.

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

Общая схема выглядит следующим образом:

1. Каждый пользователь генерирует пару ключей: один для шифрования, другой для дешифрования.

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

3. Если пользователь A собирается послать сообщение пользователю B, он шифрует сообщение открытым ключом пользователя B.

4. Когда пользователь B получает сообщение, он дешифрует его с помощью своего личного (секретного) ключа. Другой получатель не сможет дешифровать сообщение, поскольку личный ключ B знает только B.

Описание алгоритма RSA

Исходный текст должен быть переведен в числовую форму, этот метод считается известным. В результате этого текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке
[0, N – 1] (о выборе N — см. ниже). Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом x, .

Каждый абонент вырабатывает свою пару ключей. Для этого он генерирует два больших простых числа p и q, вычисляет произведение . Затем он вырабатывает случайное число e, взаимно простое со значением функции Эйлера от числа N, и находит число d из условия
e∙ d = 1(mod φ (N)). Так как , то такое число d существует и оно единственно. Пару (N, e) он объявляет открытым ключом и помещает в открытый доступ. Пара (N, d) является секретным ключом. Для расшифрования достаточно знать секретный ключ. Числа p, q, в дальнейшем не нужны, поэтому их можно уничтожить.

Пользователь A, отправляющий сообщение x абоненту B, выбирает из открытого каталога пару (N, e) абонента B и вычисляет шифрованное сообщение . Чтобы получить исходный текст, абонент B вычисляет . Так как , т. е. , где k – целое, то применяя теорему Эйлера, получим: следующее соотношение: .

Пример 1. Пусть p = 7, q = 17. Тогда N = 7∙ 17 = 119, Выбираем значение е: . Пусть в нашем случае e = 5. Находим d: . Получаем d = 77, так как 77∙ 5 = 4∙ 96 + 1. Открытый ключ (119, 5), личный ключ (119, 77). Пусть х = 19. Для зашифрования число 19 возводим в 5-ю степень по модулю 119, тогда имеем 19⁵ = 2 476 099 и остаток от деления 2 476 099 на 119 равен 66. Итак, y = 19⁵ mod 119 = 66, а расшифрование x = 66⁷ mod 119 = 19.