線性同余方法（LCG）是一種產生偽亂數的方法，

線性同余法最重要的是定義了三個整數，乘數 a、增量 b和模數 m，其中a,b,m是產生器設定的常數，
為了方便理解，我打個比方
假設現在有亂數X1=1234，乘數a=2，增量b=3，模數m=1000
那么下一個亂數X2=(2*1234+3)%1000=2471%1000=471

解題用到的公式:

好了，然后根據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 = (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

第五題比較復雜呢，有小伙伴做出來的可以分享一下呀