c（加密消息）如何用RSA中的私钥解密？

Question

今天我一直在研究RSA算法的概念，这就是我所理解的。

要生成的密钥对 -

• 两个素数（P1 = 53，P2 = 59例如）相乘，以产生n（其将被用作公共模数）
• 我们使用欧拉欧拉功能在我们的n变量上并定义一个新变量phi。
• 我们生成一个公开指数e，条件是它必须是与我们的phi变量不共享因子的小奇数。

• 私钥d从该公式生成：

  

  或d = (k * (phi(n)) + 1)/e。

• 我们用数字代替变量，并得到私钥：

  

  或d = (2 * (3016) + 1)/3 = 2011

  我们代替 -

• k与2（由我所知k必须大于0且小于phi(n)）

• phi(n)与3016（因为p1 * p2 = 3127并且由于结果 是一个素数，我们得到了它披容易使用p1和p2。 （phi(n) = (p1-1) * (p2-1)）

• e与3指数（因为它不共享与3016的任何因素，它是奇数）

要使用公共密钥 -

之后，我们可以分享我们的e和n，因为电脑需要几十年才能从大n获得私钥。

我们的通信器将消息编码到十六进制中，然后将其转换为base10整数。通信器也可以添加随机整数填充以进行保护。

当消息被转变成数，模幂在其上被执行的：

[！[在这里输入的形象描述] [3] [3]

因此，如果数字信息是89例如，如果我们做模幂就可以了，我们会得到：

的问题 -

如果我们的传播者发送给我们1394这是加密的89（89^3 * mod(59 * 53) = 1394），我们如何使用我们的私钥自动解密此消息？是否有一些必须使用的具体公式？

非常感谢您的阅读。

Answer 1

鉴于：p = 53,q = 59,e = 3。

• n = p * q = 3127。
• phi(n) = (p-1) * (q-1) = 3016。
• lambda = LCM(p-1, q-1) = 1508。
• dPhi = ModInverse(e, phi(n)) = ModInverse(3, 3016) = 2011。
• dLambda = ModInverse(e, lambda) = ModInverse(3, 1508) = 503。
• 和CRT参数（在这里我们不会使用）
  • dp = dLambda % (q - 1) = 503 % 58 = 35。
  • dq = dLambda % (p - 1) = 503 % 52 = 39。
  • inverseQ = ModInverse(q, p) = ModInverse(59, 53) = 9。

注意dLambda比dPhi小（https://en.wikipedia.org/wiki/Modular_multiplicative_inverse和https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm分别在ModInverse制作使用）。虽然最初的RSA论文使用基于phi的模型，但稍后将其缩减为基于LCM的模型。由于(p-1)和(q-1)都是偶数（因为p和q是质数！= 2）lambda最终结果最多为phi/2，这使得倒数的模块空间更小。

因此，假设我们正在做原料/护垫与RSA（因为该键来说太小了做填充RSA用）：

考虑：m = 89。

c = m^e % n = 89^3 % 3127 = 704969 % 3127 = 1394。

m = c^d % n = 1394^503 % 3127 = 3.666e1581 % 3127 = ???。

取而代之，我们转到https://en.wikipedia.org/wiki/Modular_exponentiation。

m = ModPow(1394, 503, 3127) =>ModPow(1394, 0b0001_1111_0111, 3127)：

• R：1，碱：（1394％3127）= 1394，指数：0b0001_1111_0111
• R：（1 * 1394）％3127 = 1394，基：（1394 * 1394）％3127 = 1943236％3127 = 1369，指数：0b0000_1111_1011
• R：（1394 * 1369）％3127 = 1908386％3127 = 916，碱：（1369 * 1369）％3127 = 1874161％3127 = 1088，E：0b0111_1101
• R：（916 * 1088）％3127 = 996608％3127 = 2222，碱：（1088 * 1088）％3127 = 1183744％3127 = 1738，E：0b0011_1110
• R：2222，基：（1738 * 1738）％3127 = 3020644％3127 = 3089，E：0b0001_1111
• R：（2222 * 3089）％3127 = 6863758％3127 = 3120，碱：（3089 * 3089）％3127 = 9541921％ 3127 = 1444，e：0b0000_1111
• R：（3120 * 1444）％3127 = 4505280％3127 = 2400，基数：（1444 * 1444）％3127 = 2085136％3 127 = 2554，E：0b0111
• R：（2400 * 2554）％3127 = 6129600％3127 = 680，碱：（2554 * 2554）％3127 = 6522916％3127 = 3121，E：0b0011
• R： （680 * 3121）％3127 = 2122280％3127 = 2174，碱：（3121 * 3121）％3127 = 9740641％3127 = 36，E：0b0001
• R：（2174×36）％3127 = 78264％3127 = 89，碱：（36 * 36）％3127 = 1296％3127 = 1296，E：0b0000
• R：89