Python中RSA的模逆解释

Question

我发现了一个python脚本，可以在python中为RSA执行模块化反转。然而，我无法理解python中的模块化逆是如何工作的。 请您解释一下，特别是modinv和egcd，好吗 请在代码中添加注释，以便更好地理解

这是来自此链接的python代码示例， https://gist.github.com/ofaurax/6103869014c246f962ab30a513fb5b49

#!/usr/bin/env python3

p = 61
q = 53

n = p*q
phi = (p-1)*(q-1)

# Took from SO
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

e = 17
d = modinv(e, phi)

print('P =', p)
print('Q =', q)
print('N =', n)
print('Phi =', phi)
print('E =', e)
print('D =', d)
print('(E*D)%Phi =', (e*d)%phi)

多谢各位

Answer 1

您使用Extended Euclidean algorithm查找d时：

d⋅e ≡ 1 (mod λ(n));

在你的例子中e = 17和λ(n) = phi