RSA加密：系数k

您的问题有几个子问题。

我将从可以有多少个私钥的问题开始。

是的，理论上可以有几个d这样的，(m**e)**d == 1 (mod pq)对于所有m的范围[1,pq-1]

例子。让我们拿p = 11和q = 31。对于这对N = 341和phi(N) = 300. 让我们把它当作一个公钥e = 7。如果我们采用俄罗斯维基百科中给出的 RSA 的传统描述，那么我们应该采用d = 43. 的确，7*43 = 301 == 1 mod 300。您可以直接检查是否执行m了 [1, 340] 范围内的任何 RSA 加密-解密：(m**7)**43 == m (mod 341)

现在让我们尝试对 number 进行相同的检查d1 = 13。让我们用 Python 计算所有可能的值(m**7)**13 - m (mod 341)：

>>> set([((m**7)**13) % 341 - m for m in range(1,341)])
{0}

这个零是什么意思？这d1也是e=7. 此外，私钥将是数字 73、103、133 等。所有这些数字都是由一个事实将它们与 13 分开的，这个数字是 30 的倍数。什么是30？p-1这是 10（即）和 30（即q-1）的最小公倍数

在现实生活中，一个d数字是这样选择的d*e == 1 mod( lcm(p-1,q-1) )。该链接指向 openssl 中的 RSA 私钥生成功能。您可以看到正在反转的模数e。

现在谈谈他们d在视频中的想法。

更严格地说，它应该是这样的——让我们选择k它k*Phi(n)+1完全可以被 整除e。这k=2仅适用于他们的例子。在我的 11 和 31 示例中k=1。

这是为什么。如果d = (k*Phi(n)+1)/e是整数，则d*e = k*Phi(n)+1，这意味着d*e与单位模数相当Phi(n)。换句话说，d有欧拉函数取e模。

如果且互质，这k总是存在的。ePhi(n)

所以你可以反转，但效率非常低。

更新

如何有效反转。

枚举算法k的平均复杂度为n，其中n是执行反演的模数。在大的情况下，n这个过程永远不会结束。

在实践中，使用了扩展的欧几里得算法。它的最坏情况复杂度是一个较大数的对数数量级。从这个链接中，我获取了 Python 的实现并遵循了代码bezout(30,7)。明白(-3, 13, 1)是什么意思-3*30 + 13*7 = 1。

我们用模比较替换相等，得到13*7与 1 模 30 可比的结果。因此，13 是 7 模 30 的倒数。答案分 3 步找到，搜索 13。在将 7 模 300 取反的情况下（值欧拉函数的 11 * 31) 倒数也分 3 步找到，并通过枚举在 43 中找到。枚举效率低下的另一个示例k：通过欧几里得算法将 7 模 1009（大于 1000 的第一个素数）取反在 2 中执行步骤，并从统一865枚举。你可以排序，但不需要。