Основы RSA: математика без излишней теории

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

Пусть выбраны два простых числа:

  • ( p )
  • ( q )

Их произведение образует модуль:

  • ( n = p q )

Это число ( n ) становится частью открытого и закрытого ключа.

Для дальнейших вычислений используется функция Эйлера:

  • ( (n) = (p - 1)(q - 1) )

Она определяет количество чисел, взаимно простых с ( n ).

Генерация ключей RSA

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

Открытая экспонента

Выбирается число ( e ), удовлетворяющее условиям:

  • ( 1 < e < (n) )
  • ( (e, (n)) = 1 )

На практике часто используется значение 65537 — оно обеспечивает баланс между безопасностью и производительностью.

Закрытая экспонента

Закрытый ключ ( d ) вычисляется как обратное значение к ( e ) по модулю ( (n) ):

  • ( d e^{-1} (n) )

Это означает:

  • ( e d (n) )

Таким образом формируется пара:

  • Открытый ключ: ( (e, n) )
  • Закрытый ключ: ( (d, n) )

Модульная арифметика в RSA

Все операции выполняются по модулю ( n ). Это ключевой механизм безопасности.

Основная операция:

  • ( a b n )

означает, что ( a ) и ( b ) дают одинаковый остаток при делении на ( n ).

Шифрование и расшифрование

Шифрование

Сообщение ( m ), представленное числом, преобразуется в шифротекст:

  • ( c = m^e n )

Расшифрование

Шифротекст возвращается в исходное сообщение:

  • ( m = c^d n )

Свойство корректности RSA основано на теореме Эйлера и структуре мультипликативной группы по модулю ( n ).

Ограничения представления данных

RSA не работает напрямую со строками. Любые данные сначала преобразуются в число.

В реальных системах применяются:

  • кодировки (UTF-8 → байты)
  • преобразование байтов в BigInteger
  • схемы паддинга (PKCS#1, OAEP)

Без паддинга RSA уязвим к атакам на детерминированное шифрование.

Представление RSA в jsrsasign

Библиотека Jsrsasign реализует RSA через объект RSAKey, предоставляя низкоуровневый доступ к ключам и операциям.

Генерация ключа

const rsa = new RSAKey();

rsa.generate(2048, "10001"); // 65537 в hex

Здесь:

  • 2048 — длина ключа в битах
  • "10001" — открытая экспонента в hex

Импорт и экспорт ключей

RSA-ключи обычно представлены в формате PEM.

Пример приватного ключа

-----BEGIN PRIVATE KEY-----
...
-----END PRIVATE KEY-----

Загрузка ключа в Jsrsasign

const rsa = KEYUTIL.getKey(pemPrivateKey);

или для публичного:

const pub = KEYUTIL.getKey(pemPublicKey);

Шифрование через Jsrsasign

Jsrsasign поддерживает шифрование строк через RSAKey.

const rsa = KEYUTIL.getKey(publicKeyPem);

const encrypted = rsa.encrypt("Hello");

Результат обычно кодируется в hex или base64.

Расшифрование

const rsa = KEYUTIL.getKey(privateKeyPem);

const decrypted = rsa.decrypt(encryptedHex);

Внутренний механизм вычислений

RSA в Jsrsasign использует большие числа через собственную реализацию BigInteger.

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

  • возведение в степень по модулю (modPow)
  • умножение больших чисел
  • алгоритм расширенного Евклида (для вычисления обратного элемента)

Быстрое возведение в степень

Ключевая операция:

  • ( m^e n )

Вместо прямого вычисления используется метод:

  • exponentiation by squaring

Он снижает сложность с линейной до логарифмической.

Обратный элемент и алгоритм Евклида

Для вычисления ( d ) применяется расширенный алгоритм Евклида:

Нужно найти такие ( x ) и ( y ), что:

  • ( ax + by = (a, b) )

Если ( (a, b) = 1 ), то:

  • ( x a^{-1} b )

В RSA это используется для вычисления:

  • ( d = e^{-1} (n) )

Пример полного цикла RSA

const rsa = new RSAKey();
rsa.generate(1024, "10001");

const publicKey = KEYUTIL.getKey(rsa.getPublicPEM());
const privateKey = KEYUTIL.getKey(rsa.getPrivatePEM());

const message = "test message";

const encrypted = publicKey.encrypt(message);
const decrypted = privateKey.decrypt(encrypted);

Почему RSA работает

Корректность опирается на следующее свойство:

  • ( (me)d m n )

Раскрытие степени даёт:

  • ( m^{ed} n )

Так как:

  • ( ed (n) )

то существует целое ( k ), что:

  • ( ed = 1 + k(n) )

Следовательно:

  • ( m^{ed} = m^{1 + k(n)} = m (m{(n)})k )

По теореме Эйлера:

  • ( m^{(n)} n )

И всё выражение сводится к исходному ( m ).

Практическая структура ключей

RSA-ключ включает:

  • модуль ( n )

  • публичную экспоненту ( e )

  • приватную экспоненту ( d )

  • дополнительные параметры для оптимизации:

    • ( p, q )
    • ( d_p = d (p-1) )
    • ( d_q = d (q-1) )
    • коэффициент ( q^{-1} p )

Эти значения ускоряют операции через китайскую теорему об остатках (CRT).

Оптимизация через CRT

Вместо вычисления:

  • ( c^d n )

используются:

  • ( m_1 = c^{d_p} p )
  • ( m_2 = c^{d_q} q )

После этого результаты объединяются в исходное сообщение.

Это ускоряет RSA примерно в 3–4 раза.

Числовая природа безопасности

Безопасность RSA основана на задаче факторизации:

  • дано ( n )
  • нужно найти ( p ) и ( q )

Для больших ключей (2048+ бит) эта задача не имеет известного эффективного решения на классических компьютерах.

Ограничения RSA

Алгоритм плохо подходит для больших данных:

  • медленное шифрование
  • ограничение на размер блока (меньше ( n ))
  • необходимость гибридных схем

Поэтому RSA обычно используется только для:

  • шифрования симметричных ключей
  • цифровой подписи

Связь с цифровой подписью

RSA используется не только для шифрования, но и для подписи:

  • подпись: ( s = H(m)^d n )
  • проверка: ( H(m) = s^e n )

где ( H(m) ) — хэш сообщения.

Использование подписи в Jsrsasign

const rsa = KEYUTIL.getKey(privateKeyPem);

const signature = rsa.signString("message", "sha256");

Проверка:

const rsa = KEYUTIL.getKey(publicKeyPem);

const isValid = rsa.verifyString("message", signature);
Оглавление