#sage from Crypto.Util.number import * from typing import Tuple, Iterator, Iterable, Optional # Step 1: Perform Wiener's Attack in order to recover p and q # Modified a little from: https://github.com/orisano/owiener/blob/master/owiener.py def isqrt(n: int) -> int: if n == 0: return 0 x = 2 ** ((int(n).bit_length() + 1) // 2) while True: y = (x + n // x) // 2 if y >= x: return x x = y def is_perfect_square(n: int) -> bool: sq_mod256 = (1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0) if sq_mod256[n & 0xff] == 0: return False mt = ( (9, (1,1,0,0,1,0,0,1,0)), (5, (1,1,0,0,1)), (7, (1,1,1,0,1,0,0)), (13, (1,1,0,1,1,0,0,0,0,1,1,0,1)), (17, (1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1)) ) a = n % (9 * 5 * 7 * 13 * 17) if any(t[a % m] == 0 for m, t in mt): return False return isqrt(n) ** 2 == n def rational_to_contfrac(x: int, y: int) -> Iterator[int]: while y: a = x // y yield a x, y = y, x - a * y def contfrac_to_rational_iter(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]: n0, d0 = 0, 1 n1, d1 = 1, 0 for q in contfrac: n = q * n1 + n0 d = q * d1 + d0 yield n, d n0, d0 = n1, d1 n1, d1 = n, d def convergents_from_contfrac(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]: n_, d_ = 1, 0 for i, (n, d) in enumerate(contfrac_to_rational_iter(contfrac)): if i % 2 == 0: yield n + n_, d + d_ else: yield n, d n_, d_ = n, d def attack1(e: int, n: int) -> Optional[int]: f_ = rational_to_contfrac(e, n) for k, dg in convergents_from_contfrac(f_): edg = e * dg phi = edg // k x = n - phi + 1 if x % 2 == 0 and is_perfect_square((x // 2) ** 2 - n): p = (x + isqrt(x ** 2 - 4 * n)) // 2 assert n % p == 0 return p, n // p return None print("Step 1") with open("output.txt", "r") as f: exec(f.read()) p = 0 i = 0 for E in e: i += 1 print('r=/='%(i,len(e)),end='') res = attack1(E, N) if res: p, q = res print() break assert p # Step 2: Apply Chinese Remainder Theorem print("Step 2") hg = vector(crt([x, y], [p, q]) for x, y in zip(h, g)) # Step 3: Perform an attack against AHSSP # Refer to: https://blog.maple3142.net/2023/04/30/d3ctf-2023-writeups/#d3pack print("Step 3") h, g, e = map(vector, [h, g, e]) def find_ortho_fp(*vecs, M = p): assert len(set(len(v) for v in vecs)) == 1 L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))], [ZZ(M), 0]]) print("LLL", L.dimensions()) nv = len(vecs) L[:, :nv] *= M L = L.LLL() ret = [] for row in L: if row[:nv] == 0: ret.append(row[nv:]) return matrix(ret) def find_ortho_zz(*vecs, M = p): assert len(set(len(v) for v in vecs)) == 1 L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))]]) print("LLL", L.dimensions()) nv = len(vecs) L[:, :nv] *= M L = L.LLL() ret = [] for row in L: if row[:nv] == 0: ret.append(row[nv:]) return matrix(ret) def attack2(v, e, p0): F = Zmod(p0) v = v.change_ring(F) e = e.change_ring(F) Mhe = find_ortho_fp(v, e, M = p0) assert Mhe * v % p0 == 0 assert Mhe * e % p0 == 0 Lx = find_ortho_zz(*Mhe[: m - n], M = p0).T Me = find_ortho_fp(e, M = p0) assert Me * e % p0 == 0 alpha = (Me * matrix(F, Lx)).solve_right(Me * v) xa = Lx * alpha s = (xa - v)[0] / e[0] return s s = attack2(hg, e, N) unpad = lambda s: s[:s.index(b'x00')] if b'x00' in s else s print(unpad(long_to_bytes(int(s))))