Научный руководитель: Вильданов Алмаз Нафкатович, к.ф.-м.н.
Уфимский университет науки и технологий, Нефтекамский филиал
RSA (Rivest–Shamir–Adleman) — один из первых и наиболее известных асимметричных криптографических алгоритмов. Его устойчивость основана на сложности разложения больших чисел на простые множители. Благодаря этому RSA применяется в цифровых подписях, протоколах передачи данных (SSL/TLS, SSH, PGP), а также в электронных сертификатах.
Система Maple предоставляет удобные инструменты для работы с целыми числами произвольной длины, поиска простых чисел, вычислений по модулю и нахождения обратных элементов. Это делает её подходящей как для образовательных целей, так и для научных исследований в области криптографии.
RSA основан на трудности факторизации больших чисел. Если известны два больших простых числа p и q, то легко вычислить их произведение n=p⋅q. Однако, зная только n, крайне сложно (при достаточной длине) восстановить p и q — именно на этом и базируется безопасность алгоритма.
Основные понятия
- Модуль n — произведение двух больших простых чисел.
- Открытый ключ — пара (n,e).
- Закрытый ключ — число d, соответствующее e и удовлетворяющее условиям модульной арифметики.
- Функция Эйлера:
φ(n)=(p−1)(q−1).
Этапы работы алгоритма RSA
1. Генерация ключей
- Выбираются два больших простых числа: p и q.
- Вычисляется модуль: n=p⋅q.
- Вычисляется функция Эйлера: φ(n)=(p−1)(q−1).
- Выбирается целое число e, такое что 1<e<φ(n) и gcd (e,φ(n))=1 (взаимно простое).
- Вычисляется d, обратное к e по модулю φ(n):
d≡e^−1 mod φ(n).
Публичный ключ: (n,e).
Приватный ключ: d
2. Шифрование
Пусть сообщение — это число m, где 0 ≤ m < n Зашифрованное сообщение:
c=m^e mod n
3. Дешифрование
Расшифровка выполняется с помощью приватного ключа d:
m=c^d mod n
Реализация RSA в Maple:
Генерация ключей
p := randprime(10^10..10^11):
q := randprime(10^10..10^11):
n := p*q:
phi := (p-1)*(q-1):
e := 65537: #стандартное значение экспоненты
d := invmod(e, phi):
PublicKey := (n, e):
PrivateKey := d:
Шифрование сообщения
Encrypt := (m, e, n) -> PowerMod(m, e, n):
m := 123456: # пример сообщения
c := Encrypt(m, e, n):
Дешифрование сообщения
Decrypt := (c, d, n) -> PowerMod(c, d, n):
m_dec := Decrypt(c, d, n):
В результате (m) и (m_{dec}) совпадают, что подтверждает корректность алгоритма.
Анализ безопасности в Maple
С помощью Maple можно проводить исследования: – проверять скорость факторизации при малых значениях (n); – моделировать атаки при неправильном выборе параметров; – анализировать время вычислений при разных размерах ключей.
Таким образом, Maple позволяет не только реализовать RSA, но и экспериментально исследовать его устойчивость.
Безопасность RSA
Безопасность RSA основана на трудности факторизации числа nnn на множители ppp и qqq. Пока эта задача остаётся вычислительно сложной, RSA считается надёжным.
Возможные уязвимости:
- Маленькие ключи: если n недостаточно велик, его можно разложить на множители (современные атаки справляются с 1024-битными ключами).
- Плохая генерация простых чисел: уязвимость к атакам повторного использования.
- Атаки с выбранным шифротекстом, если не используется паддинг (например, PKCS#1 или OAEP).
- Квантовые компьютеры: алгоритм Шора позволяет факторизовать большие числа за полиномиальное время — это потенциальная угроза RSA в будущем.
Применение на практике
RSA широко используется в:
- SSL/TLS (защита HTTPS)
- Электронной подписи (например, в документах PDF)
- VPN и SSH (аутентификация и обмен ключами)
- Протоколах шифрования электронной почты (PGP, GPG)
- Цифровых сертификатах (X.509)
Заключение
Рассмотрение алгоритма RSA в системе Maple объединяет математическую теорию и практические вычисления. Такой подход облегчает понимание работы алгоритма, позволяет проводить эксперименты и моделировать реальные криптографические сценарии. Использование Maple делает изучение RSA наглядным и прикладным, что особенно важно в образовательных и исследовательских проектах.
Библиографический список
- Rivest, R., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
- Stallings, W. (2017). Cryptography and Network Security: Principles and Practice. Pearson.
- Schneier, B. (2015). Applied Cryptography. Wiley.
- Paar, C., & Pelzl, J. (2009). Understanding Cryptography. Springer.
- RFC 8017: PKCS #1: RSA Cryptography Specifications. IETF.
- Katz, J., & Lindell, Y. (2020). Introduction to Modern Cryptography. CRC Press.