不互素时的攻击与修复)
1. RSA基础回顾与问题背景RSA加密算法的安全性基于大整数分解的困难性。在标准RSA中公钥指数e和私钥指数d需要满足$e \cdot d \equiv 1 \pmod{\phi(n)}$其中$\phi(n)(p-1)(q-1)$。这意味着e必须与$\phi(n)$互素否则d不存在模逆元。但在NPUCTF2020的EzRSA题目中出题人故意设置了一个特殊条件e与$\phi(n)$不互素具体场景中e54722$\phi(n)$也是偶数。这种设计打破了常规RSA的使用前提需要特殊处理才能解密。2. 题目关键点分析题目给出了三个关键参数n p*q # 2048位的大整数 gift lcm(p-1, q-1) # p-1和q-1的最小公倍数 e 54722 # 偶数 c pow(m, e, n) # 密文这里有几个关键信息gift的数学意义根据数论知识lcm(a,b)*gcd(a,b) a*b因此 $$\phi(n)(p-1)(q-1) \text{gcd}(p-1,q-1) \times \text{lcm}(p-1,q-1)$$e的特性54722分解质因数为2*27361这意味着e与$\phi(n)$至少共享公因子2。攻击路径需要通过gift重构$\phi(n)$然后处理e不互素的情况。3. 攻击步骤详解3.1 重构欧拉函数φ(n)首先利用gift和n的位数关系推算gcd(p-1,q-1)gift_bits 2045 # gift的二进制位数 n_bits 2048 # n的二进制位数因为$\phi(n)(p-1)(q-1)$的位数通常是2048位与n相同而gift是2045位所以 $$\text{gcd}(p-1,q-1) \approx 2^{3} 8$$实际测试发现gcd在[4,8]之间可以通过爆破尝试from gmpy2 import gcd, invert for g in [4, 6, 8]: # 可能的gcd值 phi gift * g try: d invert(e//2, phi) # 注意这里先用e//2 # 后续处理... except: continue3.2 处理e与φ(n)不互素由于e和$\phi(n)$有公因子2直接求逆元会失败。解决方案是降阶处理令$e e/2 27361$此时e与$\phi(n)$互素。修改加密公式 $$c \equiv m^e \equiv (m^2)^{e} \pmod{n}$$解密得到$m^2$用标准RSA解密得到$m^2 \mod n$开平方恢复m在整数域求平方根Python实现关键代码e_prime e // 2 # 27361 d invert(e_prime, phi) m_square pow(c, d, n) m gmpy2.iroot(m_square, 2)[0] # 整数开平方3.3 完整攻击脚本结合上述步骤的完整解决方案import gmpy2 from Crypto.Util.number import long_to_bytes n 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121 gift 2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104 c 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319 e 54722 # 爆破gcd(p-1,q-1) for g in range(4, 9, 2): # 尝试4,6,8 phi gift * g try: d gmpy2.invert(e//2, phi) m_square pow(c, int(d), n) m, is_valid gmpy2.iroot(m_square, 2) if is_valid: print(long_to_bytes(m)) break except: continue4. 数学原理深度解析4.1 为什么需要e与φ(n)互素RSA的解密依赖于 $$ m \equiv c^d \equiv m^{e \cdot d} \pmod{n} $$只有当$e \cdot d \equiv 1 \pmod{\phi(n)}$时才能保证$m^{e \cdot d} \equiv m \pmod{n}$。如果e与$\phi(n)$不互素d不存在模逆元信息空间会出现坍缩导致多个明文对应同一个密文4.2 公因子情况下的可解条件当$gcd(e,\phi(n))g$时可以通过以下步骤恢复明文计算$e e/g$找到$d$使得$e \cdot d \equiv 1 \pmod{\phi(n)}$计算$m \equiv c^{d} \equiv m^g \pmod{n}$在模n下求g次根得到m关键限制g不能太大通常为2、3等小整数否则求高次根的计算复杂度会急剧上升。5. 工程实践中的防御方案在实际密码学工程中为避免此类问题e的选择原则使用标准素数如65537验证$gcd(e,\phi(n))1$参数检查def validate_rsa_params(p, q, e): phi (p-1)*(q-1) assert gcd(e, phi) 1, e must be coprime with phi(n)安全实现建议在密钥生成阶段拒绝不安全的参数组合使用标准的PKCS#1 v2.2规范考虑使用OpenSSL等成熟库而非自行实现6. 扩展攻击场景类似的技术还可应用于以下场景多素数RSA当$npqr$时$\phi(n)(p-1)(q-1)(r-1)$e的选择需要与所有因子互素Paillier加密系统当使用合数作为生成元时可能出现类似问题SM2数字签名部分参数选择不当会导致签名失败我在实际审计中曾遇到一个案例某区块链项目自定义了e65536导致约1/4的钱包无法正常签名。通过类似的降阶处理e65536/164096临时修复了该问题。7. CTF中的变种题型除了NPUCTF2020的EzRSA类似的题型还包括e与φ(n)有较大公因子需要更高次的开方运算已知gcd(p-1,q-1)的特殊值如光滑数情况多组密文共享n通过中国剩余定理攻击这类题目通常的突破点是利用题目给出的特殊关系如本题的gift尝试小范围内的暴力枚举结合数学变换降低问题复杂度
从NPUCTF2020 EzRSA看RSA中e与φ(n)不互素时的攻击与修复
发布时间：2026/7/15 2:50:53
1. RSA基础回顾与问题背景RSA加密算法的安全性基于大整数分解的困难性。在标准RSA中公钥指数e和私钥指数d需要满足$e \cdot d \equiv 1 \pmod{\phi(n)}$其中$\phi(n)(p-1)(q-1)$。这意味着e必须与$\phi(n)$互素否则d不存在模逆元。但在NPUCTF2020的EzRSA题目中出题人故意设置了一个特殊条件e与$\phi(n)$不互素具体场景中e54722$\phi(n)$也是偶数。这种设计打破了常规RSA的使用前提需要特殊处理才能解密。2. 题目关键点分析题目给出了三个关键参数n p*q # 2048位的大整数 gift lcm(p-1, q-1) # p-1和q-1的最小公倍数 e 54722 # 偶数 c pow(m, e, n) # 密文这里有几个关键信息gift的数学意义根据数论知识lcm(a,b)*gcd(a,b) a*b因此 $$\phi(n)(p-1)(q-1) \text{gcd}(p-1,q-1) \times \text{lcm}(p-1,q-1)$$e的特性54722分解质因数为2*27361这意味着e与$\phi(n)$至少共享公因子2。攻击路径需要通过gift重构$\phi(n)$然后处理e不互素的情况。3. 攻击步骤详解3.1 重构欧拉函数φ(n)首先利用gift和n的位数关系推算gcd(p-1,q-1)gift_bits 2045 # gift的二进制位数 n_bits 2048 # n的二进制位数因为$\phi(n)(p-1)(q-1)$的位数通常是2048位与n相同而gift是2045位所以 $$\text{gcd}(p-1,q-1) \approx 2^{3} 8$$实际测试发现gcd在[4,8]之间可以通过爆破尝试from gmpy2 import gcd, invert for g in [4, 6, 8]: # 可能的gcd值 phi gift * g try: d invert(e//2, phi) # 注意这里先用e//2 # 后续处理... except: continue3.2 处理e与φ(n)不互素由于e和$\phi(n)$有公因子2直接求逆元会失败。解决方案是降阶处理令$e e/2 27361$此时e与$\phi(n)$互素。修改加密公式 $$c \equiv m^e \equiv (m^2)^{e} \pmod{n}$$解密得到$m^2$用标准RSA解密得到$m^2 \mod n$开平方恢复m在整数域求平方根Python实现关键代码e_prime e // 2 # 27361 d invert(e_prime, phi) m_square pow(c, d, n) m gmpy2.iroot(m_square, 2)[0] # 整数开平方3.3 完整攻击脚本结合上述步骤的完整解决方案import gmpy2 from Crypto.Util.number import long_to_bytes n 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121 gift 2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104 c 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319 e 54722 # 爆破gcd(p-1,q-1) for g in range(4, 9, 2): # 尝试4,6,8 phi gift * g try: d gmpy2.invert(e//2, phi) m_square pow(c, int(d), n) m, is_valid gmpy2.iroot(m_square, 2) if is_valid: print(long_to_bytes(m)) break except: continue4. 数学原理深度解析4.1 为什么需要e与φ(n)互素RSA的解密依赖于 $$ m \equiv c^d \equiv m^{e \cdot d} \pmod{n} $$只有当$e \cdot d \equiv 1 \pmod{\phi(n)}$时才能保证$m^{e \cdot d} \equiv m \pmod{n}$。如果e与$\phi(n)$不互素d不存在模逆元信息空间会出现坍缩导致多个明文对应同一个密文4.2 公因子情况下的可解条件当$gcd(e,\phi(n))g$时可以通过以下步骤恢复明文计算$e e/g$找到$d$使得$e \cdot d \equiv 1 \pmod{\phi(n)}$计算$m \equiv c^{d} \equiv m^g \pmod{n}$在模n下求g次根得到m关键限制g不能太大通常为2、3等小整数否则求高次根的计算复杂度会急剧上升。5. 工程实践中的防御方案在实际密码学工程中为避免此类问题e的选择原则使用标准素数如65537验证$gcd(e,\phi(n))1$参数检查def validate_rsa_params(p, q, e): phi (p-1)*(q-1) assert gcd(e, phi) 1, e must be coprime with phi(n)安全实现建议在密钥生成阶段拒绝不安全的参数组合使用标准的PKCS#1 v2.2规范考虑使用OpenSSL等成熟库而非自行实现6. 扩展攻击场景类似的技术还可应用于以下场景多素数RSA当$npqr$时$\phi(n)(p-1)(q-1)(r-1)$e的选择需要与所有因子互素Paillier加密系统当使用合数作为生成元时可能出现类似问题SM2数字签名部分参数选择不当会导致签名失败我在实际审计中曾遇到一个案例某区块链项目自定义了e65536导致约1/4的钱包无法正常签名。通过类似的降阶处理e65536/164096临时修复了该问题。7. CTF中的变种题型除了NPUCTF2020的EzRSA类似的题型还包括e与φ(n)有较大公因子需要更高次的开方运算已知gcd(p-1,q-1)的特殊值如光滑数情况多组密文共享n通过中国剩余定理攻击这类题目通常的突破点是利用题目给出的特殊关系如本题的gift尝试小范围内的暴力枚举结合数学变换降低问题复杂度
：时距曲线实战解析与复杂介质模拟)
