SCERush's Blog
0%

密码学实践（二）

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

之前记录了替代和置换类加解密
这里为流密码部分代码

流密码

RC4

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
import hashlib
import base64

def KSA(key):
    """ 密钥初始流程KSA """
    key = hashlib.md5(key.encode('UTF-8')).hexdigest()
    S = []
    K = []
    for i in range(256):
        S.append(i)
        K.append(key[i % len(key)])
    j = 0
    for i in range(256):
        j = (j + S[i] + ord(K[i])) % 256
        S[i], S[j] = S[j], S[i]
    return S

def PRGA(text, key):
    """ 加解密算法 """
    S = KSA(key)
    outText = ""
    i = j = 0
    for a in text:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        t = (S[i] + S[j]) % 256

        c = chr(ord(a) ^ S[t])
        outText += c
    return outText

def encodeBase64(text):
    """ text to base64 """
    text1 = text.encode('UTF-8')
    text2 = base64.b64encode(text1)
    text3 = text2.decode()
    return text3

def decodeBase64(text):
    """ base64 to text """
    text1 = text.encode()
    text2 = base64.b64decode(text1)
    text3 = text2.decode('UTF-8')
    return text3

def encrypt(plaintext, key):
    """ 加密最终输出为base64串 """
    plain = encodeBase64(plaintext)
    cipher = PRGA(plain, key)
    return encodeBase64(cipher)

def decrypt(ciphertext, key):
    """ 因为之前输出是base64串，所以需要对其检验 """
    try:
        cipher = decodeBase64(ciphertext)
    except Exception:
        return -1
    else:
        plain = PRGA(cipher, key)
        return decodeBase64(plain)

分块密码

DES

desMatrix.py

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
# 初始置换
IP = [58, 50, 42, 34, 26, 18, 10, 2,
      60, 52, 44, 36, 28, 20, 12, 4,
      62, 54, 46, 38, 30, 22, 14, 6,
      64, 56, 48, 40, 32, 24, 16, 8,
      57, 49, 41, 33, 25, 17, 9, 1,
      59, 51, 43, 35, 27, 19, 11, 3,
      61, 53, 45, 37, 29, 21, 13, 5,
      63, 55, 47, 39, 31, 23, 15, 7]

# 末置换
FP = [40, 8, 48, 16, 56, 24, 64, 32,
      39, 7, 47, 15, 55, 23, 63, 31,
      38, 6, 46, 14, 54, 22, 62, 30,
      37, 5, 45, 13, 53, 21, 61, 29,
      36, 4, 44, 12, 52, 20, 60, 28,
      35, 3, 43, 11, 51, 19, 59, 27,
      34, 2, 42, 10, 50, 18, 58, 26,
      33, 1, 41, 9, 49, 17, 57, 25]

# 扩展置换
E_Box = [32, 1, 2, 3, 4, 5, 4, 5,
         6, 7, 8, 9, 8, 9, 10, 11,
         12, 13, 12, 13, 14, 15, 16, 17,
         16, 17, 18, 19, 20, 21, 20, 21,
         22, 23, 24, 25, 24, 25, 26, 27,
         28, 29, 28, 29, 30, 31, 32, 1]

# P盒
P_Box = [16, 7, 20, 21, 29, 12, 28, 17,
         1, 15, 23, 26, 5, 18, 31, 10,
         2, 8, 24, 14, 32, 27, 3, 9,
         19, 13, 30, 6, 22, 11, 4, 25]

# S盒
S_Box = [
    [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
     0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
     4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
     15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13],

    [15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
     3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
     0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
     13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9],

    [10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
     13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
     13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
     1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12],

    [7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
     13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
     10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
     3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14],

    [2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
     14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
     4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
     11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3],

    [12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
     10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
     9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
     4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13],

    [4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
     13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
     1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
     6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12],

    [13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
     1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
     7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
     2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11],

]

# 密钥置换
PC_1 = [57, 49, 41, 33, 25, 17, 9,
        1, 58, 50, 42, 34, 26, 18,
        10, 2, 59, 51, 43, 35, 27,
        19, 11, 3, 60, 52, 44, 36,
        63, 55, 47, 39, 31, 23, 15,
        7, 62, 54, 46, 38, 30, 22,
        14, 6, 61, 53, 45, 37, 29,
        21, 13, 5, 28, 20, 12, 4]

# 压缩置换
PC_2 = [14, 17, 11, 24, 1, 5, 3, 28,
        15, 6, 21, 10, 23, 19, 12, 4,
        26, 8, 16, 7, 27, 20, 13, 2,
        41, 52, 31, 37, 47, 55, 30, 40,
        51, 45, 33, 48, 44, 49, 39, 56,
        34, 53, 46, 42, 50, 36, 29, 32]

# 密钥位移
LS = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

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
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
import re
import tools
import binascii
from desMatrix import *

def strToHex(str_text):
    """
    将str型数据转换成16进制字符串
    :param str_text: str
    :return: hex
    """
    return binascii.hexlify(str_text.encode()).decode()

def hexToBin(hex_text):
    """
    将hex型数据转换成2进制的字符串
    :param hex_text: hex
    :return: bin
    """
    bin_text = ''
    for i in hex_text:
        text_ord = int(i, 16)
        bin_text += decToBinStr(text_ord)
    # 将text与key补全，使长度其为64整数倍
    hex_len = len(hex_text) % 16
    if hex_len != 0:
        bin_text += '0' * (16 - hex_len) * 4
    return bin_text

def decToBinStr(d, lens=4):
    """
    将10进制转为2进制字符串
    :param d: dec num "1"
    :param lens:
    :return: bin num "0001"
    """
    bin_text = ''
    for i in range(lens):
        bin_text = str(d >> i & 1) + bin_text
    return bin_text

def binToHex(bin_text):
    """
    将2进制字符串转为hex型字符串
    :param bin_text: bin
    :return: hex
    """
    bin_num = bin_text.encode()
    res = hex(int(bin_num, 2))
    return str(res)[2:]

# 明文密文置换部分
def ipChange(bin_str):
    """
    IP盒处理
    :param bin_str: 64bit
    :return: 64bit
    """
    res = ""
    for i in IP:
        res += bin_str[i - 1]
    return res

def fpChange(bin_str):
    """
    末置换
    :param bin_str: 64bit
    :return: 64bit
    """
    res = ""
    for i in FP:
        res += bin_str[i - 1]
    return res

def eChange(bin_str):
    """
    E-Box置换
    :param bin_str: 32bit
    :return: 48bit
    """
    res = ""
    for i in E_Box:
        res += bin_str[i - 1]
    return res

def str_xor(text, key):
    """
    异或
    :param text: 48bit
    :param key: 48bit
    :return: 48bit
    """
    res = ""
    for i in range(0, len(text)):
        xor_num = int(text[i], 10) ^ int(key[i], 10)
        if xor_num == 1:
            res += '1'
        if xor_num == 0:
            res += '0'
    return res

def sChange(bin_str):
    """
    S-Box置换
    :param bin_str: 48bit
    :return: 32bit
    """
    res = ""
    c = 0
    for i in range(0, len(bin_str), 6):
        run_str = bin_str[i:i + 6]
        row = int(run_str[0] + run_str[5], 2)
        col = int(run_str[1:5], 2)
        num = bin(S_Box[c][row * 16 + col])[2:]
        for j in range(0, 4-len(num)):
            num = '0' + num
        res += num
        c += 1
    return res

def pChange(bin_str):
    """
    P-Box置换
    :param bin_str: 64bit
    :return: 64bit
    """
    res = ""
    for i in P_Box:
        res += bin_str[i - 1]
    return res

# 密钥处理部分
def pc1_Change(key):
    """
    密钥PC-1置换
    :param key: 64bit
    :return: 56bit
    """
    res = ""
    for i in PC_1:
        res += key[i - 1]
    return res

def leftShift(sub_key, num):
    """
    循环左移
    :param sub_key: 28bit
    :param num: turn
    :return: 28bit
    """
    res = sub_key[num:len(sub_key)]
    res = res + sub_key[0:num]
    return res

def pc2_Change(key):
    """
    密钥PC-2置换
    :param key: 56bit
    :return: 48bit
    """
    res = ""
    for i in PC_2:
        res += key[i - 1]
    return res

def function_f(bin_str, key):
    """
    将E-Box,xor,S-Box,P-Box的运算封装在一起
    :param bin_str: 32bit
    :param key: 48bit
    :return: 32bit
    """
    first_str = eChange(bin_str)  # E-Box 32bit->48bit
    second_str = str_xor(first_str, key)  # xor
    third_str = sChange(second_str)  # S-Box 48bit->32bit
    final_str = pChange(third_str)  # P-Box 32bit
    return final_str

def gen_key(key):
    """
    生成子密钥
    :param key: 64bit
    :return: 48bit * 16
    """
    key_list = []
    first_change = pc1_Change(key)  # 56bit
    key_C0 = first_change[0:28]  # 28bit
    key_D0 = first_change[28:]
    for i in LS:
        key_Ci = leftShift(key_C0, i)
        key_Di = leftShift(key_D0, i)
        second_change = pc2_Change(key_Ci + key_Di)  # 48bit
        key_list.append(second_change)
    return key_list

def encryptPart(bin_plain, bin_key):
    """
    加密主要算法
    :param bin_plain: 64bit
    :param bin_key: 64bit
    :return: 64bit
    """
    ip_str = ipChange(bin_plain)  # ip初始置换
    key_list = gen_key(bin_key)  # 生成子密钥
    plain_left = ip_str[0:32]
    plain_right = ip_str[32:]

    # 进行前15次轮换
    for i in range(0, 15):
        tmp_right = plain_right
        f_res = function_f(tmp_right, key_list[i])
        plain_right = str_xor(f_res, plain_left)
        plain_left = tmp_right
    # 第16次轮换
    f_res = function_f(plain_right, key_list[15])
    fin_left = str_xor(plain_left, f_res)
    fin_right = plain_right
    fin_str = fpChange(fin_left + fin_right)  # 末置换
    return fin_str

def decryptPart(bin_cipher, bin_key):
    """
    解密函数主体部分，同加密算法，注意密钥是反序的
    :param bin_cipher: 64bit
    :param bin_key: 64bit
    :return: 64bit
    """
    ip_str = ipChange(bin_cipher)
    key_list = gen_key(bin_key)
    cipher_left = ip_str[0:32]
    cipher_right = ip_str[32:]

    for i in range(0, 15):
        j = 15 - i  # 从第16个子密钥开始轮换
        tmp_right = cipher_right
        f_res = function_f(cipher_right, key_list[j])
        cipher_right = str_xor(cipher_left, f_res)
        cipher_left = tmp_right

    f_res = function_f(cipher_right, key_list[0])
    fin_left = str_xor(cipher_left, f_res)
    fin_right = cipher_right
    fin_str = fpChange(fin_left + fin_right)
    return fin_str

def encrypt(plaintext, key):
    """
    加密函数入口，主要作用是将明文和密钥转为64倍数位的2进制bit流
    :param plaintext:
    :param key:
    :return: 16进制密文
    """
    bin_plain = hexToBin(strToHex(plaintext))  # 获得明文的64倍数位bit流
    bin_key = hexToBin(strToHex(key))  # 获得密钥的64倍数位bit流
    tmp = re.findall(r'.{64}', bin_plain)  # 将明文bit流分为64一组
    bin_cipher = ""
    for i in tmp:
        bin_cipher += encryptPart(i, bin_key[0:64])  # 对每组bit流进行加密
    return binToHex(bin_cipher)  # 返回16进制密文

def decrypt(ciphertext, key):
    """
    基本上同加密算法，不同的是首先需要对输入进行检查
    """
    try:
        bin_cipher = hexToBin(ciphertext)
    except Exception:
        return -1
    else:
        bin_key = hexToBin(strToHex(key))
        tmp = re.findall(r'.{64}', bin_cipher)
        bin_plain = ""
        for i in tmp:
            bin_plain += decryptPart(i, bin_key[0:64])
        return tools.bytesToLong(int(bin_plain.encode(), 2))

if __name__ == '__main__':
    m = "123456789 asd 加解密"
    k = "123Des密码"
    c = encrypt(m, k)
    print(c)
    d = decrypt(c, k)
    print(d)

公钥密码

RSA相关的之前已经有了，这里主要是素性检验算法 RabinMiller 算法

RabinMiller 算法

RabinMiller主要是用于检测素数

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
import random

def rabinMiller(num):
    """ RabinMiller算法具体实现 """
    t = num - 1
    s = 0
    # 计算 n - 1 = 2 ^ s * t
    while t % 2 == 0:
        t = t // 2
        s += 1
    for trials in range(10):
        # 随机整数b，2 <= b <= n-2
        b = random.randrange(2, num - 1)
        # r0 = b ^ t(mod n)
        r = pow(b, t, num)
        if r != 1:
            i = 0
            while r != (num - 1):
                if i == s - 1:
                    return False
                else:
                    i = i + 1
                    r = (r ** 2) % num
        return True

def isPrime(num):
    """ 验证素数 """
    if num < 2:
        return False
    lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
                 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
                 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241,
                 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
                 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
                 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
                 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
                 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
                 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907,
                 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

    if num in lowPrimes:
        return True
    for prime in lowPrimes:
        if num % prime == 0:
            return False
    return rabinMiller(num)

def generateLargePrime(size=1024):
    """ 生成大素数 """
    while True:
        num = random.randrange(2 ** (size - 1), 2 ** size)
        if isPrime(num):
            return num

if __name__ == '__main__':
    import time
    start = time.time()
    print(generateLargePrime())
    end = time.time()
    print(end - start)