DES简单学习

本来没兴趣（其实时太菜）去看密码学这些东西的，但是刚好密码学老师布置了一个DES分析的作业，本来是打算水一水，抄点PPT啥的交了完事，最后还是觉得有必要学习一下，顺便练习一下py，就有了这篇划水博客

发展历史及一些基本信息

• • 1971年，IBM讲LUCIFER密码改进成为建议的DES体制

  • 1975年3月17日，MBS公布该算法

  • 1977年1月15日建议被批准为联邦标准，设计推出DES芯片

  • 1981年，ISO将其作为标准，简称DEA-1

  • NSA宣布每隔5年重新审议DES是否继续作为联邦标准

  • • 1988 => FIPS46-1
    • 1993 => FIPS46-2
    • 1998 => 不再批准

  • DES虽然已有替代标准，单它仍是迄今为止得到最为广泛应用的一种算法，是一种最有代表性的分组加密体制

  • DES是第一代公开的，完全说明细节的商业级现代密码

DES算法分析

明文 => 64位一组进行分组 => IP置换 => 密钥置换 => E扩展置换 =>S盒代替 =>P盒置换 => 重复16轮 => 末置换

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

这个置换的含义是讲，原64位明文中某一位数据放到另一个位置上，比如，明文第一位经过置换后移动到了第40位，明文中的第58位则移动到了第一位，并以此类推，最后再将原来的64位数据对半分为两组32位数据，标注位L0和R0，进入下一次加密

密钥置换

在DES中，有效密钥的长度位56位，具体的原因是因为，在密钥中，每个字节的第8位是作为奇偶校验位的，所以有效密钥就只有64-8=56，所以在下面这个表中也会缺少8、16、24、32、40、48、56、64

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

讲56位密钥按上表进行置换后，会从置换后的密钥中生成不同的48位子密钥，子密钥产生过程：

• 将56位密钥分为两组,每组28位
• 根据加密的第几轮，让每组密钥左移对应位数

轮数	1	2	3	4	5	6	7	8
位数	1	1	2	2	2	2	2	2
轮数	9	10	11	12	13	14	15	16
位数	1	2	2	2	2	2	2	1

• 经过移动后，我们又将得到的56位密钥除第8，18，22，25，35，38，43，54这8位以外的的字符进行一次置换，就得到了一个48位的密钥，使用该密钥与48位待加密内容进行异或

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	42

E扩展置换

这一轮将IP置换的右半部分R0，32位(4*8)扩展为48位，如下图，即将第32位和5位加到新的内容中的第一和第6位，每一行都是如此

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

经过拓展之后变为48位的R0位数和密钥位数相同,继续将48位的R0和48位的密钥进行异或，进入下一步

S盒代替

将上一步异或后得到的48位数据，经过S盒进行替代运算，在这里48位的数据分为68，8组分别送入8个不同的S盒，每个盒输出6位数据，共输出48=32位数据，先给出8个S盒

s1

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

S2

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

S3

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

S4

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	19
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

S5

2	12	4	1	7	10	11	6	5	8	3	15	13	0	14	9
14	11	2	12	4	7	13	1	5	0	15	13	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

S6

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

S7

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

S8

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

我们已S8为例，假设输入的6位数据为 111111,第一位和第六位组合为11，即为十进制的3，对应S盒的第四行，中间4为1111即为16进制的15，对应第16列，这里我们的得到11,输出二进制1011，这样就完成了一个6转4的过程，8个S盒拼起来，就是32位数据，送入下一步

P盒置换

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

将置换后的32位数据与最开始的32位左半部分L0进行异或得到一个新的32位数据

将这个32位数据作为新一轮的R，上一轮的R作为新一轮的L，即：

RO => L1

加密后的R0 => R1

末置换(逆IP置换)

初始置换的逆过程，DES最后一轮后，左、右两半部分并未进行交换，而是两部分合并形成一个分组做为末置换的输入

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

置换后就可以得到密文

关于解密

解密时需要注意得是，16轮与密钥异或是，密钥顺序要和加密时相反

code

IP_table=[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]

#逆IP置换表
_IP_table=[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]

#压缩置换表1，不考虑每字节的第8位，将64bit=>56位。再进行一次密钥置换。
keyzip_table=[ 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]

#压缩置换表2，循环移位后的密钥56bit=>48bit
keyzip2_table=[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]    

#扩展置换，将32bit => 48bit
extend_table=[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]

# S1盒
S1=[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]

# S2盒
S2=[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]

# S3盒
S3=[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]

# S4盒
S4=[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]

# S5盒
S5=[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]

# S6盒
S6=[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]

# S7盒
S7=[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]

# S8盒
S8=[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]
# S盒
S=[S1,S2,S3,S4,S5,S6,S7,S8]

#P盒
P_table=[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]

import re
import getopt
import sys
import hashlib
import base64

#字符串转二进制字符串
def strToBin(strText):
    return ''.join(['{:08b}'.format(ord(c)) for c in strText])

#二进制转字符串
def binToStr(binText):
    temp = re.findall(r'.{8}',binText)
    strText = ''
    for s in temp:
        strText += chr(int(s,2))
    return strText

#0-15整数转二进制
def intToBin(intText):
    result = []
    for i in range(0,4):
        result.insert(0,str(intText % 2))
        intText = int(intText / 2)
    return result

#获取明文，并将明文使用空格扩充为8的整数倍
def getPlainText():
    plainText = input('请输入需要加密的内容：')
    addStr = len(plainText) % 8
    if addStr != 0:
        for i in range(8-int(addStr)):
            plainText += ' '
    return plainText

#明文分组并转为二进制
def groupPlain(cipherText):
    groupNum = int(len(cipherText) / 8)
    result = re.findall(r'.{8}',cipherText)
    for i in range(groupNum):
        result[i] = strToBin(result[i])
    return result,groupNum

#获取密文
def getCipherText():
    cipherText = input("请输入密文：")
    return cipherText

#解密时将输入的base64 decode为二进制字符串，并分组
def groupCipher(cipherText):
    try:
        text = str(base64.b64decode(cipherText))[2:-1]
        result = re.findall(r'.{64}',text)
        return result
    except:
        print("您输入的密文不是合法格式！")
        sys.exit()


#获取密钥，密钥取输入内容md5加密后的前8位
def getKey():
    keyStart = input('请输入密钥：')
    md5 = hashlib.md5()
    md5.update(keyStart.encode(encoding='utf-8'))
    key = md5.hexdigest()[:8]
    key = strToBin(key)
    return keyStart,key

#生成16轮的密钥,传入64位二进制密钥
def createKeys(keyBin):
    keyResult = []
    key0 = [0 for i in range(56)]
    for i in range(len(keyzip_table)):
        key0[i] = keyBin[keyzip_table[i] - 1]#64bit => 56bit
    
    for i in range(16):
        key1 = [0 for i in range(48)]
        if(i == 0 or i == 1 or i == 8 or i == 15):#左移位数
            step = 1
        else:
            step = 2
        keyGroup1 = key0[0:28]
        keyGroup2 = key0[28:56]#56bit => 两组28bit

        keyGroup1 = keyGroup1[step:] + keyGroup1[:step]
        keyGroup2 = keyGroup2[step:] + keyGroup2[:step]
        key0 = keyGroup1 + keyGroup2#分组循环左移后拼接

        for i in range(len(keyzip2_table)):
            key1[i] = key0[keyzip2_table[i] - 1]#56bits => 48bits
        
        keyResult.append(key1)#将16个子密钥放入数组并返回
    return keyResult


#IP置换
def IP(plainText):
    result = [0 for i in range(64)]
    for i in range(64):
        result[i] = plainText[IP_table[i] - 1]
    return result

#IP逆置换
def reIP(cipherText):
    result = [0 for i in range(64)]
    for i in range(64):
        result[i] = cipherText[_IP_table[i] - 1]
    return result

#E扩展置换 32bits => 48bits
def E_ExtendedReplace(plainText):
    result = [0 for i in range(48)]
    for i in range(48):
        result[i] = plainText[extend_table[i] - 1]
    return result

#S盒代替 48bits => 32bits
def S_Instead(plainText):
    result = [0 for i in range(32)]
    for i in range(8):
        row = 2 * int(plainText[i * 6]) + int(plainText[i * 6 + 5])
        column = 8*int(plainText[i*6+1]) + 4*int(plainText[i*6+2]) + 2*int(plainText[i*6+3]) + int(plainText[i*6+4])
        temp = S[i][row * 16 + column]
        for j in range(4):
            result[4 * i + j] = intToBin(temp)[j]
    return result

#P盒置换
def P_Replace(plainText):
    result = [0 for i in range(32)]
    for i in range(32):
        result[i] = plainText[P_table[i] - 1]
    return result

#异或
def xor(text1,text2):
    result = [0 for i in range(len(text1))]
    for i in range(len(text1)):
        result[i] = str(int(text1[i]) ^ int(text2[i]))
    return result

def Encryption():
    plainText = getPlainText()#获取明文，已补全为8的整数倍
    groupPlainText,groupNum = groupPlain(plainText)#获取明文分组，已转换为二进制，并获得分组数目

    keyStart,key = getKey()#获取到输入密钥，和经过处理后需要带入运算的密钥
    keys = createKeys(key)#获取到16组密钥
    
    result = ''


    #开始加密每一组明文
    for oneGroupText in groupPlainText:
        IPText = IP(oneGroupText)#IP置换
        L = [IPText[i] for i in range(32)]
        R = [IPText[i] for i in range(32,64)]#左右分组
        #16轮加密
        for i in range(16):
            temp = R
            temp = E_ExtendedReplace(temp)#E扩展
            temp = xor(temp,keys[i])#与每一轮的密钥异或
            temp = S_Instead(temp)#S盒代替
            temp = P_Replace(temp)#P盒置换
            temp = xor(temp,L)#与左半部分异或
            L = R
            R = temp
        #16轮过后，左右再交换一次
        L,R = R,L
        cipherText = L
        cipherText.extend(R)#拼接L和R
        cipherText = reIP(cipherText)#逆IP置换
        strCipherText = ''.join(cipherText)
        result += strCipherText
    print("明文为：" + plainText) 
    print("密钥为：" + keyStart)
    print(result)
    print("密文为:" + str(base64.b64encode(result.encode('utf-8')))[2:-1])



def Decrypt():
    cipherText = getCipherText()
    groupCipherText = groupCipher(cipherText)
    keyStart,key = getKey()#获取到输入密钥，和经过处理后需要带入运算的密钥
    keys = createKeys(key)#获取到16组密钥
    
    result = ''

    #开始加密每一组明文
    for oneGroupText in groupCipherText:
        IPText = IP(oneGroupText)#IP置换
        L = [IPText[i] for i in range(32)]
        R = [IPText[i] for i in range(32,64)]#左右分组
        #16轮加密
        for i in range(15,-1,-1):
            temp = R
            temp = E_ExtendedReplace(temp)#E扩展
            temp = xor(temp,keys[i])#与每一轮的密钥异或
            temp = S_Instead(temp)#S盒代替
            temp = P_Replace(temp)#P盒置换
            temp = xor(temp,L)#与左半部分异或
            L = R
            R = temp
        #16轮过后，左右再交换一次
        L,R = R,L
        plainText = L
        plainText.extend(R)#拼接L和R
        plainText = reIP(plainText)#逆IP置换
        strPlainText = ''.join(plainText)
        result += strPlainText
    print("密文为：" + cipherText)
    print("密钥为：" + keyStart)
    print("密文为:" + binToStr(result))

def main(option):
    if option != '' and (option in 'Encryption,encryption,-e,-E,ENCRYPTION'):
        Encryption()
    elif option != '' and (option in 'Decrypt,decrypt,-d,-D,DECRYPTO'):
        Decrypt()
    else:
        print("加密请输入1，解密请输入2，退出输入其他值！")
        getopt = input()
        if getopt == '1':
            Encryption()
        elif getopt == '2':
            Decrypt()
        else:
            sys.exit()


if __name__ == '__main__':
    option = ''.join(sys.argv[1:2])
    main(option)