Алгоритм RSA и его применение в цифровых подписях

Содержание

1. 1. Криптография и необходимость защиты информации3
2. 2. Математические основы алгоритма RSA5
3. 3. Генерация ключей и шифрование RSA7
4. 4. Цифровые подписи на основе RSA9

1. Криптография и необходимость защиты информации

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

Долгое время криптография была искусством симметричных шифров. Схема проста: у отправителя и получателя один и тот же ключ, который служит и для зашифрования, и для расшифрования. Самый известный пример, знакомый каждому школьнику, это шифр Цезаря. В нём каждая буква заменяется на другую, отстоящую от неё на фиксированное число позиций, скажем, на три. Если ключ равен трём, «А» превращается в «Г». Получатель, зная ключ, просто сдвигает буквы обратно. Метод изящный и несложный, но именно здесь скрыта фундаментальная уязвимость всей схемы. Ключ необходимо передать адресату до начала переписки, и эта передача должна быть абсолютно надёжной. Если ключ перехватят, секретность рушится: владелец ключа получает полный доступ к содержимому переписки.

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

друг с другом и не имеют предварительных договорённостей.

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

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

Этот принцип, простой по формулировке, решил проблему распределения ключей. Не нужно заранее договариваться о секрете. Достаточно получить открытый ключ собеседника, и можно отправлять ему защищённые данные. Закрытый ключ вообще никуда не передаётся, он остаётся у владельца. Такая схема упростила шифрование и, что важнее, открыла дорогу для цифровой подписи. В ней закрытый ключ служит для создания «электронной печати», а открытый для её проверки. Именно на этой паре ключей построен алгоритм RSA, появившийся в 1977 году. Он до сих пор остаётся одним из самых распространённых криптографических механизмов в мире.

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

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

Центральное место в генерации ключей занимает функция Эйлера φ(n). Для произвольного натурального числа n она возвращает количество целых чисел от 1 до n, которые взаимно просты с n, то есть не имеют с ним общих делителей, кроме единицы. Если n является произведением двух различных простых чисел p и q, то φ(n) вычисляется тривиально: (p − 1)(q − 1). Леонард Эйлер ввёл эту функцию в середине XVIII века, и именно её мультипликативное свойство лежит в основе выбора секретной экспоненты. Без знания p и q вычислить φ(n) напрямую практически невозможно, поскольку это потребовало бы перебора всех чисел, меньших n. Данное обстоятельство напрямую связывает сложность взлома RSA с задачей разложения составного числа на простые множители.

Корректность всей схемы шифрования и подписи опирается на теорему Эйлера. Она утверждает, что для любых взаимно простых a и n выполняется сравнение a^φ(n) ≡ 1 (mod n). Это утверждение является обобщением малой теоремы Ферма, которая справедлива только для простых модулей. Практическое следствие теоремы таково: если выбрать открытую экспоненту e, взаимно простую с φ(n), то всегда можно найти такую

закрытую экспоненту d, что их произведение ed даёт остаток 1 при делении на φ(n). Тогда возведение числа в степень ed возвращает исходное значение. Именно эта обратимость гарантирует, что получатель сообщения, применив свой закрытый ключ, восстановит исходный текст без потерь. Математическое обоснование этого факта подробно разобрано в классическом труде Рональда Ривеста, Ади Шамира и Леонарда Адлемана 1978 года, где они впервые представили свою систему.

Безопасность алгоритма зиждется на асимметрии вычислительных затрат. Умножить два простых числа, например 61 и 53, чтобы получить 3233, может каждый школьник. Но обратная задача, восстановить множители по данному произведению, превращается в серьёзную вычислительную проблему по мере роста длины чисел. В современных реализациях RSA используются модули длиной 2048 бит, что соответствует числу примерно из 617 десятичных цифр. Перебор всех возможных делителей для такого числа занял бы у суперкомпьютера миллиарды лет. Хотя существуют более совершенные алгоритмы факторизации, такие как метод квадратичного решета или метод эллиптических кривых, их временная сложность остаётся субэкспоненциальной. Это означает, что при достаточном размере ключа вычислительных мощностей всей планеты недостаточно для взлома в разумные сроки. Криптоаналитики, такие как Питер Шнорр, неоднократно подчёркивали, что именно отсутствие эффективного полиномиального алгоритма факторизации делает RSA практичным. Пока математики не найдут способ быстро раскладывать большие составные числа, схема будет оставаться надёжной, что подтверждается её тридцатилетней успешной эксплуатацией в протоколах TLS и PGP.

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

После того как во второй главе была проведена необходимая математическая подготовка, перейдем к практической стороне вопроса. Генерация ключей в RSA начинается с выбора двух больших простых чисел p и q. В современных системах размер каждого из них должен быть не менее 1024 бит, а для особо критичных применений используются числа по 2048 бит. Сам процесс поиска таких чисел нетривиален. Программа генерирует случайные кандидаты и проверяет их на простоту вероятностными тестами, например тестом Миллера-Рабина. Когда оба простых числа найдены, вычисляется их произведение n = p × q. Этот модуль n задает размер всех последующих вычислений и открыто публикуется в составе ключа.

Следующий шаг связан с вычислением функции Эйлера φ(n) = (p − 1)(q − 1). Это значение нужно для выбора экспонент. Сам модуль n напрямую не раскрывает φ(n), поскольку для этого пришлось бы разложить n на множители. Открытая экспонента e выбирается как небольшое нечетное число, взаимно простое с φ(n). На практике чаще всего используют e = 65537. Оно простое, достаточно большое для защиты от ряда атак и при этом позволяет быстро выполнять возведение в степень. Закрытая экспонента d вычисляется как число, обратное к e по модулю φ(n). Иными словами, решается сравнение e × d ≡ 1 (mod φ(n)), обычно с помощью расширенного алгоритма Евклида. Открытый ключ представляет собой пару (e, n), а закрытый (d, n).

Сама процедура шифрования устроена довольно просто. Сообщение M преобразуется в числовой блок m так, чтобы выполнялось условие 0 ≤ m < n. Если сообщение длиннее модуля, его разбивают на блоки и шифруют каждый по отдельности. Шифротекст c получается возведением числа m в степень e по модулю n: c = m^e mod n. Эта операция выполняется быстро даже для больших чисел. Помогает алгоритм быстрого возведения в степень, который сокращает количество умножений с e до примерно

log₂(e).

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

Рассмотрим небольшой пример. Возьмем p = 61 и q = 53. Тогда n = 61 × 53 = 3233, а φ(n) = 60 × 52 = 3120. Выберем открытую экспоненту e = 17; она взаимно проста с 3120. Закрытая экспонента d находится из условия 17 × d ≡ 1 (mod 3120). Решая это сравнение, получаем d = 2753, поскольку 17 × 2753 = 46801 = 15 × 3120 + 1. Открытый ключ (17, 3233), закрытый (2753, 3233).

Пусть нужно зашифровать сообщение, представленное числом m = 65. Вычисляем c = 65^17 mod 3233. Для ручного счета можно последовательно возводить в квадрат и умножать, но проще использовать промежуточные вычисления: 65^2 = 4225 ≡ 992 (mod 3233), 65^4 ≡ 992² = 984064 ≡ 944 (mod 3233), и так далее. В итоге получаем c = 2790. Расшифрование выполняется возведением 2790 в степень 2753 по модулю 3233, что возвращает исходное число 65. Этот пример наглядно показывает, насколько различаются объемы вычислений при шифровании и расшифровании, хотя оба процесса используют одну и ту же операцию модульного возведения в степень.

4. Цифровые подписи на основе RSA

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

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

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

Хеш-функции здесь нужны не для скорости, а для безопасности. Алгоритм SHA-256 (стандартизирован АНБ США в 2001 году) выдаёт отпечаток длиной 256 бит. Подписать такое число быстрее, чем шифровать мегабайты данных. Но главное в другом. Хеш ведёт себя как контрольная сумма: даже незначительное изменение сообщения полностью меняет отпечаток. Подпись, вычисленная для исходного хеша, перестаёт соответствовать новому. Проверка сразу выявляет подделку, что гарантирует целостность данных. А поскольку расшифровать подпись можно только открытым ключом конкретного пользователя,

источник сообщения тоже не вызывает сомнений.

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

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