DSActf-May Crypto Writeup

from Crypto.Util.number import inverse
import itertools
c = '177401504b0125272c122743171e2c250a602e3a7c206e014a012703273a3c0160173a73753d'

c = [int(c[i: i + 2], 16) for i in range(0, len(c), 2)]

salt = 'ahh'
m = ''
salt = itertools.cycle(salt)

for i in c:
    m += chr((inverse(57, 128) * (i - ord(next(salt)))) % 128)
print(m)
>>> flag{ad7d973ffdd285b476a1a727b3a8fbc4}

from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

class LCG:
    def __init__(self, seed):
        self.a = a
        self.b = b
        self.m = m
        self.seed = seed

    def next(self):
        self.seed = (self.a*self.seed+self.b) % self.m
        return self.seed >> 16


g = 183096451267674849541594370111199688704
A = 102248652770540219619953045171664636108622486775480799200725530949685509093530
B = 74913924633988481450801262607456437193056607965094613549273335198280176291445
M = 102752586316294557951738800745394456033378966059875498971396396583576430992701
Cipher = 13040004482819935755130996285494678592830702618071750116744173145400949521388647864913527703

a = 3844066521
b = 3316005024
m = 2249804527
state1 = 16269
state2 = 4249


def gen_AB():
    x = ''
    for _ in range(64):
        x += '1' if lcg.next() % 2 else '0'
    return pow(g, int(x, 2), M), int(x, 2)

for i in tqdm(range(2 ** 16 - 1)):
    seed = (state2 << 16) + i
    lcg = LCG(seed)
    tA, ta = gen_AB()
    if tA == A:
        break

tB, tb = gen_AB()
assert (tB == B)
key = pow(A, tb, M)
print(long_to_bytes(Cipher ^ key))
>>> b'flag{4dfe14e0c6c21ffcf5a3b4f0ed1911f6}'

from Crypto.Util.number import *
from tqdm import tqdm
with open('pub.txt', 'r') as f:
    key2 = f.readlines()
key2 = [int(key2[i][:-1]) for i in range(len(key2))]

a = 11243098275181678343
b = 335428611041311731398614259824482604248524861615176787429946575184146370361110652887115402376826444538743339055691850202034085349274540292019392290484025358504275054761608502214481606484088807087063751542648223811793597463026662881020647708165593980984857948283181770647446888695205803952635117800114545071259

key1 = []
for i in key2:
    key1.append((i * inverse(a, b)) % b)

cipher = 0x8ab3086a3df540d4652c191951756a6574aca491d933e479330532f0586ce03862f82f36dea8038b8bfb0b394331d7a93050efa2a26e46d9d8ca394600456cd79e02890a2c31b02e920c28a9f27c3943ec68fe5555ff4056358f35869859d67d67702edf44b10a7690acbaeea1f4def46392922069bfb71c173a210e9ab384f7
m = ''
for i in key1:
    if cipher > i:
        m += '1'
        cipher -= i
    else:
        m += '0'
list(m).reverse()
m = ''.join(m)
print(long_to_bytes(int(m, 2)))