ПРИМЕНЕНИЕ ТЕОРИИ ЧИСЕЛ В АЛГОРИТМЕ ШИФРОВАНИЯ RSA

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

Основные определения и теоремы

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

1. Криптография – наука о методах обеспечения конфиденциальности, целостности данных, аутентификации, а также невозможности отказа от авторства.

2. Простое число – натуральное (целое положительное) число ℕ, которое имеет ровно два различных натуральных делителя – единицу и самого себя.

3. Функция Эйлера φ(n) – функция, определенная на положительных числах, значение которой равно количеству натуральных чисел, меньших n и взаимно-простых с n.

Некоторые свойства функции Эйлера:

4. НОД(a, b) = d, d - наибольший общий делитель, если

1)

2)

5. Расширенный алгоритм Евклида – алгоритм, результатом работы которого является представление НОД(a, b) в виде соотношения Безу: НОД(a,b)=, где числа s,t – коэффициенты Безу.

Пусть a,b – целые числа и не равные одновременно нулю, и последовательность чисел  определена тем, что  - остаток от деления , - остаток от деления , … , - остаток от деления , а  делится на  нацело.

НОД

Теорема Эйлера. Если числа a и n взаимно простые, то , φ(n)- функция Эйлера.

Введение

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

Генерация ключей

1. Выберем два случайных простых числа p и q, такие что . Для обеспечения максимальной безопасности следует выбирать p и q равной длины.
2. Вычислим произведение  и функцию Эйлера .
3. Выберем случайное целое число e () взаимно простое со значением функции Эйлера , т.е. НОД(e, )=1. Пара {e,n} является открытым ключом алгоритма RSA.
4. Вычислим число d (), обратное к числу e по модулю . То есть . Пара {d,n} является закрытым ключом алгоритма RSA.

Шифрование

1. Для шифрования сообщения m необходимо разбить его на цифровые блоки длиной меньшей n.
2. Используя открытый ключ {e,n}, зашифруем каждый блок сообщения по формуле
3. Зашифрованное сообщение c будет состоять из блоков той же самой длины.

Дешифрование

1. Возьмем зашифрованный блок  и используя закрытый ключ {d,n} вычислим . Операция восстановления исходного сообщения основана на теореме Эйлера:
2. Преобразуем цифровые блоки в исходное сообщение.

Пример работы алгоритма

Генерация ключей:

1. Выберем два случайных простых числа p = 47, q = 53
2. Вычислим произведение , функция Эйлера
3. Выберем случайное целое число e = 71 (1<71<2392), НОД(71,2392) =1. Пара {71,2491} будет являться открытым ключом шифрования алгоритма RSA.

Используя расширенный алгоритм Евклида, вычислим число d, обратное к числу 71 по модулю 2392. В первых двух столбцах таблицы запишем числа, для которых необходимо найти наибольший общий делитель, для нашей задачи это A=2392 и B = 71. Третий столбец содержит остаток от деления A на B. Четвертый - целая часть от деления A на B. После заполнения первых четырех столбцов, наибольшим общим делителем будет являться последний остаток отличный от нуля, то есть НОД(2392,71) = 1. Начнем заполнять последние два столбца, содержащие X и Y с конца. В последнюю строчку запишем X=0 и Y=1. Затем, зная значения  и , последовательно найдем  и  по формулам: , , где A div B = [A/B] – целая часть от деления A на B.

Таблица 1.

Расширенный алгоритм Евклида

Искомым значение обратного элемента будет являться y = -977, . Пара {1415,2491} будет закрытым ключом алгоритма RSA.

Шифрование:

Закодируем с помощью алгоритма RSA сообщение: “cамарский университет”.

1. Заменим каждую букву её порядковым номером в алфавите.

Таблица 2.

Замена букв алфавита на порядковый номер

2. Используя открытый ключ {71,2491}, зашифруем каждый блок сообщения

Таблица 3.

Шифрование

3. Таким образом зашифрованное сообщение можно представить в виде последовательности блоков с = {2224, 1, 2358, 1, 1311, 2224, 285, 1639, 1289, 1062, 1381, 1561, 1639, 1889, 2104, 1311, 2224, 1639, 164, 2104, 164}.

Дешифрование:

1. Используя закрытый ключ {1415, 2491}, расшифруем последовательно каждый блок сообщения с = {2224, 1, 2358, 1, 1311, 2224, 285, 1639, 1289, 1062, 1381, 1561, 1639, 1889, 2104, 1311, 2224, 1639, 164, 2104, 164}.

Таблица 4.

Дешифрование

2. Преобразовав порядковые номера букв алфавита в текст, получим исходное сообщение: “самарский университет”.

Заключение

В настоящей работе были изучены некоторые определения и теоремы из теории чисел необходимые для понимания алгоритма RSA. Продемонстрировано практическое применение теории чисел, а также рассмотрены основные этапы работы алгоритма RSA.

Список литературы:

1. Додонова Н.Л. Конспект лекций по дисциплине алгебраические структуры и теория чисел. Самара, 2016
2. Шнайер, Б.М. Прикладная криптография/ Б.М. Шнайер - ТРИУМФ 2002. – 816 с.