在学习线性同余的这边，可以先学习一下同余的性质，这样就可以更好推导出线性同余的一些式子，从而打好基础。
LCG线性同余一般是用来生成伪随机数。之所以被称为线性同余，是因为其是一个一次函数形式的同余关系。所以被称为线性同余
LCG线性同余的公式如下：
X n + 1 ≡ ( a X n + b ) m o d m \begin{array}{l}
X_{n+1}\equiv(aX_n+b)~mod~~m
\end{array}
X n + 1 ≡ ( a X n + b ) m o d m
根据公式和为随机数生成的原则，我们可以知道当n=1时，X1就是该伪随机数生成的种子，乘数为a、增量为b、模数为m。a、b、m是常数，在进行第一次线性同余计算之前就需要生成出来。
接下来将使用Python实现一个简单的线性同余生成伪随机数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import gmpy2from Crypto.Util.number import *x1 = getPrime(300 ) a = getPrime(300 ) b = getPrime(300 ) m = getPrime(400 ) print ("a=" ,a)print ("b=" ,b)print ("x1=" ,x1)print ("m=" ,m)for i in range (5 ): x2 = (a*x1 + b) % m print (x2) x1 = x2 a= 1175968459483406966456090481519143554882817630907948845823441780532018444918506120531929977 b= 1771585311953754515849934086382293088385852100470332754753742729896803432522527992169593681 x1= 1958646050649417670331423507925536078168554828955650164023489904471188347248885827337493979 m= 2087305402799096140417064773611985975354058627532546255789058088275247421340580318885077772617072775918918640282194298059 x2= 1755143736782662033641857317697416543633480671186803523989257194341283951413210040767177604756326440095002730678692879945 x3= 1145828592240636116674980186106829063567924466043398788944460905588293518728040539192224111467756406900750826297818190828 x4= 1317617152154417555533737049040426345657224996377259703391845352652738686814152839869990992448175372904057268106168366513 x5= 1585660622701110231691999575045218914319460173604859197300955678353666785364923873992868748212849319625712106111306159622 x6= 904208346352639111751239494125939716858178782163682717827449631839443131196456402565995740774480917441140851969042704539
这种线性同余的伪随机数是可逆的。以上方Python代码实现为例子，当我们只知道x6、a、b、m的时候，是可以反推出种子x1的。
这里使用数论进行公式推导：
由该公式 X n + 1 ≡ ( a X n + b ) m o d m 可以得到 X n + 1 − b ≡ a X n m o d m ( X n + 1 − b ) a − 1 ≡ X n m o d m 所以 X n ≡ ( X n + 1 − b ) a − 1 \begin{array}{l}
由该公式X_{n+1}\equiv(aX_n+b)~mod~~m可以得到\\
X_{n+1}-b\equiv aX_n~mod~m\\
(X_{n+1}-b)a^{-1}\equiv X_n~mod~m\\
所以X_n \equiv (X_{n+1}-b)a^{-1}
\end{array}
由 该 公 式 X n + 1 ≡ ( a X n + b ) m o d m 可 以 得 到 X n + 1 − b ≡ a X n m o d m ( X n + 1 − b ) a − 1 ≡ X n m o d m 所 以 X n ≡ ( X n + 1 − b ) a − 1
这时我们再使用Python将之前使用代码实现的线性同余种子计算出来。将计算出来的结果与上方代码实现的数据对比，发现每一步都能恢复出结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import gmpy2import libnumx6= 904208346352639111751239494125939716858178782163682717827449631839443131196456402565995740774480917441140851969042704539 a= 1175968459483406966456090481519143554882817630907948845823441780532018444918506120531929977 b= 1771585311953754515849934086382293088385852100470332754753742729896803432522527992169593681 m= 2087305402799096140417064773611985975354058627532546255789058088275247421340580318885077772617072775918918640282194298059 inva = gmpy2.invert(a,m) for i in range (5 ): x1 = inva*(x6-b)%m print ("x{}=" .format (5 -i),x1) x6 = x1 x5= 1585660622701110231691999575045218914319460173604859197300955678353666785364923873992868748212849319625712106111306159622 x4= 1317617152154417555533737049040426345657224996377259703391845352652738686814152839869990992448175372904057268106168366513 x3= 1145828592240636116674980186106829063567924466043398788944460905588293518728040539192224111467756406900750826297818190828 x2= 1755143736782662033641857317697416543633480671186803523989257194341283951413210040767177604756326440095002730678692879945 x1= 1958646050649417670331423507925536078168554828955650164023489904471188347248885827337493979
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import uuidfrom Crypto.Util.number import *flag = b'flag{' + str (uuid.uuid4()).encode() + b'}' seed = bytes_to_long(flag) a = getPrime(512 ) b = getPrime(512 ) m = getPrime(512 ) print (seed.bit_length())for i in range (getPrime(16 )): seed = (a*seed+b)%m print ("seed=" ,seed)print ("a=" ,a)print ("b=" ,b)print ("m=" ,m)""" seed= 8379187872616044902823412850791633458517713967450924509092363734121098956085733672285350146201666608381153642887782927302932173648273976274669809990328831 a= 12031387796950906767804036906662364047664306111626661679198264630101904075847299943911577093348162441882555310591680021392734074717250187222203511278029771 b= 10261262649282211877390561800126847866849262518532790034042684738529108792276541148781061895570224426776680870943786422453658756913187227045796728409689443 m= 11160002078152535878070259785707721977563709504419289315044867176286302776295441399315427572539417707984834270987593756765841872796036351635033304769459121 """
这个是LCG线性同余中最基础的题目，也就是之前介绍的种子恢复，恢复公式如下：
由该公式 X n + 1 ≡ ( a X n + b ) m o d m 可以得到 X n + 1 − b ≡ a X n m o d m ( X n + 1 − b ) a − 1 ≡ X n m o d m 所以 X n ≡ ( X n + 1 − b ) a − 1 m o d m \begin{array}{l}
由该公式X_{n+1}\equiv(aX_n+b)~mod~~m可以得到\\
X_{n+1}-b\equiv aX_n~mod~m\\
(X_{n+1}-b)a^{-1}\equiv X_n~mod~m\\
所以X_n \equiv (X_{n+1}-b)a^{-1}~mod~m
\end{array}
由 该 公 式 X n + 1 ≡ ( a X n + b ) m o d m 可 以 得 到 X n + 1 − b ≡ a X n m o d m ( X n + 1 − b ) a − 1 ≡ X n m o d m 所 以 X n ≡ ( X n + 1 − b ) a − 1 m o d m
同时线性同余的次数比较小，可以直接爆破出来，故exp如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 import libnumimport gmpy2seed= 8379187872616044902823412850791633458517713967450924509092363734121098956085733672285350146201666608381153642887782927302932173648273976274669809990328831 a= 12031387796950906767804036906662364047664306111626661679198264630101904075847299943911577093348162441882555310591680021392734074717250187222203511278029771 b= 10261262649282211877390561800126847866849262518532790034042684738529108792276541148781061895570224426776680870943786422453658756913187227045796728409689443 m= 11160002078152535878070259785707721977563709504419289315044867176286302776295441399315427572539417707984834270987593756765841872796036351635033304769459121 inva = gmpy2.invert(a,m) for i in range (2 **16 ): seed = (inva * (seed-b)) % m flag = libnum.n2s(int (seed)) if b'flag{' in flag: print (flag)
这题也是比较基础的，会同余运算就可以做出来，题目如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import uuidfrom Crypto.Util.number import *flag = b'flag{' + str (uuid.uuid4()).encode() + b'}' seed = bytes_to_long(flag) a = getPrime(512 ) b = getPrime(512 ) m = getPrime(512 ) print (seed.bit_length())for i in range (getPrime(16 )): seed = (a*seed+b)%m print ("seed1=" ,seed)print ("seed2=" ,(a*seed+b)%m)print ("a=" ,a)print ("m=" ,m)""" seed1= 531973671893938590891166532927678655864565393738116427922572557506025108235216759806737399801119759856160150391106874665378068384866349886977652077013438 seed2= 1361557289970617709933919229554395969185828255089665259119447446116543300465417408286545585929108129459088324772003218284071418162834923905260908910496766 a= 10250630758919387797595748955427550276736499491563067533232555141599540797442386371367762754532478057757408062575670433043155292776017769035793609687331051 m= 8700779545188587710107135184103042871181270596905294614305926035580770981701558125880969503139565221510112690290974525315751618287127382573107541549876591 """
这题题目中并没有把b的值给我们，但是给了seed1、seed2，这样连续的两个种子，所以我们可以根据公式将b推导出来。推导过程如下：
由于 s e e d 2 和 s e e d 1 满足关系： s e e d 2 ≡ ( a ∗ s e e d 1 + b ) m o d ( m ) 所以可以得到： s e e d 2 − a ∗ s e e d 1 ≡ b m o d ( m ) 如果 b 小于 m 的话，那么 b 的值就可以计算出来了 ( 一般题目都会设定 b 小于 m ) \begin{array}{l}
由于seed_2和seed_1满足关系：
seed_2 \equiv (a*seed_1+b)~mod~(m)\\
所以可以得到：seed_2-a*seed_1 \equiv b ~mod~(m)\\
如果b小于m的话，那么b的值就可以计算出来了(一般题目都会设定b小于m)
\end{array}
由 于 s e e d 2 和 s e e d 1 满 足 关 系 ： s e e d 2 ≡ ( a ∗ s e e d 1 + b ) m o d ( m ) 所 以 可 以 得 到 ： s e e d 2 − a ∗ s e e d 1 ≡ b m o d ( m ) 如 果 b 小 于 m 的 话 ， 那 么 b 的 值 就 可 以 计 算 出 来 了 ( 一 般 题 目 都 会 设 定 b 小 于 m )
由该公式 s e e d n + 1 ≡ ( a s e e d n + b ) m o d m 可以得到 s e e d n + 1 − b ≡ a s e e d n m o d m ( s e e d n + 1 − b ) a − 1 ≡ s e e d n m o d m 所以 s e e d n ≡ ( s e e d n + 1 − b ) a − 1 \begin{array}{l}
由该公式seed_{n+1}\equiv(aseed_n+b)~mod~~m可以得到\\
seed_{n+1}-b\equiv aseed_n~mod~m\\
(seed_{n+1}-b)a^{-1}\equiv seed_n~mod~m\\
所以seed_n \equiv (seed_{n+1}-b)a^{-1}
\end{array}
由 该 公 式 s e e d n + 1 ≡ ( a s e e d n + b ) m o d m 可 以 得 到 s e e d n + 1 − b ≡ a s e e d n m o d m ( s e e d n + 1 − b ) a − 1 ≡ s e e d n m o d m 所 以 s e e d n ≡ ( s e e d n + 1 − b ) a − 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import libnumimport gmpy2seed1= 531973671893938590891166532927678655864565393738116427922572557506025108235216759806737399801119759856160150391106874665378068384866349886977652077013438 seed2= 1361557289970617709933919229554395969185828255089665259119447446116543300465417408286545585929108129459088324772003218284071418162834923905260908910496766 a= 10250630758919387797595748955427550276736499491563067533232555141599540797442386371367762754532478057757408062575670433043155292776017769035793609687331051 m= 8700779545188587710107135184103042871181270596905294614305926035580770981701558125880969503139565221510112690290974525315751618287127382573107541549876591 b = (seed2-a*seed1)%m inva = gmpy2.invert(a,m) for i in range (2 **16 ): seed1 = (inva * (seed1-b)) % m flag = libnum.n2s(int (seed1)) if b'flag{' in flag: print (flag)
虽然只知道线性同余的余数m，但是题目会给出3个连续的随机数，所以经过一些简单的mod性质就可以反求出a、b，从而得到爆破得到flag。其实题目1到题目3就是LCG简单的运用
题目如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import uuidfrom Crypto.Util.number import *flag = b'flag{' + str (uuid.uuid4()).encode() + b'}' global seedseed = bytes_to_long(flag) a = getPrime(512 ) b = getPrime(512 ) m = getPrime(512 ) print (seed.bit_length())def LCG (j=1 ): global seed global a global b global m for i in range (j): seed = (a*seed+b)%m return seed seed1 = LCG(getPrime(16 )) print ("seed1=" ,seed1)print ("seed2=" ,LCG())print ("seed3=" ,LCG())print ("m=" ,m)""" seed1= 2827216214576534336943777005123511471823436090335252393645112419570975229759556636830932516427545175967431054029648341329102624221802844678613411400354465 seed2= 6739808433556029368062086080181502049125125080627863660643998265824366534355952238175430699144661366211106869790133344229073059100842345248720603112990029 seed3= 11199248685462107566254268225211529785065220120667376228876192591905380244018582530462155032889397130443123124892469894668030293885611847611347153064649077 m= 11704323998983239157543714242926070009162244149411783281995136317037553672748457912719439389115781420796561654954980143303208349356582984947550465065062153 """
我们已知三个连续的seed，所以我们要先从这三个连续的seed中求解a、b，那么我们先把这三个seed的生成公式列出来，去寻找其中的关系。
s e e d n + 3 ≡ a ∗ s e e d n + 2 + b m o d ( m ) ——① s e e d n + 2 ≡ a ∗ s e e d n + 1 + b m o d ( m ) ——② s e e d n + 1 ≡ a ∗ s e e d n + b m o d ( m ) ——③ \begin{array}{l}
seed_{n+3} \equiv a*seed_{n+2} + b~mod~(m)——①\\
seed_{n+2} \equiv a*seed_{n+1} + b~mod~(m)——②\\
seed_{n+1} \equiv a*seed_{n} + b~mod~(m)——③\\
\end{array}
s e e d n + 3 ≡ a ∗ s e e d n + 2 + b m o d ( m ) — — ① s e e d n + 2 ≡ a ∗ s e e d n + 1 + b m o d ( m ) — — ② s e e d n + 1 ≡ a ∗ s e e d n + b m o d ( m ) — — ③
这时我们注意到，当我们用①式减去②式的时候就可以消除b，从而只剩a这个未知数。再通过逆元，就可以求得a的值。推导过程如下：
由① − ②后 s e e d n + 3 − s e e d n + 2 ≡ a ∗ ( s e e d n + 2 − s e e d n + 1 ) m o d m 所以可以得到 a ≡ ( s e e d n + 3 − s e e d n + 2 ) ∗ ( s e e d n + 2 − s e e d n + 1 ) − 1 m o d m 进而就可以求出 a 的值 \begin{array}{l}
由①-②后\\
seed_{n+3}-seed_{n+2} \equiv a*(seed_{n+2}-seed_{n+1})~mod~m\\
所以可以得到a \equiv (seed_{n+3}-seed_{n+2})*(seed_{n+2}-seed_{n+1})^{-1}~mod~m\\
进而就可以求出a的值
\end{array}
由 ① − ② 后 s e e d n + 3 − s e e d n + 2 ≡ a ∗ ( s e e d n + 2 − s e e d n + 1 ) m o d m 所 以 可 以 得 到 a ≡ ( s e e d n + 3 − s e e d n + 2 ) ∗ ( s e e d n + 2 − s e e d n + 1 ) − 1 m o d m 进 而 就 可 以 求 出 a 的 值
由于 s e e d 2 和 s e e d 1 满足关系： s e e d 2 ≡ ( a ∗ s e e d 1 + b ) m o d ( m ) 所以可以得到： s e e d 2 − a ∗ s e e d 1 ≡ b m o d ( m ) 如果 b 小于 m 的话，那么 b 的值就可以计算出来了 ( 一般题目都会设定 b 小于 m ) \begin{array}{l}
由于seed_2和seed_1满足关系：
seed_2 \equiv (a*seed_1+b)~mod~(m)\\
所以可以得到：seed_2-a*seed_1 \equiv b ~mod~(m)\\
如果b小于m的话，那么b的值就可以计算出来了(一般题目都会设定b小于m)
\end{array}
由 于 s e e d 2 和 s e e d 1 满 足 关 系 ： s e e d 2 ≡ ( a ∗ s e e d 1 + b ) m o d ( m ) 所 以 可 以 得 到 ： s e e d 2 − a ∗ s e e d 1 ≡ b m o d ( m ) 如 果 b 小 于 m 的 话 ， 那 么 b 的 值 就 可 以 计 算 出 来 了 ( 一 般 题 目 都 会 设 定 b 小 于 m )
由该公式 X n + 1 ≡ ( a X n + b ) m o d m 可以得到 X n + 1 − b ≡ a X n m o d m ( X n + 1 − b ) a − 1 ≡ X n m o d m 所以 X n ≡ ( X n + 1 − b ) a − 1 m o d m \begin{array}{l}
由该公式X_{n+1}\equiv(aX_n+b)~mod~~m可以得到\\
X_{n+1}-b\equiv aX_n~mod~m\\
(X_{n+1}-b)a^{-1}\equiv X_n~mod~m\\
所以X_n \equiv (X_{n+1}-b)a^{-1}~mod~m
\end{array}
由 该 公 式 X n + 1 ≡ ( a X n + b ) m o d m 可 以 得 到 X n + 1 − b ≡ a X n m o d m ( X n + 1 − b ) a − 1 ≡ X n m o d m 所 以 X n ≡ ( X n + 1 − b ) a − 1 m o d m
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import libnumimport gmpy2seed1= 10108051321861483351146900164216421892303009074656802642877936583945209211824578941394860642895401474842454756358571425297290866115811478315969469383227365 seed2= 8298226438937024399394666985834505690086603252528046129859113649133899140071972599739560890259143306149555973037260633540419279012435819303313598457142205 seed3= 4040251672571936101829332270253013469888558365857467089318400495951696581101064249945316791749876515080521266364225982926900210409347049898895583868092005 m= 12089789856272284182347576409237995357111118927995723026914974156516478831606354451543318914508084516001638686608043717164669987097325696399241720793523921 tmp1 = seed3 - seed2 tmp2 = seed2 - seed1 d = gmpy2.invert(tmp2,m) a = tmp1*d % m b = (seed2-a*seed1)%m inva = gmpy2.invert(a,m) for i in range (2 **16 ): seed1 = (seed1-b)*inva%m result = seed1 flag = libnum.n2s(int (result)) if b'flag' in flag: print (flag)
此题目，线性同余的三个常量都没有给出来，只给出了连续的5个伪随机数种子。这时就不能使用之前同余的方法求解a、b、m这三个常量了。
接下来给出题目：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import uuidfrom Crypto.Util.number import *flag = b'flag{' + str (uuid.uuid4()).encode() + b'}' global seedseed = bytes_to_long(flag) a = getPrime(512 ) b = getPrime(512 ) m = getPrime(512 ) print (seed.bit_length())def LCG (j=1 ): global seed global a global b global m for i in range (j): seed = (a*seed+b)%m return seed seed1 = LCG(getPrime(16 )) print ("seed1=" ,seed1)print ("seed2=" ,LCG())print ("seed3=" ,LCG())print ("seed4=" ,LCG())print ("seed5=" ,LCG())""" seed1= 8882189538537884841386817978925990419679390989222082262426747871669922060619212506347637919610274469352197322485195404952238539726684418554965437474894033 seed2= 26181825248265790657015394331398550621932888484883214933669628142354350156591363815825902457241771469307266983798658003141531387525750750982100768789681 seed3= 5162748072528245673425575431035879979464479877261305134740771827174030696226375909360527017281269320966239427847977512098462466936874687956543764287106111 seed4= 5955932703947171683212008141979712484552012134034532274524300082660183321066810041115841187139634739333173857023358416494328062781308380883364166112433671 seed5= 8434739796373089074290814615951718348972722331963760268691288790219878601780066237759979838964927465417068870322434703689154391611081522042317515083459762 """
s e e d n + 1 ≡ a ∗ s e e d n + b m o d ( m ) ——① s e e d n + 2 ≡ a ∗ s e e d n + 1 + b m o d ( m ) ——② s e e d n + 3 ≡ a ∗ s e e d n + 2 + b m o d ( m ) ——③ s e e d n + 4 ≡ a ∗ s e e d n + 3 + b m o d ( m ) ——④ s e e d n + 5 ≡ a ∗ s e e d n + 4 + b m o d ( m ) ——⑤ \begin{array}{l}
seed_{n+1} \equiv a*seed_{n} + b~mod~(m)——①\\
seed_{n+2} \equiv a*seed_{n+1} + b~mod~(m)——②\\
seed_{n+3} \equiv a*seed_{n+2} + b~mod~(m)——③\\
seed_{n+4} \equiv a*seed_{n+3} + b~mod~(m)——④\\
seed_{n+5} \equiv a*seed_{n+4} + b~mod~(m)——⑤\\
\end{array}
s e e d n + 1 ≡ a ∗ s e e d n + b m o d ( m ) — — ① s e e d n + 2 ≡ a ∗ s e e d n + 1 + b m o d ( m ) — — ② s e e d n + 3 ≡ a ∗ s e e d n + 2 + b m o d ( m ) — — ③ s e e d n + 4 ≡ a ∗ s e e d n + 3 + b m o d ( m ) — — ④ s e e d n + 5 ≡ a ∗ s e e d n + 4 + b m o d ( m ) — — ⑤
这时，我们需要消元，将b消去，所以我们就将②式-①式
s e e d n + 2 − s e e d n + 1 ≡ a ∗ ( s e e d n + 1 − s e e d n ) m o d ( m ) \begin{array}{l}
seed_{n+2} - seed_{n+1} \equiv a*(seed_{n+1}-seed_{n}) ~mod~(m)
\end{array}
s e e d n + 2 − s e e d n + 1 ≡ a ∗ ( s e e d n + 1 − s e e d n ) m o d ( m )
t n = s e e d n − s e e d n − 1 t_{n}=seed_n-seed_{n-1}
t n = s e e d n − s e e d n − 1
t n + 2 ≡ a ∗ t n + 1 m o d ( m ) t_{n+2}\equiv a*t_{n+1} ~mod(m)
t n + 2 ≡ a ∗ t n + 1 m o d ( m )
t n + 3 ≡ a ∗ t n + 2 ≡ a 2 t n + 1 m o d ( m ) t n + 4 ≡ a ∗ t n + 3 ≡ a 3 t n + 1 m o d ( m ) t n + 5 ≡ a ∗ t n + 4 ≡ a 4 t n + 1 m o d ( m ) \begin{array}{l}
t_{n+3}\equiv a*t_{n+2} \equiv a^2t_{n+1}~mod(m)\\
t_{n+4}\equiv a*t_{n+3} \equiv a^3t_{n+1}~mod(m)\\
t_{n+5}\equiv a*t_{n+4} \equiv a^4t_{n+1}~mod(m)
\end{array}
t n + 3 ≡ a ∗ t n + 2 ≡ a 2 t n + 1 m o d ( m ) t n + 4 ≡ a ∗ t n + 3 ≡ a 3 t n + 1 m o d ( m ) t n + 5 ≡ a ∗ t n + 4 ≡ a 4 t n + 1 m o d ( m )
数列 { t n } 在模 m 的意义下成等比数列 数列\{t_{n}\}在模m的意义下成等比数列
数 列 { t n } 在 模 m 的 意 义 下 成 等 比 数 列
t n + m ∗ t n + k = t n + m + k 2 2 其中 m + k 要为偶数 t_{n+m}*t_{n+k}=t^{2}_{n+\frac{m+k}{2}}\\
其中m+k要为偶数
t n + m ∗ t n + k = t n + 2 m + k 2 其 中 m + k 要 为 偶 数
t n + 1 ∗ t n + 3 ≡ t n + 2 2 m o d m 从而推导出如下式子 : t t n + 1 ∗ t n + 3 − t n + 2 2 ≡ 0 m o d m 即 m ∣ ( t t n + 1 ∗ t n + 3 − t n + 2 2 ) \begin{array}{l}
t_{n+1}*t_{n+3}\equiv t^2_{n+2}~mod~m\\
从而推导出如下式子:\\
t_{t_n+1}*t_{n+3}-t^2_{n+2}\equiv0~mod~m\\
即m\mid (t_{t_n+1}*t_{n+3}-t^2_{n+2})
\end{array}
t n + 1 ∗ t n + 3 ≡ t n + 2 2 m o d m 从 而 推 导 出 如 下 式 子 : t t n + 1 ∗ t n + 3 − t n + 2 2 ≡ 0 m o d m 即 m ∣ ( t t n + 1 ∗ t n + 3 − t n + 2 2 )
t n + 3 ∗ t n + 5 ≡ t n + 4 2 m o d m 从而得到 : m ∣ ( t t n + 3 ∗ t n + 5 − t n + 4 2 ) \begin{array}{l}
t_{n+3}*t_{n+5} \equiv t^2_{n+4} ~mod~m\\
从而得到:\\
m\mid (t_{t_n+3}*t_{n+5}-t^2_{n+4})
\end{array}
t n + 3 ∗ t n + 5 ≡ t n + 4 2 m o d m 从 而 得 到 : m ∣ ( t t n + 3 ∗ t n + 5 − t n + 4 2 )
所以m就为这俩个式子的公因数。但是这时，假如我们使用gcd，则求的是其最大公因数。如果我们知道连续的种子数足够多的话，我们根据如下最大公因数的性质，就可以得到使用gcd的计算的结果很可能就是m。定理如下：
设 a 1 , a 2 , . . . , a n 是不全为零的整数 ( 可以假定它们都是正整数 ) ，且 ( a 1 , a 2 ) = d 2 , ( d 2 , a 3 ) = d 3 , . . . , ( d n − 2 , a n − 1 ) = d n − 1 , ( d n − 1 , a n ) = d n , 则 ( a 1 , a 2 , . . . , a n ) = d n \begin{array}{l}
设a_1,a_2,...,a_n是不全为零的整数(可以假定它们都是正整数)，且\\
(a_1,a_2)=d_2,~~(d_2,a_3)=d_3~~,...,~~(d_{n-2},a_{n-1})=d_{n-1},(d_{n-1},a_{n})=d_n,\\
则(a_1,a_2,...,a_n)=d_n
\end{array}
设 a 1 , a 2 , . . . , a n 是 不 全 为 零 的 整 数 ( 可 以 假 定 它 们 都 是 正 整 数 ) ， 且 ( a 1 , a 2 ) = d 2 , ( d 2 , a 3 ) = d 3 , . . . , ( d n − 2 , a n − 1 ) = d n − 1 , ( d n − 1 , a n ) = d n , 则 ( a 1 , a 2 , . . . , a n ) = d n
但是我们这题会出现情况就是，连续的种子数知道的不够多，所以我们gcd求得的最大公因数，不一定是m，但是一定是比m大的数。但是由算数基本定理的推论可以得到我们所求得的最大公因数一定是m的倍数，这时如果最大公因数与m的位数较小的时候，我们就可以爆破出m。
具体的exp如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 import libnumimport gmpy2from Crypto.Util.number import *seed1= 8882189538537884841386817978925990419679390989222082262426747871669922060619212506347637919610274469352197322485195404952238539726684418554965437474894033 seed2= 26181825248265790657015394331398550621932888484883214933669628142354350156591363815825902457241771469307266983798658003141531387525750750982100768789681 seed3= 5162748072528245673425575431035879979464479877261305134740771827174030696226375909360527017281269320966239427847977512098462466936874687956543764287106111 seed4= 5955932703947171683212008141979712484552012134034532274524300082660183321066810041115841187139634739333173857023358416494328062781308380883364166112433671 seed5= 8434739796373089074290814615951718348972722331963760268691288790219878601780066237759979838964927465417068870322434703689154391611081522042317515083459762 seed = [seed1,seed2,seed3,seed4,seed5] t = [] for i in range (len (seed)-1 ): t.append(seed[i+1 ]-seed[i]) print (len (t))gcd = [] for j in range (len (t)-2 ): gcd.append(t[j]*t[j+2 ]-t[j+1 ]*t[j+1 ]) for k in range (len (gcd)-1 ): m = gmpy2.gcd(gcd[k],gcd[k+1 ]) print (m)print (m.bit_length())for i in range (1 ,2 **7 ): k = m//i if isPrime(k) and k.bit_length()==512 : break print (k)tmp1 = seed3 - seed2 tmp2 = seed2 - seed1 d = gmpy2.invert(tmp2,k) a = tmp1*d % k b = (seed2-a*seed1)%k inva = gmpy2.invert(a,k) for i in range (2 **16 ): seed1 = (seed1-b)*inva%k result = seed1 flag = libnum.n2s(int (result)) if b'flag' in flag: print (flag) """ 4 1137090816770073197270424957175401500912007414994958444869947426763852840666172756763250313958809835698300332761138846841317554909814663527655009571916688230 519 10337189243364301793367499610685468190109158318135985862454067516035025824237934152393184672352816688166366661464898607648341408271042395705954632471969893 b'flag{119598ba-c059-4a6f-8d34-17fcdda15923}' """
LCG还可以和RSA综合起来，例如利用LCG生成素数之类的。
