RSA加密算法五:扩展欧几里得算法计算d

之前的算法中d的值是枚举的,总觉得很奇怪,虽然是为了演示

这次用官方指定算法:扩展欧几里得算法来计算得到d的值

代码只写如何从p,q,e中得到d


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = egcd(b, a%b)
        d = x-a/b*y
        return g, y, d

def get_d(fn,e):
    d = egcd(fn, e)[2]
    if d < 0:
        d = d+fn
    return d

p, q, e = 61, 53, 17
fn = (p-1)*(q-1)
print get_d(fn, e)

计算得到的结果为 2753

 

您可能还喜欢...