Статья опубликована в рамках: XLV Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 29 сентября 2016 г.)
Наука: Математика
Скачать книгу(-и): Сборник статей конференции
дипломов
ПРИМЕНЕНИЕ ТЕОРИИ ЧИСЕЛ В АЛГОРИТМЕ ШИФРОВАНИЯ 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 с открытым ключом, безопасность которого основана на трудности задачи факторизации, то есть разложении числа на простые множители.
Генерация ключей
- Выберем два случайных простых числа p и q, такие что
. Для обеспечения максимальной безопасности следует выбирать p и q равной длины.
- Вычислим произведение
и функцию Эйлера
.
- Выберем случайное целое число e (
) взаимно простое со значением функции Эйлера
, т.е. НОД(e,
)=1. Пара {e,n} является открытым ключом алгоритма RSA.
- Вычислим число d (
), обратное к числу e по модулю
. То есть
. Пара {d,n} является закрытым ключом алгоритма RSA.
Шифрование
- Для шифрования сообщения m необходимо разбить его на цифровые блоки длиной меньшей n.
- Используя открытый ключ {e,n}, зашифруем каждый блок сообщения по формуле
- Зашифрованное сообщение c будет состоять из блоков
той же самой длины.
Дешифрование
- Возьмем зашифрованный блок
и используя закрытый ключ {d,n} вычислим
. Операция восстановления исходного сообщения основана на теореме Эйлера:
- Преобразуем цифровые блоки в исходное сообщение.
Пример работы алгоритма
Генерация ключей:
- Выберем два случайных простых числа p = 47, q = 53
- Вычислим произведение
, функция Эйлера
- Выберем случайное целое число 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.
Расширенный алгоритм Евклида
A |
B |
A mod B |
[A/B] |
X |
Y |
2392 |
71 |
49 |
33 |
29 |
-977 |
71 |
49 |
22 |
1 |
-20 |
29 |
49 |
22 |
5 |
2 |
9 |
-20 |
22 |
5 |
2 |
4 |
-2 |
9 |
5 |
2 |
1 |
2 |
1 |
-2 |
2 |
1 |
0 |
2 |
0 |
1 |
Искомым значение обратного элемента будет являться y = -977, . Пара {1415,2491} будет закрытым ключом алгоритма RSA.
Шифрование:
Закодируем с помощью алгоритма RSA сообщение: “cамарский университет”.
- Заменим каждую букву её порядковым номером в алфавите.
Таблица 2.
Замена букв алфавита на порядковый номер
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- Используя открытый ключ {71,2491}, зашифруем каждый блок сообщения
Таблица 3.
Шифрование
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- Таким образом зашифрованное сообщение можно представить в виде последовательности блоков с = {2224, 1, 2358, 1, 1311, 2224, 285, 1639, 1289, 1062, 1381, 1561, 1639, 1889, 2104, 1311, 2224, 1639, 164, 2104, 164}.
Дешифрование:
- Используя закрытый ключ {1415, 2491}, расшифруем последовательно каждый блок сообщения с = {2224, 1, 2358, 1, 1311, 2224, 285, 1639, 1289, 1062, 1381, 1561, 1639, 1889, 2104, 1311, 2224, 1639, 164, 2104, 164}.
Таблица 4.
Дешифрование
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- Преобразовав порядковые номера букв алфавита в текст, получим исходное сообщение: “самарский университет”.
Заключение
В настоящей работе были изучены некоторые определения и теоремы из теории чисел необходимые для понимания алгоритма RSA. Продемонстрировано практическое применение теории чисел, а также рассмотрены основные этапы работы алгоритма RSA.
Список литературы:
- Додонова Н.Л. Конспект лекций по дисциплине алгебраические структуры и теория чисел. Самара, 2016
- Шнайер, Б.М. Прикладная криптография/ Б.М. Шнайер - ТРИУМФ 2002. – 816 с.
дипломов
Оставить комментарий