angstrom CTF 2022 | log log log

#angstromctf_2022

from secrets import randbits
from flag import flag

flagbits = len(flag) * 8
flag = int(flag.hex(),16)

q = 127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043
p = q * 2^1024 + 1

assert p in Primes()

nbits = p.nbits()-1

e = randbits(nbits-flagbits)
e <<= flagbits
e |= flag

K = GF(p)
g = K.multiplicative_generator()
a = g^e

print(hex(p))
print(g)
print(hex(a))
print(flagbits)

discrete log

https://see-math.math.tamu.edu/~rojas/rex.pdf に載ってる方法でやったけど時間かかる。

もっと簡単に解けるはず

def easy_bit(p, g, h):
    if legendre_symbol(h, p) == 1:
        return 0
    else:
        return 1

def ensure_qr(p, g, h):
    if legendre_symbol(h, p) == -1:
        return h * inverse_mod(g, p) % p
    return h

p = 0xb4ec8caf1c16a20c421f4f78f3c10be621bc3f9b2401b1ecd6a6b536c9df70bdbf024d4d4b236cbfcb202b702c511aded6141d98202524709a75a13e02f17f2143cd01f2867ca1c4b9744a59d9e7acd0280deb5c256250fb849d96e1e294ad3cf787a08c782ec52594ef5fcf133cd15488521bfaedf485f37990f5bd95d5796b0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
g = 3
h = 0xaf99914e5fb222c655367eeae3965f67d8c8b3a0b3c76c56983dd40d5ec45f5bcde78f7a817dce9e49bdbb361e96177f95e5de65a4aa9fd7eafec1142ff2a58cab5a755b23da8aede2d5f77a60eff7fb26aec32a9b6adec4fe4d5e70204897947eb441cc883e4f83141a531026e8a1eb76ee4bff40a8596106306fdd8ffec9d03a9a54eb3905645b12500daeabdb4e44adcfcecc5532348c47c41e9a27b65e71f8bc7cbdabf25cd0f11836696f8137cd98088bd244c56cdc2917efbd1ac9b6664f0518c5e612d4acdb81265652296e4471d894a0bd415b5af74b9b75d358b922f6b088bc5e81d914ae27737b0ef8b6ac2c9ad8998bd02c1ed90200ad6fff4a37
l = 880

K = GF(p)
bits = ""
from tqdm import tqdm
for i in tqdm(range(l)):
    bits += str(easy_bit(p, g, h))
    h = ensure_qr(p, g, h)
    h = K(h).sqrt()

    if len(bits) % 8 == 0:
        m = int(bits[::-1], 2)
        print(m.to_bytes((m.bit_length() + 7) // 8, "big"))