1. #sage
2.  
3. from Crypto.Util.number import *
4. from typing import Tuple, Iterator, Iterable, Optional
5.  
6. # Step 1: Perform Wiener's Attack in order to recover p and q
7. # Modified a little from: https://github.com/orisano/owiener/blob/master/owiener.py
8.  
9. def isqrt(n: int) -> int:
10.     if n == 0:
11.         return 0
12.     x = 2 ** ((int(n).bit_length() + 1) // 2)
13.     while True:
14.         y = (x + n // x) // 2
15.         if y >= x:
16.             return x
17.         x = y
18.  
19. def is_perfect_square(n: int) -> bool:
20.     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)
21.     if sq_mod256[n & 0xff] == 0:
22.         return False
23.  
24.     mt = (
25.         (9, (1,1,0,0,1,0,0,1,0)),
26.         (5, (1,1,0,0,1)),
27.         (7, (1,1,1,0,1,0,0)),
28.         (13, (1,1,0,1,1,0,0,0,0,1,1,0,1)),
29.         (17, (1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1))
30.     )
31.     a = n % (9 * 5 * 7 * 13 * 17)
32.     if any(t[a % m] == 0 for m, t in mt):
33.         return False
34.  
35.     return isqrt(n) ** 2 == n
36.  
37. def rational_to_contfrac(x: int, y: int) -> Iterator[int]:
38.     while y:
39.         a = x // y
40.         yield a
41.         x, y = y, x - a * y
42.  
43. def contfrac_to_rational_iter(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]:
44.     n0, d0 = 0, 1
45.     n1, d1 = 1, 0
46.     for q in contfrac:
47.         n = q * n1 + n0
48.         d = q * d1 + d0
49.         yield n, d
50.         n0, d0 = n1, d1
51.         n1, d1 = n, d
52.  
53. def convergents_from_contfrac(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]:
54.     n_, d_ = 1, 0
55.     for i, (n, d) in enumerate(contfrac_to_rational_iter(contfrac)):
56.         if i % 2 == 0:
57.             yield n + n_, d + d_
58.         else:
59.             yield n, d
60.         n_, d_ = n, d
61.  
62. def attack1(e: int, n: int) -> Optional[int]:
63.     f_ = rational_to_contfrac(e, n)
64.     for k, dg in convergents_from_contfrac(f_):
65.         edg = e * dg
66.         phi = edg // k
67.         x = n - phi + 1
68.         if x % 2 == 0 and is_perfect_square((x // 2) ** 2 - n):
69.             p = (x + isqrt(x ** 2 - 4 * n)) // 2
70.             assert n % p == 0
71.             return p, n // p
72.     return None
73.  
74.  
75. print("Step 1")
76. with open("output.txt", "r") as f: exec(f.read())
77.  
78. p = 0
79. i = 0
80. for E in e:
81.     i += 1
82.     print('r=/='%(i,len(e)),end='')
83.     res = attack1(E, N)
84.     if res:
85.         p, q = res
86.         print()
87.         break
88. assert p
89.  
90. # Step 2: Apply Chinese Remainder Theorem
91.  
92. print("Step 2")
93.  
94. hg = vector(crt([x, y], [p, q]) for x, y in zip(h, g))
95.  
96.  
97.  
98. # Step 3: Perform an attack against AHSSP
99. # Refer to: https://blog.maple3142.net/2023/04/30/d3ctf-2023-writeups/#d3pack
100.  
101. print("Step 3")
102.  
103. h, g, e = map(vector, [h, g, e])
104.  
105. def find_ortho_fp(*vecs, M = p):
106.     assert len(set(len(v) for v in vecs)) == 1
107.     L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))], [ZZ(M), 0]])
108.     print("LLL", L.dimensions())
109.     nv = len(vecs)
110.     L[:, :nv] *= M
111.     L = L.LLL()
112.     ret = []
113.     for row in L:
114.         if row[:nv] == 0:
115.             ret.append(row[nv:])
116.     return matrix(ret)
117.  
118. def find_ortho_zz(*vecs, M = p):
119.     assert len(set(len(v) for v in vecs)) == 1
120.     L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))]])
121.     print("LLL", L.dimensions())
122.     nv = len(vecs)
123.     L[:, :nv] *= M
124.     L = L.LLL()
125.     ret = []
126.     for row in L:
127.         if row[:nv] == 0:
128.             ret.append(row[nv:])
129.     return matrix(ret)
130.  
131. def attack2(v, e, p0):
132.     F = Zmod(p0)
133.     v = v.change_ring(F)
134.     e = e.change_ring(F)
135.     Mhe = find_ortho_fp(v, e, M = p0)
136.     assert Mhe * v % p0 == 0
137.     assert Mhe * e % p0 == 0
138.     Lx = find_ortho_zz(*Mhe[: m - n], M = p0).T
139.     Me = find_ortho_fp(e, M = p0)
140.     assert Me * e % p0 == 0
141.     alpha = (Me * matrix(F, Lx)).solve_right(Me * v)
142.     xa = Lx * alpha
143.     s = (xa - v)[0] / e[0]
144.     return s
145.  
146. s = attack2(hg, e, N)
147.  
148. unpad = lambda s: s[:s.index(b'x00')] if b'x00' in s else s
149.  
150. print(unpad(long_to_bytes(int(s))))