c（加密信息）在RSA中是如何用私钥解密的？
How is c (encrypted message) decrypted by private key in RSA?
今天一直在研究RSA算法的概念，这就是我的理解。
生成密钥对-
- 两个质数（例如p1 = 53，p2 = 59）相乘生成
n（将用作public模数）
- 我们在
n 变量上使用 Euler 的 totient 函数并定义一个新变量 phi。
- 我们生成一个 public 指数
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。 (phi(n) = (p1-1) * (p2-1))
e 与 3 的指数（因为它与 3016 没有任何因数且是奇数）
要使用public键-
之后我们可以分享我们的 e 和 n，因为计算机需要几十年才能从大 n.
获取私钥
我们的通信器将消息编码为十六进制，然后将其转换为 base10 整数。 Communicator 还可以添加随机整数填充以进行保护。
当消息变成数字时，对其进行模幂运算：
[![在此处输入图片描述][3]][3]
例如，如果数字中的消息是 89，如果我们对其进行模幂运算，我们将得到：
1394
问题 -
如果我们的通讯器发送给我们的1394是加密的89（89^3 * mod(59 * 53) = 1394），我们如何使用我们的私钥自动解密这个消息？是否有必须使用的特定公式？
非常感谢您的阅读。
给定：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.
(https://en.wikipedia.org/wiki/Modular_multiplicative_inverse and https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 用于制作 ModInverse)
请注意 dLambda 小于 dPhi。虽然最初的 RSA 论文使用了基于 phi 的模型，但后来它被简化为基于 LCM 的模型。由于 (p-1) 和 (q-1) 都是偶数（因为 p 和 q 是质数！= 2） lambda 最终最多为 phi / 2，为逆函数创建一个更小的模块 space。
因此，假设我们正在执行 raw/unpadded 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 % 3127 = 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
今天一直在研究RSA算法的概念，这就是我的理解。
生成密钥对-
- 两个质数（例如p1 = 53，p2 = 59）相乘生成
n（将用作public模数） - 我们在
n变量上使用 Euler 的 totient 函数并定义一个新变量phi。 - 我们生成一个 public 指数
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。 (phi(n) = (p1-1) * (p2-1))e与3的指数（因为它与 3016 没有任何因数且是奇数）
要使用public键-
之后我们可以分享我们的 e 和 n，因为计算机需要几十年才能从大 n.
我们的通信器将消息编码为十六进制，然后将其转换为 base10 整数。 Communicator 还可以添加随机整数填充以进行保护。
当消息变成数字时，对其进行模幂运算：
[![在此处输入图片描述][3]][3]
例如，如果数字中的消息是 89，如果我们对其进行模幂运算，我们将得到：
1394
问题 -
如果我们的通讯器发送给我们的1394是加密的89（89^3 * mod(59 * 53) = 1394），我们如何使用我们的私钥自动解密这个消息？是否有必须使用的特定公式？
非常感谢您的阅读。
给定：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.
(https://en.wikipedia.org/wiki/Modular_multiplicative_inverse and https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 用于制作 ModInverse)
请注意 dLambda 小于 dPhi。虽然最初的 RSA 论文使用了基于 phi 的模型，但后来它被简化为基于 LCM 的模型。由于 (p-1) 和 (q-1) 都是偶数（因为 p 和 q 是质数！= 2） lambda 最终最多为 phi / 2，为逆函数创建一个更小的模块 space。
因此，假设我们正在执行 raw/unpadded 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 % 3127 =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