04-the-onetime-pad.py

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

from tqdm import tqdm

class LCG:
    def __init__(self, x, m):
        self._x = x
        self._a = 2
        self._m = m
    
    def next(self):
        self._x = (self._x*self._a) % self._m
        return self._x

def main():
    m = 16411099384203967235
    length = 311
    c = 258578933248047129070234127076818734931906736562394908260192233729045538766864090271939203007290696772322321

    t = 0
    for b in range(50):
        t = 2*t + ((c>>(311+b))&1)
    
    lb = ((t+0)*m + 2**50 - 1) // 2**50
    ub = ((t+1)*m + 2**50 - 1) // 2**50

    for xf in tqdm(range(lb, ub)):
        x0 = xf * pow(2, -311, m) % m
        lcg = LCG(x0, m)

        rand = 0
        for i in range(361):
            rand += (lcg.next() & 1) << i
        flag = int.to_bytes(c ^ rand, (361+7)//8, 'big')
        if b"kurenaifCTF" not in flag: continue
        print(xf, flag)
    # kurenaifCTF{lowest_bit_oracle_is_funny}

if __name__ == '__main__':
    main()