Contents

PBCTF2021

A CTF event with highly speaking by perfect-blue team.

Alkaloid Stream

  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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83  #!/usr/bin/env python3 import random from flag import flag def keygen(ln): # Generate a linearly independent key arr = [ 1 << i for i in range(ln) ] for i in range(ln): for j in range(i): if random.getrandbits(1): arr[j] ^= arr[i] for i in range(ln): for j in range(i): if random.getrandbits(1): arr[ln - 1 - j] ^= arr[ln - 1 - i] return arr def gen_keystream(key): ln = len(key) # Generate some fake values based on the given key... fake = [0] * ln for i in range(ln): for j in range(ln // 3): if i + j + 1 >= ln: break fake[i] ^= key[i + j + 1] # Generate the keystream res = [] for i in range(ln): t = random.getrandbits(1) if t: res.append((t, [fake[i], key[i]])) else: res.append((t, [key[i], fake[i]])) # Shuffle! random.shuffle(res) keystream = [v[0] for v in res] public = [v[1] for v in res] return keystream, public def xor(a, b): return [x ^ y for x, y in zip(a, b)] def recover_keystream(key, public): st = set(key) keystream = [] for v0, v1 in public: if v0 in st: keystream.append(0) elif v1 in st: keystream.append(1) else: assert False, "Failed to recover the keystream" return keystream def bytes_to_bits(inp): res = [] for v in inp: res.extend(list(map(int, format(v, '08b')))) return res def bits_to_bytes(inp): res = [] for i in range(0, len(inp), 8): res.append(int(''.join(map(str, inp[i:i+8])), 2)) return bytes(res) flag = bytes_to_bits(flag) key = keygen(len(flag)) keystream, public = gen_keystream(key) assert keystream == recover_keystream(key, public) enc = bits_to_bytes(xor(flag, keystream)) print(enc.hex()) print(public) 

simple algebraic problem

fake has always a 0 element,we can recover the key and flag-stream step by step.

solve by my teammates

  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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55  from Crypto.Util.number import * from data import * keys = [] tmp = pub.copy() for key in tmp: if key[0] == 0: keys.append(key[1]) tmp.remove(key) print('last key:' + str(key[1])) elif key[1] == 0: keys.append(key[0]) tmp.remove(key) print('last key:' + str(key[0])) fake = keys[0] for _ in range(len(pub) - 1): for key in tmp: if key[0] == fake: keys.insert(0, key[1]) tmp.remove(key) fake = 0 elif key[1] == fake: keys.insert(0, key[0]) tmp.remove(key) fake = 0 if len(keys) <= len(pub) // 3: for i in keys: fake ^= i else: for i in keys[:len(pub)//3]: fake ^= i print(len(keys)) print(keys) def recover_keystream(key, public): st = set(key) keystream = '' for v0, v1 in public: if v0 in st: keystream += '0' elif v1 in st: keystream += '1' else: assert False, "Failed to recover the keystream" return keystream stream = recover_keystream(keys, pub) print(strxor(long_to_bytes(int(stream, 2)), long_to_bytes(cipher))) # pbctf{super_duper_easy_brute_forcing_actually_this_one_was_made_by_mistake} 

Yet Another RSA

A varant RSA cryptosystem based on a cubic Pell

solve

The left of the paper shows me the POC in theory,and@mystizshows the analysis result of data-range

$0​≡k\phi +1≡k(p ^2 +p+1)(q ^2 +q+1)+1$

$≡k[n ^2 +n+1+(n+1)(p+q)+(p ^2 +q ^2)]+1(mod e)$

There are three unknown elements: $k \approx d \approx 2^{400}$, $p+q \approx 2^{512}$ and $p^2 + q^2 \approx 2^{1024}$ ​

And $e\approx 2^{2048}$,$2048>1024+512+400$

we can use coppersmith to attack it

  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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141  #! /usr/bin/sage from time import time from sage.all import * from sage.groups.generic import bsgs from Crypto.Util.number import * import itertools from tqdm import tqdm from rich.progress import track from rich.traceback import install install() from time import * p1 = time() # ----------------------------------- def add(P, Q, mod): m, n = P p, q = Q if p is None: return P if m is None: return Q if n is None and q is None: x = m * p % mod y = (m + p) % mod return (x, y) if n is None and q is not None: m, n, p, q = p, q, m, n if q is None: if (n + p) % mod != 0: x = (m * p + 2) * inverse(n + p, mod) % mod y = (m + n * p) * inverse(n + p, mod) % mod return (x, y) elif (m - n ** 2) % mod != 0: x = (m * p + 2) * inverse(m - n ** 2, mod) % mod return (x, None) else: return (None, None) else: if (m + p + n * q) % mod != 0: x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod return (x, y) elif (n * p + m * q + 2) % mod != 0: x = (m * p + (n + q) * 2) * inverse(n * p + m * q + 2, mod) % mod return (x, None) else: return (None, None) def power_mul(P, a, mod): res = (None, None) t = P while a > 0: if a % 2: res = add(res, t, mod) t = add(t, t, mod) a >>= 1 return res def small_roots(f, bounds, m=1, d=None): if not d: d = f.degree() R = f.base_ring() N = R.cardinality() f /= f.coefficients().pop(0) f = f.change_ring(ZZ) G = Sequence([], f.parent()) for i in range(m+1): base = N^(m-i) * f^i for shifts in itertools.product(range(d), repeat=f.nvariables()): g = base * prod(map(power, f.variables(), shifts)) G.append(g) B, monomials = G.coefficient_matrix() monomials = vector(monomials) factors = [monomial(*bounds) for monomial in monomials] for i, factor in enumerate(factors): B.rescale_col(i, factor) B = B.dense_matrix().LLL() B = B.change_ring(QQ) for i, factor in enumerate(factors): B.rescale_col(i, 1/factor) H = Sequence([], f.parent().change_ring(QQ)) for h in filter(None, B*monomials): H.append(h) I = H.ideal() if I.dimension() == -1: H.pop() elif I.dimension() == 0: roots = [] for root in I.variety(ring=ZZ): root = tuple(R(root[var]) for var in f.variables()) roots.append(root) return roots return [] N= int(144256630216944187431924086433849812983170198570608223980477643981288411926131676443308287340096924135462056948517281752227869929565308903867074862500573343002983355175153511114217974621808611898769986483079574834711126000758573854535492719555861644441486111787481991437034260519794550956436261351981910433997) e= int(3707368479220744733571726540750753259445405727899482801808488969163282955043784626015661045208791445735104324971078077159704483273669299425140997283764223932182226369662807288034870448194924788578324330400316512624353654098480234449948104235411615925382583281250119023549314211844514770152528313431629816760072652712779256593182979385499602121142246388146708842518881888087812525877628088241817693653010042696818501996803568328076434256134092327939489753162277188254738521227525878768762350427661065365503303990620895441197813594863830379759714354078526269966835756517333300191015795169546996325254857519128137848289) R = Integers(e) PR. = PolynomialRing(R) f = k * (N**2 + N*p_q + p_q**2 - N + p_q + 1) + 1 bounds = (2**513, 2**400) print("strating LLL") p_q, k = small_roots(f, bounds, m=3, d=4)[0] p_q = 24061328198598730023892644418337616625129173971437927448877972244319015467758683782803490794256724311673381106878622466514439272631375460573992290498030162 k = 245962077700976781389651438762467784060458007726399012831680541230865888041508191613184353923990248850900264645309752826 print(p_q,k) E = 123436198430194873732325455542939262925442894550254585187959633871500308906724541691939878155254576256828668497797665133666948295292931357138084736429120687210965244607624309318401630252879390876690703745923686523066858970889657405936739693579856446294147129278925763917931193355009144768735837045099705643710, 47541273409968525787215157367345217799670962322365266620205138560673682435124261201490399745911107194221278578548027762350505803895402642361588218984675152068555850664489960683700557733290322575811666851008831807845676036420822212108895321189197516787046785751929952668898176501871898974249100844515501819117 PR. = PolynomialRing(ZZ) f = x**2 - int(p_q) * x + N (p, _), (q, _) = f.roots() phi = (p ** 2 + p + 1) * (q ** 2 + q + 1) d = int(pow(e, -1, phi)) tmp = power_mul(E, d, N) flag1 = long_to_bytes(tmp[0])[:35].decode() flag2 = long_to_bytes(tmp[1])[:36].decode() print(flag1+flag2 ) # [(245962077700976781389651438762467784060458007726399012831680541230865888041508191613184353923990248850900264645309752826, 24061328198598730023892644418337616625129173971437927448877972244319015467758683782803490794256724311673381106878622466514439272631375460573992290498030162)] # pbctf{I_love_to_read_crypto_papers_and_implement_the_attacks_from_them} p2 = time() print(p2-p1)