我是一名高中生,正在写一篇关于 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 个小时里我一直在尝试解决这个问题,并到处寻找答案。我正在手工执行扩展欧几里得算法,但由于结果有效,我的计算应该是正确的。
提前致谢,
Mads
你离得太近了,你会踢自己的。
3168-887=2281。
具体来说,如果你有一个 mod x,那么 A 必须满足0<=a<x
。如果不是,请根据需要多次添加或减去 x,直到达到此范围。这称为模运算。
您可能想阅读线性同余和数论。这些主题是英国的学位水平数学(我猜你称之为大学),所以不要担心它看起来有点奇怪。线性同余简单地说-887 mod 3168
and 2281 mod 3168
实际上是同一件事,因为它们是同一类的一部分,该类结果为2281 mod 3168
在要求的范围内。2281+3168 mod 3168
也会在那个班级。
玩得开心!
附: PARI/GP 是一个实用数论学家用于计算的工具。也许值得一瞧。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)