背景RSA 加密过程看似简单c m e m o d n c m^e \bmod ncmemodn但直接计算解密操作m c d m o d n m c^d \bmod nmcdmodn效率很低因为d 通常是非常大的整数与 n 同数量级。什么是中国剩余定理优化CRT为了加速解密运算会将私钥指数d拆分成两部分存储dp d mod (p-1)dq d mod (q-1)这种方法叫做CRT 优化中国剩余定理优化广泛用于实际 RSA 产品中。CRT 优化原理核心思想分而治之将对大模数 n 的幂运算拆分为对两个小模数 p 和 q 的幂运算模数 n p × qp、q 为大素数分别计算模 p 和模 q 的结果最后用 CRT 合并得到最终结果效率提升约 4 倍指数长度减少一半参数公式已知 RSA 私钥参数p, q大素数n p × qd私钥指数定义CRT 参数d p d m o d ( p − 1 ) d q d m o d ( q − 1 ) q inv q − 1 m o d p ( 满足 q ⋅ q inv ≡ 1 ( m o d p ) 也就是 p 模 q 下的逆元 ) p inv p − 1 m o d q ( 满足 p ⋅ p inv ≡ 1 ( m o d q ) 也就是 q 模 p 下的逆元 ) \begin{aligned} dp d \bmod (p-1) \\ dq d \bmod (q-1) \\ q_{\text{inv}} q^{-1} \bmod p \quad (\text{满足 } q \cdot q_{\text{inv}} \equiv 1 \pmod{p}也就是p 模 q 下的逆元)\\ p_{\text{inv}} p^{-1} \bmod q \quad (\text{满足 } p \cdot p_{\text{inv}} \equiv 1 \pmod{q}也就是q 模 p 下的逆元) \end{aligned}dpdqqinvpinvdmod(p−1)dmod(q−1)q−1modp(满足q⋅qinv≡1(modp)也就是p模q下的逆元)p−1modq(满足p⋅pinv≡1(modq)也就是q模p下的逆元)解密原理由于 dp d mod (p-1)dq d mod (q-1)根据费马小定理cdmod p cdpmod p因为 d ≡ dp mod (p-1)cdmod q cdqmod q因为 d ≡ dq mod (q-1)所以可以分别在较小的模 p 和模 q 下计算幂运算再合并结果。解密步骤步骤一分别在模 p 和模 q 下计算m1 cdpmod pm2 cdqmod q步骤二用 CRT 合并恢复 m有两种等价公式公式 Am m1 p × ((m2 - m1) × pinv mod q)公式 Bm m2 q × ((m1 - m2) × qinv mod p)简单例子我们用 p13, q17, e5 的例子来演示 CRT 解密。选择明文 m 20。加密明文mn p×q 13 × 17 221c memod n 205mod 221 141普通解密φ(n)(p-1)(q-1)12×16192e×d ≡ 1(mod φ (n))5×d ≡ 1(mod 192)从1开始带入得到d77的时候满足公式mcdmod n 14177mod 221 20可以看到这个计算量还是挺大的CRT解密φ(n)(p-1)(q-1)12×16192e×d ≡ 1(mod φ (n))5×d ≡ 1(mod 192)dp d mod (p-1) 77 mod 12 5dq d mod (q-1) 77 mod 16 13步骤一分别在模 p 和模 q 下计算m1 cdpmod p 1415mod 13141 mod 13 11112 121 mod 13 4114 42 16 mod 13 3115 114× 11 3 × 11 33 mod 13 33 - 2×13 7所以 m1 7m2 cdqmod q 14113mod 17141 mod 17 552 25 mod 17 854 82 64 mod 17 1358 132 169 mod 17 16513 58× 54× 51 16 × 13 × 5 1040 mod 17 1040 - 61×17 1040 - 1037 3所以 m2 3注意m1 7m2 3两者都不等于明文 m 20而且两者彼此也不相等这正是 CRT 合并发挥作用的地方。代码实现m1pow(c,dp,p)m2pow(c,dq,q)步骤二用 CRT 合并先求 pinv p(-1)mod q 13(-1)mod 17找 13 × ? ≡ 1 (mod 17)13 × 4 52 3 × 17 1所以 pinv 4用公式 Am m1 p × ((m2 - m1) × pinv mod q)m2 - m1 3 - 7 -4在模 17 下 -4 mod 17 13(m2 - m1) × pinv 13 × 4 52 mod 17 52 - 3×17 1m 7 13 × 1 7 13 20✓验证普通解密 m cdmod n 14177mod 221 20与 CRT 解密结果相同代码实现pinvmod_inverse(p,q)m_crtm1p*(((m2-m1)*pinv)%q)m_crtm_crt%n代码实现# # RSA CRT 优化解密dp/dq 的正常用法# ## 利用中国剩余定理加速解密# 普通解密: m c^d mod n大模数慢# CRT解密: m1 c^dp mod p, m2 c^dq mod q再合并小模数快# defexgcd(a,b):扩展欧几里得算法返回 (gcd, x, y) 使得 a*x b*y gcdold_r,ra,b old_s,s1,0old_t,t0,1whiler!0:qold_r//r old_r,rr,old_r-q*r old_s,ss,old_s-q*s old_t,tt,old_t-q*treturnold_r,old_s,old_tdefmod_inverse(a,m):计算 a 在模 m 下的逆元g,x,_exgcd(a%m,m)ifg!1:raiseValueError(f{a}和{m}不互质逆元不存在)returnx%mdefmain():# ---- RSA 参数 ----p13q17np*q e5d77# 私钥# ---- 计算 dp, dqCRT 优化的关键----dpd%(p-1)# dp d mod (p-1)dqd%(q-1)# dq d mod (q-1)# ---- 计算逆元用于 CRT 合并----pinvmod_inverse(p,q)# pinv p^(-1) mod qqinvmod_inverse(q,p)# qinv q^(-1) mod p# ---- 加密 m20选择使得 m1 ≠ m 且 m2 ≠ m 的例子----m20cpow(m,e,n)print( RSA CRT 优化解密 )print(fp {p}, q {q}, n {n})print(fd {d})print(fdp d mod (p-1) {dp})print(fdq d mod (q-1) {dq})print(fpinv p^(-1) mod q {pinv})print(fqinv q^(-1) mod p {qinv})print(f明文 m {m})print(f密文 c m^e mod n {m}^{e}mod{n}{c})print()# ---- 方法一普通解密 ----m_normalpow(c,d,n)print(f方法一普通解密: m c^d mod n {c}^{d}mod{n}{m_normal})print()# ---- 方法二CRT 优化解密 ----# 步骤1: 分别在模 p 和模 q 下计算m1pow(c,dp,p)m2pow(c,dq,q)print(f方法二CRT 优化解密:)print(f 步骤1: m1 c^dp mod p {c}^{dp}mod{p}{m1})print(f m2 c^dq mod q {c}^{dq}mod{q}{m2})print(f 注意: m1 {m1}, m2 {m2}, 两者都不等于 m {m}!)# 步骤2: 用 CRT 合并# 公式 A: m m1 p * ((m2 - m1) * pinv mod q)m_crtm1p*(((m2-m1)*pinv)%q)m_crtm_crt%nprint(f 步骤2: m m1 p * ((m2 - m1) * pinv mod q))print(f m {m1}{p}* (({m2}-{m1}) *{pinv}mod{q}))print(f m {m1}{p}* ({((m2-m1)*pinv)}mod{q}))print(f m {m1}{p}*{((m2-m1)*pinv)%q})print(f m {m_crt})# 验证print()print(f验证: 普通解密 {m_normal}, CRT解密 {m_crt}, 相等?{m_normalm_crt})if__name____main__:main()运行结果RSA CRT 优化解密p13, q17, n221d77dpd mod(p-1)5dqd mod(q-1)13pinvp^(-1)mod q4qinvq^(-1)mod p10明文 m20密文 cm^e mod n20^5 mod221141方法一普通解密: mc^d mod n141^77 mod22120方法二CRT 优化解密: 步骤1: m1c^dp mod p141^5 mod137m2c^dq mod q141^13 mod173注意: m17, m23, 两者都不等于 m20!步骤2: mm1 p *((m2 - m1)* pinv mod q)m713*((3-7)*4mod17)m713*(-16 mod17)m713*1m20验证: 普通解密20, CRT解密20, 相等? True作业dp 和 dq 双泄露直接解密题目https://ctf2.dasctf.com/dashboard/practice/b9bbb32f-f186-458f-b90b-12440c0f6aea?tabchallengeschallenge00476e14-24c3-4f98-824e-9e8faa6f6d85p8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229q12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469dp6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929dq783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041c24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852解题过程第一步分析已知条件题目给了p、q、dp、dq、c唯独没给e。对照前面的表格这是典型的dp、dq 双泄露场景有 dp、dq → 可以分别算 m mod p 和 m mod q有 p、q → 可以做 CRT 合并没有 e → 但根本不需要 e第二步用 CRT 直接解密np*q m1pow(c,dp,p)# m mod pm2pow(c,dq,q)# m mod qpinvmod_inverse(p,q)mm1p*(((m2-m1)*pinv)%q)mm%n具体实现代码# # dp/dq 双泄露直接解密# ## 已知: p, q, dp, dq, c没有 e# 目标: 用 CRT 直接恢复明文 m无需 e 和 d## 原理:# m1 c^dp mod p → m mod p# m2 c^dq mod q → m mod q# CRT 合并 → m mod n m因为 m n# defexgcd(a,b):扩展欧几里得算法返回 (gcd, x, y) 使得 a*x b*y gcdold_r,ra,b old_s,s1,0old_t,t0,1whiler!0:qold_r//r old_r,rr,old_r-q*r old_s,ss,old_s-q*s old_t,tt,old_t-q*treturnold_r,old_s,old_tdefmod_inverse(a,m):计算 a 在模 m 下的逆元g,x,_exgcd(a%m,m)ifg!1:raiseValueError(f{a}和{m}不互质逆元不存在)returnx%mdefmain():# ---- 题目参数 ----p8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229q12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469dp6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929dq783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041c24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852np*qprint( dp/dq 双泄露直接解密 )print(f已知: p, q, dp, dq, c没有 e)print(fn p * q {n})print()# ---- 步骤一: 分别计算 m1, m2 ----m1pow(c,dp,p)m2pow(c,dq,q)print(fm1 c^dp mod p {m1})print(fm2 c^dq mod q {m2})print()# ---- 步骤二: 求 pinv ----pinvmod_inverse(p,q)print(fpinv p^(-1) mod q {pinv})print(f验证: p * pinv mod q {(p*pinv)%q})print()# ---- 步骤三: CRT 合并 ----mm1p*(((m2-m1)*pinv)%q)mm%nprint(fm m1 p * ((m2 - m1) * pinv mod q) mod n)print(fm {m})print()# ---- 转换为字节串 ----m_bytesm.to_bytes((m.bit_length()7)//8,big)print(f明文(字节串):{m_bytes})try:decodedm_bytes.decode(utf-8)print(f明文(字符串):{decoded})exceptUnicodeDecodeError:print(f明文(hex):{m_bytes.hex()})if__name____main__:main()运行结果dp/dq 双泄露直接解密已知: p, q, dp, dq, c没有 e np * q109210398828158223465895635258029643930515693675330017779193028528096972652708069255883624939676091261905307196813890635754474687965306531502974686518298689014392416676342645001746385863541788507455929231806265338993534706784795837535761853412237421925097396146009391428003980024852446286649902292842662882471236205708947583488541946060878951m1c^dp mod p11630208090204506176302961171539022042721137807911818876637821759101m2c^dq mod q11630208090204506176302961171539022042721137807911818876637821759101pinvp^(-1)mod q4916920835028959325323720506435251340559830138944112676539029926466验证: p * pinv mod q1mm1 p *((m2 - m1)* pinv mod q)mod n m11630208090204506176302961171539022042721137807911818876637821759101明文(字节串): bnoxCTF{W31c0m3_70_Ch1n470wn}明文(字符串): noxCTF{W31c0m3_70_Ch1n470wn}本题中 m1 m2说明明文 m 同时小于 p 和 qm 比 p、q 都小所以 m mod p m mod q mCRT 合并后还是 m 本身。这是最简单的情况——连合并步骤都可以省掉。答案noxCTF{W31c0m3_70_Ch1n470wn}
