• LCG，是伪随机数生成器PRNG的一个比较简单的算法，可以从该算法入门一下伪随机数生成器。
  • LCG的考点还是比较多的，特别是还有变种LCG，这就导致不好归纳出LCG对应的题型，本篇博客只做介绍LCG算法的过程以及收集些题目（如果做多了能形成总结后续会补充）

LCG线性同余

  • 在学习线性同余的这边，可以先学习一下同余的性质，这样就可以更好推导出线性同余的一些式子，从而打好基础。

介绍

  • LCG线性同余一般是用来生成伪随机数。之所以被称为线性同余，是因为其是一个一次函数形式的同余关系。所以被称为线性同余
  • LCG线性同余的公式如下：

Xn+1≡(aXn+b) mod  m\begin{array}{l} X_{n+1}\equiv(aX_n+b)~mod~~m \end{array}

  • 根据公式和为随机数生成的原则，我们可以知道当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 gmpy2
from 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的。
  • 这里使用数论进行公式推导：

由该公式Xn+1≡(aXn+b) mod  m可以得到Xn+1−b≡aXn mod m(Xn+1−b)a−1≡Xn mod m所以Xn≡(Xn+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}

  • 这时我们再使用Python将之前使用代码实现的线性同余种子计算出来。将计算出来的结果与上方代码实现的数据对比，发现每一步都能恢复出结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
import libnum
x6= 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

LCG基础

题目1_已知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
import uuid
from 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线性同余中最基础的题目，也就是之前介绍的种子恢复，恢复公式如下：

由该公式Xn+1≡(aXn+b) mod  m可以得到Xn+1−b≡aXn mod m(Xn+1−b)a−1≡Xn mod m所以Xn≡(Xn+1−b)a−1 mod 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}

  • 同时线性同余的次数比较小，可以直接爆破出来，故exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import libnum
import gmpy2
seed= 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)
# b'flag{7ecc05dc-c4be-47b0-830e-06e1ea8ccfe8}'

题目2_未知b

  • 这题也是比较基础的，会同余运算就可以做出来，题目如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import uuid
from 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推导出来。推导过程如下：

由于seed2和seed1满足关系：seed2≡(a∗seed1+b) mod (m)所以可以得到：seed2−a∗seed1≡b mod (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}

  • 之后就是按照题目1的方式进行操作即可

由该公式seedn+1≡(aseedn+b) mod  m可以得到seedn+1−b≡aseedn mod m(seedn+1−b)a−1≡seedn mod m所以seedn≡(seedn+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}

  • 所以exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum
import gmpy2
seed1= 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)
        
# b'flag{29e65022-9ea5-45a3-9e02-704c800c8cf9}'

题目3_未知a、b

  • 虽然只知道线性同余的余数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 uuid
from Crypto.Util.number import *
flag = b'flag{' + str(uuid.uuid4()).encode() + b'}'
global seed
seed = 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的生成公式列出来，去寻找其中的关系。

seedn+3≡a∗seedn+2+b mod (m)——①seedn+2≡a∗seedn+1+b mod (m)——②seedn+1≡a∗seedn+b mod (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}

  • 这时我们注意到，当我们用①式减去②式的时候就可以消除b，从而只剩a这个未知数。再通过逆元，就可以求得a的值。推导过程如下：

由①−②后seedn+3−seedn+2≡a∗(seedn+2−seedn+1) mod m所以可以得到a≡(seedn+3−seedn+2)∗(seedn+2−seedn+1)−1 mod 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}

  • 得到a的之后，后面求b就是按照题目2的思路

由于seed2和seed1满足关系：seed2≡(a∗seed1+b) mod (m)所以可以得到：seed2−a∗seed1≡b mod (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}

  • 接下来就是利用题目1的思路去恢复flag

由该公式Xn+1≡(aXn+b) mod  m可以得到Xn+1−b≡aXn mod m(Xn+1−b)a−1≡Xn mod m所以Xn≡(Xn+1−b)a−1 mod 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}

  • 本题的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
import libnum
import gmpy2
seed1= 10108051321861483351146900164216421892303009074656802642877936583945209211824578941394860642895401474842454756358571425297290866115811478315969469383227365
seed2= 8298226438937024399394666985834505690086603252528046129859113649133899140071972599739560890259143306149555973037260633540419279012435819303313598457142205
seed3= 4040251672571936101829332270253013469888558365857467089318400495951696581101064249945316791749876515080521266364225982926900210409347049898895583868092005
m= 12089789856272284182347576409237995357111118927995723026914974156516478831606354451543318914508084516001638686608043717164669987097325696399241720793523921
# 求a
tmp1 = seed3 - seed2
tmp2 = seed2 - seed1
d = gmpy2.invert(tmp2,m)
a = tmp1*d % m

# 求b
b = (seed2-a*seed1)%m

# 得到flag
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)
# b'flag{aedc6711-27f6-49a1-8876-6f8c24b64760}'

题目4_未知a、b、m

  • 此题目，线性同余的三个常量都没有给出来，只给出了连续的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 uuid
from Crypto.Util.number import *
flag = b'flag{' + str(uuid.uuid4()).encode() + b'}'
global seed
seed = 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
"""

  • 接下来，推导一下该题的解密过程。该题的解密过程要先根据所给的连续的seed，通过一定的运算，将模数m求出，这样才能按照之前的题目思路去解题。

  • 这里运用了两个数学思想，一个是消元的数学思想，另一个是利用GCD公因素的思想去求模数m。

  • 先列出连续seed生成的5个式子

seedn+1≡a∗seedn+b mod (m)——①seedn+2≡a∗seedn+1+b mod (m)——②seedn+3≡a∗seedn+2+b mod (m)——③seedn+4≡a∗seedn+3+b mod (m)——④seedn+5≡a∗seedn+4+b mod (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}

  • 这时，我们需要消元，将b消去，所以我们就将②式-①式

seedn+2−seedn+1≡a∗(seedn+1−seedn) mod (m)\begin{array}{l} seed_{n+2} - seed_{n+1} \equiv a*(seed_{n+1}-seed_{n}) ~mod~(m) \end{array}

  • 这里为了表达简洁，就记

tn=seedn−seedn−1t_{n}=seed_n-seed_{n-1}

  • 所以②式-①式的结果就为

tn+2≡a∗tn+1 mod(m)t_{n+2}\equiv a*t_{n+1} ~mod(m)

  • 同理使用③式-②式，④式-③式，⑤式-④式得到

tn+3≡a∗tn+2≡a2tn+1 mod(m)tn+4≡a∗tn+3≡a3tn+1 mod(m)tn+5≡a∗tn+4≡a4tn+1 mod(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}

  • 所以我们可以得到

数列{tn}在模m的意义下成等比数列数列\{t_{n}\}在模m的意义下成等比数列

  • 所以利用等比数列的如下性质：

tn+m∗tn+k=tn+m+k22其中m+k要为偶数t_{n+m}*t_{n+k}=t^{2}_{n+\frac{m+k}{2}}\\ 其中m+k要为偶数

  • 则我们所构造出来的数列就满足：

tn+1∗tn+3≡tn+22 mod m从而推导出如下式子:ttn+1∗tn+3−tn+22≡0 mod m即m∣(ttn+1∗tn+3−tn+22)\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}

  • 通过这5个连续的种子，还可以构造出

tn+3∗tn+5≡tn+42 mod m从而得到:m∣(ttn+3∗tn+5−tn+42)\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}

  • 所以m就为这俩个式子的公因数。但是这时，假如我们使用gcd，则求的是其最大公因数。如果我们知道连续的种子数足够多的话，我们根据如下最大公因数的性质，就可以得到使用gcd的计算的结果很可能就是m。定理如下：

设a1,a2,...,an是不全为零的整数(可以假定它们都是正整数)，且(a1,a2)=d2,  (d2,a3)=d3  ,...,  (dn−2,an−1)=dn−1,(dn−1,an)=dn,则(a1,a2,...,an)=dn\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}

  • 但是我们这题会出现情况就是，连续的种子数知道的不够多，所以我们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 libnum
import gmpy2
from 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
b = (seed2-a*seed1)%k

# 得到flag
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进阶

题目1_未知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
32
33
34
35
from Crypto.Util.number import *

flag = b'NSSCTF{******}'

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed


lcg = LCG(bytes_to_long(flag), getPrime(255), getPrime(255), getPrime(256))

for i in range(getPrime(16)):
    lcg.generate()

print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())

'''
25445927935559969212648839062255651208014967526951331344342413906051118248013
81572970970116732975667604095930675262596098540738447440566868976253289440293
6956793925625110803779114150160476498676179542815207353218944386232051429289
88042506866508011592456777776490262927213783361334741921985316105965255450508
5652832125321707726481846809536180176877263519327268361130605456255558285092
'''

题目2_

  • 题目附件如下：
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
from Crypto.Util.number import *

flag = b'NSSCTF{******}'

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数
        self.flag = False

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        res = self.seed

        if self.flag:
            self.seed = (self.a * self.seed + self.b) % self.m
            res ^= self.seed
            self.flag = False
        else:
            self.flag = True

        return res


lcg = LCG(getPrime(255), getPrime(255), getPrime(255), getPrime(256))

c = []

for i in flag:
    c.append(lcg.generate() ^ i)
print(c)
print(lcg.m)

'''
[81584814741951826167713561762884044749048079878360104563221563015822544621540, 93774760261034631093081035207221372813019987098149361262601038324099824472054, 53112192781012087485274553474853632087816801546442125719635637229018761488068, 2924887129824568911354849666428337550752599339091846591306018510128364566374, 21489990371365635422785076328770373828885757507356970523345619197796699087823, 45879660646340087141208055037066375147112612144063751742878749538204227647223, 68489396663324980653667192480812664021869948970659960358303067756448465248962, 106889067933287464289046552070470006133240972888450185109202715048686699770828, 45880917337468560299586085034530981103079386360947740224437019696010705713504, 44264427891073836008413354425617411470794292209211384045023099147459280509219, 24230854692675475429275139738088072605035575993176371386080324243155457150129, 8324829808769566925849341513418987623474730556806514831163330951245904438885, 13973295373237298763688022823721063100979589794182834257587248359004917441233, 40946970689568765965479545541224654394849339592509835480100207197078299041359, 41840081504865349688826985386071119017476641799355114557538740232932639805078, 20173660813342267765549269084351072606374939924324411963087931476551280937102, 33606081253499380984005089985487426429461377845068803275630456930310532986647, 21863306888078087145487841917128593612722746009415567682629070350617384468865, 37705360427047642228657480542621387728505622206223322417535025830856191360682, 76394681592345473096361076203950244792678301231422301484911180053914754005660, 14445142875816535158206035170377032683179793846233008705044594781585126076422, 76399214426521271006629720299525001174165796205749509219669267796220760134668, 48963361037454561463427264514426072688886329876142403917863459848710167638299, 109755604120091903232536460005725058368768352544336587465785487037503069265532, 17629553207776828354200662140051287891918116980656890326744743673721478286748, 64351418114534266602263136861745778649986755405007304878601484056610206992412, 1747194514208114750564282571686979051305610098513675807068241335365552682058, 56440847349017714736424452565973705850353327138481306660630101075958036251012, 18938739898623474715723504727391335128374527047687506411988651179137118171744, 34278503747994897302186149009581131251220326132850950491516438997495387264420, 72969803022057770880126275760677059716202452292880774447222892410118789218019, 19417982285559688444222393534193336662626856272322246741671289881637819984704, 38932105919523769034923643449893605497694818272441279941830436762371582468828, 24487288126435161549395310046903919643631441162265499768468716075450020699817, 77947965534521507739806158990664078948320830860457514407123697810624486050992, 93592878110302845089477843503011449712615737528118407775734483884221947105328, 32343810136347248011294525044239112669043703094468690713290095304517010526441, 4266795492711034746844951873371293640112776112917444572367841878085540177393, 6300133545866819909237032926248008487617976145506739614351429803502021968529, 26352416759406189276920683254378055106857652225447447091766229194386845355426, 68287091881944595556206987513213507798534966894295689804598980654045436174566, 62270136231836751497834210500471298464586030814010376146250902975780514165809, 85625702418726025519718781583849588251758820858251438931591819496539009280818, 113920561374108800569700231300461418282579193845321015637813953548023720736907]
85862744900431564568351211721208164015422102334384451423751646954931287835189
'''

LCG变种

题目1—x=a(x-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
32
33
34
from Crypto.Util.number import *

flag = b'NSSCTF{******}'

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数

    def generate(self):
        self.seed = self.a * (self.seed - self.b) % self.m
        return self.seed


lcg = LCG(bytes_to_long(flag), getPrime(256), getPrime(256), getPrime(256))

for i in range(getPrime(16)):
    lcg.generate()

print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())

'''
57648351648792284446777383544515312078150027665462203747924668509833442797796
90378879763416486117626477831653213918315023665514305359005153448529276829825
21826576702665114807208181233864324586557058567478767825970403161758214940301
47594460970742467761038407996122637655856234121180714918606854365482948918701
11871076497267630136796123094001159466754095580273018347962555675375123133730
'''

LCG综合运用

  • LCG的运用比较多，因为很多加密都需要用到随机数发生器。这里给出几个要用到的地方：
    • RSA加密中随机生成的俩个大素数需要用到随机数生成器，生成随机数并判断是否为素数。
    • DSA、ECDSA等数字签名需要随机数来生成k。
    • 对称加密需要使用随机数生成器来生成密钥。

LCG生成素数

  • LCG还可以和RSA综合起来，例如利用LCG生成素数之类的。

题目1_LCG生成RSA素数