流密码

在密码学中,流密码(英语: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
    8
    for 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]
    endfor

    PRGA

    下面i,j是两个指针。每收到一个字节,就进行while循环。通过一定的算法((a),(b))定位S盒中的一个元素,并与输入字节异或,得到k。循环中还改变了S盒((c))。如果输入的是明文,输出的就是密文;如果输入的是密文,输出的就是明文。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    i := 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
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
#python2
def KSA(key):
keylength = len(key)

S = range(256)

j = 0
for i in range(256):
j = (j + S[i] + key[i % keylength]) % 256
S[i], S[j] = S[j], S[i] # swap

return S

def PRGA(S):
i = 0
j = 0
while True:
i = (i + 1) % 256
j = (j + S[i]) % 256
S[i], S[j] = S[j], S[i] # swap

K = S[(S[i] + S[j]) % 256]
yield K

def RC4(key):
S = KSA(key)
return PRGA(S)


if __name__ == '__main__':
key = 'Key'
plaintext = 'Plaintext'

def convert_key(s):
return [ord(c) for c in s]
key = convert_key(key)

keystream = RC4(key)

import sys
for c in plaintext:
sys.stdout.write("%02X" % (ord(c) ^ keystream.next()))
print
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
#python3
N = 256
S = [0] * N
key = 'keykeykey'
Key = [0] * N

t = [220,71,127,110,154,216,96,119,244,176,140,84,176,170,38,35,2,66,142,186,144,140,171,134,36,110,248]

for i in range(N):
S[i] = i
Key[i] = ord(key[i % len(key)])

j = 0
for i in range(N):
j = (j + S[i] + Key[i]) % N
S[i], S[j] = S[j], S[i]

i = 0
j = 0
for k in range(len(t)):
i = (i + 1) % N
j = (j + S[i]) % N
S[i], S[j] = S[j], S[i]
t[k] ^= S[(S[i] + S[j]) % N]

print(t)
print(''.join(chr(k) for k in t))

线性同余生成器 / 线性同余方法(LCG)

线性同余方法(LCG)是个产生伪随机数的方法。

它是根据递归公式产生:

$ N_{k+1} = (A\times N_{k}+B){\pmod {M}} $
其中 $A,B,M$ 是产生器设定的常数。

LCG的周期最大为 $M$,但大部分情况都会少于 $M$。要令LCG达到最大周期,应符合以下条件:

  1. $B,M$ 互质;

  2. $M$ 的所有质因数都能整除 $A-1$;

  3. 若 $M$ 是4的倍数,$A-1$ 也是;

  4. $A,B,N_{0}$ 都比 $M$ 小;

  5. $A,B$ 是正整数。

参考:攻击线性同余生成器(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
30
31
32
33
34
35
36
37
38
39
from functools import reduce
from math import gcd
from Crypto.Util.number import *

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m

def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)

def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return crack_unknown_multiplier(states, modulus)

# N[i+1] = (A*N[i]+B) % M
# A,B,N均未知
sequence = []
modulus, multiplier, increment = crack_unknown_modulus(sequence)
print('A = '+str(multiplier))
print('B = '+str(increment))
print('N = '+str(modulus))

多次一密(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
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
#脚本1
import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
if ord('a') <= x and x <= ord('z'): return True
if ord('A') <= x and x <= ord('Z'): return True
return False


def infer(index, pos):
if msg[index, pos] != 0:
return
msg[index, pos] = ord(' ')
for x in range(len(c)):
if x != index:
msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

def know(index, pos, ch):
msg[index, pos] = ord(ch)
for x in range(len(c)):
if x != index:
msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)


dat = []

def getSpace():
for index, x in enumerate(c):
res = [xo.strxor(x, y) for y in c if x!=y]
f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
cnt = [f(pos) for pos in range(len(x))]
for pos in range(len(x)):
dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('Problem.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
infer(index, pos)

know(10, 21, 'y')
know(8, 14, 'n')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)
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
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
#脚本2
#!/usr/bin/python
## OTP - Recovering the private key from a set of messages that were encrypted w/ the same private key (Many time pad attack) - crypto100-many_time_secret @ alexctf 2017
# Original code by jwomers: https://github.com/Jwomers/many-time-pad-attack/blob/master/attack.py)

import string
import collections
import sets, sys

# 11 unknown ciphertexts (in hex format), all encrpyted with the same key
c1='daaa4b4e8c996dc786889cd63bc4df4d1e7dc6f3f0b7a0b61ad48811f6f7c9bfabd7083c53ba54'
c2='c5a342468c8c7a88999a9dd623c0cc4b0f7c829acaf8f3ac13c78300b3b1c7a3ef8e193840bb'
c3='dda342458c897a8285df879e3285ce511e7c8d9afff9b7ff15de8a16b394c7bdab920e7946a05e9941d8308e'
c4='d9b05b4cd5ce7c8f938bd39e24d0df191d7694dfeaf8bfbb56e28900e1b8dff1bb985c2d5aa154'
c5='d9aa4b00c88b7fc79d99d38223c08d54146b88d3f0f0f38c03df8d52f0bfc1bda3d7133712a55e9948c32c8a'
c6='c4b60e46c9827cc79e9698936bd1c55c5b6e87c8f0febdb856fe8052e4bfc9a5efbe5c3f57ad4b9944de34'
c7='d9aa5700da817f94d29e81936bc4c1555b7b94d5f5f2bdff37df8252ffbecfb9bbd7152a12bc4fc00ad7229090'
c8='c4e24645cd9c28939a86d3982ac8c819086989d1fbf9f39e18d5c601fbb6dab4ef9e12795bbc549959d9229090'
c9='d9aa4b598c80698a97df879e2ec08d5b1e7f89c8fbb7beba56f0c619fdb2c4bdef8313795fa149dc0ad4228f'
c10='cce25d48d98a6c8280df909926c0de19143983c8befab6ff21d99f52e4b2daa5ef83143647e854d60ad5269c87'
c11='d9aa4b598c85668885df9d993f85e419107783cdbee3bbba1391b11afcf7c3bfaa805c2d5aad42995ede2cdd82977244'
ciphers = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11]
# The target ciphertext we want to crack

# XORs two string
def strxor(a, b): # xor two strings (trims the longer input)
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b)])

def target_fix(target_cipher):
print '-------begin-------'

# To store the final key
final_key = [None]*150
# To store the positions we know are broken
known_key_positions = set()

# For each ciphertext
for current_index, ciphertext in enumerate(ciphers):
counter = collections.Counter()
# for each other ciphertext
for index, ciphertext2 in enumerate(ciphers):
if current_index != index: # don't xor a ciphertext with itself
for indexOfChar, char in enumerate(strxor(ciphertext.decode('hex'), ciphertext2.decode('hex'))): # Xor the two ciphertexts
# If a character in the xored result is a alphanumeric character, it means there was probably a space character in one of the plaintexts (we don't know which one)
if char in string.printable and char.isalpha(): counter[indexOfChar] += 1 # Increment the counter at this index
knownSpaceIndexes = []

# Loop through all positions where a space character was possible in the current_index cipher
for ind, val in counter.items():
# If a space was found at least 7 times at this index out of the 9 possible XORS, then the space character was likely from the current_index cipher!
if val >= 7: knownSpaceIndexes.append(ind)
#print knownSpaceIndexes # Shows all the positions where we now know the key!

# Now Xor the current_index with spaces, and at the knownSpaceIndexes positions we get the key back!
xor_with_spaces = strxor(ciphertext.decode('hex'),' '*150)
for index in knownSpaceIndexes:
# Store the key's value at the correct position
final_key[index] = xor_with_spaces[index].encode('hex')
# Record that we known the key at this position
known_key_positions.add(index)

# Construct a hex key from the currently known key, adding in '00' hex chars where we do not know (to make a complete hex string)
final_key_hex = ''.join([val if val is not None else '00' for val in final_key])
# Xor the currently known key with the target cipher
output = strxor(target_cipher.decode('hex'),final_key_hex.decode('hex'))

print "Fix this sentence:"
print ''.join([char if index in known_key_positions else '*' for index, char in enumerate(output)])+"\n"

# WAIT.. MANUAL STEP HERE
# This output are printing a * if that character is not known yet
# fix the missing characters like this: "Let*M**k*ow if *o{*a" = "cure, Let Me know if you a"
# if is too hard, change the target_cipher to another one and try again
# and we have our key to fix the entire text!

#sys.exit(0) #comment and continue if u got a good key

print '------end------'

for i in ciphers:
target_fix(i)

交互猜:

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
from functools import reduce

def xor(*args):
if len(args) == 2:
x, y = args
return bytes([a ^ b for a, b in zip(x, y)])
return reduce(xor, args)

ct = [
b"\xc1=\x01}\xe7\x1c\x94YRj\xb3\xa7K@\xde\x0c\x9a\xc9\x00\xb0ZB\r\x87\r\x8b\x8f\xffQ\xc7",
b"\xfc\x1d4^\xd0o\xb2GE|\x89\xe4^]\xcfE\x86\xdd\x1e\x8a\r@\x1c\x96r\x92\x87\xec\x19\xd4",
b"\xfa\x19!P\x82;\xa8G\x10\x7f\x80\xa5DP\xdeE\x94\xc8S\x9cHH\x1f\x8a!\x87\xc0\xe3\x1f\xcd",
]
key = xor(b"SECFEST{", ct[0])

while True:
pts = [xor(key, c) for c in ct]
for i, pt in enumerate(pts):
print(i, pt)
idx = int(input("Enter index: "))
if idx == -1:
break
c = input("Enter next char: ")[0]
key += bytes([ord(c) ^ ct[idx][len(key)]])
print("Current key:", key.hex())
print([xor(key, c) for c in ct])

TEA / XTEA / XXTEA

  • TEA

    微型加密算法(Tiny Encryption AlgorithmTEA)是一种易于描述和执行的块密码,通常只需要很少的代码就可实现。TEA 操作处理在两个 32 位无符号整型上(可能源于一个 64 位数据),并且使用一个 128 位的密钥。设计者是 Roger NeedhamDavid 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)
    #include <stdio.h>
    #include <stdint.h>

    //加密函数
    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

    XTEATEA 的升级版,增加了更多的密钥表,移位和异或操作等等。

    加密过程:

    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版,带符号
    #include<stdio.h>

    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[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
    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)$ 组成:

img

移位寄存器三要素:

  1. 初始状态:由用户确定

  2. 反馈函数:$f(a_1,a_2,\cdots,a_n)$ 是 $n$ 元布尔函数,即函数的自变量和因变量只取0和1这两个可能值

  3. 输出序列

如果反馈函数是线性的,那么我们称其为线性反馈移位寄存器(LFSR):

img

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
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
#Example
#coding=utf-8

from pwn import *
r=remote('182.92.108.71',30607)

c=[]
for i in range(10):
r.recvline()
r.sendlineafter('guess: ','0')
x=r.recvline()
if 'Right' in x:
c+=[0]
else:
xx=int(x.strip().split('is ')[1])
c+=[xx]

print(c)

class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1

def next(self):
nextdata = (self.init << 1) & self.lengthmask
i = self.init & self.mask & self.lengthmask
output = 0
while i != 0:
output ^= (i & 1)
i = i >> 1
nextdata ^= output
self.init = nextdata
return output

def random(self, nbit):
output = 0
for _ in range(nbit):
output <<= 1
output |= self.next()
return output


mask = 0b1011001010001010000100001000111011110101
N = 40
key = ''
for i in range(N // 4):
t = c[i]
for j in range(3, -1, -1):
key += str(t >> j & 1)
idx = 0
ans = ""
key = key[39] + key[:40]
print(key)
while idx < 40:
tmp = 0
for i in range(40):
if mask >> i & 1:
tmp ^= int(key[39 - i])
ans = str(tmp) + ans
idx += 1
key = key[39] + str(tmp) + key[1:39]
init = int(ans, 2)
print(init)


prng = lfsr(init, 0b1011001010001010000100001000111011110101, 40)


for i in range(10):
print(prng.random(4))

for i in range(90):
r.recvline()
r.sendlineafter('guess: ',str(prng.random(4)))
print(r.recvline())

print(r.recvall())

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
    4
    0x61707865, 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
    #define R(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
    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轮的计算结果和原始矩阵相加得到最终输出
    }
  • 输出

    每一次核函数运算,都能够通过key、nonce、block-counter生成64字节的输出block,经过多次输入和核函数运算,将每一次的生成结果拼接最终组成长度为 $2^{70}$ 的字节流。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Encrypt
from Crypto.Cipher import Salsa20
plaintext = b'Attack at dawn'
secret = b'*Thirty-two byte (256 bits) key*'
cipher = Salsa20.new(key=secret)
msg = cipher.nonce + cipher.encrypt(plaintext)

# Decrypt
from Crypto.Cipher import Salsa20
secret = b'*Thirty-two byte (256 bits) key*'
msg_nonce = msg[:8]
ciphertext = msg[8:]
cipher = Salsa20.new(key=secret, nonce=msg_nonce)
plaintext = cipher.decrypt(ciphertext)

Chacha20

Chacha20是ChaCha系列流密码,作为Salsa密码的改良版,具有更强的抵抗密码分析攻击的特性,“20”表示该算法有20轮的加密计算。

由于是流密码,故以字节为单位进行加密,安全性的关键体现在密钥流生成的过程,即所依赖的伪随机数生成器(PRNG)的强度,加密过程即是将密钥流与明文逐字节异或得到密文,反之,解密是将密文再与密钥流做一次异或运算得到明文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Encrypt
from Crypto.Cipher import ChaCha20
plaintext = b'Attack at dawn'
secret = b'*Thirty-two byte (256 bits) key*'
cipher = ChaCha20.new(key=secret)
msg = cipher.nonce + cipher.encrypt(plaintext)

# Decrypt
from Crypto.Cipher import ChaCha20
secret = b'*Thirty-two byte (256 bits) key*'
msg_nonce = msg[:8]
ciphertext = msg[8:]
cipher = ChaCha20.new(key=secret, nonce=msg_nonce)
plaintext = cipher.decrypt(ciphertext)

Rabbit

Rabbit 是一种高速流密码,于 2003 年在 FSE 研讨会上首次提出。Rabbit 使用一个 128 位密钥和一个 64 位初始化向量。该加密算法的核心组件是一个位流生成器,该流生成器每次迭代都会加密 128 个消息位。Rabbit 也是一种对称加密算法。

不加盐版本:https://asecuritysite.com/encryption/rabbit2

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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
import collections
import hashlib
import random
import rabbit
import binascii
import sys

def enc_long(n):
'''Encodes arbitrarily large number n to a sequence of bytes.
Big endian byte order is used.'''
s = ""
while n > 0:
s = chr(n & 0xFF) + s
n >>= 8
return s

WORDSIZE = 0x100000000

rot08 = lambda x: ((x << 8) & 0xFFFFFFFF) | (x >> 24)
rot16 = lambda x: ((x << 16) & 0xFFFFFFFF) | (x >> 16)

def _nsf(u, v):
'''Internal non-linear state transition'''
s = (u + v) % WORDSIZE
s = s * s
return (s ^ (s >> 32)) % WORDSIZE

class Rabbit:

def __init__(self, key, iv = None):
'''Initialize Rabbit cipher using a 128 bit integer/string'''

if isinstance(key, str):
# interpret key string in big endian byte order
if len(key) < 16:
key = '\x00' * (16 - len(key)) + key
# if len(key) > 16 bytes only the first 16 will be considered
k = [ord(key[i + 1]) | (ord(key[i]) << 8)
for i in range(14, -1, -2)]
else:
# k[0] = least significant 16 bits
# k[7] = most significant 16 bits
k = [(key >> i) & 0xFFFF for i in range(0, 128, 16)]

# State and counter initialization
x = [(k[(j + 5) % 8] << 16) | k[(j + 4) % 8] if j & 1 else
(k[(j + 1) % 8] << 16) | k[j] for j in range(8)]
c = [(k[j] << 16) | k[(j + 1) % 8] if j & 1 else
(k[(j + 4) % 8] << 16) | k[(j + 5) % 8] for j in range(8)]

self.x = x
self.c = c
self.b = 0
self._buf = 0 # output buffer
self._buf_bytes = 0 # fill level of buffer

next(self)
next(self)
next(self)
next(self)

for j in range(8):
c[j] ^= x[(j + 4) % 8]

self.start_x = self.x[:] # backup initial key for IV/reset
self.start_c = self.c[:]
self.start_b = self.b

if iv != None:
self.set_iv(iv)

def reset(self, iv = None):
'''Reset the cipher and optionally set a new IV (int64 / string).'''

self.c = self.start_c[:]
self.x = self.start_x[:]
self.b = self.start_b
self._buf = 0
self._buf_bytes = 0
if iv != None:
self.set_iv(iv)

def set_iv(self, iv):
'''Set a new IV (64 bit integer / bytestring).'''

if isinstance(iv, str):
i = 0
for c in iv:
i = (i << 8) | ord(c)
iv = i

c = self.c
i0 = iv & 0xFFFFFFFF
i2 = iv >> 32
i1 = ((i0 >> 16) | (i2 & 0xFFFF0000)) % WORDSIZE
i3 = ((i2 << 16) | (i0 & 0x0000FFFF)) % WORDSIZE

c[0] ^= i0
c[1] ^= i1
c[2] ^= i2
c[3] ^= i3
c[4] ^= i0
c[5] ^= i1
c[6] ^= i2
c[7] ^= i3

next(self)
next(self)
next(self)
next(self)


def __next__(self):
'''Proceed to the next internal state'''

c = self.c
x = self.x
b = self.b

t = c[0] + 0x4D34D34D + b
c[0] = t % WORDSIZE
t = c[1] + 0xD34D34D3 + t // WORDSIZE
c[1] = t % WORDSIZE
t = c[2] + 0x34D34D34 + t // WORDSIZE
c[2] = t % WORDSIZE
t = c[3] + 0x4D34D34D + t // WORDSIZE
c[3] = t % WORDSIZE
t = c[4] + 0xD34D34D3 + t // WORDSIZE
c[4] = t % WORDSIZE
t = c[5] + 0x34D34D34 + t // WORDSIZE
c[5] = t % WORDSIZE
t = c[6] + 0x4D34D34D + t // WORDSIZE
c[6] = t % WORDSIZE
t = c[7] + 0xD34D34D3 + t // WORDSIZE
c[7] = t % WORDSIZE
b = t // WORDSIZE

g = [_nsf(x[j], c[j]) for j in range(8)]

x[0] = (g[0] + rot16(g[7]) + rot16(g[6])) % WORDSIZE
x[1] = (g[1] + rot08(g[0]) + g[7]) % WORDSIZE
x[2] = (g[2] + rot16(g[1]) + rot16(g[0])) % WORDSIZE
x[3] = (g[3] + rot08(g[2]) + g[1]) % WORDSIZE
x[4] = (g[4] + rot16(g[3]) + rot16(g[2])) % WORDSIZE
x[5] = (g[5] + rot08(g[4]) + g[3]) % WORDSIZE
x[6] = (g[6] + rot16(g[5]) + rot16(g[4])) % WORDSIZE
x[7] = (g[7] + rot08(g[6]) + g[5]) % WORDSIZE

self.b = b
return self

def derive(self):
'''Derive a 128 bit integer from the internal state'''

x = self.x
return ((x[0] & 0xFFFF) ^ (x[5] >> 16)) | \
(((x[0] >> 16) ^ (x[3] & 0xFFFF)) << 16)| \
(((x[2] & 0xFFFF) ^ (x[7] >> 16)) << 32)| \
(((x[2] >> 16) ^ (x[5] & 0xFFFF)) << 48)| \
(((x[4] & 0xFFFF) ^ (x[1] >> 16)) << 64)| \
(((x[4] >> 16) ^ (x[7] & 0xFFFF)) << 80)| \
(((x[6] & 0xFFFF) ^ (x[3] >> 16)) << 96)| \
(((x[6] >> 16) ^ (x[1] & 0xFFFF)) << 112)


def keystream(self, n):
'''Generate a keystream of n bytes'''

res = ""
b = self._buf
j = self._buf_bytes
next = self.__next__
derive = self.derive

for i in range(n):
if not j:
j = 16
next()
b = derive()
res += chr(b & 0xFF)
j -= 1
b >>= 1

self._buf = b
self._buf_bytes = j
return res

def encrypt(self, data):
'''Encrypt/Decrypt data of arbitrary length.'''

res = ""
b = self._buf
j = self._buf_bytes
next = self.__next__
derive = self.derive

for c in data:
if not j: # empty buffer => fetch next 128 bits
j = 16
next()
b = derive()
res += chr(ord(c) ^ (b & 0xFF))
j -= 1
b >>= 1
self._buf = b
self._buf_bytes = j
return res

decrypt = encrypt

message="Hello"
key="qwerty"
iv=0

key1 = hashlib.md5(key.encode()).hexdigest()

print("Message:\t\t",message)
print("IV:\t",iv)
print("Encryption password:\t",key)
print("Encryption key:\t\t",key1)
print("\n======Rabbit encryption========")

iv=0

msg=Rabbit(key1,iv).encrypt(message)
print("Encrypted:\t",binascii.hexlify(msg.encode()))

text=Rabbit(key1,iv).decrypt(msg)

print("Decrypted:\t",text)

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# y = x ^ (x>>>p) ^ (x>>>q)

from operator import xor
from functools import reduce

def move(n, k):
s = bin(n)[2:].zfill(64)
k &= 63
return int(s[k:] + s[:k], 2)

def encrypt(x, ks):
return xor(x, reduce(xor, map(lambda k: move(x, k), ks)))

def decrypt(y, ks):
for _ in range(6):
y = encrypt(y, ks)
ks = [k << 1 for k in ks]
return y

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
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
def _int32(x):
return int(0xFFFFFFFF & x)

class MT19937:
# 根据seed初始化624的state
def __init__(self, seed):
self.mt = [0] * 624
self.mt[0] = seed
self.mti = 0
for i in range(1, 624):
self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

# 提取伪随机数
def extract_number(self):
if self.mti == 0:
self.twist()
y = self.mt[self.mti]
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
self.mti = (self.mti + 1) % 624
return _int32(y)

# 对状态进行旋转
def twist(self):
for i in range(0, 624):
y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
if y % 2 != 0:
self.mt[i] = self.mt[i] ^ 0x9908b0df

分为三段:

  1. 导入seed,初始化伪随机数发生器

    每次生成 mt[i] 是由前一项进行运算得到的,第一项 mt[0] == seed,总生成 624 项整数的列表(以及其他参数)作为 state

    中间的元组类型有 625 项,前 624 项即是之前提到的整数,而第 625 项(此时等于 624)是该 state 此时对应的第几个整数,也就是说,再下一次执行 extract_number() 函数时的 state 里面应该调用第几个整数。

  2. 进行 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]

  3. 继续 extract_number() 函数

    在判断执行 twist() 函数与否之后,从目前的 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
    9
    import 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
    13
    import 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()
  • 完整 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
    28
    def 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
    24
    def 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 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
    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
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
from gmpy2 import invert

def _int32(x):
return int(0xFFFFFFFF & x)

def init(seed):
mt = [0] * 624
mt[0] = seed
for i in range(1, 624):
mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
return mt

def invert_right(res,shift):
tmp = res
for i in range(32//shift):
res = tmp^res>>shift
return _int32(res)

def recover(last):
n = 1<<32
inv = invert(1812433253,n)
for i in range(623,0,-1):
last = ((last-i)*inv)%n
last = invert_right(last,30)
return last

seed = 2080737669
state = init(seed)

print(recover(state[-1]) == seed)