Challenge:

from Crypto.Util.number import GCD

import os
import hashlib

BITS = 1024

def getrandbits(bits):
    l = (bits + 7) // 8
    v = int.from_bytes(os.urandom(l), 'little')

    to_shift = 8 * l - bits
    return v >> to_shift

class LCG:
    def __init__(self, mod):
        self.mod = mod
        self.vs = [getrandbits(BITS // 3) for _ in range(6)]
        self.bs = [getrandbits(BITS) for _ in range(6)]
        self.c = getrandbits(BITS)
    
    def get(self):
        new_v = (sum(v * b for v, b in zip(self.vs, self.bs)) + self.c) % self.mod
        self.vs = self.vs[1:] + [new_v]
        return new_v


p = 0xd6911ad7da2912f38bd2d04c150be9b7fee1f5770e6a8ea7ffc0a559069b24ebfcd3d535b3ce2696f0b6ad7270bc76e023212bdaf6fa16da726098606dfc8d90246f4a94516a8fbd6290a96323b515995ecb66765fe1f66c39c928bf03ac1cbcbc8294aeed908e97d9d24f16f4ec88a98a4fd4ffa1c98d307521ba08a5b2a52b
assert p.bit_length() == BITS

a = int.from_bytes(os.urandom(BITS // 8), 'little')
lcg = LCG(p - 1)

vs = lcg.vs[:]

for i in range(20):
    print(pow(a, lcg.get(), p))

to_hash = "".join(str(v) for v in vs)
f = hashlib.sha256(to_hash.encode()).hexdigest()
flag = f"DH}"

with open('flag', 'w') as f:
    f.write(flag)

# If you have multiple flag candidates...
hashed_flag = hashlib.sha256(flag.encode()).hexdigest()
print(hashed_flag)

5155731157292315912978978254324178376035986916549172932406909008207087271765769935905509777453518498267910492995302909010821757648233494899349714271058199332799186103092905378878807058600286090301283789592928502257025713591956329151742357617348739124688450090553926560632449371356107640399801390574804997012
98045678034464298753183285126236123356170196628839448003495467096354836799805478162768298407699423373992597049338608624935835362696780663891234383546352945065202326807500409155758904899963951516049816447378133845786023886034472185344479957494794670141563083581857739059304619387342683778590733691134697726045
146020076937197153355699408953562825288582818943343192326283415030858896497507025194825546904626692562124316971583517349340948352164103045327527593357372334758767441058121974405538425265096637127779397046561309829147962803543040036770922818371127429436718203482354912969627686640719291436382244738039805903552
129573965043870633067612563609639916200306954430681415279868108672584163812885268465785098637864070377098259118223065697798607122101805549308495425144114088049152964271437249481620882590059241665900369774878910073351450098826735325189172665603869194662577045309821997676992018518513173540003559522087069114032
55064255393048944648500215909804343085661579673098305084076237580032978440436034334484836381962126648387881666117752809275280540772971867143407129253143207460570774795277443943661997034958577424454899667087944045500138752234618368990571862039157416988656198316621852209713720445937221847036611962430545676606
23959302556328511400788200493288581905797342544384302531055037492759392938105274134124772530168902908028305196697465581826559830423538726768321688434487471776966238772630419500064546443580347105287554646534166391344094463298543494551946904494111904646486925284624870504896899861366402727672910796566589176340
107583713209744087654441044820066168539572581202815101069636020652219440631066663353725524647541344500531615737812327363366200139389891145308454163053371231740005004634252665194243447957288352198626504868529645902378821740482615351356594710069715377511592961867497878832168811593025149522607963745829602387196
37129799513950498838067483474861261553212397368796740061675164304059104708024265285330079409652928324396072751312922418198147549163115340282657467871054461375036910240563242568783122322230201154634165219354528555617066383104852737514079722111852070697675071104151630865220047152232949064913639272000662517240
47626032908467019531077841086099089293447801445959888272588026627461883962857987023126164057947618346461755133086564800755320616560923161873492334490436397151600254290551147309770273671860557925683437779917918159112688730076046076377462225411995187755828762773805070915514548526853773629479729269816149281520
59332025176662350040928695859912531971872588311282924427927514561104635326082696653309257285515741502952734133731632793314214289055135462585169596130890643051003628248395343886920177802936076872344589150487379692781473934779724448356709363894013329465076029626947882529021901236714131565557301633447135387424
61498580460643173455301736513818085147411890992911333169361422555372405217173937118184027398252308832558142907266210028530806917827388389734429286610290662783429802416384314436884885291984389549936840355761181360252834697168855805389468991087079252371590394698580388059769212566783037731004228647832806945183
103752028923448930158751778378675984946759086211264811814063307970365818476103743800769498227803549792684672566327165136198941559357769659962385888853549494607045428072378163090103515330586493205668898162147177529638945131170707739513480390105127880525777935454249969907206737754526439327330928171270288604980
147045439145575849710016672820762942977642581718701376005534157819703157033471901358013771539342410439496347724557944233126419845822645005317431901192661446180582623925084879427478128385408139180916372460910746711904991095314093049177148413263801326774416281146283205487374695243367356206284192157117142750356
50317234744514115230538100683745424669624971660918141069655412258911052442248745594667529744943115431478893317981205630985959069324043522558019522796567848731617521156402333101365867110344164467507209521294175078625633787850962538381026285659203227405722911198270184595615830752437229639179368029499373394809
123583574485009557769832604317250034794087688220016963784524391339518305546123997075520342948695132330833344856538687126931771034148203595496378858083485788309064426920922370732274815779556057784283124084638042002163095570678845631456865490848208833731606640085697879109576791088100805998914432157404262758422
137013550532566348059416536584214499684910558252222219572478189936522654478923490787713695208431520910169758863997658176746417665084747230982440096677937684491489610885873542860076157315048886653488775478509696171662331080957723268374523729718619190704170918231089601496158611113313467199040717973472465657258
98616353061028547728338344360788324040824727422053855565104245874267308624270851659980289092600853506740828305429165251521184081903585796204620343464041117777060844261757021939966333807159496789275411308024521143642402645579816481018894723208832388714499339706333422937221307397072243262894802878886797416132
57377098562837461042072003881398068471979158618046594946939285006404001098112711368062431662775961739521002045801329174134139027237998624428017045328582949259180420941751715887072538307857422623848096378705643451437029198987227073562838905288593679592382419224720735467728236118132057012731169540167476659329
59808259043323374947686486802193741373224282295486060716272194863335203044880984801269183201871710381527770915382378645900020663697210241729696592049485347266498487264335059332736450347888873516072750690141099753845429486732122488000350744796869552405660096235150255068149145565942752645253341535299696819475
24069591697721704330170100103523146903131628178239878093251810702786179285899288594455453105212828005605278773355853358648333997822228128660858365783207204832082711681564054168755419525932369725161712223287987459532355022780431770888332585062078534028754156134639536522803925597679238497165637860260293479408
84ddfb01c817c0b0d47950be86d56f95a68154737379340d2478091c9969f276


Solve:

for i in range(20):
    print(pow(a, lcg.get(), p))

First we see this discrete log problem to deal with, p-1 is smooth except for 1 large factor I’ll call q:

437783772190199073880149177995377542774868874003257679907195250599458950046958305407675539673116198429241134455385589287589308835951942117013730609199201

So let’s define m = (p-1)/q and work mod m.

from sympy.ntheory.residue_ntheory import discrete_log

BITS = 1024
p = 0xd6911ad7da2912f38bd2d04c150be9b7fee1f5770e6a8ea7ffc0a559069b24ebfcd3d535b3ce2696f0b6ad7270bc76e023212bdaf6fa16da726098606dfc8d90246f4a94516a8fbd6290a96323b515995ecb66765fe1f66c39c928bf03ac1cbcbc8294aeed908e97d9d24f16f4ec88a98a4fd4ffa1c98d307521ba08a5b2a52b
q = 437783772190199073880149177995377542774868874003257679907195250599458950046958305407675539673116198429241134455385589287589308835951942117013730609199201
m = (p-1)//q

class LCG:
    def __init__(self, mod):
        self.mod = mod
        self.vs = [randint(0, 2**(BITS//3)) for _ in range(6)]
        self.bs = [randint(0, 2**BITS) for _ in range(6)]
        self.c = randint(0, 2**BITS)
    
    def get(self):
        new_v = (sum(v * b for v, b in zip(self.vs, self.bs)) + self.c) % self.mod
        self.vs = self.vs[1:] + [new_v]
        return new_v


a = randint(0, 2**(BITS//8))
lcg = LCG(p - 1)

states = []
output = []
for i in range(20):
    state = lcg.get()
    states.append(state)
    output.append(pow(a, state, p))


xx = []
g = 2 #random base
for o in output:
    _g = pow(g, q, p)
    _o = pow(o, q, p)
    xx.append(int(discrete_log(p, _o, _g, order=m)))


Now all xx is some multiple of states mod p, you can see it if the inverse exists:

print(xx[0] * pow(states[0], -1, m) % m)
print(xx[1] * pow(states[1], -1, m) % m)
print(xx[2] * pow(states[2], -1, m) % m)


Now we subtract groups of 2 equations to eliminate c, we get:

bs = lcg.bs
assert (xx[7]-xx[6]) % m == (bs[0]*(xx[1]-xx[0]) + bs[1]*(xx[2]-xx[1]) + bs[2]*(xx[3]-xx[2]) + bs[3]*(xx[4]-xx[3]) + bs[4]*(xx[5]-xx[4]) + bs[5]*(xx[6]-xx[5])) % m
assert (xx[8]-xx[7]) % m == (bs[0]*(xx[2]-xx[1]) + bs[1]*(xx[3]-xx[2]) + bs[2]*(xx[4]-xx[3]) + bs[3]*(xx[5]-xx[4]) + bs[4]*(xx[6]-xx[5]) + bs[5]*(xx[7]-xx[6])) % m
assert (xx[9]-xx[8]) % m == (bs[0]*(xx[3]-xx[2]) + bs[1]*(xx[4]-xx[3]) + bs[2]*(xx[5]-xx[4]) + bs[3]*(xx[6]-xx[5]) + bs[4]*(xx[7]-xx[6]) + bs[5]*(xx[8]-xx[7])) % m
...


Or,

assert k*(av[7]-av[6]) % m == (k*bs[0]*(av[1]-av[0]) + k*bs[1]*(av[2]-av[1]) + k*bs[2]*(av[3]-av[2]) + k*bs[3]*(av[4]-av[3]) + k*bs[4]*(av[5]-av[4]) + k*bs[5]*(av[6]-av[5])) % m
assert k*(av[8]-av[7]) % m == (k*bs[0]*(av[2]-av[1]) + k*bs[1]*(av[3]-av[2]) + k*bs[2]*(av[4]-av[3]) + k*bs[3]*(av[5]-av[4]) + k*bs[4]*(av[6]-av[5]) + k*bs[5]*(av[7]-av[6])) % m
assert k*(av[9]-av[8]) % m == (k*bs[0]*(av[3]-av[2]) + k*bs[1]*(av[4]-av[3]) + k*bs[2]*(av[5]-av[4]) + k*bs[3]*(av[6]-av[5]) + k*bs[4]*(av[7]-av[6]) + k*bs[5]*(av[8]-av[7])) % m
...


And now we want to rearrange for v[i]:

assert k*bs[0]*av[0] % m == (-k*av[7] + k*av[6] + k*bs[0]*av[1] + k*bs[1]*av[2] - k*bs[1]*av[1] + k*bs[2]*av[3] - k*bs[2]*av[2] + k*bs[3]*av[4] - k*bs[3]*av[3] + k*bs[4]*av[5] - k*bs[4]*av[4] + k*bs[5]*av[6] - k*bs[5]*av[5]) % m
assert k*bs[0]*av[0] % m == (k*av[7]*(-1) + k*av[6]*(bs[5]+1) + k*av[5]*(bs[4]-bs[5]) + k*av[4]*(bs[3]-bs[4]) + k*av[3]*(bs[2]-bs[3]) + k*av[2]*(bs[1]-bs[2]) + k*av[1]*(bs[0]-bs[1])) % m

ib = pow(bs[0], -1, m)
s7 = (ib * (-1)) % m
s6 = (ib * (bs[5]+1)) % m
s5 = (ib * (bs[4]-bs[5])) % m
s4 = (ib * (bs[3]-bs[4])) % m
s3 = (ib * (bs[2]-bs[3])) % m
s2 = (ib * (bs[1]-bs[2])) % m
s1 = (ib * (bs[0]-bs[1])) % m
for i in range(7):
    assert k*av[i] % m == (s7*k*av[i+7] + s6*k*av[i+6] + s5*k*av[i+5] + s4*k*av[i+4] + s3*k*av[i+3] + s2*k*av[i+2] + s1*k*av[i+1]) % m


Now s is solved directly, and the original vs are solved with LLL:

from sympy.ntheory.residue_ntheory import discrete_log
from tqdm import *

BITS = 1024
p = 0xd6911ad7da2912f38bd2d04c150be9b7fee1f5770e6a8ea7ffc0a559069b24ebfcd3d535b3ce2696f0b6ad7270bc76e023212bdaf6fa16da726098606dfc8d90246f4a94516a8fbd6290a96323b515995ecb66765fe1f66c39c928bf03ac1cbcbc8294aeed908e97d9d24f16f4ec88a98a4fd4ffa1c98d307521ba08a5b2a52b
q = 437783772190199073880149177995377542774868874003257679907195250599458950046958305407675539673116198429241134455385589287589308835951942117013730609199201
m = (p-1)//q

class LCG:
    def __init__(self, mod):
        self.mod = mod
        self.vs = [randint(0, 2**(BITS//3)) for _ in range(6)]
        self.original_vs = self.vs.copy()
        self.all_vs = self.vs.copy()
        self.bs = [randint(0, 2**BITS) for _ in range(6)]
        self.c = randint(0, 2**BITS)
    
    def get(self):
        new_v = (sum(v * b for v, b in zip(self.vs, self.bs)) + self.c) % self.mod
        self.all_vs.append(new_v)
        self.vs = self.vs[1:] + [new_v]
        return new_v


a = randint(0, 2**(BITS//8))
lcg = LCG(p - 1)

states = []
output = []
for i in range(20):
    state = lcg.get()
    states.append(state)
    output.append(pow(a, state, p))

xx = []
g = 2 #random base
for o in tqdm(output):
    _g = pow(g, q, p)
    _o = pow(o, q, p)
    xx.append(int(discrete_log(p, _o, _g, order=m)))

bs = lcg.bs

assert (xx[7]-xx[6]) % m == (bs[0]*(xx[1]-xx[0]) + bs[1]*(xx[2]-xx[1]) + bs[2]*(xx[3]-xx[2]) + bs[3]*(xx[4]-xx[3]) + bs[4]*(xx[5]-xx[4]) + bs[5]*(xx[6]-xx[5])) % m
assert (xx[8]-xx[7]) % m == (bs[0]*(xx[2]-xx[1]) + bs[1]*(xx[3]-xx[2]) + bs[2]*(xx[4]-xx[3]) + bs[3]*(xx[5]-xx[4]) + bs[4]*(xx[6]-xx[5]) + bs[5]*(xx[7]-xx[6])) % m
assert (xx[9]-xx[8]) % m == (bs[0]*(xx[3]-xx[2]) + bs[1]*(xx[4]-xx[3]) + bs[2]*(xx[5]-xx[4]) + bs[3]*(xx[6]-xx[5]) + bs[4]*(xx[7]-xx[6]) + bs[5]*(xx[8]-xx[7])) % m
...

av = lcg.all_vs
assert states[0] == av[6]
assert states[1] == av[7]
assert states[2] == av[8]
...

assert av[6] == (bs[5]*av[5] + bs[4]*av[4] + bs[3]*av[3] + bs[2]*av[2] + bs[1]*av[1] + bs[0]*av[0] + lcg.c) % lcg.mod
assert av[7] == (bs[5]*av[6] + bs[4]*av[5] + bs[3]*av[4] + bs[2]*av[3] + bs[1]*av[2] + bs[0]*av[1] + lcg.c) % lcg.mod
assert av[8] == (bs[5]*av[7] + bs[4]*av[6] + bs[3]*av[5] + bs[2]*av[4] + bs[1]*av[3] + bs[0]*av[2] + lcg.c) % lcg.mod
...

for i in range(20):
    try:
        k = xx[i] * pow(states[i], -1, m) % m
        break
    except:
        continue


assert k*av[6] % m == (bs[5]*k*av[5] + bs[4]*k*av[4] + bs[3]*k*av[3] + bs[2]*k*av[2] + bs[1]*k*av[1] + bs[0]*k*av[0] + k*lcg.c) % m
assert k*av[7] % m == (bs[5]*k*av[6] + bs[4]*k*av[5] + bs[3]*k*av[4] + bs[2]*k*av[3] + bs[1]*k*av[2] + bs[0]*k*av[1] + k*lcg.c) % m
assert k*av[8] % m == (bs[5]*k*av[7] + bs[4]*k*av[6] + bs[3]*k*av[5] + bs[2]*k*av[4] + bs[1]*k*av[3] + bs[0]*k*av[2] + k*lcg.c) % m
...

assert k*(av[7]-av[6]) % m == (k*bs[0]*(av[1]-av[0]) + k*bs[1]*(av[2]-av[1]) + k*bs[2]*(av[3]-av[2]) + k*bs[3]*(av[4]-av[3]) + k*bs[4]*(av[5]-av[4]) + k*bs[5]*(av[6]-av[5])) % m
assert k*(av[8]-av[7]) % m == (k*bs[0]*(av[2]-av[1]) + k*bs[1]*(av[3]-av[2]) + k*bs[2]*(av[4]-av[3]) + k*bs[3]*(av[5]-av[4]) + k*bs[4]*(av[6]-av[5]) + k*bs[5]*(av[7]-av[6])) % m
assert k*(av[9]-av[8]) % m == (k*bs[0]*(av[3]-av[2]) + k*bs[1]*(av[4]-av[3]) + k*bs[2]*(av[5]-av[4]) + k*bs[3]*(av[6]-av[5]) + k*bs[4]*(av[7]-av[6]) + k*bs[5]*(av[8]-av[7])) % m
...


assert k*bs[0]*av[0] % m == (-k*(av[7]-av[6]) + k*bs[0]*av[1] + k*bs[1]*(av[2]-av[1]) + k*bs[2]*(av[3]-av[2]) + k*bs[3]*(av[4]-av[3]) + k*bs[4]*(av[5]-av[4]) + k*bs[5]*(av[6]-av[5])) % m
assert k*bs[0]*av[1] % m == (-k*(av[8]-av[7]) + k*bs[0]*av[2] + k*bs[1]*(av[3]-av[2]) + k*bs[2]*(av[4]-av[3]) + k*bs[3]*(av[5]-av[4]) + k*bs[4]*(av[6]-av[5]) + k*bs[5]*(av[7]-av[6])) % m
assert k*bs[0]*av[2] % m == (-k*(av[9]-av[8]) + k*bs[0]*av[3] + k*bs[1]*(av[4]-av[3]) + k*bs[2]*(av[5]-av[4]) + k*bs[3]*(av[6]-av[5]) + k*bs[4]*(av[7]-av[6]) + k*bs[5]*(av[8]-av[7])) % m
...

assert k*bs[0]*av[0] % m == (-k*av[7] + k*av[6] + k*bs[0]*av[1] + k*bs[1]*av[2] - k*bs[1]*av[1] + k*bs[2]*av[3] - k*bs[2]*av[2] + k*bs[3]*av[4] - k*bs[3]*av[3] + k*bs[4]*av[5] - k*bs[4]*av[4] + k*bs[5]*av[6] - k*bs[5]*av[5]) % m
assert k*bs[0]*av[0] % m == (k*av[7]*(-1) + k*av[6]*(bs[5]+1) + k*av[5]*(bs[4]-bs[5]) + k*av[4]*(bs[3]-bs[4]) + k*av[3]*(bs[2]-bs[3]) + k*av[2]*(bs[1]-bs[2]) + k*av[1]*(bs[0]-bs[1])) % m

"""
ib = pow(bs[0], -1, m)
s7 = (ib * (-1)) % m
s6 = (ib * (bs[5]+1)) % m
s5 = (ib * (bs[4]-bs[5])) % m
s4 = (ib * (bs[3]-bs[4])) % m
s3 = (ib * (bs[2]-bs[3])) % m
s2 = (ib * (bs[1]-bs[2])) % m
s1 = (ib * (bs[0]-bs[1])) % m
for i in range(7):
    assert k*av[i] % m == (s7*k*av[i+7] + s6*k*av[i+6] + s5*k*av[i+5] + s4*k*av[i+4] + s3*k*av[i+3] + s2*k*av[i+2] + s1*k*av[i+1]) % m
"""


s = Matrix(Zmod(m), [xx[i+1:i+8] for i in range(7)]).solve_right(vector(xx[:7]))

for _ in range(6):
    xx = [s * vector(xx[:7])] + xx.copy()
vs = Matrix(ZZ, [xx[:6]]).stack(identity_matrix(6) * m).LLL()[1]

vs = [abs(v // gcd(vs)) for v in vs]
print(vs == lcg.original_vs)