PRNG

First Post:

Last Update:

随机数生成

PRNG又叫伪随机数生成器，随机数生成一般有两个要求，一个是随机性，一个是不可预测性。一般我们有两种策略进行随机数生成，一种是PRNG(伪随机数生成器)，一种就是TRNG(真随机数生成器)。

TRNG

使用某种不确定的物理源生成非确定的随机位。比如：物理噪声，键盘打击，鼠标移动，音频，视频输入等。这些物理过程本质上不可预测，因此TRNG生成的数字序列是真正的随机数。

TRNG通常有四个步骤：

1.物理随机性源采样

2.噪声处理

3.熵池收集和混合

4.随机数生成

PRNG

PRNG就是有一个确定的算法来实现随机数的生成,这边原理就不讲那么公式化了，直接上题来看看:
公式:
QQ20250202-153336-1.png
代码实现:

1
2
3
4
5
seed=*****     #初始随机数种子
Randrom_Num=[]  #生成的所有随机数
for i in range(0,n):   #表示生成n个随机数
     seed = (seed * a + b) % n   #这个新的seed计算后就是生成的随机数
     Randr_Num.append(seed)

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 from Crypto.Util.number import bytes_to_long, getPrime
from flag import flag
a = getPrime(400)
b = getPrime(400)
n = getPrime(400)
flag = bytes_to_long(flag)
seed = flag
result = []
for i in range(3):
    seed = (seed * a + b) % n
    result.append(seed)
print(result)
print(n)
"""
[1633086272556604467630727869278140040711140555507257984778706962389364338237377391272504059109316040445365656669071569236, 1206389051656797336925675372412697477889689141174380289961348552709531162180853687116202278892215286522581909284859193494, 664238088423928246579566483655935746695807924062694495126404306361290788561253706421181510449476188038387172722467882193]
2482696698513566590184292572066254640333143735400366745928208268241117181592178071999744746850718587310205478604372055081
 
"""

解密过程:
想要解密要有三个连续生成的随机数和模数才行
三个随机数分别是lcd0,lcd1,lcd2
QQ20250202-153938.png
如果怕自己的a和c是错的可以代入第三个式子去试试,一般不会将flag当作lcd0输入，所以我们还需要解一元同余式来求flag.
求解一元同余式的方法：照着公式编程就行。下面找的是一次同余式的通解，但是在ctf比赛中实际上只有一个flag，所以只有一个解，因此(a,m)就是1，这样编程的时候公式可以简略好多。
QQ20250202-154935.png
解密jio本；

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes
 
n=2482696698513566590184292572066254640333143735400366745928208268241117181592178071999744746850718587310205478604372055081
result=[1633086272556604467630727869278140040711140555507257984778706962389364338237377391272504059109316040445365656669071569236, 1206389051656797336925675372412697477889689141174380289961348552709531162180853687116202278892215286522581909284859193494, 664238088423928246579566483655935746695807924062694495126404306361290788561253706421181510449476188038387172722467882193]
 
a=((result[2]-result[1])*gmpy2.invert(result[1]-result[0],n))%n
b=(result[1]-(a*result[0]))%n
 
#求解一元同余式得到flag
flag=(((result[0]-b))*gmpy2.invert(a,n)+n)%n
 
print(long_to_bytes(flag))
≡