Криптосистема RSA и её математические основы

Содержание

1. Введение в криптографию и RSA3
2. 2. Математические основы: теория чисел5
3. 3. Генерация ключей и шифрование8
4. 4. Анализ стойкости и применения RSA11

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

Криптография появилась тогда, когда у людей возникла потребность прятать сообщения от посторонних. Самые ранние из известных шифров датируются периодом задолго до нашей эры. Юлий Цезарь в своей переписке сдвигал буквы на три позиции по алфавиту; этот метод стал хрестоматийным примером простой подстановки. В XVI веке Блез де Виженер разработал более сложную схему, в которой позиция каждого символа менялась на переменную величину, зависящую от ключевого слова. Подобные системы называют симметричными, поскольку и отправитель, и получатель используют один и тот же секрет для кодирования и декодирования информации.

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

Перелом произошёл в 1976 году. Уитфилд Диффи и Мартин Хеллман опубликовали работу, в которой описали концепцию асимметричной криптографии. Вместо одного секрета они предложили использовать два ключа: один для шифрования, другой для расшифровки. Открытый ключ можно публиковать где угодно, он не нуждается в защите. Закрытый ключ остаётся только у владельца, и его нельзя передавать никому. Любой, у кого есть открытый ключ, может зашифровать сообщение, но прочитать его способен лишь обладатель парного закрытого ключа. Таким образом, необходимость в тайной передаче секретов исчезла, ведь

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

Впрочем, Диффи и Хеллман сформулировали лишь общий принцип, не предложив конкретной математической функции для его реализации. Спустя год, в 1977-м, Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института создали первую рабочую схему. Её назвали RSA по первым буквам фамилий авторов. В основе алгоритма лежит сложность разложения больших чисел на простые множители. Несмотря на появление позже других методов, например на основе эллиптических кривых, RSA за прошедшие десятилетия стала фактическим стандартом асимметричного шифрования.

Сейчас RSA незаметно присутствует в самых обычных цифровых операциях. Протоколы SSL/TLS, которые защищают соединение браузера с сервером, используют RSA для обмена сеансовыми ключами. Электронная подпись, построенная на RSA, подтверждает подлинность программ и юридических документов. Банковские карты, почтовые сервисы, государственные порталы, всё это опирается на работу пары простых чисел, подобранных когда-то давно. Системе почти пятьдесят лет, но она продолжает защищать данные, и её актуальность объясняется не столько историческим приоритетом, сколько проверенной временем надёжностью.

2. Математические основы: теория чисел

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

Модулярная арифметика формализует привычное нам деление с остатком. Говорят, что числа a и b сравнимы по модулю m, если их разность кратна m, и записывают a ≡ b (mod m). Все операции здесь выполняются не над бесконечной прямой, а над конечным кольцом вычетов, содержащим ровно m элементов. Сложение, вычитание и умножение по модулю работают интуитивно: сначала выполняем обычное действие, затем берём остаток от деления на m. С делением сложнее. Для элемента a обратным по модулю m называют такое число x, что a·x ≡ 1 (mod m). Такой x существует не всегда, а только если a и m взаимно просты, то есть их наибольший общий делитель равен единице. Это условие принципиально. В RSA именно вычисление обратного элемента для открытой экспоненты даёт секретный ключ.

Количество чисел в диапазоне от 1 до n, взаимно простых с n, задаёт функция Эйлера φ(n). Для простого числа p значение функции тривиально: φ(p) = p − 1. Для произведения двух различных простых чисел p и q получаем φ(pq) = (p − 1)(q − 1). Эта формула становится ключом ко всей схеме. Зная разложение n на множители, любой может вычислить φ(n). Не зная его, нельзя определить секретную экспоненту. В этом

смысле функция Эйлера выполняет роль математического барьера между открытой информацией и секретом.

Теорема Эйлера, опубликованная в 1763 году, утверждает: если a и n взаимно просты, то a^φ(n) ≡ 1 (mod n). Частный случай этой теоремы для простого модуля p известен как малая теорема Ферма: a^(p−1) ≡ 1 (mod p) для любого a, не кратного p. Именно эти два утверждения обеспечивают корректность расшифрования в RSA. Когда получатель возводит шифротекст в степень секретного ключа, показатели степени сокращаются по модулю φ(n), и в силу теоремы Эйлера в результате возвращается исходное сообщение. Без этой математической гарантии вся конструкция развалилась бы.

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

Леонард Эйлер ввёл свою функцию в трактате 1763 года, и с тех пор она стала стандартным инструментом теории чисел. Современные учебники, например «Введение в криптографию» Нильса Фергюсона и Брюса Шнайера, рассматривают эти результаты как необходимую базу для любого, кто хочет понять асимметричные шифры. Без простых чисел, модулярной арифметики и теоремы Эйлера невозможно объяснить даже постановку задачи. Сами по себе эти понятия не решают криптографических проблем. Но они задают язык, на котором

эти проблемы формулируются.

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

Переход от теории чисел к практическому применению в RSA начинается с генерации ключей. Первым делом выбираются два больших простых числа, обычно обозначаемых \(p\) и \(q\). Они должны быть действительно большими и, что критически важно, случайными. Размер этих чисел напрямую определяет безопасность всей системы, поэтому на практике их получают с помощью криптографически стойких генераторов случайных чисел. Таблицы или предсказуемые алгоритмы здесь недопустимы.

Затем вычисляется модуль \(n = p \cdot q\). Это произведение входит и в открытый, и в закрытый ключ. Если \(p\) и \(q\) известны, значение функции Эйлера \(\varphi(n) = (p-1)(q-1)\) находится без труда. Эта функция показывает, сколько чисел, меньших \(n\), взаимно просты с ним, и именно она задаёт структуру ключевой пары. Держать \(p\), \(q\) и \(\varphi(n)\) в секрете необходимо: их раскрытие мгновенно компрометирует систему.

Теперь выбирается открытая экспонента \(e\). Это число должно быть взаимно простым с \(\varphi(n)\). На практике чаще всего берут \(e = 65537\), так как его двоичная запись проста и это ускоряет возведение в степень. После этого вычисляется закрытая экспонента \(d\), обратный элемент к \(e\) по модулю \(\varphi(n)\). Иными словами, \(d\) подбирается так, чтобы выполнялось равенство \(e \cdot d \equiv 1 \pmod{\varphi(n)}\). Для этого применяется расширенный алгоритм Евклида. Пара \((e, n)\) публикуется как открытый ключ, а \((d, n)\) хранится в тайне.

Сам процесс шифрования по форме предельно прост. Сообщение \(M\) представляется как целое число, меньшее \(n\). Шифротекст \(C\) получается возведением \(M\) в степень \(e\) по модулю \(n\): \(C = M^e \bmod n\). Дешифрование, это обратная операция: получатель возводит \(C\) в степень \(d\) по модулю \(n\) и восстанавливает исходное сообщение \(M = C^d \bmod n\). Математическая основа

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

Требования к параметрам строги. Современный стандарт безопасности предписывает использовать модуль \(n\) размером не менее 2048 бит. Меньшие ключи, например 1024-битные, считаются уязвимыми; NIST исключил их из своих рекомендаций ещё в 2013 году. Простые числа \(p\) и \(q\) должны быть примерно одинаковой длины, чтобы затруднить факторизацию \(n\) методом квадратичного решета или алгоритмом Полларда. Кроме того, они не должны быть слишком близки друг к другу, иначе модуль можно разложить через разность квадратов. Наконец, генерация должна быть абсолютно случайной, поскольку предсказуемые простые числа делают систему открытой для атаки.

Чтобы увидеть, как алгоритм работает на практике, удобно разобрать пример с крошечными числами. Возьмём \(p = 61\) и \(q = 53\). Тогда \(n = 61 \cdot 53 = 3233\), а \(\varphi(n) = 60 \cdot 52 = 3120\). Выберем открытую экспоненту \(e = 17\), она взаимно проста с 3120. С помощью расширенного алгоритма Евклида находим \(d = 2753\), так как \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\). Открытый ключ, \((17, 3233)\), закрытый, \((2753, 3233)\). Пусть сообщение \(M = 65\). Шифруем: \(65^{17} \bmod 3233 = 2790\). Получатель возводит 2790 в степень 2753 по модулю 3233 и получает исходное 65. Разумеется, в реальной системе числа в сотни раз длиннее, но логика операций абсолютно идентична.

Важно понимать, что простота \(p\) и \(q\), это не единственное условие. Случайность их выбора определяет непредсказуемость ключа, а секретность, невозможность восстановления \(d\) из открытых данных. Если злоумышленник сможет факторизовать \(n\), он получит \(p\) и \(q\), затем \(\varphi(n)\), и, наконец, \(d\). Поэтому вся стойкость RSA сводится к вычислительной сложности

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

4. Анализ стойкости и применения RSA

Стойкость RSA держится на том, что факторизовать достаточно большой модуль n практически невозможно. Самая прямая атака, перебор всех простых делителей, превращается в задачу, которую не решить за разумное время, если размер ключа от 2048 бит. Но математическая сложность это не единственная угроза. Есть атаки по времени: злоумышленник замеряет, сколько длится дешифрование или подпись, и по микроразличиям восстанавливает закрытую экспоненту. Опаснее атаки на основе выбранного шифротекста. Если криптоаналитик может заставить систему расшифровать подготовленные им сообщения, он иногда способен вычислить секретный ключ. Чтобы защититься от таких сценариев, применяют схему дополнения OAEP (Optimal Asymmetric Encryption Padding). Она добавляет к сообщению случайные биты и хеш-функцию перед шифрованием, превращая детерминированный алгоритм RSA в вероятностный. В итоге один и тот же открытый текст даёт разные шифротексты, и атаки по выбранному шифротексту теряют эффективность.

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

Главное ограничение RSA, производительность. Операции с модулем в 2048 или 4096 бит требуют значительных вычислительных ресурсов, поэтому они на порядки медленнее симметричных алгоритмов. Управление ключами тоже остаётся слабым местом: закрытый ключ нужно хранить в защищённом аппаратном модуле, а сертификаты открытых ключей требуют

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