Solution to UTCTF 2019 - Jacobi's Chance Encryption
Jacobi’s Chance Encryption
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
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) == 0: str += "1" else: str += "0" i += 1 if i % 8 == 0: sol += chr(int(str, 2)) str = "" print(sol)
The flag was