LCG STATE 高位

from Crypto.Util.number import *
from secret import seed,flag
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()
assert flag == '0xGame{' + MD5(seed) + '}'
assert seed.bit_length() == 256

class LCG:
    def __init__(self,bits:int,seed:int):
        self.m = getPrime(bits+1)
        self.a = getPrime(bits)
        self.b = getPrime(bits)
        self.cur = ( self.a * seed + self.b ) % self.m
 
    def extract(self):
        ret=self.cur >> 115#截断低位，等价于%2**n，输出流截断（r0+k*2**115=c0)
        self.cur = ( self.a * self.cur + self.b ) % self.m
        return ret
 
lcg=LCG(bits=256,seed=seed)
 
out = []
for _ in range(20):
    out.append(lcg.extract())
 
print(f'm = {lcg.m}')
print(f'a = {lcg.a}')
print(f'b = {lcg.b}')
print(f'out = {out}')
'''
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
out = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]
'''

#模型：c0=a*seed+b,r0=c0*2**115,ci+1=a*ci+b modm,ri=ci*2**115
#转换成真正的模型：C0=a*seed+b omdm,Ci+1=a*Ci+b mod m,但每一个得到的Ci截断
#目标C0,其实还是ECDSA的那种类型,r0是小量
#每一个输出泄露257-115=142bit，142*20=2840
#隐藏20*115+seed.bit_length=2556,符合信息论

from Crypto.Util.number import *
from hashlib import md5
 
def MD5(m):return md5(str(m).encode()).hexdigest()
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
c = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]
 
ge = [[0]*21 for i in range(21)]
#画图更好理解
for i in range(19):
    ge[i][i] = m
ge[-2][-2],ge[-1][-1] = 1,1
ge[-2][0], ge[-1][0]  = a,a*(c[0]<<115)+b-(c[1]<<115)
for i in range(1,19):
    ge[-2][i]=a^(i+1)
    ge[-1][i]=ge[-1][i-1]*a+a*(c[i]<<115)+b-(c[i+1]<<115)
 
Ge = Matrix(ZZ,ge)
Ge = Ge.LLL()
assert Ge[0][-1] == 1
state = abs(Ge[0][-2])+(c[0]<<115)
seed = pow(a,-1,m)*(state-b)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')
 
# 101639613050544872292192629515273562035022699788445344858455157668840828973361
# '0xGame{459049e068d93f6d70f1ea0da705264a}'