zer0pts CTF 2021 | easy pseudorandom

#zer0ptsCTF2021

from Crypto.Util.number import*
from flag import flag

nbits = 256
p = random_prime(1 << nbits)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)

b = randrange(p)
d = 2
F = v^2 + b

v0 = randrange(p)
v1 = F(v0)

k = ceil(nbits * (d / (d + 1)))
w0 = (v0 >> (nbits - k))
w1 = (v1 >> (nbits - k))

# encrypt
m = bytes_to_long(flag)
v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)

print(f"p = {p}")
print(f"b = {b}")
print(f"m = {m}")
print(f"w0 = {w0}")
print(f"w1 = {w1}")

はえー

難しそう。

なんかガチャガチャやりつつmultivariate coppersmithをやると解ける

import itertools
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

# https://github.com/defund/coppersmith
def small_roots(f, bounds, m=1, d=None):
   if not d:
      d = f.degree()

   R = f.base_ring()
   N = R.cardinality()
   
   f /= f.coefficients().pop(0)
   f = f.change_ring(ZZ)

   G = PolynomialSequence([], f.parent())
   for i in range(m+1):
       power = N^(m-i) * f^i
       for shifts in itertools.product(range(d), repeat=f.nvariables()):
           g = power
           for variable, shift in zip(f.variables(), shifts):
               g *= variable^shift
           G.append(g)

   B, monomials = G.coefficient_matrix()
   monomials = vector(monomials)

   factors = [monomial(*bounds) for monomial in monomials]
   for i, factor in enumerate(factors):
       B.rescale_col(i, factor)

   B = B.dense_matrix().LLL()

   B = B.change_ring(QQ)
   for i, factor in enumerate(factors):
       B.rescale_col(i, 1/factor)
   B = B.change_ring(ZZ)

   H = Sequence([], f.parent().change_ring(QQ))
   for h in B*monomials:
       if h.is_zero():
           continue
       H.append(h.change_ring(QQ))
       I = H.ideal()
       if I.dimension() == -1:
           H.pop()
       elif I.dimension() == 0:
           V = I.variety(ring=ZZ)
           if V:
               roots = []
               for root in V:
                   root = map(R, map(root.__getitem__, f.variables()))
                   roots.append(tuple(root))
               return roots

   return []

# nbits = 256
# p = random_prime(1 << nbits)
# Fp = Zmod(p)
# P.<v> = PolynomialRing(Fp)
# 
# b = randrange(p)
# d = 2
# F = v^2 + b
# 
# v0 = randrange(p)
# v1 = F(v0)
# 
# k = ceil(nbits * (d / (d + 1))) # 171, nbits-k=85
# 
# t0 = int(v0) % (2**(nbits-k))
# t1 = int(v1) % (2**(nbits-k))
# 
# w0 = (v0 >> (nbits - k))
# w1 = (v1 >> (nbits - k))
# 
# w0 = w0 << (nbits - k)
# w1 = w1 << (nbits - k)
# 
# PR.<x0,x1> = PolynomialRing(GF(p))
# f = w0*w0 + 2*x0*w0 + x0*x0 - w1 + b - x1
# y0, y1 = small_roots(f, [2**85, 2**85], m=2, d=2)[0]
# 
# print(t0.nbits(), t1.nbits())
# print(int(y0).bit_length(), int(y1).bit_length())
# 
# print(t0, t1)
# print(y0, y1)

nbits = 256
d = 2
k = ceil(nbits * (d / (d + 1))) # 171, nbits-k=85

p = 43343132318542115908109143315552470697591037366597387898555021129243891268321
b = 41626875266611172180637084755555430560267242697294225673939722754126407735314
m = 26949942292579858219052254038266486253954430094782895839375885288766769341049
w0 = 736213423532176860355024979639742034476924805552604
w1 = 453768168211027546342885075363551218230698462688285

w0 = w0 << (nbits - k)
w1 = w1 << (nbits - k)

PR.<x0,x1> = PolynomialRing(GF(p))
f = w0*w0 + 2*x0*w0 + x0*x0 - w1 + b - x1
y0, y1 = small_roots(f, [2**85, 2**85], m=2, d=2)[0]

v0 = int(w0 + y0)
v1 = int(w1 + y1)

P.<v> = PolynomialRing(Zmod(p))
F = v^2 + b

v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)
print(bytes.fromhex(hex(m)[2:]))