流密码

在密码学中,流密码(英语: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
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
#!/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)

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())

SM4

SM4是一种分组密码算法,其分组长度为128位(即16字节,4字),密钥长度也为128位(即16字节,4字)。其加解密过程采用了32轮迭代机制(与DES、AES类似),每一轮需要一个轮密钥(与DES、AES类似)。

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
# Python
class SM4Cipher:
def __init__(self, key: bytes):
if not len(key) == 16:
raise ValueError("SM4 key must be length of 16. ")
self._key_r = self._generate_key(key)
self.block_size = 16

def encrypt(self, plaintext: bytes):
return self._do(plaintext, self._key_r)

def decrypt(self, ciphertext: bytes):
return self._do(ciphertext, self._key_r[::-1])

def _do(self, text: bytes, key_r: list):
text_ = [0 for _ in range(4)]
# 将 128bit 转化成 4x32bit
for i in range(4):
text_[i] = int.from_bytes(text[4 * i:4 * i + 4], 'big')
for i in range(32):
box_in = text_[1] ^ text_[2] ^ text_[3] ^ key_r[i]
box_out = self._s_box(box_in)
temp = text_[0] ^ box_out ^ self._rot_left(box_out, 2) ^ self._rot_left(box_out, 10)
temp = temp ^ self._rot_left(box_out, 18) ^ self._rot_left(box_out, 24)
text_ = text_[1:] + [temp]
text_ = text_[::-1] # 结果逆序
# 将 4x32bit 合并成 128bit
result = bytearray()
for i in range(4):
result.extend(text_[i].to_bytes(4, 'big'))
return bytes(result)

def _generate_key(self, key: bytes):
"""密钥生成"""
key_r, key_temp = [0 for _ in range(32)], [0 for _ in range(4)]
FK = [0xa3b1bac6, 0x56aa3350, 0x677d9197, 0xb27022dc]
CK = [0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269, 0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9,
0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249, 0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9,
0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229, 0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209, 0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279]
# 将 128bit 拆分成 4x32bit
for i in range(4):
temp = int.from_bytes(key[4 * i:4 * i + 4], 'big')
key_temp[i] = temp ^ FK[i]
# 循环生成轮密钥
for i in range(32):
box_in = key_temp[1] ^ key_temp[2] ^ key_temp[3] ^ CK[i]
box_out = self._s_box(box_in)
key_r[i] = key_temp[0] ^ box_out ^ self._rot_left(box_out, 13) ^ self._rot_left(box_out, 23)
key_temp = key_temp[1:] + [key_r[i]]
return key_r

@staticmethod
def _s_box(n: int):
BOX = [0xD6, 0x90, 0xE9, 0xFE, 0xCC, 0xE1, 0x3D, 0xB7, 0x16, 0xB6, 0x14, 0xC2, 0x28, 0xFB, 0x2C, 0x05, 0x2B,
0x67, 0x9A, 0x76, 0x2A, 0xBE, 0x04, 0xC3, 0xAA, 0x44, 0x13, 0x26, 0x49, 0x86, 0x06, 0x99, 0x9C, 0x42,
0x50, 0xF4, 0x91, 0xEF, 0x98, 0x7A, 0x33, 0x54, 0x0B, 0x43, 0xED, 0xCF, 0xAC, 0x62, 0xE4, 0xB3, 0x1C,
0xA9, 0xC9, 0x08, 0xE8, 0x95, 0x80, 0xDF, 0x94, 0xFA, 0x75, 0x8F, 0x3F, 0xA6, 0x47, 0x07, 0xA7, 0xFC,
0xF3, 0x73, 0x17, 0xBA, 0x83, 0x59, 0x3C, 0x19, 0xE6, 0x85, 0x4F, 0xA8, 0x68, 0x6B, 0x81, 0xB2, 0x71,
0x64, 0xDA, 0x8B, 0xF8, 0xEB, 0x0F, 0x4B, 0x70, 0x56, 0x9D, 0x35, 0x1E, 0x24, 0x0E, 0x5E, 0x63, 0x58,
0xD1, 0xA2, 0x25, 0x22, 0x7C, 0x3B, 0x01, 0x21, 0x78, 0x87, 0xD4, 0x00, 0x46, 0x57, 0x9F, 0xD3, 0x27,
0x52, 0x4C, 0x36, 0x02, 0xE7, 0xA0, 0xC4, 0xC8, 0x9E, 0xEA, 0xBF, 0x8A, 0xD2, 0x40, 0xC7, 0x38, 0xB5,
0xA3, 0xF7, 0xF2, 0xCE, 0xF9, 0x61, 0x15, 0xA1, 0xE0, 0xAE, 0x5D, 0xA4, 0x9B, 0x34, 0x1A, 0x55, 0xAD,
0x93, 0x32, 0x30, 0xF5, 0x8C, 0xB1, 0xE3, 0x1D, 0xF6, 0xE2, 0x2E, 0x82, 0x66, 0xCA, 0x60, 0xC0, 0x29,
0x23, 0xAB, 0x0D, 0x53, 0x4E, 0x6F, 0xD5, 0xDB, 0x37, 0x45, 0xDE, 0xFD, 0x8E, 0x2F, 0x03, 0xFF, 0x6A,
0x72, 0x6D, 0x6C, 0x5B, 0x51, 0x8D, 0x1B, 0xAF, 0x92, 0xBB, 0xDD, 0xBC, 0x7F, 0x11, 0xD9, 0x5C, 0x41,
0x1F, 0x10, 0x5A, 0xD8, 0x0A, 0xC1, 0x31, 0x88, 0xA5, 0xCD, 0x7B, 0xBD, 0x2D, 0x74, 0xD0, 0x12, 0xB8,
0xE5, 0xB4, 0xB0, 0x89, 0x69, 0x97, 0x4A, 0x0C, 0x96, 0x77, 0x7E, 0x65, 0xB9, 0xF1, 0x09, 0xC5, 0x6E,
0xC6, 0x84, 0x18, 0xF0, 0x7D, 0xEC, 0x3A, 0xDC, 0x4D, 0x20, 0x79, 0xEE, 0x5F, 0x3E, 0xD7, 0xCB, 0x39,
0x48]
result = bytearray()
# 将 32bit 拆分成 4x8bit,依次进行S盒变换
for item in list(n.to_bytes(4, 'big')):
result.append(BOX[item])
return int.from_bytes(result, 'big')

@staticmethod
def _rot_left(n, m):
"""循环左移"""
return ((n << m) | (n >> (32 - m))) & 0xFFFFFFFF

key = bytes.fromhex("0123456789ABCDEFFEDCBA9876543210") # 128bit密钥
plaintext = bytes.fromhex("00112233445566778899aabbccddeeff") # 128bit明文
sm4 = SM4Cipher(key)
print(sm4.encrypt(plaintext).hex()) # 09325c4853832dcb9337a5984f671b9a
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
// C
#include <stdio.h>
#include <iostream>
#include<bits/stdc++.h>
#include <string.h>
/************************************固定参数****************************************/
//S盒
const unsigned char Sbox[256] = {
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
};
//CK为固定参数,用于密钥扩展算法
const unsigned int CK[32] = {
0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269,
0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9,
0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,
0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9,
0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229,
0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209,
0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279 };
//系统参数FK,密钥扩展算法中会使用到
const unsigned int FK[4]={0xA3B1BAC6, 0x56AA3350, 0x677D9197, 0xB27022DC};
/************************************全局变量****************************************/
unsigned int rk[32];//子密钥
unsigned int X[32];//每一轮加密的结果
unsigned int X_0[32];//每一轮解密的结果
unsigned int y[4];//暂时存放32轮后的密文
unsigned int y2[4];//暂时存放32轮后的明文
/***********************************测试用例*****************************************/
unsigned int key[4]={0x01234567,0x89abcdef,0xfedcba98,0x76543210};//
//unsigned int message[4]={0x01234567,0x89abcdef,0xfedcba98,0x76543210};
//unsigned int message[16]={0xFF, 0xD8, 0xFF, 0xE0, 0x00, 0x10, 0x4A, 0x46, 0x49, 0x46, 0x00, 0x01, 0x01, 0x00, 0x00, 0x01};
/*
*利用S盒非线性置换
*传进来的A(32位)取高位的8位(大端机真实的低位在高位储存)与0xFF做与运算,
*经过Sbox置换后放置低位的8位中,再与其他置换出的数做或运算得到t
*截断用 >>(位数) & 0xff,而拼接用 |
*/
unsigned int T(unsigned int A){
unsigned int t;
t = Sbox[(A)>>24&0xFF]<<24|Sbox[(A)>>16&0xFF]<<16|Sbox[(A)>>8&0xFF]<<8|Sbox[(A)&0xFF];
return t;
}
/*
*循环右移
*x为数,y为右移的位数
*/
unsigned int Rotl(unsigned int x, unsigned int y){
unsigned int t = ((x)>>(y)|(x)<<(32-(y)));
return t;
}
/*
*线性转换L1
*在轮函数中用到
*/
unsigned int L1(unsigned int t){
t = (t)^Rotl(t,2)^Rotl(t,10)^Rotl(t,18)^Rotl(t,24);
return t;
}
/*
*线性转换L2
*在子密钥扩展中用到
*/
unsigned int L2(unsigned int t){
t = (t)^Rotl(t,12)^Rotl(t,22);
return t;
}
/*
*sms4加密算法
*/
void encrypt(unsigned int x[], unsigned int rk[32], int num){
for(int i=0; i<32; i+=4){
x[0+num] = x[0+num]^L1(T(x[1+num]^x[2+num]^x[3+num]^rk[i+0]));
x[1+num] = x[1+num]^L1(T(x[2+num]^x[3+num]^x[0+num]^rk[i+1]));
x[2+num] = x[2+num]^L1(T(x[3+num]^x[0+num]^x[1+num]^rk[i+2]));
x[3+num] = x[3+num]^L1(T(x[0+num]^x[1+num]^x[2+num]^rk[i+3]));
X[i+0] = x[0+num];
X[i+1] = x[1+num];
X[i+2] = x[2+num];
X[i+3] = x[3+num];
}
y[0] = X[31];
y[1] = X[30];
y[2] = X[29];
y[3] = X[28];
}
/*
*sms4解密算法
*/
void decrypt(unsigned int x[], unsigned int rk[32], int num){
for(int i=0; i<32; i+=4){
x[0] = x[0]^L1(T(x[1]^x[2]^x[3]^rk[31-i]));
x[1] = x[1]^L1(T(x[2]^x[3]^x[0]^rk[30-i]));
x[2] = x[2]^L1(T(x[3]^x[0]^x[1]^rk[29-i]));
x[3] = x[3]^L1(T(x[0]^x[1]^x[2]^rk[28-i]));
X_0[i+0] = x[0];
X_0[i+1] = x[1];
X_0[i+2] = x[2];
X_0[i+3] = x[3];
}
y2[0] = X_0[31];
y2[1] = X_0[30];
y2[2] = X_0[29];
y2[3] = X_0[28];
}
/*
*密钥扩展算法
*/
void keyExt(unsigned int key[4]){
unsigned int K[4];
K[0] = key[0]^FK[0];
K[1] = key[1]^FK[1];
K[2] = key[2]^FK[2];
K[3] = key[3]^FK[3];
for(int i=0; i<32; i+=4){
K[0] = K[0]^L2(T(K[1]^K[2]^K[3]^CK[i+0]));
K[1] = K[1]^L2(T(K[2]^K[3]^K[0]^CK[i+1]));
K[2] = K[2]^L2(T(K[3]^K[0]^K[1]^CK[i+2]));
K[3] = K[3]^L2(T(K[0]^K[1]^K[2]^CK[i+3]));
rk[i+0] = K[0];
rk[i+1] = K[1];
rk[i+2] = K[2];
rk[i+3] = K[3];
}
}
int main(){
unsigned int cipher[4];
unsigned int *message_0;
//生成子密钥
keyExt(key);
//开始解密
FILE *p = fopen("./cipher.txt", "r+");
FILE *p2 = fopen("./decrypted_message.txt", "wb");
printf("\n明文为:\n");
for(int j=0;j<494868;j+=4){
for(int i=0;i<4;i++)
fscanf(p,"%08x", &cipher[i]);
decrypt(cipher,rk,j);
message_0 = y2;
for(int i=0;i<4;i++){
printf("%08x ", message_0[i]);
fprintf(p2,"%08x ", message_0[i]);
}
printf("\n");
fprintf(p2,"\n");
}
fclose(p);
fclose(p2);
}