CRT

强网先锋 baby_crt 考点是 CRT-RSA，找到一篇paper：Wagner’s Attack on a Secure CRT-RSA Algorithm Reconsidered 然后看到里面提到可以这样获取 $p$： $$ \large gcd(m^{c_1}-Sig^e,N)=p $$ 这个题目只有 $c_1$ 没有给出，但是很小，可以直接爆破。 from Crypto.Util.number import * from hashlib import sha1 e = 65537 n = 26318358382258215770827770763384603359524444566146134039272065206657135513496897321983920652242182112479484135343436206815722605756557098241887233837248519031879444740922789351356138322947108346833956405647578838873425658405513192437479359531790697924285889505666769580176431360506227506064132034621123828090480606055877425480739950809109048177976884825589023444901953529913585288143291544181183810227553891973915960951526154469344587083295640034876874318610991153058462811369615555470571469517472865469502025030548451296909857667669963720366290084062470583318590585472209798523021029182199921435625983186101089395997 m = 26275493320706026144196966398886196833815170413807705805287763413013100962831703774640332765503838087434904835657988276064660304427802961609185997964665440867416900711128517859267504657627160598700248689738045243142111489179673375819308779535247214660694211698799461044354352200950309392321861021920968200334344131893259850468214901266208090469265809729514249143938043521579678234754670097056281556861805568096657415974805578299196440362791907408888958917063668867208257370099324084840742435785960681801625180611324948953657666742195051492610613830629731633827861546693629268844700581558851830936504144170791124745540 sig = 20152941369122888414130075002845764046912727471716839854671280255845798928738103824595339885345405419943354215456598381228519131902698373225795339649300359363119754605698321052334731477127433796964107633109608706030111197156701607379086766944096066649323367976786383015106681896479446835419143225832320978530554399851074180762308322092339721839566642144908864530466017614731679525392259796511789624080228587080621454084957169193343724515867468178242402356741884890739873250658960438450287159439457730127074563991513030091456771906853781028159857466498315359846665211412644316716082898396009119848634426989676119219246 for c1 in range(1, 65536): p = GCD(pow(m, c1, n) - pow(sig, e, n), n) if p == 1: continue print(p) break q = n // p flag = "flag{" + sha1(long_to_bytes(p if p < q else q)).hexdigest() + "}" print(flag) # flag{601cb6f6d990ed5b89cf0de60508a95c07543793} bank proof_of_work: ...

piece_of_cake 两个函数大概都是一个类似 RSA 的操作，加上一个加密算法，之前的一篇博客有介绍， An Introduction to Mathematical Cryptography 书里称这个算法是 “a toy model of a real public key cryptosystem”。（bitlength 凑的刚刚好可以保证解密，很巧妙） make_cake()这边的cake很小（256bits）符合正常解密的条件，可以直接用高斯格基规约算法，然而eat_cake()这边的cake是比较大的（768bits）就会导致在取模的时候值容易发生改变，所以给它加上几个g，并使用给出的pow来验证是否是正确的cake。 规约得到的密钥对 $(F, G)$ 是不一定等于原来的密钥对 $(f, g)$，但它们在解密过程是等价的，我们得到的密钥对 长度都是 768bits。 exp 多跑几次就能得到 flag。 from gmpy2 import iroot, sqrt, invert from pwn import remote from string import ascii_letters, digits from hashlib import sha256 r = remote('170.106.35.18', 8631) def proof_of_work(txt, Hash): for a in ascii_letters+digits: for b in ascii_letters+digits: for c in ascii_letters+digits: if sha256((a+b+c+txt).encode()).hexdigest() == Hash: return a+b+c def gaussian(v1, v2): while True: if sqrt(v2[0]**2 + v2[1]**2) < sqrt(v1[0]**2 + v1[1]**2): v1, v2 = v2, v1 m = int((v1[0]*v2[0] + v1[1]*v2[1]) / (v1[0]**2 + v1[1]**2)) if m == 0: return (v1, v2) v2 = [v2[0] - m * v1[0], v2[1] - m * v1[1]] r.recvuntil("XXX+") nonce = r.recv(17).decode() r.recvuntil(" == ") target = r.recv(64).decode() r.recvuntil("\nGive me XXX:") w = proof_of_work(nonce, target) r.send(str(w)+"\n") r.recvuntil("What's your choice?\n") r.send("1\n") r.recvline() temp = r.recvline().strip().decode().split(" ") q, h, c = [int(i) for i in temp] N = int(r.recvline().strip().decode()) cip = int(r.recvline().strip().decode()) s1, s2 = gaussian([1, h], [0, q]) f, g = s1[0], s1[1] cake = (c * f % q) % g cake = invert(f, g) * cake % g for k in range(10000): if pow(cake, 0x10001, N) == cip: print("cake is: ", cake) break cake += g r.send(str(cake) + "\n") print(r.recvline().strip().decode()) #WMCTF{Wh4t_A_pi3ce_of_CAKE!} babySum 密度接近 0.8 的子集和问题（Subset sum problem），BKZ-24 跑得比较慢好在成功率高一点。 ...

模数两两互素时 from Crypto.Util.number import inverse from functools import reduce def crt(a, m): '''Return a solution to a Chinese Remainder Theorem problem. ''' M = reduce(lambda x, y: x * y, m) Mi = [M // i for i in m] t = [inverse(Mi[i], m[i]) for i in range(len(m))] x = sum([a[i] * t[i] * Mi[i] for i in range(len(m))]) return x % M 不满足模数两两互素时 这种情况有最小解 $x$ 满足条件，很多博客也讲的很详细，但是没找到 Python 写的… ...