利用中国剩余定理进行弱RSA解密

先决条件：RSA算法为什么RSA解密的过程会如此缓慢呢？RSA解密的过程比加密要慢，因为在解密过程中，私钥参数“d”的值必然很大。此外，参数“p”和“q”也是非常大的质数。给定整数c、e、p和q，需要找到这样的m值：c = m的e次方 mod (p * q)（针对弱整数的RSA解密算法）基础知识：

• RSA是一种公钥加密系统，用于实现消息的安全传输。
• RSA过程通常包括四个步骤： (1) 密钥生成 (2) 密钥分发 (3) 加密 (4) 解密
• 消息/信息加密整个过程都是使用“公钥”来完成的。
• 消息/信息解密整个过程是使用“私钥”来完成的。与公钥一起生成的参数（p、q、d）就是用来进行加密和解密的。
• 私钥只有用户自己知道，而公钥则可以告诉任何希望向拥有相应私钥的人发送加密消息的人。
• 公钥由两个参数组成：模数n和指数e。模数是由两个非常大的质数相乘得到的（如下所示，这两个质数分别表示为p和q）。要解密这条消息，用户需要将模数n分解为两个质数因子。而找到e的模逆元则是一个相当困难的任务。正是因为这个原因，RSA算法才具有安全性。
• 首先，需要将文本消息转换为相应的十进制数值。这个十进制数值就是参数“m”的值，我们接下来会计算这个值。现在，我们可以通过以下方式对这条消息进行加密：c = m的e次方 mod (p * q)其中，c表示被加密的文本。

在这段代码中，我们利用了模数以及指数的数值较弱这一特点，试图通过找到 p、q 和 d 的值来破解加密算法。在这些示例中，我们将尝试在已知 p 和 q 的情况下，找到 d 的值。注意：在这个例子中，我们使用的数值都相对较小。p以及q但实际上，我们使用的数值都是非常大的。p还有q为了确保我们的RSA系统能够保持安全性。示例：

输入： 
c = 1614
e = 65537
p = 53
q = 31

输出：
1372

说明：
We calculate c = pow(m, e) % (p * q). 
Insert m = 1372. 
On calculating, we get c = 1614.

输入：
c = 3893595
e = 101
p = 3191
q = 3203

输出：
6574839

说明：
As shown above, if we calculate pow(m, e)mod(p * q)
with m = 6574839, we get c = 3893595

通常情况下，我们可以通过以下步骤来计算 m 的值：(1) 计算 e 的模运算逆元。我们可以使用以下公式来辅助计算：d = e^(-1) * (mod lambda(n))其中，λ表示……卡迈克尔 totient 函数. 阅读卡迈克尔函数m = pow(c, d) % (p * q)(3) 我们可以利用中国剩余定理来更快地完成这个计算。关于中国剩余定理的更多内容，可以参考下面的函数说明。 如需了解更多关于中国剩余定理的信息，可以查阅RSA加密系统相关的资料。 以下是这种方法的Python实现： Python

# 用于计算两个数的最大公约数的函数# 使用欧几里得算法进行整数运算def gcd(p, q):        if q == 0:        返回 p            返回 gcd(q, p % q)# 用于查找的功能# 两个整数的最大公约数def LCM(p, q):    返回 p * q / GCD(p, q)# 实现扩展功能的函数# 欧几里得算法def egcd(e, φ):        if e == 0:        返回 (φ, 0, 1)    否则:        g, y, x = egcd(φ % e, e)        返回 (g, x - (φ // e) * y, y)# 用于计算模运算中的逆元的函数def modinv(e, φ):        g, x, y = egcd(e, φ)    返回 x % φ# 中国剩余定理的实现def 中国剩余定理(dq, dp, p, q, c):        # 信息部分1    m1 = 功率(c, dp, p)        # 消息部分2    m2 = 功率(c, dq, q)        qinv = modinv(q, p)    h = (qinv * (m1 - m2)) % p    m = m2 + h * q    返回 m# 驱动程序代码p = 9817q = 9907e = 65537c = 36076319d = modinv(e, LCM(p - 1, q - 1))“……”pow(a, b, c) 函数用于计算 a 的 b次方。模数 c 的计算速度，比 pow(a, b) % c 要快得多。此外，我们还使用了中国剩余定理。该方程被拆分后，我们就有必要计算两个数值了。那些其方程中的模值和指数都较小的数值。通过这种方式，可以减少计算时间。“……”dq = 功率(d, 1, q - 1)dp = 功率(d, 1, p - 1)打印 中国剩余定理(dq, dp, p, q, c)

输出：

41892906