Pinhole

An easy crypto. My friend poiko asked me to have a look after his solve failed. He spoiled me1 by outlining how he tried to solve it though… I ended up doing it the exact same way2, so it was a super quick solve, like half an hour-ish. The trickiest part was loading back Sage’s print()-ed output back into Sage.

Upon opening the file you’re presented with the following:

def random_poly(degree):
  R.<x> = ZZ[]
  while True:
    f = x**degree
    for i in range(1, degree):
      f += randint(-3, 3) * x ** (degree - i)
    if f.degree() == degree:
      return f

def genkey(a,d,r,s):
  M, N = [SL2Z.random_element() for _ in '01']
  A = N * matrix(ZZ, [[0, -1], [1, 1]]) * N**(-1)
  B = N * matrix(ZZ, [[0, -1], [1, 0]]) * N**(-1)
  # r, s = [randint(5, 14) for _ in '01']
  U, V = (B * A) ** r, (B * A**2) ** s
  F = []
  for j in range(2):
    Ux = [random_poly(d[j]) for _ in range(4)]
    Ux = [Ux[i] - Ux[i](a) + U[i // 2][i % 2] for i in range(4)]
    Ux = matrix([[Ux[0], Ux[1]], [Ux[2], Ux[3]]])
    F.append(Ux)
  X, Y = M * F[0] * M ** (-1), M * F[1] * M ** (-1)
  pubkey, privkey = (X, Y), (M, a)
  return pubkey, privkey

genkey() is a royal mess. It almost looks like the author started with some interesting idea, two non-similar matrices in , doing some random base changes…but then he got drunk or had a panic attack or something, because the Ux stuff that is happening in the loop just looks like garbled nonsense brayed by an idiot’s ass. He also forgot that V ever existed.

So how was it easy? Well, it’s because of this:

def encrypt(msg, pubkey):
  X, Y = pubkey
  C = Y
  for b in msg:
    C *= X ** (int(b) + 1) * Y
  return C

Meaning you can just ignore the drunk pseudo-math above and test which of and is integral for each bit…

Total code for my solve:

import re

# The hardest part.
monomial = re.compile(r'( - |-|)(\d+)(?:\*(x)(?:\^(\d+))?)?')

def extract_poly(R,s):
  x = R.gen()
  cur = R(0)
  u = R(1)
  for (pre,c,isx,e) in monomial.findall(s):
    if e == '':
      e = '1' if isx else '0'
    cur += R(c) * (u << int(e)) * (-1 if '-' in pre else 1)
    if e == '0':
      yield cur
      cur = R(0)

out = open('Pinhole/output.txt').read()
Px = PolynomialRing(ZZ,'x')
V = list(extract_poly(Px,out))

X = Matrix([V[:2],V[2:4]])
Y = Matrix([V[4:6],V[6:8]])
V = Matrix([V[8:10],V[10:12]])

def xy_bits(V,X,Y):
  while V != Y:
    V *= Y^-1
    assert V.denominator() == 1
    if (V * X^-2).denominator() == 1:
      yield 1
      V *= X^-2
    else:
      yield 0
      V *= X^-1
      assert V.denominator() == 1

print(bytes.fromhex(sum(2**i*x for i,x in enumerate(xy_bits(V,X,Y))).hex()))
  1. I asked him not to, but what can you do, sheesh. I can get quite jealous about wanting to do problems on my own, because it’s the primary motivation and joy I derive from CTFs.

  2. Turns out he just had a bug in his approach. Serves him right for being a spoilsport.