Rating: 5.0

# Hill (100 solves, 89 points)

## Problem:

I found these characters on top of a hill covered with algae ... bruh I can't figure it out can you help me?

wznqca{d4uqop0fk_q1nwofDbzg_eu}

by bnuno

## Solution:

From the title, it looks like we have a Hill cipher: https://en.wikipedia.org/wiki/Hill_cipher

And knowing the flag format, we can do a known plaintext attack.

With 6 known characters, we can guess that the key is a 2x2 matrix, which only requires 4 known characters. Any larger key requires more than 6 known characters.

Let the key be denoted as K.

Knowing that "utflag" maps to "wznqca", we know that:

and

Notice that from the first two equations,

Now since

we can do

to get K.

From there, we just need to get character pairs and left multiply them by K<sup>-1</sup>.

We also need to be wary of the capital D and the other symbols in the flag.

## Code:

The code below prints the flag in small letters so I manually changed the T to caps to get the flag.

inv26 is just a helper function to find the inverse modulo 26 of a number using Extended Euclidean algorithm: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm.

tempM is the known plaintext matrix and tempC is the corresponding ciphertext matrix. tempK is the key matrix.

```python3

from numpy import *

def inv26(x):

a1 = 1

b1 = 0

c1 = x%26

a2 = 0

b2 = 1

c2 = 26

while c1>0 and c2>0:

if c1>c2:

a1-=a2*(c1//c2)

b1-=b2*(c1//c2)

c1%=c2

elif c2>c1:

a2-=a1*(c2//c1)

b2-=b1*(c2//c1)

c2%=c1

if c1>0:

return a1

else:

return a2

c = list("wznqca{d4uqop0fk_q1nwofDbzg_eu}".lower())

tempM = array([[20, 5], [19, 11]])

d = int(round(linalg.det(tempM)))

tempM = multiply(linalg.inv(tempM), d*inv26(d)).astype("int")

tempM = remainder(tempM, 26)

tempC = array([[22, 13], [25, 16]])

tempK = dot(tempC, tempM)

tempK = remainder(tempK, 26)

"""

print(remainder(dot(tempK, array([[20], [19]])), 26))#22, 25

print(remainder(dot(tempK, array([[5], [11]])), 26))#13, 16

print(remainder(dot(tempK, array([[0], [6]])), 26))#2, 0

"""

d = int(round(linalg.det(tempK)))

tempK = multiply(linalg.inv(tempK), d*inv26(d)).astype("int")

tempK = remainder(tempK, 26)

i=0

while i < len(c):

if c[i]>="a" and c[i]<="z":

for j in range(i+1, len(c)):

if c[j]>="a" and c[j]<="z":

C = array([[ord(c[i])-ord("a")], [ord(c[j])-ord("a")]])

C = remainder(dot(tempK, C), 26)

c[i] = chr(C[0][0]+ord("a"))

c[j] = chr(C[1][0]+ord("a"))

i=j

break

i+=1

ans = ""

for i in c:

ans += i

print(ans)

```

## Flag

```

utflag{d4nger0us_c1pherText_qq}

```

Original writeup (https://github.com/rocketninja7/CTF-Writeups/blob/master/UTCTF/Hill.md).