easyRSA - Writeup by AI

easyRSA - Writeup by AI题目信息来源: BugKu类别: Crypto (RSA)难度: 简单/中等考点分析RSA 共模攻击Common Modulus Attack扩展欧几里得算法Python 大整数运算与字节转换PKCS#1 v1.5 填充格式处理考点权重表考点权重说明RSA 共模攻击识别30%发现同一明文用相同 N、不同 e 加密两次扩展欧几里得算法30%计算 s1, s2 使得 e1s1 e2s2 1负指数处理20%当 s1 或 s2 为负数时需计算模逆元数据提取20%从填充的随机数中提取原始 flag解题思路1. 代码分析阅读RSA.py可知N大整数(4096位)e117e265537# 读取 flag 并添加随机填充dataflagwhile(len(data)512-11):datachr(random.randint(0,255))data data_numint(data.encode(hex),16)# 使用相同的 N不同的 e 加密两次encrypt1pow(data_num,e1,N)# c1encrypt2pow(data_num,e2,N)# c22. 攻击原理这是典型的RSA 共模攻击场景同一明文mmm使用相同模数NNN、不同公钥指数e1,e2e_1, e_2e1​,e2​加密密文c1me1(modN)c_1 m^{e_1} \pmod{N}c1​me1​(modN),c2me2(modN)c_2 m^{e_2} \pmod{N}c2​me2​(modN)若gcd⁡(e1,e2)1\gcd(e_1, e_2) 1gcd(e1​,e2​)1则存在整数s1,s2s_1, s_2s1​,s2​使得e1⋅s1e2⋅s21e_1 \cdot s_1 e_2 \cdot s_2 1e1​⋅s1​e2​⋅s2​1根据扩展欧几里得算法可求得s1,s2s_1, s_2s1​,s2​则明文可通过下式恢复mc1s1⋅c2s2(modN)m c_1^{s_1} \cdot c_2^{s_2} \pmod{N}mc1s1​​⋅c2s2​​(modN)证明c1s1⋅c2s2≡(me1)s1⋅(me2)s2(modN)≡me1⋅s1e2⋅s2(modN)≡m1(modN)≡m(modN) \begin{aligned} c_1^{s_1} \cdot c_2^{s_2} \equiv (m^{e_1})^{s_1} \cdot (m^{e_2})^{s_2} \pmod{N} \\ \equiv m^{e_1 \cdot s_1 e_2 \cdot s_2} \pmod{N} \\ \equiv m^1 \pmod{N} \\ \equiv m \pmod{N} \end{aligned}c1s1​​⋅c2s2​​​≡(me1​)s1​⋅(me2​)s2​(modN)≡me1​⋅s1​e2​⋅s2​(modN)≡m1(modN)≡m(modN)​3. 实现细节使用gmpy2库进行高精度整数运算当s1s_1s1​或s2s_2s2​为负数时需要计算对应的模逆元c−s≡(c−1)∣s∣(modN)c^{-s} \equiv (c^{-1})^{|s|} \pmod{N}c−s≡(c−1)∣s∣(modN)解密后需去除 PKCS#1 v1.5 格式的随机填充详细步骤步骤 1: 读取密文文件defread_hex_file(filename):withopen(filename,rb)asf:hex_dataf.read().hex()returnmpz(hex_data,16)c1read_hex_file(flag.enc1)c2read_hex_file(flag.enc2)步骤 2: 使用扩展欧几里得算法求 s1, s2importgmpy2 e1mpz(17)e2mpz(65537)# gcdext 返回 (g, s1, s2) 使得 e1*s1 e2*s2 gs1,s2gmpy2.gcdext(e1,e2)[1:3]# 结果s1 30841, s2 -8步骤 3: 计算模逆元如果需要ifs10:c1_invgmpy2.invert(c1,N)c1_powgmpy2.powmod(c1_inv,-s1,N)else:c1_powgmpy2.powmod(c1,s1,N)ifs20:c2_invgmpy2.invert(c2,N)c2_powgmpy2.powmod(c2_inv,-s2,N)else:c2_powgmpy2.powmod(c2,s2,N)步骤 4: 恢复明文m(c1_pow*c2_pow)%N步骤 5: 转换为字节并提取 flagbyte_length(m.bit_length()7)//8plaintext_bytesm.to_bytes(byte_length,big)# 查找 flag 标记foriinrange(len(plaintext_bytes)):candidateplaintext_bytes[i:]ifbflag{incandidate:flag_indexcandidate.find(bflag{)print(candidate[flag_index:].decode(utf-8))break完整代码#!/usr/bin/env python# -*- coding: utf-8 -*-importgmpy2fromgmpy2importmpz# 模数 NNmpz(0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929)# 公钥指数e1mpz(17)e2mpz(65537)# 读取密文defread_hex_file(filename):withopen(filename,rb)asf:hex_dataf.read().hex()returnmpz(hex_data,16)c1read_hex_file(flag.enc1)c2read_hex_file(flag.enc2)# 扩展欧几里得算法s1,s2gmpy2.gcdext(e1,e2)[1:3]# 处理负指数ifs10:c1_invgmpy2.invert(c1,N)c1_powgmpy2.powmod(c1_inv,-s1,N)else:c1_powgmpy2.powmod(c1,s1,N)ifs20:c2_invgmpy2.invert(c2,N)c2_powgmpy2.powmod(c2_inv,-s2,N)else:c2_powgmpy2.powmod(c2,s2,N)# 恢复明文m(c1_pow*c2_pow)%N# 转换为字节byte_length(m.bit_length()7)//8plaintext_bytesm.to_bytes(byte_length,big)# 提取 flagforiinrange(len(plaintext_bytes)):candidateplaintext_bytes[i:]ifbflag{incandidate:flag_indexcandidate.find(bflag{)print(f[] Flag:{candidate[flag_index:].decode(utf-8)})break运行结果[*]N 的位数4096[*]c1 的位数4095[*]c2 的位数4096[*]e1:17, e2:65537[*]gcd(e1, e2)1[*]s130841, s2-8[*]验证e1*s1 e2*s21[]Flag: flag{cry_is_so_hard_but_this_is_so_easy}