之前的DES、AES加密解密，只需要知道怎么调用API接口就可以了，基本不涉及到内部的具体算法，今天来看看中国剩余算法在RSA解密中的应用，下面这道题给了密文c、两个大素数p和q、私钥 d 对 (mod p - 1) 的模dp和私钥 d 对 (mod q - 1) 的模dq，让你解密c。

中国剩余定理CRT可以加速RSA解密过程，当RSA私钥包含了CRT参数 dp 和 dq 时，可以利用CRT来将一次模 N 的解密运算转换为两次模 p 和模 q 的运算，从而加速RSA解密。

ailx10

网络安全优秀回答者

网络安全硕士

去咨询

1、了解RSA 加密5步曲：

（1）选择两个大素数 p 和 q，计算模数 N：

N = p * q。

（2）计算欧拉函数 φ(N)：

φ(N) = (p - 1) * (q - 1)。

（3）选择公钥 e：

选择一个与 φ(N) 互质的指数 e，通常选择较小的质数。

（4）生成私钥 d：

计算 d，使得 (d * e) % φ(N) = 1。

（5）加密明文 m：

将明文 m 转换成整数，然后使用公钥 (e, N) 进行加密，得到密文 c。

2、使用私钥解密密文 c：

使用私钥 (d, N) 对密文 c 进行解密，得到原始的明文 m。

3、RSA 中国剩余定理解密密文c：

dp 是私钥 d 对 (mod p - 1) 的模。换句话说，dp = d mod (p - 1)。dq 是私钥 d 对 (mod q - 1) 的模。换句话说，dq = d mod (q - 1)。中国剩余定理使用私钥 (dp, dq, p, q) 对密文 c 进行解密，得到原始的明文 m。

使用python3编程进行解密，成功获得flag

# -*- coding: utf-8 -*-from Crypto.Util.number import inverse# 已知参数dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961 # 替换为实际的 dp 值dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659 # 替换为实际的 dq 值p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243 # 替换为实际的 p 值q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629 # 替换为实际的 q 值c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885 # 替换为实际的密文 c 值# 使用CRT恢复dqInv = inverse(q, p)m1 = pow(c, dp, p)m2 = pow(c, dq, q)h = (qInv * (m1 - m2)) % pm = m2 + h * q# 输出解密后的明文print(bytes.fromhex(hex(m)[2:]).decode())# Theres_more_than_one_way_to_RSA