RSA:使用扩展欧几里德算法的私钥计算

Question

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

Answer 1

你太近了,你会踢自己.

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是理论家用于计算的公用事业编号.也许值得一瞧.