Даны два открытых ключа и e, чтобы найти секретные ключи. ⇐ Python

[Гость]

Недавно я посещаю занятия по кибербезопасности. Мне было интересно, если бы мне дали два открытых ключа, n1 и n2 (и e - показатель степени) - как можно было бы сгенерировать закрытый ключ для n1? В этом сценарии n1 и n2 имеют общие простые числа.

Я знаю, что мне нужно использовать

𝑑=𝑒^(−1) 𝑚𝑜𝑑 (𝑝−1)(𝑞−1)

и я также знаю, что, поскольку они имеют общие простые числа (p), я легко могу найти соответствующее им q. Однако я застрял в расчете d.

def Calculate_private_key(n1, n2, e): # Шаг 1. Вычислите простой коэффициент (p), общий для n1 и n2. p = НОД(n1, n2) # Шаг 2: Рассчитайте остальные коэффициенты (q1 и q2) q1 = n1 // р q2 = n2 // р # Шаг 3: Вычислите долю (фи) модуля (n) фи1 = (p - 1) * (q1 - 1) фи2 = (p - 1) * (q2 - 1) # Шаг 4: Вычисление обратного модуля d1 = find_modular_inverse(e, phi1) d2 = find_modular_inverse(e, phi2) q1_inv = find_modular_inverse(q1, p) q2_inv = find_modular_inverse(q2, p) d = (d1 * q1 * q2_inv + d2 * q2 * q1_inv) % (p * q1 *q2) вернуть д Я предполагаю, что для решения d была необходима CRT, и это то, что я написал, но ответ был неверным. Мне было интересно, где что-то пошло не так. Любая информация будет принята с благодарностью. Мне было интересно, не неправильно ли я применил верхнюю формулу.

РЕДАКТИРОВАТЬ: Чтобы быть более понятным, gcd/find_modular_inverse являются самоопределяемыми функциями.
def gcd(a, b): пока б: а, б = б, а % б вернуть защита расширенного_евклидова (а, б): если б == 0: вернуть а, 1, 0 еще: НОД, x, y = расширенный_евклидов (b, a % b) вернуть НОД, y, x - (a // b) * y защита find_modular_inverse(q2, p): НОД, x, _ = расширенное_евклидово (p, q2) если х < 0: х += р вернуть х