Проверка RSA в PyCryptodome: используйте λ(n), а не φ(n)

Разбираемся, почему в RSA PyCryptodome e и d обратны по λ(n), а не по φ(n). Пошаговые примеры с gmpy2 и Python, корректная проверка через lcm(p−1,q−1).

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

Как воспроизвести проблему

Ниже приведён минимальный пример, который использует Crypto.PublicKey.RSA и gmpy2 для вычисления остатка (e · d − 1) по модулю (p − 1)(q − 1). Ожидание, что этот остаток всегда будет равен нулю, и приводит к путанице.

from Crypto.PublicKey import RSA
import gmpy2 as gp

z = gp.mpz(0)
o = gp.mpz(1)

kpair = RSA.generate(1024)
p_val = gp.mpz(kpair.p)
q_val = gp.mpz(kpair.q)
n_mod = gp.mpz(kpair.n)
d_sec = gp.mpz(kpair.d)
e_pub = gp.mpz(kpair.e)

phi_mod = gp.mul(gp.sub(p_val, o), gp.sub(q_val, o))
quot, rem = gp.t_divmod(gp.sub(gp.mul(e_pub, d_sec), o), phi_mod)

print("remainder:", rem)
assert rem == z

Что происходит на самом деле

Корень проблемы в предположении, что e и d являются взаимно обратными по модулю функции Эйлера (phi) для n. В PyCryptodome d строится как обратное к e относительно лямбда-функции Кармайкла для n, а не функции Эйлера. Оба подхода корректны для RSA, но использование лямбда Кармайкла даёт закрытую экспоненту на несколько бит меньше и поэтому немного эффективнее. Этого подхода придерживаются PyCryptodome и многие другие реализации.

Для модулей RSA, построенных из двух простых p и q, лямбда Кармайкла вычисляется как lcm(p − 1, q − 1). Получить её почти так же просто, как произведение (p − 1)(q − 1), но это меняет сравнение, которому должны удовлетворять e и d.

Как правильно проверять

Чтобы валидировать ключевой материал так же, как его определяет PyCryptodome, вычислите наименьшее общее кратное p − 1 и q − 1 и проверьте обратимость по модулю этого значения.

from Crypto.PublicKey import RSA
import gmpy2 as gp
import math

z = gp.mpz(0)
o = gp.mpz(1)

kpair = RSA.generate(1024)
p_val = gp.mpz(kpair.p)
q_val = gp.mpz(kpair.q)
d_sec = gp.mpz(kpair.d)
e_pub = gp.mpz(kpair.e)

lam_mod = math.lcm(int(p_val - o), int(q_val - o))
quo2, rem2 = gp.t_divmod(gp.sub(gp.mul(e_pub, d_sec), o), gp.mpz(lam_mod))

print("remainder_lambda:", rem2)
assert rem2 == z

Если хотите, то же условие можно записать ещё проще:

assert (int(e_pub) * int(d_sec)) % lam_mod == 1

Почему это важно

При аудите или инструментировании криптографического кода легко добавить проверки, которые принимают функцию Эйлера за «канонический» модуль для обратимости. Это допущение вызовет ложные срабатывания в библиотеках, использующих лямбда Кармайкла, хотя ключи корректны и алгоритмы работают правильно. Понимание того, на какой модуль ориентируется реализация, предотвращает неверную диагностику и помогает согласовать проверки с устройством библиотеки.

Выводы

Если вы проверяете ключи RSA из PyCryptodome, не ожидайте, что (e · d − 1) mod (p − 1)(q − 1) будет нулём для каждого ключа. Вместо этого используйте lcm(p − 1, q − 1) как модуль проверки. Это соответствует тому, как библиотека определяет закрытую экспоненту, помогает избежать ложных ошибок assert и отражает распространённую практику немного уменьшать d без ущерба для корректности RSA.