from random import randrange from secrets import flag, key from Crypto.Util.number import long_to_bytes def bsum(state, taps, l): ret = 0 for i in taps: ret ^= (state >> (l - i)) return ret & 1 class Gen: def __init__(self, key, slength): self.state = key self.slength = slength self.TAPS = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32, 33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64] def clock(self): out = bsum(self.state, self.TAPS, self.slength) self.state = (out << (self.slength - 1)) + (self.state >> 1) return out def insertflag(fn, flag): txt = b'' with open(fn, 'rb') as f: txt = f.read() i = randrange(0, len(txt)) txt = txt[:i] + flag + txt[i:] with open(fn, 'wb') as f: f.write(txt) def gf256_multiply(a,b): p = 0 for _ in range(8): if b % 2: p ^= a check = a & 0x80 a <<= 1 if check == 0x80: a ^= 0x1b b >>= 1 return p % 256 def encrypt(fn, outf, cipher): pt = b'' with open(fn, 'rb') as f: pt = f.read() ct = b'' for byte in pt: genbyte = 0 for i in range(8): genbyte = genbyte << 1 genbyte += cipher.clock() ct += long_to_bytes(gf256_multiply(genbyte, byte)) with open(outf, 'wb') as f: f.write(ct) insertflag('pt', flag) cipher = Gen(key, 64) encrypt('pt', 'ct', cipher)
pt は与えられておらず、謎の pub.sage というファイルが与えられている
R.<x> = PolynomialRing(GF(2), 'x') poly = [REDACTED] assert poly.degree() == 64 M = [poly.list()[1:]] for i in range(63): M.append([1 if j == i else 0 for j in range(64)]) M = Matrix(GF(2), M) A = M^[REDACTED] E, S = A.eigenspaces_right(format='galois')[0] assert E == 1 keyvec = S.random_element() key = int(''.join([str(d) for d in keyvec]), 2) print(key)
これは解かなくてもいいんじゃないかなぁ、という気がする。
公式 https://cor.team/posts/corCTF-2021---Crypto-Challenge-Writeups
https://blog.y011d4.com/20210823-corctf-writeup/#mystery_stream
S3v3ru5は力技で解いていた
mport ast from random import randrange from Crypto.Util.number import long_to_bytes import string def bsum(state, taps, l): ret = 0 for i in taps: ret ^= (state >> (l - i)) return ret & 1 class Gen: def __init__(self, key, slength): self.state = key self.slength = slength self.TAPS = [2, 4, 5, 7, 10, 12, 13, 17, 19, 24, 25, 27, 30, 32, 33, 34, 35, 45, 47, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 64] def clock(self): out = bsum(self.state, self.TAPS, self.slength) self.state = (out << (self.slength - 1)) + (self.state >> 1) return out def gf256_divison(numerator, denominator): return division_table[(numerator, denominator)] def get_state(pt_8, ct_8): gen_bytes = [] for i, j in zip(pt_8, ct_8): gen_bytes.append(gf256_divison(j, i)) state = [] for b in gen_bytes: state.extend(list(map(int, bin(b)[2:].zfill(8)))) return int("".join(map(str, state[::-1])), 2) def decrypt(ct, cipher): pt = [] for byte in ct: genbyte = 0 for i in range(8): genbyte = genbyte << 1 genbyte += cipher.clock() pt.append(gf256_divison(byte, genbyte)) return bytes(pt) division_table = ast.literal_eval(open("divison_table").read()) ct = open("ct", "rb").read() flag_format = b"corctf{" charset = b"abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_" for first_char in charset: flag_prefix = flag_format + bytes([first_char]) print("Trying flag prefix =", flag_prefix.decode()) for ind in range(len(ct) - 10): nct = ct[ind:] try: state = get_state(flag_prefix, nct[:8]) cipher = Gen(state, 64) npt = decrypt(nct[8:50], cipher) j = 0 for i in npt: if i < 32 or i >= 128: break j += 1 else: print("Found a valid candidate at", ind) print("pt =", npt) if j >= 10: print(ind, flag_prefix + npt) except KeyError: continue
FF = GF(2) _.<x> = FF['x'] modulus = x^128 + x^7 + x^2 + x + 1 F.<z> = GF(2^modulus.degree(), modulus=modulus) R = FF[','.join(f'x{i}' for i in range(modulus.degree()))] vars = R.gens() a = z^127 + z^124 + z^120 + z^118 + z^117 + z^115 + z^112 + z^111 + z^110 + z^109 + z^105 + z^104 + z^103 + z^102 + z^98 + z^96 + z^95 + z^89 + z^88 + z^87 + z^85 + z^83 + z^82 + z^81 + z^78 + z^77 + z^75 + z^73 + z^71 + z^70 + z^67 + z^63 + z^62 + z^61 + z^60 + z^58 + z^57 + z^55 + z^54 + z^53 + z^51 + z^49 + z^42 + z^40 + z^38 + z^36 + z^35 + z^34 + z^33 + z^28 + z^26 + z^25 + z^24 + z^23 + z^20 + z^18 + z^16 + z^14 + z^13 + z^10 + z^8 + z^4 + 1 b = vector(FF, (z^127 + z^125 + z^124 + z^123 + z^122 + z^119 + z^115 + z^114 + z^112 + z^110 + z^109 + z^107 + z^105 + z^104 + z^101 + z^98 + z^97 + z^95 + z^92 + z^88 + z^87 + z^86 + z^84 + z^82 + z^78 + z^76 + z^75 + z^74 + z^73 + z^70 + z^69 + z^67 + z^59 + z^58 + z^56 + z^55 + z^53 + z^52 + z^50 + z^45 + z^43 + z^42 + z^40 + z^38 + z^37 + z^34 + z^32 + z^31 + z^26 + z^24 + z^22 + z^21 + z^20 + z^19 + z^18 + z^17 + z^13 + z^9 + z^7 + z^5 + z^4 + z^3 + z^2 + z + 1).polynomial().list()) def embed(x): return sum(z^i * v for i, v in enumerate(x)) embedded = embed(vars) M = [[0 for _ in range(modulus.degree() + 1)] for _ in range(modulus.degree() + 1)] for j, v in enumerate(vars): poly = F((a * embedded).coefficient({v: 1})).polynomial() for i in range(modulus.degree()): M[i][j] = poly.monomial_coefficient((z^i).polynomial()) M[-1][-1] = 1 mult_a = Matrix(FF, M)
