LCG HNP

from Crypto.Util.number import getPrime, inverse
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() == 510
 
class LuanGao:
    def __init__(self, bits:int, seed:int):
        self.bits = bits
        self.m = getPrime(self.bits)
        self.a = getPrime(self.bits // 2)
        self.cur = (self.a * seed) % self.m
 
    def extract(self):
        ret = self.cur
        b = getPrime(self.bits // 4)
        self.cur = ( self.a * self.cur + b ) % self.m
        return ret
 
C = LuanGao(512, seed)
Cs = [C.extract() for _ in range(5)]
 
print(f'Cs = {Cs}')
print(f'C.m = {C.m}')
 
'''
Cs = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
C.m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
'''
#题干解读：C为未知，a未知，有4条方程，Ci+1=a*Ci+bi mod m,有4组方程（Ci循环生成）

#注意量级，b的量级比其他的量级小，这时b是泄露，4条b的bit量和a相同，符合信息论
#还原式子：Ci+1=a*Ci+bi mod m,其中C0就是a*seed%m,想要还原C0,要还原出a
#其实这个时候就已经可以套公式知道是HNP了，标准构造
from Crypto.Util.number import *
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()
m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
c = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
ge = [
[m,0,0,0,0,0],
[0,m,0,0,0,0],
[0,0,m,0,0,0],
[0,0,0,m,0,0],
[c[0],c[1],c[2],c[3],1,0],#这里构造少许不同，有2行C，因为式子是C-C
[c[1],c[2],c[3],c[4],0,1]]#依然是竖解，最后得到（b,b,b,b,-a,1)
Ge = Matrix(ZZ,ge)
L = Ge.LLL()
a = abs(L[0][-2])#取得a
seed = c[0]*inverse(a,m)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')
# '0xGame{2db84757dd4197f9b9441be25f35bfd5}'
# 2512273436977220996062855314655393786244910444920037228737234078954182704102442213664768806368325362960908940985195233026259876194811260795362098878115082