RSA:基于扩展欧几里德算法的私钥计算
RSA:基于扩展欧几里德算法的私钥计算
提问于 2010-12-13 00:26:53
我是一名高中生，正在写一篇关于RSA的论文，我正在用一些非常小的素数做一个例子。我知道系统是如何工作的，但我终生不能使用扩展的欧几里德算法来计算私钥。
以下是我到目前为止所做的工作：
我选择了质数p=37和q=89，我计算了N=3293，，
- ，我选择了一个数字e，所以e和3168是相对质数。我正在用标准的欧几里德算法检查这个，它工作得很好。My e=25
现在我只需要计算私钥d，它应该满足ed=1 (Mod3168)
使用扩展的欧几里德算法找到d，这样我就得到了-887·25+7·3168=1，我去掉了7，得到d=-887。然而，试图解密一条消息，这是不起作用的。
我从我的书中知道d应该是2281，它是有效的，但我不知道他们是如何得出这个数字的。
有人能帮上忙吗？在过去的4个小时里，我一直在试着解决这个问题，并且到处寻找答案。我手工做了扩展的欧几里德算法，但由于结果是有效的，我的计算应该是正确的。
提前谢谢你，
Mads
回答 1
Stack Overflow用户
发布于 2010-12-13 00:33:12
你太接近了，你会踢到自己的。
具体地说，如果你有mod x，那么A必须满足0<=a<x。如果不是，则根据需要多次添加或减去x，直到您在此范围内。这就是所谓的模运算。
你可能想要阅读线性同余和数论。在英国，这些主题是学位级别的数学(我猜你会称之为大学)，所以如果看起来有点奇怪，不要担心。线性同余简单地说，-887 mod 3168和2281 mod 3168实际上是同一件事，因为它们是同一个类的一部分，这个类在所需的范围内被证明为2281 mod 3168。2281+3168 mod 3168也会在那个班级里。
玩得开心!
P.S. PARI/GP是理论家用于计算的效用数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4422633
复制相关文章
相似问题