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))....

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)....

模数两两互素时 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 写的… 与 $m$ 互素时一样，$m$ 不互素时显然也会有无限个解 $X = k \cdot M + x$ ，但是 $m$ 之间不互素时，在模 $M$ 的意义下也可能会有多个解。...