#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))))