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位)e1=17e2=65537# 读取 flag 并添加随机填充data=flagwhile(len(data)<512-11):data=chr(random.randint(0,255))+data data_num=int(data.encode('hex'),16)# 使用相同的 N，不同的 e 加密两次encrypt1=pow(data_num,e1,N)# c1encrypt2=pow(data_num,e2,N)# c22. 攻击原理
这是典型的RSA 共模攻击场景：
- 同一明文mmm使用相同模数NNN、不同公钥指数e1,e2e_1, e_2e1,e2加密
- 密文：c1=me1(modN)c_1 = m^{e_1} \pmod{N}c1=me1(modN),c2=me2(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⋅s1+e2⋅s2=1e_1 \cdot s_1 + e_2 \cdot s_2 = 1e1⋅s1+e2⋅s2=1
- 根据扩展欧几里得算法可求得s1,s2s_1, s_2s1,s2
- 则明文可通过下式恢复：
m=c1s1⋅c2s2(modN)m = c_1^{s_1} \cdot c_2^{s_2} \pmod{N}m=c1s1⋅c2s2(modN)
证明：
c1s1⋅c2s2≡(me1)s1⋅(me2)s2(modN)≡me1⋅s1+e2⋅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_data=f.read().hex()returnmpz(hex_data,16)c1=read_hex_file('flag.enc1')c2=read_hex_file('flag.enc2')步骤 2: 使用扩展欧几里得算法求 s1, s2
importgmpy2 e1=mpz(17)e2=mpz(65537)# gcdext 返回 (g, s1, s2) 使得 e1*s1 + e2*s2 = gs1,s2=gmpy2.gcdext(e1,e2)[1:3]# 结果：s1 = 30841, s2 = -8步骤 3: 计算模逆元（如果需要）
ifs1<0:c1_inv=gmpy2.invert(c1,N)c1_pow=gmpy2.powmod(c1_inv,-s1,N)else:c1_pow=gmpy2.powmod(c1,s1,N)ifs2<0:c2_inv=gmpy2.invert(c2,N)c2_pow=gmpy2.powmod(c2_inv,-s2,N)else:c2_pow=gmpy2.powmod(c2,s2,N)步骤 4: 恢复明文
m=(c1_pow*c2_pow)%N步骤 5: 转换为字节并提取 flag
byte_length=(m.bit_length()+7)//8plaintext_bytes=m.to_bytes(byte_length,'big')# 查找 flag 标记foriinrange(len(plaintext_bytes)):candidate=plaintext_bytes[i:]ifb'flag{'incandidate:flag_index=candidate.find(b'flag{')print(candidate[flag_index:].decode('utf-8'))break完整代码
#!/usr/bin/env python# -*- coding: utf-8 -*-importgmpy2fromgmpy2importmpz# 模数 NN=mpz(0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929)# 公钥指数e1=mpz(17)e2=mpz(65537)# 读取密文defread_hex_file(filename):withopen(filename,'rb')asf:hex_data=f.read().hex()returnmpz(hex_data,16)c1=read_hex_file('flag.enc1')c2=read_hex_file('flag.enc2')# 扩展欧几里得算法s1,s2=gmpy2.gcdext(e1,e2)[1:3]# 处理负指数ifs1<0:c1_inv=gmpy2.invert(c1,N)c1_pow=gmpy2.powmod(c1_inv,-s1,N)else:c1_pow=gmpy2.powmod(c1,s1,N)ifs2<0:c2_inv=gmpy2.invert(c2,N)c2_pow=gmpy2.powmod(c2_inv,-s2,N)else:c2_pow=gmpy2.powmod(c2,s2,N)# 恢复明文m=(c1_pow*c2_pow)%N# 转换为字节byte_length=(m.bit_length()+7)//8plaintext_bytes=m.to_bytes(byte_length,'big')# 提取 flagforiinrange(len(plaintext_bytes)):candidate=plaintext_bytes[i:]ifb'flag{'incandidate:flag_index=candidate.find(b'flag{')print(f"[+] Flag:{candidate[flag_index:].decode('utf-8')}")break运行结果
[*]N 的位数：4096[*]c1 的位数：4095[*]c2 的位数：4096[*]e1:17, e2:65537[*]gcd(e1, e2)=1[*]s1=30841, s2=-8[*]验证：e1*s1 + e2*s2=1[+]Flag: flag{cry_is_so_hard_but_this_is_so_easy}