2

我一直在通过网络书籍工作并点击 RSA 部分。考虑 p=5 和 q=11 的 RSA 算法。

so I get N = p*q = 55 right?

and z = (p-1) * (q -1) = 40

我想我做对了，但是这本书对如何计算并不是很清楚。

书中的例子说 e = 3 但没有给出原因。是因为作者喜欢还是另有原因？

以及如何找到 d 以使 de= 1(mod z) 和 d < 160

感谢您在这方面的任何帮助，它现在有点在我之上。

4

2 回答 2

3

您对n和z的计算是正确的。

RSA 密码系统由三个变量n、d和e组成。变量e是三者中最不重要的，通常是任意选择以使计算简单；3 和 65537 是e最常见的选择。唯一的要求是e是奇数并且与 totient 互质（z在你的实现中）；因此，e经常被选为素数，因此无论选择什么 totient，它都将是 totient 的互素数。3和65537经常用于e的原因是因为它使计算变得容易；这两个数字在其二进制表示中只有两个 1 位，因此只需要复杂循环的两次迭代。

您可以在我的博客上看到 RSA 密码系统的实现。如果您在那里四处逛逛，您还会发现其他一些您可能感兴趣的与加密相关的东西。

于 2013-04-03T15:09:01.063 回答
2

您正在寻找的是扩展欧几里得算法

例如，请参阅维基百科或这里

于 2013-04-03T17:27:23.620 回答