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)
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"))