[zer0pts CTF 2020] ROR

tags: zer0pts CTF crypto

Overview

We're given the encoder script and the output.

import random
from secret import flag

ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))

N = 1
for base in [2, 3, 7]:
    N *= pow(base, random.randint(123, 456))
e = random.randint(271828, 314159)

m = int.from_bytes(flag, byteorder='big')
assert m.bit_length() < N.bit_length()

for i in range(m.bit_length()):
    print(pow(ror(m, i, m.bit_length()), e, N))

Solution

(x^e mod N) % (2^whatever) will be 0 when the least significant bit of ROR(m,i) is 0, otherwise 1.

flag = 0

with open("../distfiles/chall.txt", "r") as f:
    for i, line in enumerate(f):
        x = int(line)
        if x % 2**100 != 0:
            flag |= 1 << i

print(bytes.fromhex(hex(flag)[2:]))