Метод RSA: генерация ключей и шифрование

Содержание

1. 1. Криптография с открытым ключом3
2. 2. Математические основы RSA5
3. 3. Генерация ключей и шифрование8
4. 4. Практическая реализация и анализ10
5. Список литературы13

1. Криптография с открытым ключом

До середины 1970-х криптография оставалась симметричной: отправитель и получатель использовали один и тот же секретный ключ. Такая схема порождала фундаментальную проблему, которую Уитфилд Диффи и Мартин Хеллман описали в своей работе 1976 года «Новые направления в криптографии». Прежде чем начать защищённый обмен, сторонам нужно было безопасно договориться об общем ключе. Если канал связи прослушивается, передача ключа по нему превращается в порочный круг: секрет нельзя передать, не имея уже установленного секрета.

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

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

Первую практическую реализацию этой идеи предложили в 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института. Алгоритм получил название RSA по первым буквам фамилий авторов. Любопытно, что их работа появилась почти случайно: первоначальные попытки построить одностороннюю функцию с потайным входом не удавались, и Адлеман даже пытался

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

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

Однако у RSA есть ограничения, о которых стоит помнить. Скорость асимметричного шифрования значительно ниже, чем у симметричных алгоритмов вроде AES, поэтому в реальных системах RSA обычно применяется не для шифрования больших массивов данных, а для передачи сеансовых ключей. Практические реализации сталкиваются и с другими сложностями: уязвимости возникают при использовании малых экспонент, отсутствии случайности в заполнении или небезопасных режимах дополнения. Классический пример, который приводит Брюс Шнайер в своей книге «Прикладная криптография», демонстрирует, как детерминированное шифрование одного и того же сообщения позволяет злоумышленнику угадать его перебором.

Тем не менее, именно RSA заложил фундамент современной инфраструктуры открытых ключей. На нём построены протоколы TLS, защищающие веб-трафик, системы шифрования электронной почты PGP и многое другое. Полвека активного использования не сломали алгоритм, а лишь отточили понимание того, в каких условиях он безопасен.

2. Математические основы RSA

Модульная арифметика работает с остатками от деления целых чисел на фиксированное натуральное число n, которое называют модулем. Два числа считаются сравнимыми по этому модулю, если их разность делится на n нацело. Эту систему ввёл Карл Гаусс в 1801 году в «Арифметических исследованиях». Она превращает бесконечный ряд целых чисел в конечное кольцо вычетов. Внутри этого кольца выполняются все операции RSA, и именно поэтому алгоритм вообще реализуем: размер чисел, с которыми имеет дело криптография, ограничен размером модуля.

Отдельно стоит остановиться на возведении в степень по модулю. Попытка вычислить a^b mod n напрямую, возведя сначала a в степень b, обречена на провал даже для умеренных значений b. Промежуточный результат разрастается до астрономических масштабов. Вместо этого применяют метод последовательного умножения с приведением остатка после каждого шага. Например, для 7^10 mod 13 можно перемножать остатки: 7^2 mod 13 = 10, затем 10^2 mod 13 = 9, и так далее. Такой подход, известный как бинарное возведение в степень, требует всего O(log b) умножений. Этого достаточно, чтобы вычисления оставались выполнимыми даже для показателей с тысячей знаков.

Центральное место в построении RSA занимает функция Эйлера φ(n), которая считает количество чисел от 1 до n, взаимно простых с n. Для простого числа p имеем φ(p) = p − 1. Если n представляет собой произведение двух разных простых чисел p и q, то φ(n) = (p − 1)(q − 1). Это свойство несёт в себе ключевую интригу: значение φ(n) легко получить, если знаешь разложение n на множители, но найти его, не зная p и q, практически невозможно. Именно этот асимметричный разрыв лежит в основе безопасности алгоритма. Секретная экспонента d выбирается как число, обратное открытой экспоненте e по модулю φ(n). Иными словами, подбирается такое d, что ed ≡ 1 (mod

φ(n)).

Существование обратного элемента гарантирует теорема Эйлера: если a взаимно просто с n, то a^φ(n) ≡ 1 (mod n). Опубликованная Леонардом Эйлером в 1763 году, она обобщает малую теорему Ферма, которая работает только для простых модулей. В контексте RSA эта теорема обеспечивает математическую корректность всей схемы. Если выбрать e и d так, что ed = 1 + k·φ(n) для некоторого целого k, то для любого сообщения m, взаимно простого с n, получается цепочка равенств: m^(ed) ≡ m^(1+kφ(n)) ≡ m·(m^φ(n))^k ≡ m·1^k ≡ m (mod n).

Случай, когда m не взаимно просто с n, приходится рассматривать отдельно. Поскольку n = pq, где p и q простые, m может делиться на p или на q, но не на оба сразу (иначе m было бы кратно n, и сообщение оказалось бы тривиальным). Для m, кратного p, сравнение m^(ed) ≡ m (mod p) выполняется тривиально. По модулю q оно следует из теоремы Эйлера. Китайская теорема об остатках, известная ещё из древнекитайских математических трактатов, утверждает: если остатки совпадают по обоим модулям, они совпадают и по модулю n. Так что корректность дешифрования сохраняется для всех сообщений без исключений.

Свойства простых чисел, на которых держится RSA, математики изучали на протяжении тысячелетий. Евклид доказал бесконечность множества простых чисел около 300 года до н.э. Позже Адамар и Валле-Пуссен в 1896 году доказали теорему о распределении простых чисел, которая описывает их частоту среди натуральных чисел. Для практики важна именно плотность: вероятность того, что случайное число около x окажется простым, примерно равна 1/ln x. Для 1024-битного числа эта вероятность составляет около 1/710. Это означает, что подходящие простые числа можно находить простым перебором с проверкой на простоту.

Сама проверка на простоту тоже нетривиальна. Детерминированный тест Миллера опирается на обобщение малой теоремы Ферма, но его корректность требует выполнения расширенной гипотезы Римана. Поэтому на практике применяют вероятностный тест Миллера-Рабина. Для случайно выбранных оснований он даёт ложноположительный ответ с вероятностью не более 4^(−k), где k это число раундов тестирования. Уже при k = 20 вероятность ошибки оказывается ниже вероятности сбоя аппаратного обеспечения.

Функция Эйлера и теорема Эйлера образуют тот математический фундамент, на котором стоит вся конструкция RSA. Они позволяют строить взаимно обратные преобразования в кольце вычетов, не раскрывая секретных параметров. Эта элегантность в сочетании с практической реализуемостью и сделала схему Ривеста, Шамира и Адлемана стандартом де-факто в асимметричной криптографии на десятилетия.

3. Генерация ключей и шифрование

Теперь, когда модульная арифметика и функция Эйлера заданы, можно перейти к практической процедуре. Генерация ключей начинается с выбора двух больших простых чисел, обычно обозначаемых p и q. Их размер напрямую определяет криптостойкость всей системы, поэтому на практике используют числа длиной от 1024 бит каждое. Случайность выбора критична: если простые числа окажутся предсказуемыми, злоумышленник сможет восстановить секретный ключ.

Следующий шаг, вычисление модуля n как произведения p и q. Это число является частью обоих ключей и открыто публикуется. Затем находят функцию Эйлера φ(n). Поскольку n, произведение двух простых чисел, φ(n) = (p−1)(q−1). Значение φ(n) держится в секрете, так как именно через него вычисляется закрытая экспонента.

Далее выбирается открытая экспонента e. Это небольшое нечетное число, обычно 65537, которое взаимно просто с φ(n). Условие взаимной простоты гарантирует, что для e существует обратное число по модулю φ(n). Закрытая экспонента d вычисляется как решение сравнения ed ≡ 1 (mod φ(n)). Иными словами, d, это мультипликативное обратное к e по модулю φ(n). Открытый ключ, пара (e, n), закрытый, (d, n).

Процедура шифрования выглядит так. Пусть m, числовое представление сообщения, причем 0 ≤ m < n. Чтобы зашифровать, отправитель возводит m в степень e и берет остаток от деления на n: c = m^e mod n. Полученное число c, шифротекст. Для дешифрования получатель возводит c в степень d по модулю n: m = c^d mod n. Здесь важна асимметрия: знание e и n не позволяет вычислить d без факторизации n.

Корректность этой схемы следует из теоремы Эйлера. Так как ed ≡ 1 (mod φ(n)), можно записать ed = k·φ(n) + 1 для некоторого

целого k. Тогда c^d ≡ (m^e)^d = m^(ed) = m^(k·φ(n)+1) ≡ m (mod n). Последний переход опирается на то, что m^φ(n) ≡ 1 (mod n) для чисел, взаимно простых с n. Если m и n не взаимно просты, доказательство требует отдельного рассмотрения, но результат остается тем же. Так дешифрование восстанавливает исходное сообщение без потери информации.

4. Практическая реализация и анализ

Перейдём от теории к практике. Работу алгоритма проще всего проследить на конкретном примере с маленькими числами, где все вычисления можно проверить вручную. Пусть абоненты Алиса и Боб хотят обменяться сообщением. Алиса выбирает два простых числа, например p = 61 и q = 53. Их произведение n = 3233, а функция Эйлера φ(n) = (p-1)(q-1) = 3120. В качестве открытой экспоненты e она берёт число 17, которое взаимно просто с 3120. Секретная экспонента d вычисляется как обратный элемент к e по модулю φ(n); в данном случае d = 2753. Открытый ключ это пара (n, e), закрытый ключ это (n, d).

Теперь Боб шифрует сообщение. Пусть он хочет передать число m = 65. Шифротекст c вычисляется как остаток от деления 65^17 на 3233, что даёт c = 2790. Алиса, получив c, возводит его в степень d: 2790^2753 mod 3233 = 65. Исходное сообщение восстановлено. На этом примере видна вся схема: генерация ключей сводится к нахождению трёх чисел, шифрование к одному возведению в степень, дешифрование к другому.

Описанная процедура в псевдокоде занимает не более десятка строк. Генерация ключей требует лишь операций умножения, проверки простоты и расширенного алгоритма Евклида. На практике вместо учебных 61 и 53 берутся простые числа длиной от 1024 бит каждое. И здесь возникает главный вопрос безопасности. Криптостойкость RSA держится на том, что разложить n на множители, зная только открытый ключ, вычислительно сложно. Однако прогресс не стоит на месте: в 2009 году группа исследователей во главе с Торстеном Кляйнунгом успешно факторизовала 768-битное число RSA-768, затратив около двух лет вычислений на кластере из сотен машин.

Именно поэтому современные стандарты, включая рекомендации NIST, требуют использовать ключи длиной не менее 2048 бит. 1024-битные ключи, ещё

встречающиеся в старых системах, сегодня считаются уязвимыми: по оценкам специалистов, их факторизация становится реальной для хорошо оснащённой лаборатории. Длина в 3072 или 4096 бит обеспечивает запас прочности на десятилетия вперёд, но цена такого запаса растёт нелинейно.

Тут мы подходим к вопросу производительности. Возведение числа в степень с показателем в тысячи бит по модулю, размер которого сопоставим с этим показателем, операция небыстрая. Аппаратная реализация на современных процессорах выполняет RSA-шифрование со скоростью порядка нескольких мегабит в секунду. Симметричные алгоритмы вроде AES работают в сотни раз быстрее, достигая гигабитных скоростей на том же оборудовании. Разница особенно заметна при дешифровании: закрытая экспонента обычно значительно больше открытой.

Поэтому в реальных протоколах, таких как TLS, RSA применяют не для шифрования потока данных, а для передачи сессионного ключа. Схема выглядит так: клиент генерирует случайный симметричный ключ длиной 256 бит, шифрует его открытым ключом сервера и отправляет. Сервер расшифровывает его своим закрытым ключом, после чего обе стороны переходят на быстрый симметричный шифр. Такое гибридное построение позволяет сочетать удобство асимметричной криптографии с высокой скоростью симметричной. RSA берёт на себя лишь разовую операцию обмена ключами, а весь последующий трафик обрабатывается AES.

Есть у RSA и другие ограничения, о которых стоит помнить. Размер шифруемого блока не может превышать длину модуля минус несколько байт. При 2048-битном ключе за одно шифрование передаётся максимум 245 байт данных. Кроме того, чистый RSA детерминирован: одинаковое сообщение всегда даёт одинаковый шифротекст. Это позволяет атакующему угадывать содержимое, сравнивая шифротексты. Для борьбы с этим в реальные реализации добавляют случайное заполнение по стандарту OAEP. Без подобных ухищрений алгоритм

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

СПИСОК ЛИТЕРАТУРЫ

1. RSA — Википедия — https://ru.wikipedia.org/wiki/RSA

2. Криптографическая система RSA — https://intuit.ru/studies/courses/552/408/lecture/9371?page=3

3. Криптография с открытым ключом — https://logic.pdmi.ras.ru/~sergey/teaching/cryptoclub15/05-publickey.pdf

4. RSA простыми словами и в картинках — https://habr.com/ru/articles/745820/

5. Чем опасен чистый RSA? Разбираем подводные камни — https://habr.com/ru/articles/838882/

6. RSA: от простых чисел до электронной подписи — https://habr.com/ru/articles/534014/

7. Создание ключей, шифрование и дешифрование — https://moluch.ru/archive/283/63831

8. Лабораторная работа 2 — https://swsu.ru/sveden/files/MU_PZ_Informacionnaya_bezopasnosty._Algoritm_shifrovaniya_RSA..pdf