20

我是一名高中生,正在写一篇关于 RSA 的论文,我正在用一些非常小的素数做一个例子。我了解系统的工作原理,但我无法终生使用扩展欧几里得算法计算私钥。

这是我到目前为止所做的:

  • 我选择了质数 p=37 和 q=89 并计算出 N=3293
  • 我计算出 (p-1)(q-1)=3168
  • 我选择了一个数字 e,以便 e 和 3168 互质。我正在用标准的欧几里得算法检查这个,效果很好。我的 e=25

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

使用扩展欧几里得算法找到 d 使得 de+tN=1 我得到 -887•25+7•3168=1。我把 7 扔掉,得到 d=-887。但是,尝试解密消息是行不通的。

我从我的书中知道 d 应该是 2281,它有效,但我不知道他们是如何得出这个数字的。

任何人都可以帮忙吗?在过去的 4 个小时里,我一直在尝试解决这个问题,并且到处寻找答案。我正在手动执行扩展欧几里得算法,但由于结果有效,我的计算应该是正确的。

提前致谢,

麦兹

4

1 回答 1

20

你离得太近了,你会踢自己。

3168-887=2281。

具体来说,如果你有一个 mod x,那么 A 必须满足0<=a<x。如果不是,请根据需要多次添加或减去 x,直到您在此范围内。这称为模运算。

您可能想阅读线性同余和数论。这些主题是英国学位级别的数学(我猜你会称之为大学),所以如果看起来有点奇怪,请不要担心。线性同余只是说-887 mod 3168并且2281 mod 3168实际上是同一件事,因为它们是同一类的一部分,结果是2281 mod 3168在所需范围内的类。2281+3168 mod 3168也会在那个班级。

玩得开心!

PS PARI/GP 是实用数理论家用于计算的实用程序数。也许值得一瞧。

于 2010-12-12T16:33:11.863 回答