UTCTF|Jacobi’s Chance Encryption - crypto-writeup-public

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)

一緒に flag.enc が渡される。一部抜粋してみるとこんな感じ

3ad3750f859c2c8fc1eb2076f876322cd17421c1cff88,0,0,0,3a46387fd709d3b4692cab59248ad3f426e9b8cd5bffe,0,2a6670878e3f48cfd5abcb7940b6df1d22650a438e905,0,5b9c517cca0d3ab82864545d1c943d8ab198650830b38,0,0,0,...

暗号化の仕組みを見てみる。

public key が整数値で渡されてるのに n, y = pub_key っていうのはおかしくないか？
平文を1bitずつ暗号化しているらしい
0なら $x ^ 2 \mod n$
1なら $y x^2 \mod n$

この暗号化の仕組みを使ってて0がこんなに多いということはまずないと思う。それこそ $y = 0$ とかでないとだめ。

とりあえずそれでやってみる

は？　解けた。いやこれは本番で解けておくべき…… utflag{did_u_pay_attention_in_number_theory}

xs = open("flag.enc").read().strip().split(",")

flag = ""
bits = ""
for x in xs:
    if x == "0":
        bits += "1"
    else:
        bits += "0"

    if len(bits) == 8:
        flag += chr(int(bits, 2))
        bits = ""

print(flag)