小编mad*_*ads的帖子

我是一名高中生,正在写一篇关于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