Практическая реализация алгоритма шифрования RSA

Введение в асимметричную криптографию и историю RSA

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

Проблема симметричного шифрования

До середины 1970-х годов вся криптография была симметричной. Это означает, что для зашифровки и расшифровки сообщения использовался один и тот же секретный ключ.

Представьте, что Алиса хочет отправить Бобу секретное письмо в сундуке. Она вешает на сундук замок и закрывает его своим ключом. Чтобы Боб мог открыть сундук, Алиса должна как-то передать ему этот же ключ. Если она отправит ключ почтой, его могут перехватить. Если они встретятся лично, то проблема решена, но в цифровом мире (интернет) личная встреча для обмена ключами с каждым сайтом невозможна.

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

Революция: Асимметричная криптография

В 1976 году Уитфилд Диффи и Мартин Хеллман предложили концепцию криптографии с открытым ключом. Идея заключалась в использовании пары ключей:

Открытый ключ (Public Key): Доступен всем. Используется для шифрования.

Закрытый ключ (Private Key): Хранится только у владельца. Используется для расшифровки.

Вернемся к аналогии с сундуком. В асимметричной системе Боб раздает всем желающим свои открытые замки (открытый ключ). Алиса берет замок Боба, вешает его на сундук и защелкивает. Теперь открыть сундук может только Боб, так как ключ от этого замка есть только у него. Даже сама Алиса не сможет открыть сундук после того, как защелкнула замок.

> В асимметричной криптографии и алгоритме RSA, в частности, публичный и приватный ключи являются двумя частями одного целого и неразрывны друг с другом. > > habr.com

История создания RSA

Хотя Диффи и Хеллман предложили концепцию, у них не было готовой реализации алгоритма, который позволял бы эффективно шифровать данные и создавать цифровые подписи. Эту задачу решили трое ученых из Массачусетского технологического института (MIT): Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman).

Поиск односторонней функции

Ривест и Шамир (информатики) предлагали различные функции, а Адлеман (математик) искал в них уязвимости. Они искали одностороннюю функцию с лазейкой (trapdoor function). Это такая математическая операция, которую легко выполнить в одну сторону, но практически невозможно обратить назад без знания специального секрета (лазейки).

Согласно ru.wikipedia.org, прорыв случился в апреле 1977 года после вечеринки в честь Песаха. Рон Ривест, не в силах уснуть, всю ночь формализовывал идею, и к утру статья была практически готова. Алгоритм получил название по первым буквам фамилий создателей: RSA.

Секретное открытие GCHQ

Интересный исторический факт: аналогичная система была изобретена еще в 1973 году английским математиком Клиффордом Коксом, работавшим в британской разведке (GCHQ). Однако из-за грифа секретности его работа не была опубликована и стала известна общественности только в 1997 году. Поэтому лавры первенства и название алгоритма достались ученым из MIT.

Публикация в Scientific American

Первое широкое описание RSA появилось в августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American. Авторы предложили читателям расшифровать сообщение, зашифрованное с помощью RSA, пообещав награду в 100 долларов. Задача, известная как RSA-129, была решена только спустя 17 лет, в 1994 году, что продемонстрировало высокую надежность алгоритма на тот момент.

Математическая основа RSA

Безопасность RSA держится на сложности факторизации больших чисел.

Легко умножить два простых числа:

Где и — простые множители, а — их произведение.

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

Основные операции

В RSA все вычисления происходят по модулю . Операция «по модулю» (обозначается как ) — это нахождение остатка от деления.

Пример:

Где — делимое, — делитель, а — остаток ().

#### Шифрование

Чтобы зашифровать сообщение (представленное как число), Алиса использует открытый ключ получателя (пару чисел и ) и вычисляет шифротекст :

Где: * — шифротекст (зашифрованное сообщение). * — исходное сообщение (число). * — открытая экспонента (часть открытого ключа). * — модуль (произведение двух больших простых чисел). * — операция взятия остатка от деления.

#### Расшифровка

Боб, получив , использует свой закрытый ключ (число ) для восстановления :

Где: * — восстановленное исходное сообщение. * — шифротекст. * — секретная экспонента (закрытый ключ). * — тот же самый модуль, что и при шифровании.

Магия заключается в том, что подобрать , зная только и , вычислительно невозможно, если достаточно велико (например, 2048 или 4096 бит).

Цифровая подпись

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

Это используется для цифровой подписи:

Боб шифрует хеш документа своим закрытым ключом.

Алиса расшифровывает его открытым ключом Боба.

Если расшифровка прошла успешно, это математически доказывает, что сообщение мог отправить только владелец закрытого ключа (Боб).

Итоги

* Симметричное шифрование требует безопасного канала для передачи ключа, что сложно реализовать в глобальной сети. * Асимметричное шифрование решает эту проблему, используя пару ключей: открытый (для всех) и закрытый (секретный). * Алгоритм RSA был создан в 1977 году Ривестом, Шамиром и Адлеманом и основан на сложности разложения больших чисел на простые множители. * Безопасность RSA гарантируется тем, что, зная произведение двух больших простых чисел (), практически невозможно найти сами эти числа. * RSA используется не только для шифрования данных, но и для создания цифровых подписей, подтверждающих авторство.

Математический фундамент: простые числа и функция Эйлера

В предыдущей статье мы рассмотрели историю RSA и поняли, что безопасность этого алгоритма держится на сложности математических вычислений. Но каких именно? Чтобы написать свой генератор ключей, нам нужно спуститься на уровень «железа» математики — в теорию чисел.

Сегодня мы разберем строительные блоки RSA: простые числа, понятие взаимной простоты и знаменитую функцию Эйлера. Без понимания этих вещей код RSA будет выглядеть как набор случайных заклинаний.

Простые числа: атомы математики

Вся криптография с открытым ключом начинается с простых чисел.

Простое число — это натуральное число больше 1, которое делится без остатка только на 1 и на само себя. Примеры: и так далее.

Числа, которые имеют другие делители, называются составными (например, ).

Почему это важно для RSA?

Согласно habr.com, безопасность RSA основывается на сложности задачи факторизации.

Представьте, что я даю вам два простых числа:

Перемножить их легко:

Но если я дам вам число и попрошу найти, из каких двух простых чисел оно состоит, задача станет сложнее. Для чисел длиной в сотни знаков эта задача становится неразрешимой за разумное время даже для суперкомпьютеров. Именно это свойство — «легко перемножить, невозможно разложить обратно» — является той самой односторонней функцией, которую искали Ривест, Шамир и Адлеман.

Взаимно простые числа (Coprimes)

Для работы RSA нам недостаточно просто простых чисел. Нам нужно понятие взаимной простоты.

Два числа называются взаимно простыми, если их наибольший общий делитель (НОД) равен 1. Это значит, что у них нет общих делителей, кроме единицы.

Пример 1: Возьмем числа и . * Делители : . * Делители : .

Единственный общий делитель — . Значит, и — взаимно простые, хотя сами по себе они составные.

Пример 2: Возьмем числа и . * Делители : . * Делители : .

Общий делитель (кроме 1) — это . Значит, они не взаимно простые.

> Числа и называются взаимно простыми, если НОД этих чисел равен 1. > > habr.com

Функция Эйлера

Теперь мы подходим к сердцу алгоритма RSA. Леонард Эйлер ввел функцию, которая обозначается греческой буквой (фи) и называется функцией Эйлера (или тотиентом).

Определение: — это количество натуральных чисел, меньших , которые являются взаимно простыми с .

Согласно ru.wikipedia.org, эта функция играет ключевую роль в алгоритме RSA.

Как это считать? (Ручной метод)

Давайте вычислим . Нам нужно найти числа от 1 до 9, которые не имеют общих делителей с 10 (кроме 1).

1 — взаимно просто с 10 (НОД = 1). (Берем)

2 — делится на 2, как и 10. (Пропускаем)

3 — взаимно просто с 10. (Берем)

4 — делится на 2. (Пропускаем)

5 — делится на 5. (Пропускаем)

6 — делится на 2. (Пропускаем)

7 — взаимно просто с 10. (Берем)

8 — делится на 2. (Пропускаем)

9 — взаимно просто с 10. (Берем)

Итого мы нашли 4 числа: . Значит:

Формулы для RSA

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

#### Свойство 1: Для простого числа

Если — простое число, то все числа от до являются взаимно простыми с ним (потому что у простого числа нет делителей).

Формула:

Где: * — значение функции Эйлера для числа . * — простое число.

Пример: . (Числа 1, 2, 3, 4, 5, 6 — все взаимно просты с 7).

#### Свойство 2: Мультипликативность

Если мы знаем разложение числа на два взаимно простых множителя и (то есть ), то значение функции можно найти перемножением значений для множителей.

Формула:

Где: * — искомое значение функции для составного числа. * и — значения функции для множителей.

Главная формула RSA

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

Где: * — функция Эйлера от модуля . * и — секретные простые числа, из которых состоит .

Пример расчета: Пусть , . Тогда . Вычислим :

Это означает, что существует ровно 40 чисел меньше 55, которые не имеют с ним общих делителей.

Теорема Эйлера

Зачем нам знать количество этих чисел? Ответ дает Теорема Эйлера. Она связывает возведение в степень с модульной арифметикой.

Теорема гласит:

Где: * — любое целое число, взаимно простое с . * — функция Эйлера от числа . * — знак сравнения по модулю (означает, что остатки от деления левой и правой части на равны). * — операция взятия остатка от деления на . * — результат операции (остаток равен 1).

По данным ru.wikipedia.org), эта теорема является обобщением малой теоремы Ферма и лежит в основе расшифровки RSA.

Практический смысл

Эта формула говорит нам: если мы возведем число в степень , мы получим (с точки зрения остатка от деления). Это создает математический «цикл». Зная размер этого цикла (который равен ), мы можем управлять процессом шифрования и расшифровки.

Если злоумышленник знает только , но не знает и , он не может вычислить . А не зная , он не может найти секретный ключ для расшифровки.

Итоги

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

Взаимно простые числа — это числа, у которых НОД равен 1. Они не обязательно должны быть простыми сами по себе (пример: 8 и 15).

Функция Эйлера показывает количество чисел, меньших и взаимно простых с ним.

Для RSA критически важна формула: если , то .

Теорема Эйлера () создает математическую основу для обратимости шифрования.