【CTF-CRYPTO-教学-RSA】第四节：dp泄露攻击（已知dp、e、n，无需私钥即可解密）

什么是 dp 泄露攻击如果攻击者获取了dp或 dq、e、n和c就可以在不知道完整私钥的情况下分解 n恢复出 p 和 q计算出完整的私钥 d解密密文 c攻击原理关键数学推导e × dp - 1 m × (p-1)根据 RSA 性质私钥指数 d 满足e × d ≡ 1 (mod φ(n))因为 φ(n) (p-1)(q-1)所以 d 也满足e × d ≡ 1 (mod p-1)即e × d 1 k × (p-1)其中 k 为某个整数。而 dp d mod (p-1)意味着 d 可以写成d dp m × (p-1)其中 m 为某个整数。将 d 的表达式代入 e × d ≡ 1 (mod p-1)e × (dp m × (p-1)) ≡ 1 (mod p-1)展开后e × dp e × m × (p-1) ≡ 1 (mod p-1)因为 e × m × (p-1) 一定是 (p-1) 的倍数所以e × dp ≡ 1 (mod p-1)即e × dp - 1 m × (p-1)其中 m 是某个整数。m 的取值范围1 ≤ m e由于 0 dp p-1且 e 1我们有e × dp e × (p-1)e × dp - 1 e × (p-1) - 1所以 m e又因为 e × dp 1dp ≥ 1, e ≥ 2所以 m ≥ 1。结论m 的取值范围是 1 ≤ m e攻击步骤枚举 m 从 1 到 e-1对每个 m计算p (e × dp - 1) / m 1验证 n mod p 0如果成立则找到了 p计算 q n / p计算 φ(n) (p-1)(q-1)计算 d e^(-1) mod φ(n)解密密文m c^d mod n简单例子我们用p13, q17来演示整个过程。前置知识已知p 13, q 17n p × q 13 × 17 221φ(n) (p-1)(q-1) 12 × 16 192e 5公钥指数计算私钥d e^(-1) mod φ(n) 5^(-1) mod 192找 5 × ? ≡ 1 (mod 192)5 × 77 385 2 × 192 1所以 d 77计算 dpdp d mod (p-1) 77 mod 12 5加密明文 m2c m^e mod n 2^5 mod 221 32攻击过程现在假设攻击者只知道n221, e5, dp5, c32要恢复明文。第一步计算 e×dp - 1e × dp - 1 5 × 5 - 1 24所以 24 m × (p-1)其中 1 ≤ m 5代码实现edp_minus1e*dp-1第二步枚举 mm1p 24/1 1 25n mod 25 221 mod 25 21 ≠ 0 ✗m2p 24/2 1 13n mod 13 221 mod 13 0 ✓ 找到了代码实现# ---- 第二步: 枚举 m 求 p ----foundFalseform_valinrange(1,e):ifedp_minus1%m_val0:candidate_pedp_minus1//m_val1ifn%candidate_p0:p_recoveredcandidate_p q_recoveredn//p_recovered m_foundm_val foundTrueprint(fm{m_val}: p (e*dp-1)/{m_val} 1 {edp_minus1}/{m_val} 1 {candidate_p})print(f n mod{candidate_p}{n%candidate_p}✓ 找到因子!)breakelse:print(fm{m_val}: p {candidate_p}, n mod p {n%candidate_p}✗)else:candidate_pedp_minus1//m_val1print(fm{m_val}: e*dp-1 不能被{m_val}整除, p {candidate_p}✗)ifnotfound:print(未找到正确的因子)return第三步恢复 qq n / p 221 / 13 17第四步计算 φ(n) 和 dφ(n) (p-1)(q-1) (13-1)(17-1) 12 × 16 192d e(-1)mod φ(n) 5(-1)mod 192 77第五步解密m cdmod n 3277mod 221 2验证加密时 m2解密后 m2闭环成功代码实现# # RSA dp 泄露攻击# ## 已知: n, e, dp, c# 目标: 恢复 p, q, d解密密文 c## 原理:# e*dp ≡ 1 (mod p-1)# e*dp - 1 m*(p-1), 其中 1 m e# 枚举 m 即可求出 p# 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():# ---- 题目参数 ----e5n221dp5c32print( RSA dp 泄露攻击 )print(f已知: e{e}, n{n}, dp{dp}, c{c})print()# ---- 第一步: 计算 e*dp - 1 ----edp_minus1e*dp-1print(fe*dp - 1 {e}*{dp}- 1 {edp_minus1})print(f需要枚举 m 从 1 到{e-1}(因为 1 m e))print()# ---- 第二步: 枚举 m 求 p ----foundFalseform_valinrange(1,e):ifedp_minus1%m_val0:candidate_pedp_minus1//m_val1ifn%candidate_p0:p_recoveredcandidate_p q_recoveredn//p_recovered m_foundm_val foundTrueprint(fm{m_val}: p (e*dp-1)/{m_val} 1 {edp_minus1}/{m_val} 1 {candidate_p})print(f n mod{candidate_p}{n%candidate_p}✓ 找到因子!)breakelse:print(fm{m_val}: p {candidate_p}, n mod p {n%candidate_p}✗)else:candidate_pedp_minus1//m_val1print(fm{m_val}: e*dp-1 不能被{m_val}整除, p {candidate_p}✗)ifnotfound:print(未找到正确的因子)return# ---- 第三步: 恢复 q ----print(f\np {p_recovered})print(fq n/p {q_recovered})print(f验证: p*q n?{p_recovered*q_recoveredn})# ---- 第四步: 计算 φ(n) 和 d ----phi(p_recovered-1)*(q_recovered-1)dmod_inverse(e,phi)print(f\nφ(n) (p-1)(q-1) ({p_recovered}-1)({q_recovered}-1) {phi})print(fd e^(-1) mod φ {d})# ---- 第五步: 解密 ----m_decpow(c,d,n)print(f\n解密: m c^d mod n {c}^{d}mod{n}{m_dec})# ---- 转换为字节串 ----m_bytesm_dec.to_bytes((m_dec.bit_length()7)//8,big)print(f\n明文:{m_bytes})if__name____main__:main()运行结果RSA dp 泄露攻击已知:e5,n221,dp5,c32e*dp -15*5 -124需要枚举 m 从1到4(因为1me)m1: p25, n mod p21✗m2: p(e*dp-1)/2 124/2 113n mod130✓ 找到因子!p13qn/p17验证: p*qn? True φ(n)(p-1)(q-1)(13-1)(17-1)192de^(-1)mod φ77解密: mc^d mod n32^77 mod2212明文: b\x02作业dp泄露攻击题目https://ctf2.dasctf.com/dashboard/practice/b9bbb32f-f186-458f-b90b-12440c0f6aea?tabchallengeschallenge22420fad-675d-48a7-adb7-2ab894c932bfe 65537 n 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113 dp 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657 c 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751 求明文作为 flag 提交解题过程第一步分析已知条件已知 e65537, n, dp, c这是一个 dp 泄露攻击的典型场景需要通过枚举 m1 ≤ m e来分解 n第二步计算 e×dp - 1 并枚举 medp_minus1e*dp-1# 枚举 m 从 1 到 65536form_valinrange(1,e):ifedp_minus1%m_val0:candidate_pedp_minus1//m_val1ifn%candidate_p0:pcandidate_p qn//pbreak找到 m 4404成功分解 np 13468634736343473907717969603434376212206335187555458742257940406618189481177835992217885676243155145465521141546915941147336786447889325606555333350540003q 18432009829596386103558375461387837845170621179295293289126504231317130550979989727125205467379713835047300158256398009229511746203459540859429194971855371第三步计算私钥 d 并解密phi(p-1)*(q-1)dmod_inverse(e,phi)mpow(c,d,n)具体实现代码# # dp泄露攻击# 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():# ---- 题目参数 ----e65537n248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113dp905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657c140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751print( 作业3: dp泄露攻击 )print(f已知: e{e})print(fn{n})print(fdp{dp})print(fc{c})print()# ---- 第一步: 计算 e*dp - 1 ----edp_minus1e*dp-1print(fe*dp - 1 {e}*{dp}- 1)print(f{edp_minus1})print(f需要枚举 m 从 1 到{e-1})print()# ---- 第二步: 枚举 m 求 p ----foundFalseform_valinrange(1,e):ifedp_minus1%m_val0:candidate_pedp_minus1//m_val1ifn%candidate_p0:pcandidate_p qn//p m_foundm_val foundTrueprint(f找到 m {m_found})print(fp (e*dp-1)/m 1)print(f ({edp_minus1})/{m_found} 1)print(f {p})print(fq n/p {q})print(f验证: p*q n?{p*qn})breakifnotfound:print(未找到正确的因子)return# ---- 第三步: 计算 φ(n) 和 d ----phi(p-1)*(q-1)dmod_inverse(e,phi)print(f\nφ(n) (p-1)(q-1))print(f {phi})print(fd {e}^(-1) mod φ)print(f {d})# ---- 第四步: 解密 ----m_decpow(c,d,n)print(f\n解密: m c^d mod n)print(f {m_dec})# ---- 第五步: 转换为字节串 ----m_bytesm_dec.to_bytes((m_dec.bit_length()7)//8,big)print(f\n明文(字节串):{m_bytes})try:decodedm_bytes.decode(utf-8)print(f明文(字符串):{decoded})exceptUnicodeDecodeError:print(f明文(hex):{m_bytes.hex()})if__name____main__:main()运行结果作业3: dp泄露攻击已知:e65537n248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113dp905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657c140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751e*dp -165537*905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657 -159315867378856659089589938133524992838556700165994240300903969550746506475107189709727568518174855260630155107372617804812871207516504589971269688075778168808需要枚举 m 从1到65536找到 m4404p(e*dp-1)/m 113468634736343473907717969603434376212206335187555458742257940406618189481177835992217885676243155145465521141546915941147336786447889325606555333350540003qn/p18432009829596386103558375461387837845170621179295293289126504231317130550979989727125205467379713835047300158256398009229511746203459540859429194971855371验证: p*qn? True φ(n)(p-1)(q-1)248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670446536428489604864269408388233229385110283347278332394130113040720698361459971843083058974654167036569976726345315473316225080897072784301302480781343510740d65537^(-1)mod φ63183802294329275109394617778318843917232869063572889334764759976175767511604500261826320177778480001780606046979134286524100781096232758191739978884872103517518763547448555987181526927783445069597824169314037723507625024774847068531404022517009193374276930768809067581593826912268843157943539151615618807073解密: mc^d mod n3670434958110785066911905751469631231338751225710158680692616521935747246580688484040488309932916523151997明文(字节串): bflag{wow_leaking_dp_breaks_rsa?_98924743502}明文(字符串): flag{wow_leaking_dp_breaks_rsa?_98924743502}答案flag{wow_leaking_dp_breaks_rsa?_98924743502}