线性同余方法（LCG）是一种产生伪随机数的方法。 线性同余法最重要的是定义了三个整数，乘数 a、增量 b和模数 m，其中a,b,m是产生器设定的常数。 为了方便理解，我打个比方 假设现在有随机数X1=1234，乘数a=2，增量b=3，模数m=1000 那么下一个随机数X2=(2*1234+3)%1000=2471%1000=471

解题用到的公式:

目的公式1.X_n+1反推出X_nX_n=(a^-1 (X_n+1 - b))%m2.求aa=((X_n+2-X_n+1)(X_n+1-X_n)^-1)%m3.求bb=(X_n+1 - aX_n)%m4.求mt_n=X_n+1-X_n，m=gcd((t_n+1t_n-1 - t_nt_n) , (t_nt_n-2 - t_n-1t_n-1))

下面是公式证明: 其实公式证明挺复杂的可以最后看，先看看例题也不错哦 公式1: X_n+1 = aX_n + b (mod m) aX_n = X_n+1 - b (mod m) X_n = a^-1 (X_n+1 - b) (mod m) 模逆运算用到扩展欧几里得算法

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算

公式2 解先行方程组 X_n+2 = aX_n+1 + b (mod m) X_n+1 = aX_n + b (mod m) X_n+2 - X_n+1 = a(X_n+1-X_n) (mod m) a = (X_n+2 - X_n+1)(X_n+1 - X_n)^-1 (mod m) 公式3 X_n+1 = aX_n + b (mod m) b = X_n+1 - aX_n (mod m) 公式4 设t_n = X_n+1 - X_n t_n = (aX_n+b) - (aX_n-1+b) = at_n-1(mod m) t_n+1t_n-1 - t_nt_n = (aat_n-1t_n-1 - at_n-1at_n-1) = 0 (mod m) 即T_n = t_n+1t_n-1 - t_nt_n是m的倍数，求T_n , T_n-1最大公因数即为m m = gcd((t_n+1t_n-1 - t_nt_n) , (t_nt_n-2 - t_n-1t_n-1))

好了，然后根据lcg算法有六种ctf题型

lcg-1

from Crypto.Util.number import * flag = b'Spirit{***********************}' plaintext = bytes_to_long(flag) length = plaintext.bit_length() a = getPrime(length) b = getPrime(length) n = getPrime(length) seed = 33477128523140105764301644224721378964069 print("seed = ",seed) for i in range(10): seed = (a*seed+b)%n ciphertext = seed^plaintext print("a = ",a) print("b = ",b) print("n = ",n) print("c = ",ciphertext) # seed = 33477128523140105764301644224721378964069 # a = 216636540518719887613942270143367229109002078444183475587474655399326769391 # b = 186914533399403414430047931765983818420963789311681346652500920904075344361 # n = 155908129777160236018105193822448288416284495517789603884888599242193844951 # c = 209481865531297761516458182436122824479565806914713408748457524641378381493

这道题的题意是: 他定义了一个变量叫plaintext，长字节字符串flag转换为整数得到的. 定义了一个整数seed = 33477128523140105764301644224721378964069 seed通过10次lcg转换之后再和plaintext二进制异或得到ciphertext getPrime是根据输入length产生随机数的函数 思路: 想要得到flag就要知道plaintext 想要知道plaintext只能通过ciphertext = seed ^ plaintex这个表达式推出 而ciphertext==c我们知道，式子中的seed可以通过他给的初始seed,a,b,n运用算法lcg十次得到 然后根据异或的特性求解出plaintext，即plaintext = seed ^ ciphertext (异或特性，c=a异或b，那么a=b异或c，或者b=a异或c) 解题代码如下

seed = 33477128523140105764301644224721378964069 a = 216636540518719887613942270143367229109002078444183475587474655399326769391 b = 186914533399403414430047931765983818420963789311681346652500920904075344361 n = 155908129777160236018105193822448288416284495517789603884888599242193844951 c = 209481865531297761516458182436122824479565806914713408748457524641378381493 for i in range(10): seed = (a*seed+b)%n plaintext=seed^c print(long_to_bytes(plaintext)) 答案Spirit{0ops!___you_know__LCG!!}

lcg-2

from Crypto.Util.number import * flag = b'Spirit{*****************************}' plaintext = bytes_to_long(flag) length = plaintext.bit_length() a = getPrime(length) b = getPrime(length) n = getPrime(length) seed = plaintext for i in range(10): seed = (a*seed+b)%n ciphertext = seed print("a = ",a) print("b = ",b) print("n = ",n) print("c = ",ciphertext) # a = 59398519837969938359106832224056187683937568250770488082448642852427682484407513407602969 # b = 32787000674666987602016858366912565306237308217749461581158833948068732710645816477126137 # n = 43520375935212094874930431059580037292338304730539718469760580887565958566208139467751467 # c = 8594514452808046357337682911504074858048299513743867887936794439125949418153561841842276

根据题意求flag相当于求plaintext，求plaintext相当于求初始seed，我们知道lcg算法十次之后的seed=ciphertext=c，而c我们已知，我们还知道a，b，n。所以这道题要我们从lcg十次之后的seed推算出初始seed 用公式1：X_n=(a^-1 (X_n+1 - b))%n 这里a^-1是a相对于模数m的逆元，他也有公式

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算

所以解题代码如下

a = 59398519837969938359106832224056187683937568250770488082448642852427682484407513407602969 b = 32787000674666987602016858366912565306237308217749461581158833948068732710645816477126137 n = 43520375935212094874930431059580037292338304730539718469760580887565958566208139467751467 c = 8594514452808046357337682911504074858048299513743867887936794439125949418153561841842276 MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算 ani=MMI(a,n) seed=c for i in range(10): seed = (ani*(seed-b))%n print(long_to_bytes(seed) 答案Spirit{Orzzz__number_the0ry_master!!}

lcg-3

from Crypto.Util.number import * flag = b'Spirit{*********************}' plaintext = bytes_to_long(flag) length = plaintext.bit_length() a = getPrime(length) seed = getPrime(length) n = getPrime(length) b = plaintext output = [] for i in range(10): seed = (a*seed+b)%n output.append(seed) ciphertext = seed print("a = ",a) print("n = ",n) print("output1 = ",output[6]) print("output2 = ",output[7]) # a = 3227817955364471534349157142678648291258297398767210469734127072571531 # n = 2731559135349690299261470294200742325021575620377673492747570362484359 # output1 = 56589787378668192618096432693925935599152815634076528548991768641673 # output2 = 2551791066380515596393984193995180671839531603273409907026871637002460

求flag相当于求plaintext，plaintext相当于求b，然后在看看我们已知的条件，我们知道a，知道n知道10次lcg中的第6次和第7次的结果，所以我们要根据已知的信息求b 用公式3：b=(X_n+1 - aX_n)%n直接求出b 上代码

a = 3227817955364471534349157142678648291258297398767210469734127072571531 n = 2731559135349690299261470294200742325021575620377673492747570362484359 output1 = 56589787378668192618096432693925935599152815634076528548991768641673 output2 = 2551791066380515596393984193995180671839531603273409907026871637002460 b=(output2-a*output1)%n plaintext=b print(long_to_bytes(plaintext)) 答案Spirit{Y0u_@r3_g00d_at__math}

lcg-4

from Crypto.Util.number import * flag = b'Spirit{********************************}' plaintext = bytes_to_long(flag) length = plaintext.bit_length() a = getPrime(length) b = getPrime(length) n = getPrime(length) seed = plaintext output = [] for i in range(10): seed = (a*seed+b)%n output.append(seed) print("n = ",n) print("output = ",output) # n = 714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819 # output = [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276]

第四题给了n和10次lcg的output序列 用公式2：a=((X_n+2-X_n+1)(X_n+1-X_n)^-1)%n 用已知信息可以求出a 再用a，output序列，n求出b 根据output序列第一个反推出初始seed 即可求解

n = 714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819 output = [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276] MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算 a=(output[2]-output[1])*MMI((output[1]-output[0]),n)%n ani=MMI(a,n) b=(output[1]-a*output[0])%n seed = (ani*(output[0]-b))%n plaintext=seed print(long_to_bytes(plaintext)) 答案Spirit{Gr3at__J0b!_You_can_be___better!}

lcg-5

from Crypto.Util.number import * flag = b'Spirit{****************************************}' plaintext = bytes_to_long(flag) length = plaintext.bit_length() a = getPrime(length) b = getPrime(length) n = getPrime(length) seed = plaintext output = [] for i in range(10): seed = (a*seed+b)%n output.append(seed) print("output = ",output) # output = [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]

用公式4 解题代码

from Crypto.Util.number import * def gcd(a,b): if(b==0): return a else: return gcd(b,a%b) s = [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982] t = [] for i in range(9): t.append(s[i]-s[i-1]) all_n = [] for i in range(7): all_n.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1]))) MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算 for n in all_n: n=abs(n) if n==1: continue a=(s[2]-s[1])*MMI((s[1]-s[0]),n)%n ani=MMI(a,n) b=(s[1]-a*s[0])%n seed = (ani*(s[0]-b))%n plaintext=seed print(long_to_bytes(plaintext))

结果

b'\x00' b'\xd6\xce\xc7P)\xf9l\xc7\xc8{h\xf0\xc0\xdcX\xd7q\xc7\xd4\xd1L;\xb7hh*\xc2\xb4\xa3,\xbb\xa1}&\x94Z\xda\x19\x95\xbb\xa6\x93g\xec\xd7\xc6\x15c' b'\xd6\xce\xc7P)\xf9l\xc7\xc8{h\xf0\xc0\xdcX\xd7q\xc7\xd4\xd1L;\xb7hh*\xc2\xb4\xa3,\xbb\xa1}&\x94Z\xda\x19\x95\xbb\xa6\x93g\xec\xd7\xc6\x15c' b'Spirit{final__lcg__is__co0m1ing__are_you_ready?}' b'\xeb\xf7.\xdc!\xe5O\xb4\x11\xed\xf1\xa5\xca\xa1\x9b\x15\xda\x85\xc1\x19\xebGd\n\x93\x04\xb2PW\x9c\xc0^\x8c\xf8\xdd5\xf9\xcf\x1c\xad\x8b\xdd\xde\x1a/\xa6H\x08' b'\xeb\xf7.\xdc!\xe5O\xb4\x11\xed\xf1\xa5\xca\xa1\x9b\x15\xda\x85\xc1\x19\xebGd\n\x93\x04\xb2PW\x9c\xc0^\x8c\xf8\xdd5\xf9\xcf\x1c\xad\x8b\xdd\xde\x1a/\xa6H\x08'

lcg-6

from Crypto.Util.number import * flag = b'Spirit{*****************}' plaintext = bytes_to_long(flag) length = plaintext.bit_length() a = getPrime(length) b = getPrime(length) n = getPrime(length) seed = plaintext output = [] for i in range(10): seed = (seed*a+b)%n output.append(seed>>64) print("a = ",a) print("b = ",b) print("n = ",n) print("output = ",output) # a = 731111971045863129770849213414583830513204814328949766909151 # b = 456671883153709362919394459405008275757410555181682705944711 # n = 666147691257100304060287710111266554526660232037647662561651 # output = [16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]