Crypto

hxb 2021 crypto signin $n1/n2$ 的连分数展开是对 $q1/q2$ 的一个逼近，所以枚举连分数中的每一项，就可以得到 $q1, q2$ 了，分解之后正常进行 RSA 解密得到 flag。 from Crypto.Util.number import GCD, inverse, long_to_bytes, isPrime pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989) c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394) n1, n2 = pk e = 0x10001 def getRoot(x, n): high = 1 while high ** n <= x: high *= 2 low = high // 2 while low < high: mid = (low + high) // 2 if low < mid and mid**n < x: low = mid elif high > mid and mid**n > x: high = mid else: return mid return mid + 1 # https://github.com/pablocelayes/rsa-wiener-attack def rational_to_contfrac(x, y): a = x // y pquotients = [a] while a * y != x: x, y = y, x - a*y a = x // y pquotients.append(a) return pquotients def convergents_from_contfrac(frac): convs = [] for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0:i])) return convs def contfrac_to_rational(frac): if len(frac) == 0: return (0, 1) num = frac[-1] denom = 1 for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num return (num, denom) frac = rational_to_contfrac(n1, n2) convergents = convergents_from_contfrac(frac) p1, p2 = None, None for (P1, P2) in convergents: gcd1, gcd2 = GCD(P1, n1), GCD(P2, n2) p1 = gcd1 if (gcd1.bit_length() <= 128 and isPrime(gcd1)) else p1 p2 = gcd2 if (gcd2.bit_length() <= 128 and isPrime(gcd2)) else p2 print(f"[+]p1: {p1}") print(f"[+]p2: {p2}") q1, q2 = getRoot(n1 // p1, 4), getRoot(n2 // p2, 4) phi1 = (p1 - 1) * (q1 - 1) * q1**3 phi2 = (p2 - 1) * (q2 - 1) * q2**3 m1 = pow(c1, inverse(e, phi1), n1) m2 = pow(c2, inverse(e, phi2), n2) flag = (long_to_bytes(m1) + long_to_bytes(m2)).decode() print(f"[~]flag: {flag}") ''' [+]p1: 181856133933383097933223133658050179553 [+]p2: 196443958511498599913330690975430421229 [~]flag: flag{8ef333ac-21a7-11ec-80f1-00155d83f114} ''' fastOT Python 的random的内部是MT19937 伪随机数生成器，虽然生成的随机数周期很大，但是内部状态（state）很少，仅仅有 624 个，每个值都是 32bit 的。 ...

easyxor shift函数是个常见的移位异或操作，convert是对一个数字使用不同的 key 和 mask 进行 4 次移位异或，这个函数在已知 key 的情况下是可逆的。 encrypt函数是对明文块进行两种模式（CBC和OFB）的块加密，块长度为 8，对于每一块的加密使用的就是上面的convert函数。 首先通过密文的长度可以得知一共被分成了 6 块；前 3 块明文使用 OFB 模式，后三块明文使用 CBC 模式；keys 是一个长度为 4 的列表，列表中每个值的范围是(-32, 32)，$64^4$ 爆破也是可以接受的。 读完题目代码之后可以想到其实我们已经知道第一块明文了，就是 flag 的格式ByteCTF{，而OFB模式实际上是加密的key，最终结果和明文块异或，所以第一个明文块异或第一个密文块就可以知道第一个 key 加密的结果，也就是cur_c = convert(last, k)的cur_c，这样就可以得到第二块的 last。 现在对于第二块，已知 IV（last），未知 keys，已知明文是可显示字符，所以可以爆破 keys 了，把能解出可显示字符明文的 keys 都保留出来，发现有 4836 个 keys 是满足的，那么我们还要借助第三块再筛一次，最终只得到一组 keys。 from itertools import product from tqdm import tqdm from Crypto.Util.number import bytes_to_long, long_to_bytes def check(s): return min([((i < 129) and (i > 31)) for i in s]) c = "89b8aca257ee2748f030e7f6599cbe0cbb5db25db6d3990d3b752eda9689e30fa2b03ee748e0da3c989da2bba657b912" c_list = [int(c[i*16:i*16+16], 16) for i in range(len(c) // 16)] known_m = bytes_to_long(b'ByteCTF{') range64 = list(range(-32, 33)) cur_c = known_m ^ c_list[0] print(cur_c) k_cnt = 0 for a,b,c,d in tqdm(product(range64, range64, range64, range64)): last = cur_c k = [a, b, c, d] try_cur_c = convert(last, k) m1 = long_to_bytes(try_cur_c ^ c_list[1]) if check(m1): # 只筛选这第一轮的话，4836个k是满足条件的，所以得筛第二轮 last = try_cur_c try_cur_c = convert(last, k) m2 = long_to_bytes(try_cur_c ^ c_list[2]) if check(m2): k_cnt += 1 try: print(m1.decode() + m2.decode(), k) except: print("error") print(k_cnt) # keys = [-12, 26, -3, -31] # ByteCTF{5831a241s-f30980 现在已经得到了keys和前三块的明文，可以接着解后三块明文了。 ...

这题使用的加密算法是 Demytko，属于一种类似 RSA 的在椭圆曲线上的加密算法，这题的攻击思路也是可以完全类比 RSA Hastad 广播攻击。 加密后的结果是椭圆曲线上的点， Division Polynomials 使我们可以用仅含一个未知数的多项式来表示这个点的 $x$ 坐标： $$ \begin{aligned} \psi_{-1} &=-1 \\ \psi_{0} &=0 \\ \psi_{1} &=1 \\ \psi_{2} &=2 y \\ \psi_{3} &=3 x^{4}+6 a x^{2}+12 b x-a^{2} \\ \psi_{4} &=4 y\left(x^{6}+5 a x^{4}+20 b x^{3}-5 a^{2} x^{2}-4 a b x-8 b^{2}-a^{3}\right) \\ \psi_{2 i+1} &=\psi_{i}\left(\psi_{i+2} \psi_{i-1}^{2}-\psi_{i-2} \psi_{i+1}^{2}\right) / 2 y, i \geq 2 \\ \psi_{2 i} &=\psi_{i+2} \psi_{i}^{3}-\psi_{i+1}^{3} \psi_{i-1}, i \geq 3 \end{aligned} $$ ...

0xGame2020是第一届0xGame比赛，时间持续一个月，面向零基础的新生。题目和exp可以在我的GitHub上找到：https://github.com/Am473ur/My-CTF-Challenge/tree/main/0xGame2020 ，这里记录一下出题人角度的 wp。 Week 1 Calendar 题目给了一张图片和一串逗号隔开的坐标信息，没看出来的话不难想到去百度一下“日历加密”，这题只是做了简单的修改。 SAT1,THU1,MON3,MON2,WED3,SUN2,THU1,SUN4,FRI3,THU1,MON4,MON4,FRI4,THU3,SUN4,SUN2,TUE4,THU1,FRI1,MON3,MON2 懒得百度的话，也不难看出前三个字母代表周一到周日，紧跟的数字范围是 1～4，所以他们代表两个坐标，列举出来并用a～z替换1～26，即可得到 flag。 easyXor 做出这题只需要知道异或的逆运算还是异或，反过来跑一遍就拿到了flag。 exp: cipher = [72, 63, 38, 12, 8, 30, 30, 6, 82, 4, 84, 88, 92, 7, 79, 29, 8, 90, 85, 26, 25, 87, 80, 10, 20, 20, 9, 4, 80, 73, 31, 5, 82, 0, 1, 92, 0, 0, 94, 81, 4, 85, 27, 35] flag = "" cipher += [ord("^")] for i in range(len(cipher)-1): flag = chr(cipher[len(cipher) - i - 2] ^ cipher[len(cipher) - i - 1]) + flag cipher[len(cipher) - i - 2] = ord(flag[0]) print(flag) # 0xGame{ec15a9eb-08b7-4c39-904d-27eed888f73f} 发现有的学弟跑完脚本手动补0，exp正确的话，是可以得到完整flag的。 ...

强网先锋 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 跑得比较慢好在成功率高一点。 ...

Crypto RSA 同一个解密指数用了三次加密同一段明文，这本书第129页介绍了 Common Private Exponent Attack： CRYPTANALYSIS OF RSA AND ITS VARIANTS 这题的情况和里面的样例是一样的，可以直接套用这个格子然后LLL即可算出d： from binascii import hexlify, unhexlify e0 = 0x9a7dc3e0f2a3531035b18541df28b8407502c2101970862d19b107ea7dc37554e5ac620b3ce4be38e5d6fd6b1920aef9e017aa383e3c1dd8e7847dc7715832fa450d1b572cfe133c702c598ed022d40ad193608bcfeb9b9aebc910dd3257caa42e503764475b89bb99056822e21ba5723d9eee3196a6fca3debd1c7687fd310d n0 = 0xa98c363cf72b3bce39bae63a9d3d5ba0acaa7e81f9b1191ce20bb0b54a8c19216d20af640121c482e882c0772671280af9f42c764128a94104266dd65c0bcd93766e0f0ce119072302b7f3e5cc4b5cfece38e4124041a8f8dcbdb9193f35bede2c284e40f80398bf0ba0609229fa27faa2d51c552ff1ed911a6f6f220b7b6fed c0 = 0x57fcf94d27451fc35386e0f6eff53c6540ccff51862c992f4b59d0d49fa350493041c5be2f54a37f3afe81aa5e9a738461b3b709a4611a7289c83d769cb02f3c5d18e65d68f6fff1df0418c8a7351be1d7cce1a7514797c9bdc67d969224d783a5d004d67a5ef986d564ab1945e5c83a53d8d1dcb5e45323764a200e737b80c e1 = 0xbb31e6433057edfed88b6a37e4419a828d1575b2b9d04a5058cd912d5efb06b2f0c5c06c5d0dd35ebeda8afa8a9cc945c244c13fc501c76e720c2c04cab70c9f906c4a810defdd84c3a38507cdf79b4e4b0c7770cc3d2d862ea9bd5fe2469290d9d2a09c8164437e9d5b7b3a9c49d111e5caa9577f8ed1ef1916ec4cb71bbb8d n1 = 0xbcc2c4f4f51abb236b411f1f9d86d71133eb2d4ffe45a319b6ab6df1174b9ee619e696666702655b6c185735298cc008e9b7df842c480d3d42bb67228b6c7408a7afe68ab85ee1c80f43c8c52764c79ffdecc6e3a5ea76c1123affe9f02c649e5f5ca0a4082107ce4a2040e5756bf6a2b34757aefa5fb6fec6d7a9e86f0c8159 c1 = 0xacf91d2b6a300a60193485ef2e1127b5863c69da71ab9e7d71a3213e960a73e42f8e8031bf0ef20184ae0a259fd50260aacce06546af2f8bbef8a2f360c8f7511ad9c99d8715012ce0a4fa8dbba8c10d74f477156076bdfda80dc449eec3b45c7cd82802ecce7635e186d29744df04fcf812dc7e2d2f3c8cd751e4fcea43db1e e2 = 0x332f82f338c8b84524103d310d59fc541b66705948c57eaf972b26bb209a6ddde3d6930948a559ac1a3a26790cb1a133a90b999b164d4e22014b27660dad4e5639ffc19bcd2e4961c5b00b9116f49c3c02880bb3ad32972287442d6a86a9c86cd3981ee1084df4322edb9c5da39146e10de0586c8b5433a851d649a45c5a73cd n2 = 0xd0ad4d11576bb041ea2ce53f354dba362a93411a37f4a529e8b5eeae83a3437df6bd5e4e1f87a4d324a6ce2850f3568c929f5d5f73fef45bda03fa7bff00304a1eb833ce3535ee3552aa62b644f0d3c1679fe2c57b978c695f03e5b2d18d9b0821c7e0ca332f552b12e2b7109210d051bbe9d9b9e3cc3b16c81e77ebca65aca3 c2 = 0xc59078ae7cb454c970f272f595da71ae2b681156a1ce7112d9b96346f38bcdca87192ea39ac273851210e9f98f0d89f1bc657ce69ca14708cba8b319160a1f67b8cfc3643dc9b6a70769d8d64a9a3504d799f3d9afca7c7114880f4ccb5bef35738e660e4ede1c884f4a60f1f0e559fb754abd8e4b905ad3626a876bea43ec8e M = isqrt(max(n0, n1, n2)) M = 10704523536419069847275584063070587220303695362157261593514212717132031073368631333467085885236049291630529090309346493924305038011673707087598638071644281 B = matrix(ZZ, [ [M, e0, e1, e2], [0, -n0, 0, 0], [0, 0, -n1, 0], [0, 0, 0, -n2], ]) BL = B.LLL() temp = int(BL[0, 0]) if temp < 0: temp *= -1 d = int(temp // M) m = hex(pow(c2, d, n2))[2:] print(unhexlify(m)) print(d) #b'SCTF{673ff064da31c0d7aee56884b01a09}' #1235666648165896286568418878956456259719846117790808720561608081687435539909970845494445047046945948132187344353861 Lattice 这题是109维的NTRU加密，在An Introduction to Mathematical Cryptography书里有介绍使用格基规约攻击NTRU的算法，如图构建一个格子，然后进行约减，一开始用LLL，没有找到合适的约减基，然后用BKZ-24很容易找到了，可能由于格比较稀疏，尽管格子相当于是218维，测试了BKZ-32都可以在20秒之内规约完成，取约减后的最短向量，就得到了 $f’$ 和 $g’$（前 $n$ 位是 $f’$，后 $n$ 位 $g’$）。 ...

NLFSR task.py from flag import a, b, c, d, flag assert flag == "De1CTF{" + ''.join([hex(i)[2:] for i in [a, b, c, d]]) + "}" assert [len(bin(i)[2:]) for i in [a, b, c, d]] == [19, 19, 13, 6] ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31 def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2) def combine(): global a, b, c, d a = lfsr(a, ma) b = lfsr(b, mb) c = lfsr(c, mc) d = lfsr(d, md) [ao, bo, co, do] = [i & 1 for i in [a, b, c, d]] return (ao*bo) ^ (bo*co) ^ (bo*do) ^ co ^ do def genkey(nb): s = '' for i in range(nb*8): s += str(combine()) open("data", "w+").write(s) genkey(128 * 1024) LFSR部分把r左移一位，m和r二进制值共同为1位数的奇偶决定空位补1或0。 ...

“not_RSA” in DASCTF 看了大佬的博客才知道是 Paillier cryptosystem，wtcl… 不过还是记录一下自己推导的解题过程 直接使用现成的 Paillier cryptosystem 解密算法解决这题非常容易，分解 n 然后直接套 decrypt 函数就解开了… 题目： from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse from secret import flag,p,q from sympy import isprime,nextprime import random m = bytes_to_long(flag) n = p * q g = n + 1 r = random.randint(1, n) c = (pow(g, m, n * n) * pow(r, n, n * n)) % (n * n) print('c =', c) print('n =', n) 主要加密过程是： ...

Notes for $An\ Introduction\ to\ Mathematical\ Cryptography$ “A toy model of a real public key cryptosystem” 这里以 An Introduction to Mathematical Cryptography 书中的一个简单的加密模型为例，简单介绍一下通过高斯格基规约算法（Gaussian Lattice Reduction）解决二维的格上的寻找最短向量问题。 最近在书中看到这个，刚好 西电新生赛@Mini L-CTF 有两个题目刚好是用这个模型实现的，当做例题写个 writeup。 task.py from Crypto.Util.number import bytes_to_long, getPrime, inverse from gmpy2 import iroot q = getPrime(1024) f = getPrime(511) g = getPrime(511) while g < iroot(q//4, 2)[0] or g > iroot(q//2, 2)[0]: g = getPrime(511) f_inv_q = inverse(f, q) h = f_inv_q * g % q m = bytes_to_long(b'flag') # flag is base**(flag) r = getPrime(510) e = (r * h + m) % q print(f) print(g) print(q) print(e) ''' f = 4685394431238242086047454699939574117865082734421802876855769683954689809016908045500281898911462887906190042764753834184270447603004244910544167081517863 g = 5326402554595682620065287001809742915798424911036766723537742672943459577709829465021452623299712724999868094408519004699993233519540500859134358256211397 q = 172620634756442326936446284386446310176482010539257694929884002472846127607264743380697653537447369089693337723649017402105400257863085638725058903969478143249108126132543502414741890867122949021941524916405444824353100158506448429871964258931750339247018885114052623963451658829116065142400435131369957050799 e = 130055004464808383851466991915980644718382040848563991873041960765504627910537316320531719771695727709826775790697704799143461018934672453482988811575574961674813001940313918329737944758875566038617074550624823884742484696611063406222986507537981571075140436761436815079809518206635499600341038593553079293254 ''' 其中私钥为 $(f, g)$ ，公钥为 $(q, h)$，已经给出了私钥，所以解密过程非常简单。 ...