Facebook
From Astrageldon, 2 Weeks ago, written in Python.
Embed
Download Paste or View Raw
Hits: 196
  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))))