在密码学中，流密码（英语：Stream cipher），又译为流加密、资料流加密，是一种对称加密算法，加密和解密双方使用相同伪随机加密数据流（pseudo-random stream）作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流。实践中数据通常是一个位（bit）并用异或（xor）操作加密。
伪随机密钥流（keystream）由一个随机的种子（seed）通过算法（称为：PRG，pseudo-random generator）得到，$k$ 作为种子，则 $G(k)$ 作为实际使用的密钥进行加密解密工作。为了保证流加密的安全性，PRG必须是不可预测的。该算法解决了对称加密完善保密性（perfect secrecy）的实际操作困难，由于完善保密性要求密钥长度不短于明文长度，故而实际操作存在困难，改由较短数据流通过特定算法得到密钥流。
RC4
在密码学中，RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，因此也属于对称加密算法。RC4是有线等效加密（WEP）中采用的加密算法，也曾经是TLS可采用的算法之一。
由美国密码学家罗纳德·李维斯特（Ronald Rivest）在1987年设计的。由于RC4算法存在弱点，2015年2月所发布的 RFC 7465 规定禁止在TLS中使用RC4加密算法。
RC4由伪随机数生成器和异或运算组成。RC4的密钥长度可变，范围是[1,255]。RC4一个字节一个字节地加解密。给定一个密钥，伪随机数生成器接受密钥并产生一个S盒。S盒用来加密数据，而且在加密过程中S盒会变化。
由于异或运算的对合性，RC4加密解密使用同一套算法。
算法
KSA
初始化长度为256的S盒。第一个for循环将0到255的互不重复的元素装入S盒。第二个for循环根据密钥打乱S盒。
1 | for i from 0 to 255 |
PRGA
下面i,j是两个指针。每收到一个字节，就进行while循环。通过一定的算法（(a),(b)）定位S盒中的一个元素，并与输入字节异或，得到k。循环中还改变了S盒（(c)）。如果输入的是明文，输出的就是密文；如果输入的是密文，输出的就是明文。
1 | i := 0 |
此算法保证每256次循环中S盒的每个元素至少被交换过一次。
1 | N = 256 |
线性同余生成器 / 线性同余方法（LCG）
线性同余方法（LCG）是个产生伪随机数的方法。
它是根据递归公式产生：
$ N_{k+1} = (A\times N_{k}+B){\pmod {M}} $
其中 $A,B,M$ 是产生器设定的常数。
LCG的周期最大为 $M$，但大部分情况都会少于 $M$。要令LCG达到最大周期，应符合以下条件：
$B,M$ 互质；
$M$ 的所有质因数都能整除 $A-1$；
若 $M$ 是4的倍数，$A-1$ 也是；
$A,B,N_{0}$ 都比 $M$ 小；
$A,B$ 是正整数。
1 | from functools import reduce |
多次一密（Many Time Pad Attack）
用同一个密钥去加密多条明文，当密文条数较多时就很容易被攻击，例如Many Time Pad。
这个攻击的原理是 $c_1⊕c_2 = m_1⊕m_2$，而通过 $m_1⊕m_2$ 可以分析出 $m_1⊕m_2$，因此 $m_1⊕m_2$ 不再安全。
1 | #脚本1 |
1 | #脚本2 |
交互猜：
1 | from functools import reduce |
TEA / XTEA / XXTEA
TEA
微型加密算法（
Tiny Encryption Algorithm，TEA）是一种易于描述和执行的块密码，通常只需要很少的代码就可实现。TEA操作处理在两个32位无符号整型上（可能源于一个64位数据），并且使用一个128位的密钥。设计者是Roger Needham和David Wheeler。加密过程：
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
48from Crypto.Util.number import *
def encrypt(v, k):
v0 = v[0]
v1 = v[1]
x = 0
delta = 0x9E3779B9
k0 = k[0]
k1 = k[1]
k2 = k[2]
k3 = k[3]
for i in range(32):
x += delta
x = x & 0xFFFFFFFF
v0 += ((v1 << 4) + k0) ^ (v1 + x) ^ ((v1 >> 5) + k1)
v0 = v0 & 0xFFFFFFFF
v1 += ((v0 << 4) + k2) ^ (v0 + x) ^ ((v0 >> 5) + k3)
v1 = v1 & 0xFFFFFFFF
v[0] = v0
v[1] = v1
return v
def decrypt(v, k):
v0 = v[0]
v1 = v[1]
x = 0x9E3779B9 * 32
delta = 0x9E3779B9
k0 = k[0]
k1 = k[1]
k2 = k[2]
k3 = k[3]
for i in range(32):
v1 -= ((v0 << 4) + k2) ^ (v0 + x) ^ ((v0 >> 5) + k3)
v1 = v1 & 0xFFFFFFFF
v0 -= ((v1 << 4) + k0) ^ (v1 + x) ^ ((v1 >> 5) + k1)
v0 = v0 & 0xFFFFFFFF
x -= delta
x = x & 0xFFFFFFFF
v[0] = v0
v[1] = v1
return v
plain = [1, 2]
key = [2, 2, 3, 4]
encrypted = encrypt(plain, key)
print(encrypted)
decrypted = decrypt(encrypted, key)
print(decrypted)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//C版，带符号位移(unsigned int -→ int)
//加密函数
void encrypt (int* v, int* k) {
int v0=v[0], v1=v[1], sum=0, i; /* set up */
int delta=0x9e3779b9; /* a key schedule constant */
int k0=k[0], k1=k[1], k2=k[2], k3=k[3]; /* cache key */
for (i=0; i < 32; i++) { /* basic cycle start */
sum += delta;
v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
} /* end cycle */
v[0]=v0; v[1]=v1;
}
//解密函数
void decrypt (int* v, int* k) {
int v0=v[0], v1=v[1], sum=0x9e3779b9*32, i; /* set up */
int delta=0x9e3779b9; /* a key schedule constant */
int k0=k[0], k1=k[1], k2=k[2], k3=k[3]; /* cache key */
for (i=0; i<32; i++) { /* basic cycle start */
v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
sum -= delta;
} /* end cycle */
v[0]=v0; v[1]=v1;
}
int main()
{
int v[14656]={0},k[4]={0x67616C66, 0x6B61667B, 0x6C665F65, 0x7D216761};
FILE *p1 = fopen("./tea.png.out", "rb");
fread(&v, 4, 14656, p1);
fclose(p1);
for(int i=0;i<14656;i+=2){
decrypt(&v[i], k);
}
FILE *p2 = fopen("./tea.png", "wb");
fwrite(&v, 4, 14656, p2);
fclose(p2);
return 0;
}
XTEA
XTEA是TEA的升级版，增加了更多的密钥表，移位和异或操作等等。加密过程：
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
40from Crypto.Util.number import *
def encrypt(v, k):
v0 = v[0]
v1 = v[1]
x = 0
delta = 0x9E3779B9
for i in range(32):
v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (x + k[x & 3])
v0 = v0 & 0xFFFFFFFF
x += delta
x = x & 0xFFFFFFFF
v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (x + k[(x >> 11) & 3])
v1 = v1 & 0xFFFFFFFF
v[0] = v0
v[1] = v1
return v
def decrypt(v, k):
v0 = v[0]
v1 = v[1]
delta = 0x9E3779B9
x = delta * 32
for i in range(32):
v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (x + k[(x >> 11) & 3])
v1 = v1 & 0xFFFFFFFF
x -= delta
x = x & 0xFFFFFFFF
v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (x + k[x & 3])
v0 = v0 & 0xFFFFFFFF
v[0] = v0
v[1] = v1
return v
plain = [1, 2]
key = [2, 2, 3, 4]
encrypted = encrypt(plain, key)
print(encrypted)
decrypted = decrypt(encrypted, key)
print(decrypted)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//C版，带符号
int map[2] = {0xB5ABA743, 0x4C5B3EE0};
void decode(int* v) {
int sum = 0;
for(int i=0; i<32; ++i)
sum += 0x9E3779B9;
int key[] = {1, 2};
for(int j=0; j<32; ++j) {
v[1] -= (((v[0] << 4) ^ (v[0] >> 5)) + v[0]) ^ (sum + key[sum & 3]);
v[0] -= (((v[1] << 4) ^ (v[1] >> 5)) + v[1]) ^ (sum + key[sum & 3]);
sum -= 0x9E3779B9;
}
}
int main() {
decode(map);
for(int i=0; i<2; ++i)
printf("%d\n", map[i]);
return 0;
}
XXTEA
XXTEA，又称Corrected Block TEA，是XTEA的升级版。加密过程：
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
49from Crypto.Util.number import *
def shift(z, y, x, k, p, e):
return ((((z >> 5) ^ (y << 2)) + ((y >> 3) ^ (z << 4))) ^ ((x ^ y) + (k[(p & 3) ^ e] ^ z)))
def encrypt(v, k):
delta = 0x9E3779B9
n = len(v)
rounds = 6 + 52 // n
x = 0
z = v[n - 1]
for i in range(rounds):
x = (x + delta) & 0xFFFFFFFF
e = (x >> 2) & 3
for p in range(n - 1):
y = v[p + 1]
v[p] = (v[p] + shift(z, y, x, k, p, e)) & 0xFFFFFFFF
z = v[p]
p += 1
y = v[0]
v[n - 1] = (v[n - 1] + shift(z, y, x, k, p, e)) & 0xFFFFFFFF
z = v[n - 1]
return v
def decrypt(v, k):
delta = 0x9E3779B9
n = len(v)
rounds = 6 + 52 // n
x = (rounds * delta) & 0xFFFFFFFF
y = v[0]
for i in range(rounds):
e = (x >> 2) & 3
for p in range(n - 1, 0, -1):
z = v[p - 1]
v[p] = (v[p] - shift(z, y, x, k, p, e)) & 0xFFFFFFFF
y = v[p]
p -= 1
z = v[n - 1]
v[0] = (v[0] - shift(z, y, x, k, p, e)) & 0xFFFFFFFF
y = v[0]
x = (x - delta) & 0xFFFFFFFF
return v
plain = [1, 2]
key = [2, 2, 3, 4]
encrypted = encrypt(plain, key)
print(encrypted)
decrypted = decrypt(encrypted, key)
print(decrypted)
LFSR
线性反馈移位寄存器（Linear feedback shift register，LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。线性反馈移位寄存器(LFSR)归属于移位寄存器(FSR)，除此之外还有非线性移位寄存器（NFSR）。
$\text{GF}(2)$ 上一个 $n$ 级反馈移位寄存器由 $n$ 个二元存储器与一个反馈函数 $f(a_1,a_2,\cdots,a_n)$ 组成：
移位寄存器三要素：
初始状态：由用户确定
反馈函数：$f(a_1,a_2,\cdots,a_n)$ 是 $n$ 元布尔函数，即函数的自变量和因变量只取0和1这两个可能值
输出序列
如果反馈函数是线性的，那么我们称其为线性反馈移位寄存器(LFSR)：
LFSR的输出序列 $\{a_n\}$ 满足：
$\begin{cases} a_{n+1} = c_1a_{n} \oplus c_2a_{n-1} \oplus\cdots\oplus c_na_1 \newline a_{n+2} = c_1a_{n+1} \oplus c_2a_{n} \oplus\cdots\oplus c_na_2 \newline \vdots \newline a_{n+i} = c_1a_{n+i-1} \oplus c_2a_{n+i-2} \oplus\cdots\oplus c_na_i \end{cases}$
对于 $n$ 级线性反馈移位寄存器，最长周期为 $2^n-1$（排除全0），达到最长周期的序列一般称为 $m$ 序列。
1 | #Example |
Salsa20
Salsa20是一种流式对称加密算法，类似于Chacha20，算法性能相比AES能够快3倍以上。
Salsa20算法通过将32 Byte的key和8 Byte的随机数nonce扩展为 $2^{70}$ Byte的随机字节流，通过随机字节流和异或操作实现加解密，因此Salsa20算法中随机字节流的生成为关键所在。
Salsa20算法生成随机字节流时，一次生成一个64字节的block，每一个block是通过将key、nonce和block number以及部分常量组成64字节的input，通过核函数，输出64字节的output。最终多个block组成长度为 $2^{70}$ 的随机字节流，在生成过程中，每个block相互独立。
输入
64字节的input分为16个word，每个word为4字节，由以下8部分组成：
4字节的常量0x61707865
key的前16字节
4字节的常量0x3320646e
8字节的随机数nonce
8字节的block-counter
4字节的常量0x79622d32
key的剩余16字节
4字节的常量0x6b206574最终64字节（16 words）组成一个4*4的矩阵。例如，对于key (1, 2, 3, 4, 5, . . . , 32)，nonce
(3, 1, 4, 1, 5, 9, 2, 6)，以及 block 7的初始矩阵为：1
2
3
40x61707865, 0x04030201, 0x08070605, 0x0c0b0a09
0x100f0e0d, 0x3320646e, 0x01040103, 0x06020905
0x00000007, 0x00000000, 0x79622d32, 0x14131211
0x18171615, 0x1c1b1a19, 0x201f1e1d, 0x6b206574核函数
Salsa20算法核函数将64字节的输入以矩阵形式作为参数，输出64字节的运算结果。
Salsa20核函数运算主要包括的运算如下，其中a和b皆为32bit（4 Byte）的数据：
- 32 bit模加：
(a + b) mod 2^32 - 异或：
a XOR b - 左移：
a <<< b，其中b为常量，在Salsa20算法中左移的值为7、9、13、18
针对输入矩阵中的每个word，执行20轮的如下操作：
b ⊕= (a ⊞ c) <<< k，其中⊕为异或，⊞模加，<<<为左移。经过20轮计算后，将输出的矩阵核原始矩阵相加，得到输出。
Salsa20核函数具体实现如下：
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
void salsa20_word_specification(uint32 out[16],uint32 in[16])
{
int i;
uint32 x[16];
for (i = 0;i < 16;++i) x[i] = in[i];
for (i = 20;i > 0;i -= 2) { // 20轮计算
x[ 4] ^= R(x[ 0]+x[12], 7); x[ 8] ^= R(x[ 4]+x[ 0], 9);
x[12] ^= R(x[ 8]+x[ 4],13); x[ 0] ^= R(x[12]+x[ 8],18);
x[ 9] ^= R(x[ 5]+x[ 1], 7); x[13] ^= R(x[ 9]+x[ 5], 9);
x[ 1] ^= R(x[13]+x[ 9],13); x[ 5] ^= R(x[ 1]+x[13],18);
x[14] ^= R(x[10]+x[ 6], 7); x[ 2] ^= R(x[14]+x[10], 9);
x[ 6] ^= R(x[ 2]+x[14],13); x[10] ^= R(x[ 6]+x[ 2],18);
x[ 3] ^= R(x[15]+x[11], 7); x[ 7] ^= R(x[ 3]+x[15], 9);
x[11] ^= R(x[ 7]+x[ 3],13); x[15] ^= R(x[11]+x[ 7],18);
x[ 1] ^= R(x[ 0]+x[ 3], 7); x[ 2] ^= R(x[ 1]+x[ 0], 9);
x[ 3] ^= R(x[ 2]+x[ 1],13); x[ 0] ^= R(x[ 3]+x[ 2],18);
x[ 6] ^= R(x[ 5]+x[ 4], 7); x[ 7] ^= R(x[ 6]+x[ 5], 9);
x[ 4] ^= R(x[ 7]+x[ 6],13); x[ 5] ^= R(x[ 4]+x[ 7],18);
x[11] ^= R(x[10]+x[ 9], 7); x[ 8] ^= R(x[11]+x[10], 9);
x[ 9] ^= R(x[ 8]+x[11],13); x[10] ^= R(x[ 9]+x[ 8],18);
x[12] ^= R(x[15]+x[14], 7); x[13] ^= R(x[12]+x[15], 9);
x[14] ^= R(x[13]+x[12],13); x[15] ^= R(x[14]+x[13],18);
}
for (i = 0;i < 16;++i) out[i] = x[i] + in[i]; // 输入矩阵经过20轮的计算结果和原始矩阵相加得到最终输出
}- 32 bit模加：
输出
每一次核函数运算，都能够通过key、nonce、block-counter生成64字节的输出block，经过多次输入和核函数运算，将每一次的生成结果拼接最终组成长度为 $2^{70}$ 的字节流。
1 | # Encrypt |
Chacha20
Chacha20是ChaCha系列流密码，作为Salsa密码的改良版，具有更强的抵抗密码分析攻击的特性，“20”表示该算法有20轮的加密计算。
由于是流密码，故以字节为单位进行加密，安全性的关键体现在密钥流生成的过程，即所依赖的伪随机数生成器（PRNG）的强度，加密过程即是将密钥流与明文逐字节异或得到密文，反之，解密是将密文再与密钥流做一次异或运算得到明文。
1 | # Encrypt |
Rabbit
Rabbit 是一种高速流密码，于 2003 年在 FSE 研讨会上首次提出。Rabbit 使用一个 128 位密钥和一个 64 位初始化向量。该加密算法的核心组件是一个位流生成器，该流生成器每次迭代都会加密 128 个消息位。Rabbit 也是一种对称加密算法。
不加盐版本：https://asecuritysite.com/encryption/rabbit2
1 | import collections |
Xorshift
Xorshift 随机数生成器是 George Marsaglia 发明的一类伪随机数生成器。它们通过和自己逻辑移位后的数进行异或操作来生成序列中的下一个数。这在现代计算机体系结构非常快。它们是线性反馈移位寄存器的一个子类，其简单的实现使它们速度更快且使用更少的空间。然而，必须仔细选择合适参数以达到长周期。
问题：在循环移位异或加密中，我们已知变换后的密文 y ，以及多个偏移的密钥 ks ，要求出原文 x。
定理：在长度为 2 的方幂的二进制串中，循环移位异或变换中，如果有奇数项，那么这个变换是可逆的，否则就是不可逆的。
例：
加密：$y=x \oplus (x \ggg p) \oplus (x \ggg q)$
解密：$x=x \oplus (y \ggg p) \oplus (y \ggg q)$
1 | # y = x ^ (x>>>p) ^ (x>>>q) |
MT19937
梅森旋转算法（Mersenne Twister Algorithm，简称 MT）是为了解决过去伪随机数发生器（Pseudo-Random Number Generator，简称 PRNG）产生的伪随机数质量不高而提出的新算法。该算法在 1997 年提出。
Mersenne Twister 最常见的实现方式使用 624 个 32 bits 的初始状态。这些整数按顺序分发（分发前对每个初始数进行转换），分发完后对该状态应用某种算法以获取下一组 624 个整数。以及可以通过得到连续的 624 个输出，还原出原来的 624 个 states，再根据原算法推算出接下来每个 state 下一次的 value，从而算出接下来的输出。
32 bits实现：
1 | def _int32(x): |
分为三段：
导入seed，初始化伪随机数发生器
每次生成
mt[i]是由前一项进行运算得到的，第一项mt[0] == seed，总生成 624 项整数的列表（以及其他参数）作为state。中间的元组类型有 625 项，前 624 项即是之前提到的整数，而第 625 项（此时等于 624）是该
state此时对应的第几个整数，也就是说，再下一次执行extract_number()函数时的state里面应该调用第几个整数。进行
twist()函数注意是在
extract_number()函数内可能会执行twist()，进行twist()函数需要满足的条件，也就是每 624 项作为一轮直接执行extract_number()函数里后面的位运算以及抽取随机数的操作，而下一轮 624 项需要进行twist()函数替换state。这样一来，就意味着每 624 项的列表作为一次
state，当输出完 624 个伪随机数之后，需要通过twist()函数变换state，变换完成之后再进行输出伪随机数，以此类推。设新生成的
state列表为mt'，而原来的state列表为mt（注意在MT19937原代码中并没有赋值新的列表，只是不断地更新原来地列表）在
twist()函数中，每生成的新的一个state列表中的mt'[i]，只和在原来的state中的mt[i+1]以及mt[i+397]有关。而当
i+1或者i+397大于 624 时，也就是超过了一个state列表总长度时，那么mt[i+1]或者mt[i+397]实际上是mt'[(i+1) % 624]或者mt'[(i+397) % 624]。继续
extract_number()函数在判断执行
twist()函数与否之后，从目前的state列表中单独抽取每个数进行运算，运算结果即是输出的随机数。也就是说，state列表里的每个数都单独的进行与常量的位运算。
random模块
getrandbits 函数在收到超出32比特的参数，会把已生成的state放在低位，高位放置新生成的state。
攻击
求后随机数（逆 extract_number）
假设已知624个从开始连续输出的随机数，需要预测之后每一个输出的随机数，只需要逆转输出的随机数组成 state列表，然后设置伪随机数发生器的 state 即可，然后输出需要预测的随机数。
Mersenne Twister Predictor
https://github.com/kmyk/mersenne-twister-predictor
1
2
3
4
5
6
7
8
9import random
from mt19937predictor import MT19937Predictor
predictor = MT19937Predictor()
for _ in range(624):
x = random.getrandbits(32)
predictor.setrandbits(x, 32)
assert random.getrandbits(32) == predictor.getrandbits(32)randcrack
https://github.com/tna0y/Python-random-module-cracker
1
2
3
4
5
6
7
8
9
10
11
12
13import random, time
from randcrack import RandCrack
random.seed(time.time())
rc = RandCrack()
for i in range(624):
rc.submit(random.getrandbits(32))
# Could be filled with random.randint(0,4294967294) or random.randrange(0,4294967294)
print("Random result: {}\nCracker result: {}"
.format(random.randrange(0, 4294967295), rc.predict_randrange(0, 4294967295)))原始
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# 脚本1
# right shift inverse
def inverse_right(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp
# left shift inverse
def inverse_left(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp
def recover(y):
y = inverse_right(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right(y,11)
return y&0xffffffff
random_number = []
state = [recover(i) for i in random_number]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# 脚本2
from random import Random
def invert_right(m,l,val=''):
length = 32
mx = 0xffffffff
if val == '':
val = mx
i,res = 0,0
while i*l<length:
mask = (mx<<(length-l)&mx)>>i*l
tmp = m & mask
m = m^tmp>>l&val
res += tmp
i += 1
return res
def invert_left(m,l,val):
length = 32
mx = 0xffffffff
i,res = 0,0
while i*l < length:
mask = (mx>>(length-l)&mx)<<i*l
tmp = m & mask
m ^= tmp<<l&val
res |= tmp
i += 1
return res
def invert_temper(m):
m = invert_right(m,18)
m = invert_left(m,15,4022730752)
m = invert_left(m,7,2636928640)
m = invert_right(m,11)
return m
def clone_mt(record):
state = [invert_temper(i) for i in record]
gen = Random()
gen.setstate((3,tuple(state+[0]),None))
return gen
prng = []
g = clone_mt(prng[:624])
for i in range(700):
g.getrandbits(32)
key = g.getrandbits(32)
print(key)
求前随机数（逆 twist()）
Extend MT19937 Predictor
https://github.com/NonupleBroken/ExtendMT19937Predictor
1
2
3
4
5
6
7
8
9
10
11
12
13
14import random
from extend_mt19937_predictor import ExtendMT19937Predictor
numbers = [random.getrandbits(64) for _ in range(1024)]
predictor = ExtendMT19937Predictor()
for _ in range(78):
predictor.setrandbits(random.getrandbits(256), 256)
_ = [predictor.backtrack_getrandbits(256) for _ in range(78)]
for x in numbers[::-1]:
assert x == predictor.backtrack_getrandbits(64)完整
state假设已知该
state中的 624 个整数，想要知道之前输出的随机数，需要逆转twist()得到上一个state或者更之前的state。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
28def backtrace(cur):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
state = cur
for i in range(623,-1,-1):
tmp = state[i]^state[(i+397)%624]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
# recover highest bit
res = tmp&high
# recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
tmp = state[i-1]^state[(i+396)%624]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res |= (tmp)&low
state[i] = res
return state部分
state假设已知 1000 个从开始第 5 个输出的连续随机数，求前 4 个输出的随机数的大小（参考V&N 2020 - backtrace）。
这 1000 个随机数可以分成两段（对应不同的
state生成的随机数），也就是前 620 个数为第一个state生成的，后 380 个数为第二个state生成的，需要求第一个state生成的前四个随机数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24def backtrace(cur):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
state = cur
for i in range(3,-1,-1):
tmp = state[i+624]^state[i+397] # mt'[i] == mt [i+624]
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res = tmp&high
tmp = state[i-1+624]^state[i+396]
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res |= (tmp)&low
state[i] = res
return state1
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84# 脚本
from random import Random
# right shift inverse
def inverse_right(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp>>shift & mask
return tmp
# left shift inverse
def inverse_left(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift & mask
return tmp
def backtrace(cur):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
state = cur
for i in range(5,-1,-1):
tmp = state[i+624]^state[i+397]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
# recover highest bit
res = tmp&high
# recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
tmp = state[i-1+624]^state[i+396]
# recover Y,tmp = Y
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res |= (tmp)&low
state[i] = res
return state
def recover_state(out):
state = []
for i in out:
i = inverse_right(i,18)
i = inverse_left_values(i,15,0xefc60000)
i = inverse_left_values(i,7,0x9d2c5680)
i = inverse_right(i,11)
state.append(i)
return state
c = []
partS = recover_state(c)
state = backtrace([0]*6+partS)[:624]
# print(state)
# state[0]不准确，因state[0]==seed，单推
# inv = invert(1812433253,1<<32)
# seed = inverse_right(((state[1]-1)*inv)%(1<<32),30)
# state[0] = int(seed)
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
flag = "flag{" + ''.join(str(prng.getrandbits(32)) for _ in range(4)) + "}"
print(flag)
求seed（逆 __init__）
根据第一次的 state，逆向 seed。
1 | from gmpy2 import invert |
