WeChall - Save the World

Posted on In Views: Disqus:

Save the World (Crypto) by Z Hastad broadcast attack — 同一消息 m，e=3，三个不同 n

Challenge

题面给出一段虚构的世界观故事：三个 RSA 公钥（e=3，三个不同 n1,n2,n3）加密了同一个对称密钥 m。目标是恢复 m 的十进制形式的最后 20 位。

1
2
3
c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

Solution

这是经典的 Hastad broadcast attack。当同一消息用同一个小指数 e=3、不同互素 modulus 加密且无 padding 时：

m^3 对三个不同的 n 同余于不同的 c。用中国剩余定理（CRT）合并，如果 m^3 < n1*n2*n3，则 CRT 结果直接等于 m^3，开三次方根即可。

1
2
3
4
5
6
7
from sympy.ntheory.modular import crt
from sympy import integer_nthroot

C, mod = crt([n1, n2, n3], [c1, c2, c3])
m, exact = integer_nthroot(int(C), 3)
assert exact
print(str(m)[-20:])

完整的从页面抓数→计算的脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import re, urllib.request

URL = 'http://www.wechall.net/en/challenge/Z/save_the_world/index.php'
COOKIE = 'WC=...'

req = urllib.request.Request(URL, headers={'Cookie': COOKIE})
html = urllib.request.urlopen(req, timeout=20).read().decode()
clean = re.sub(r'<br\s*/?>', '', html)  # 关键：去掉 <br/> 标签

def extract(pattern):
    m = re.search(pattern, clean)
    return int(m.group(1).replace('\n', '').replace(' ', ''))

n1 = extract(r'n1=(\d[\d\s\n]*?)')
c1 = extract(r'c1=(\d[\d\s\n]*?)')
n2 = extract(r'n2=(\d[\d\s\n]*?)')
c2 = extract(r'c2=(\d[\d\s\n]*?)')
n3 = extract(r'n3=(\d[\d\s\n]*?)')
c3 = extract(r'c3=(\d[\d\s\n]*?)')

from sympy.ntheory.modular import crt
from sympy import integer_nthroot

C, mod = crt([n1, n2, n3], [c1, c2, c3])
m, exact = integer_nthroot(int(C), 3)
assert exact
print(str(m)[-20:])
  • <br/> 标签：页面里的超大整数被 <br/> 换行打断，直接复制会漏数字或引入多余字符。必须用 regex 去掉 <br/> 后再提取连续数字串。
  • 静态题：n1/n2/n3/c1/c2/c3 是固定的，对所有用户相同。答案唯一，只需计算一次。
  • sympy 需要安装：uv pip install sympy 或 pip install sympy。
21987654321987654321