Name:

Jacobi’s Chance Encryption

Category:

crypto

Points:

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 * x² or x² 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 = file.readline()

data = data.split(",")

pubkey = list(factor(569581432115411077780908947843367646738369018797567841))

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

    if kronecker(int(b, 16), pubkey[1][0]) == 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}.