Skip to content

Instantly share code, notes, and snippets.

@samueltangz
Created February 13, 2021 13:37
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save samueltangz/84af56469f6c174a017f9c4da0ee12f7 to your computer and use it in GitHub Desktop.
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment