Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: XLV Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 29 сентября 2016 г.)

Наука: Математика

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Швейкин В.В., Завгородний С.Д., Танаев И.В. [и др.] ПРИМЕНЕНИЕ ТЕОРИИ ЧИСЕЛ В АЛГОРИТМЕ ШИФРОВАНИЯ RSA // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. XLV междунар. студ. науч.-практ. конф. № 8(44). URL: https://sibac.info/archive/technic/8(44).pdf (дата обращения: 29.03.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

ПРИМЕНЕНИЕ ТЕОРИИ ЧИСЕЛ В АЛГОРИТМЕ ШИФРОВАНИЯ 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.

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

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амарский университет”.

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

Таблица 2.

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

 ’с’ = 19

 ’а’ = 1

 ’м’ = 14

 ’а’ = 1

 ’р’ = 18

 ’с’ = 19

 ’к’ = 12

 ’и’ = 10

 ’й’ = 11

 ‘ ‘ = 34

 ’у’ = 21

 ’н’ = 15

 ’и’ = 10

 ’в’ = 3

 ’е’ = 6

 ’р’ = 18

 ’с’ = 19

 ’и’ = 10

 ’т’ = 20

 ’е’ = 6

 ’т’ = 20

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

Таблица 3.

Шифрование

2224

1

2358

1

1311

2224

285

1639

1289

1381

1561

1889

2104

2224

1639

164

2104

164

  1. Таким образом зашифрованное сообщение можно представить в виде последовательности блоков с = {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.

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

19

1

14

1

18

19

12

10

11

=34

21

15

=10

3

6

=18

19

10

20

6

20

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

Заключение

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

 

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

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

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.