# Solution to UTCTF 2019 - Jacobi's Chance Encryption

##### Name:

Jacobi’s Chance Encryption

crypto

750

#### Writeup We got this challenge text and an implementation of a strange crypto system that we needed to break:

Public Key 569581432115411077780908947843367646738369018797567841

Can you decrypt Jacobi’s encryption?

``````def encrypt(m, pub_key):
bin_m = ''.join(format(ord(x), '08b') for x in m)
n, y = pub_key

def encrypt_bit(bit):
x = randint(0, n)
if bit == '1':
return (y * pow(x, 2, n)) % n
return pow(x, 2, n)

return map(encrypt_bit, bin_m)
``````

And also the encrypted flag.

Looking at the implementation it does some really strange things. It loops over every bit in the plaintext and gets a large random number `x`. Then it checks if the bit is 1 or 0 and encodes that information as either y * x2 or x2 in the congruence class of y.

There is also a public key involved that’s just two primes multiplied together, but it’s more of a red herring.

This is actually a kind of neat algebra problem. We want to know if a number was a square of itself before it got reduced by modulo `n` or not, and we know that `n` and the number are coprime.

As with all math problems, someone has solved this in sage already. The name of the function is `kronecker`, so all we had to do was to write a small sage program to reverse the crypto function.

``````file = open("flag.enc", "r")

data = data.split(",")

pubkey = list(factor(569581432115411077780908947843367646738369018797567841))

i = 0
str = ""
sol = ""
for b in data:
if b == "":
continue

if kronecker(int(b, 16), pubkey) == 0:
str += "1"
else:
str += "0"

i += 1

if i % 8 == 0:
sol += chr(int(str, 2))
str = ""

print(sol)
``````

The flag was `utflag{did_u_pay_attention_in_number_theory}`.