RSA:用扩展欧氏算法计算私钥

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (66)

以下是所做的工作:

  • 我选择了素数p=37和q=89,并计算出N=3293。
  • 我计算了(p-1)(q-1)=3168。
  • 我选择了一个数字e,所以e和3168是相对素数。我用标准的欧几里得算法来检验,这很好用。我e=25

现在我只需要计算私钥d,它应该满足ed=1(Mod 3168)

用扩展的欧氏算法求d,使de+TN=1i得到-887·25+7·3168=1。我把7扔掉,得到d=-887。然而,试图解密一条消息,这是行不通的。

从我的书中知道,d应该是2281,而且它可以工作,但我不知道他们是如何得出这个数字的。

提问于
用户回答回答于

3168-887=2281

具体来说,如果你有一个mod x,那么A必须满足0<=a<x。如果没有,可以根据需要添加或减去x,直到在此范围内。这就是所谓的模块化算法。

你可能想读一读线性同余和数论。性同余简单地说-887 mod 31682281 mod 3168实际上是相同的,因为它们是同一个类的一部分,2281 mod 3168在规定的范围内。2281+3168 mod 3168也会出现在那个课程。

P.S.PAI/GP是一种实用数理论家用于计算的方法。也许值得一看。

扫码关注云+社区