# Pinhole

An easy crypto. My friend `poiko`

asked me to have a look after his solve
failed. He spoiled me^{1} by outlining how he tried to solve it though… I
ended up doing it the exact same way^{2}, 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 $SL(Z,2)$, 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 $CY_{−1}X_{−2}$ and $CY_{−1}X_{−1}$ 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()))
```