在密码学中，流密码（英语：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
2
3
4
5
6
7
8for i from 0 to 255
S[i] := i
endfor
j := 0
for( i=0 ; i<256 ; i++)
j := (j + S[i] + key[i mod keylength]) % 256
swap values of S[i] and S[j]
endforPRGA
下面i,j是两个指针。每收到一个字节，就进行while循环。通过一定的算法（(a),(b)）定位S盒中的一个元素，并与输入字节异或，得到k。循环中还改变了S盒（(c)）。如果输入的是明文，输出的就是密文；如果输入的是密文，输出的就是明文。
1
2
3
4
5
6
7
8
9i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256 //a
j := (j + S[i]) mod 256 //b
swap values of S[i] and S[j] //c
k := inputByte ^ S[(S[i] + S[j]) % 256]
output K
endwhile此算法保证每256次循环中S盒的每个元素至少被交换过一次。
1 |
#python2 |
1 |
#python3 |
线性同余生成器 / 线性同余方法（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 |
#!/usr/bin/python |
TEA / XTEA / XXTEA
-
TEA
微型加密算法（
Tiny Encryption Algorithm，TEA）是一种易于描述和执行的块密码，通常只需要很少的代码就可实现。TEA操作处理在两个32位无符号整型上（可能源于一个64位数据），并且使用一个128位的密钥。设计者是Roger Needham和David Wheeler。加密过程：
![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
40
41
42
43
44
45
46#!/usr/bin/env python
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
if __name__ == '__main__':
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的升级版，增加了更多的密钥表，移位和异或操作等等。加密过程：
![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#!/usr/bin/env python
def encrypt(rounds, v, k):
v0 = v[0]
v1 = v[1]
x = 0
delta = 0x9E3779B9
for i in range(rounds):
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(rounds, v, k):
v0 = v[0]
v1 = v[1]
delta = 0x9E3779B9
x = delta * rounds
for i in range(rounds):
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
if __name__ == '__main__':
plain = [1, 2]
key = [2, 2, 3, 4]
rounds = 32
encrypted = encrypt(rounds, plain, key)
print(encrypted)
decrypted = decrypt(rounds, 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的升级版。加密过程：
![XXTEA]()
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#!/usr/bin/env python
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
v= (v
+ shift(z, y, x, k, p, e)) & 0xFFFFFFFF
z = v
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
v= (v
- shift(z, y, x, k, p, e)) & 0xFFFFFFFF
y = v
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
if __name__ == '__main__':
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$ 序列。
-
B-M 算法
（待补充）
-
参考
1 |
#Example |
SM4
SM4是一种分组密码算法，其分组长度为128位（即16字节，4字），密钥长度也为128位（即16字节，4字）。其加解密过程采用了32轮迭代机制（与DES、AES类似），每一轮需要一个轮密钥（与DES、AES类似）。
1 |
# Python |
1 |
// C |
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 |
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): |
-
攻击
-
预测后随机数（逆
extract_number）-
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
41
42
43
44
45
46
47
48
49
50# -*- coding: utf-8 -*-
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()）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
-
FROM:Lazzaro Author:Lazzaro
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论