python - (RSA)我从 stackoverflow 得到的这个脚本返回负 d 值

Question

所以我在这个脚本中偶然发现了这个线程，它返回一个负 d 值，并且我的 p 和 q 值都是素数。这有什么原因吗？可能只是一个错误的脚本？

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def main():

    p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
    q = 156408916769576372285319235535320446340733908943564048157238512311891352879208957302116527435165097143521156600690562005797819820759620198602417583539668686152735534648541252847927334505648478214810780526425005943955838623325525300844493280040860604499838598837599791480284496210333200247148213274376422459183
    e = 65537
    ct = 313988037963374298820978547334691775209030794488153797919908078268748481143989264914905339615142922814128844328634563572589348152033399603422391976806881268233227257794938078078328711322137471700521343697410517378556947578179313088971194144321604618116160929667545497531855177496472117286033893354292910116962836092382600437895778451279347150269487601855438439995904578842465409043702035314087803621608887259671021452664437398875243519136039772309162874333619819693154364159330510837267059503793075233800618970190874388025990206963764588045741047395830966876247164745591863323438401959588889139372816750244127256609

    # compute n
    n = p * q

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

    # Compute modular inverse of e
    gcd, a, b = egcd(e, phi)
    d = a

    print( "n:  " + str(d) );

    # Decrypt ciphertext
    pt = pow(ct,d,n)
    print( "pt: " + str(pt) )

if __name__ == "__main__":
    main()

Answer 1

这种情况可能会发生，我将在下面解释原因，但出于实际目的，您会想知道如何解决它。答案是将 phi 添加到 d 并使用该值:一切都会按照 RSA 的方式工作。

那么为什么会发生这种情况呢？该算法计算扩展 gcd。 egcd 的结果是 a*e + b*phi = gcd，对于 RSA，我们有 gcd = 1 所以 a*e + b *phi = 1。

如果你看看这个方程模 phi (这是乘法组的阶数)，那么 a*e == 1 mod phi 这就是你所需要的让 RSA 发挥作用。事实上，通过相同的同余，您可以将 phi 的任意倍数与 a 相加或相减，并且同余仍然成立。

现在再看一下方程:a*e + b*phi = 1。我们知道e和phi是正整数。这个方程中不能包含所有正整数，否则它加起来不可能等于 1(它会比 1 大得多)。因此，这意味着 a 或 b 将为负数。有时a 为负，有时b 为负。当它是 b 时，您的 a 就会如您所愿:一个正整数，然后将其分配给值 d。但其他时候，您会得到 a 的负值。我们不希望出现这种情况，因此只需向其中添加 phi 并将其设为 d 的值即可。