Solution to UTCTF 2019 - Jacobi's Chance Encryption
Jacobi’s Chance Encryption
We got this challenge text and a 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 is a 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 have solved this in sage already. The name of 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)