RSA计算d

Question

不确定这是否是提出加密问题的正确位置,但是这里是.

我想在RSA中找出"d",我已经计算出p,q,e,n和øn;

p = 79, q = 113, e = 2621

n = pq                   ø(n) = (p-1)(q-1)
n = 79 x 113 = 8927      ø(n) = 78 x 112 = 8736

e = 2621
d = ???

我似乎无法找到d,我知道d应该是一个值... edmodø(n)= 1.任何帮助将不胜感激

编辑:一个例子是e = 17,d = 2753,øn= 3120

17*2753 mod 3120 = 1

Answer 1

您正在寻找e(mod n)的模逆,可以使用扩展的欧几里德算法计算:

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q := b // x # integer division
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

因此,在您的示例中,inverse(17, 3120)= 2753和inverse(2621, 8736)= 4373.如果您不想实现该算法,可以向Wolfram | Alpha询问答案.