DES算法学习笔记

一般来说，DES算法中

密钥长度为64比特（实际为：56比特 + 8位校验）

DES以64比特为一个单位进行加密，称这64比特的单位为分组。

以分组为单位进行处理的密码算法称为分组密码。

这里学习、记录最为广义的DES（即：具体的操作细则、操作逻辑可以被人为改动

先附上一张完整的大图。

乍一看，难免云里雾里

便从局部入手，慢慢向整体靠拢

密钥处理

由上往下，慢慢解释。

置换选择｜ Permuted Choice 1

（64位密钥，每8位为1组）不考虑每组的第8位，DES的密钥由64位减至56位

每个字节的第8位作为奇偶校验位，这里选择忽略之
产生的56位密钥由下表生成（表中没有8,16,24，32,40,48,56和64这8位）

生成方式为：
- 表中第1位57：将原来密钥中第57位放在第1位
- 表中第2位49：将原来密钥中第49位放在第2位
  
  ······
  
  从上往下，从左往右直到最后一位
置换后的56位密钥分成两部分 C0(28位) 和 D0(28位)

例：

k= 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

根据选择置换PC-1表将这64位转换为56位
k = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

将置换后的56位密钥分成两块C0(28位)和D0(28位)
C0= 1111000 0110011 0010101 0101111
D0= 0101010 1011001 1001111 0001111

循环左移｜ Left shift

将C0和D0进行循环左移变化，变换后生成C1和D1
C1和D1合并

例:

# 第一步置换后的C0和D0
C0= 1111000 0110011 0010101 0101111
D0= 0101010 1011001 1001111 0001111

# 循环左移一位，得到：
C1= 1110000 1100110 0101010 1011111
D1= 1010101 0110011 0011110 0011110

# 将左移后的C1、D1合并
C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110

注：每轮循环左移的位数由轮数决定（见下图）

压缩置换｜ Permuted Choice 2

移动后，从56位中选出48位。

这个过程中，既置换了每位的顺序，又选择了子密钥，因此称为压缩置换。

换PC-2表规则置换

（注意表中没有9，18，22，25，35，38，43和54这8位）

例：

# 左移后
C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110
# 根据PC-2表将左移后的密钥压缩成48位
K1= 000110 110000 001011 101111 111111 000111 000001 110010

压缩置换后的48位子密钥将参与到轮操作中

而C1、D1也将再进行左移和置换后得到下一轮的子密钥

明文处理

由上往下，慢慢解释。

置换IP ｜ Initial Permutation

64位明文M按如下规则重新组合
输出分为L0、R0两部分，每部分各长32位

例:

M= 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

# 根据上面的置换表得到的结果
IP= 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

# 将置换后的结果分为两部分L0、R0
L0= 1100 1100 0000 0000 1100 1100 1111 1111
R0= 1111 0000 1010 1010 1111 0000 1010 1010

轮操作｜ F

经过置换IP后的L0、R0会经过16轮的相同操作 (F)

每一轮都会有一个密钥处理过程生成的不同子密钥参与

Bring it on.

扩展置换 | E table

扩展置置换目标是IP置换后获得的右半部分R0，将32位输入扩展为48位(分为4位×8组)输出。

按表置换

注：左右两边黄色就是用来扩展的

例:

# 明文经过置换后的右半部分如下所示
R0= 1111 0000 1010 1010 1111 0000 1010 1010

# 通过扩展规则得到如下数据
E(R0)= 011110 100001 010101 010101 011110 100001 010101 010101

异或｜ XOR

扩展置换后产生的48位与对应的在密钥处理中产生的48位子密钥异或

S盒置换 | S-box

异或后得到48位的数据，将被送入S盒（6位输入4位输出）进行运算

48位输入分为8个6位的分组，一个分组对应一个S盒，对应的S盒对各组进行代替操作，最后得到32位的数据。

一个S盒就是一个4行16列的表（见下图），盒中的每一项都是一个4位的数。

S盒的6位输入确定了其对应的输出在哪一行哪一列

输入的高低两位做为行数H，中间四位做为列数L，在S-BOX中查找第H行L列对应的数据

例:

S盒的6位输入为101100
取最高位及最低位得到的值10转换为十进制为2
除去最高位及最低位的四位数字组成0110转换为十进制为6
S盒的输出为第2行，第6列所对应的值 2 的二进制 0010

P盒置换｜ P

P盒置换即按表置换

特点是该置换把输入的每位映射到输出位，任何一位都不会重复，也不会缺席

例:

# 原数据
0001 0000 1010 0001 0000 0000 0000 0001

# 替换后的值
1000 0000 0000 0000 0000 1000 1000 0110

异或｜ XOR

P盒置换的结果与最初的64位分组左半部分L0

异或得到结果为 R1， L1则等于R0

接着开始另一轮，总共要进行16次轮操作

左右32bit互换｜ 32-bit Swap

进行16次轮操作后，将L16 与 R16互换位置

即

1 2	L_ = R16 R_ = L16

逆置换IP ｜ Inverse Initial Permutation

逆置换是初始置换IP的逆过程(可以好好理解一下这句话

按表置换即可

例

L_ R_= 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100

# 进行逆置换之后

IP-1= 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101

最后得到的即为密文。

梳理一下

DES会对密钥处理，产生先后16组48位的Ki
DES还对明文处理，使明文与Ki操作，然后产生密文
总体缩略如下

原理讲解的最后，附上最开始的图

应该还算明了，消化一下就好

参考

https://blog.csdn.net/qq_41610725/article/details/116758660?spm=1001.2014.3001.5506

例题

N1DES

题目

# -*- coding: utf-8 -*-
import hashlib,base64
def f(a,b):
    digest = hashlib.sha256(a + b).digest()
    return digest[:8]

def str_xor(a,b):
    return ''.join( chr(ord(a[i]) ^ ord(b[i])) for i in range(len(a)))

def round_add(a, b):
    res = str_xor(f(a,b),f(b,a))
    return res

def permutate(table, block):
    return list(map(lambda x: block[x], table))

def str_permutate(table, block):
    t = map(lambda x: block[x], string_to_list(table))
    return ''.join(chr(i) for i in t)

def string_to_bits(data):
    data = [ord(c) for c in data]
    l = len(data) * 8
    result = [0] * l
    pos = 0
    for ch in data:
        for i in range(0,8):
            result[(pos<<3)+i] = (ch>>i) & 1
        pos += 1
    return result

def string_to_list(data):
    a = []
    a.extend(ord(i) for i in data)
    return a

s_box = [55, 87, 54, 131, 139, 71, 3, 147, 34, 212, 231, 22, 170, 230, 154, 112, 81, 225, 218, 246, 227, 23, 8, 114, 65, 111, 189, 202, 136, 250, 179, 60, 177, 28, 166, 151, 50, 224, 25, 152, 221, 219, 242, 27, 115, 93, 208, 153, 35, 162, 30, 191, 105, 140, 129, 243, 245, 186, 132, 6, 41, 63, 254, 249, 165, 217, 49, 21, 210, 241, 159, 188, 44, 200, 37, 67, 144, 197, 205, 232, 211, 69, 80, 160, 252, 84, 76, 158, 173, 157, 204, 79, 62, 86, 237, 38, 171, 51, 17, 229, 148, 39, 43, 196, 103, 57, 142, 77, 155, 46, 45, 164, 91, 133, 16, 161, 141, 190, 47, 116, 26, 207, 61, 72, 137, 56, 104, 176, 2, 75, 123, 100, 236, 9, 180, 203, 183, 128, 13, 124, 89, 58, 83, 182, 201, 233, 175, 130, 122, 52, 138, 220, 29, 178, 213, 145, 113, 127, 174, 7, 167, 214, 146, 98, 48, 14, 194, 156, 42, 206, 110, 235, 238, 18, 4, 96, 228, 149, 0, 253, 101, 107, 119, 32, 117, 134, 92, 53, 193, 94, 90, 172, 143, 185, 244, 199, 109, 102, 15, 85, 11, 209, 251, 10, 163, 12, 120, 222, 255, 126, 226, 135, 40, 192, 150, 215, 240, 99, 1, 97, 64, 36, 248, 82, 234, 68, 70, 184, 125, 198, 31, 5, 73, 187, 118, 106, 239, 169, 74, 95, 24, 20, 223, 19, 33, 78, 216, 168, 108, 59, 88, 247, 195, 66, 181, 121]

def generate(o):
    k = permutate(o,s_box)
    b = []
    for i in range(0, len(k), 7):
        b.append(k[i:i+7] + [1])
    c = []
    for i in range(32):
        pos = 0
        x = 0
        for j in b[i]:
            x += (j<<pos)
            pos += 1
        c.append((0x10001**x) % (0x7f))
    return permutate(o,s_box)



class N1ES_2:
    def __init__(self, key):
        if len(key) != 32 :
            raise Exception("key must be 32 bytes long")
        self.key = key
        self.gen_subkey()

    def gen_subkey(self):
        o = string_to_bits(self.key)
        k = []
        for i in range(8):
            o = generate(o)
            k.extend(o)
            o = string_to_bits([chr(c) for c in o[0:32]])
        self.Kn = []
        for i in range(32):
            t = map(chr, k[i * 8: i * 8 + 8])
            self.Kn.append(''.join(i for i in t))
        return

    def encrypt(self, plaintext):
        if (len(plaintext) % 16 != 0 or isinstance(plaintext, bytes) == False):
            raise Exception("plaintext must be a multiple of 16 in length")
        res = ''
        for i in range(len(plaintext) / 16):
            block = plaintext[i * 16:(i + 1) * 16]
            L = block[:8]
            R = block[8:]
            for round_cnt in range(32):
                L, R = R, str_xor(round_add(R, self.Kn[round_cnt]),L)
                L, R = str_permutate(L,s_box) , str_permutate(R,s_box)
            L, R = R, L
            res += L + R
        return res


key = "7056b257805ec2b8325795b0e6061f89"
n1es = N1ES_2(key)
cipher = n1es.encrypt(FLAG)
print base64.b64encode(cipher)  # TZPvbvJQ8l2T7G5NmrlDWPLoymq2See29B16+/xf+qk=

题解

给了密钥，密文

依照对称性，写出解密函数

inv_s = [178, 218, 128, 6, 174, 231, 59, 159, 22, 133, 203, 200, 205, 138, 165, 198, 114, 98, 173, 243, 241, 67, 11, 21, 240, 38, 120, 43, 33, 152, 50, 230, 183, 244, 8, 48, 221, 74, 95, 101, 212, 60, 168, 102, 72, 110, 109, 118, 164, 66, 36, 97, 149, 187, 2, 0, 125, 105, 141, 249, 31, 122, 92, 61, 220, 24, 253, 75, 225, 81, 226, 5, 123, 232, 238, 129, 86, 107, 245, 91, 82, 16, 223, 142, 85, 199, 93, 1, 250, 140, 190, 112, 186, 45, 189, 239, 175, 219, 163, 217, 131, 180, 197, 104, 126, 52, 235, 181, 248, 196, 170, 25, 15, 156, 23, 44, 119, 184, 234, 182, 206, 255, 148, 130, 139, 228, 209, 157, 137, 54, 147, 3, 58, 113, 185, 211, 28, 124, 150, 4, 53, 116, 106, 192, 76, 155, 162, 7, 100, 177, 214, 35, 39, 47, 14, 108, 167, 89, 87, 70, 83, 115, 49, 204, 111, 64, 34, 160, 247, 237, 12, 96, 191, 88, 158, 146, 127, 32, 153, 30, 134, 254, 143, 136, 227, 193, 57, 233, 71, 26, 117, 51, 213, 188, 166, 252, 103, 77, 229, 195, 73, 144, 27, 135, 90, 78, 169, 121, 46, 201, 68, 80, 9, 154, 161, 215, 246, 65, 18, 41, 151, 40, 207, 242, 37, 17, 210, 20, 176, 99, 13, 10, 79, 145, 224, 171, 132, 94, 172, 236, 216, 69, 42, 55, 194, 56, 19, 251, 222, 63, 29, 202, 84, 179, 62, 208]

def decrypt(self,cipher):
    res = ''
    for i in range(len(cipher) / 16):
        block = cipher[i * 16:(i + 1) * 16]
        L = block[:8]
        R = block[8:]
        for round_cnt in range(32):
            L, R = str_permutate(L,inv_s) , str_permutate(R,inv_s)
            L, R =  R,str_xor(round_add(R, self.Kn[31 - round_cnt]),L)
        L, R = R, L
        res += L + R
    return res
#n1book{4_3AsY_F3istel_n3tw0rk~~}

注意

解密时，得用inv_s（S-box的逆置换）
解密时，Ki得是反序的

HITCTF2021·baby_des

Hint：Non lined s-box

题目

# -*- coding: utf-8 -*-
#!/usr/bin/python2


from os import urandom
ROUNDS = 8

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]

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

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]


R = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]
# What is R???
# len of R = 16

def Mysbox(bits):
    a,b,c,d,e,f = (bits[0],bits[1],bits[2],bits[3],bits[4],bits[5])
    return [a^b,d^c^a,f^b^c,d^a,e^f]

def chr_to_bits(c):
    res = bin(ord(c))[2:]
    return map(int, list(res.rjust(8,'0')))

def str_to_bits(s):
    res = []
    for c in s:
        res.extend(chr_to_bits(c))
    return res

def bits_to_chr(bits):
    res = int(''.join(map(str, bits)), 2)
    return chr(res)

def bits_to_str(bits):
    res = ''
    for i in range(0, len(bits), 8):
        res += bits_to_chr(bits[i:i+8])
    return res

def xor_bits(l,r):
    return map(lambda (x,y):x^y, zip(l,r))

def F(hblk, subkey):
    bits = [hblk[x-1] for x in E]  # 扩展置换
    bits = xor_bits(bits, subkey)
    res = []
    for i in range(0, len(bits), 6):
        val = Mysbox(bits[i:i+6])
        res.extend(map(int, val))
    res = [res[x-1] for x in P]
    return res

def encrypt_block(blk, subkeys):
    assert len(blk)==8  # 8bytes = 64bits
    bits = str_to_bits(blk)
    bits = [bits[x-1] for x in IP]  # 置换IP
    for i in range(ROUNDS):  # 8轮
        left = bits[:32]  # 左右分割
        right = bits[32:]
        left = xor_bits(left, F(right, subkeys[i]))   # R的XOR
        bits = right + left
    bits = left + right  # 左右对调
    bits = [bits[x-1] for x in IP_1]   # 逆置换IP
    return bits_to_str(bits)

def gen_subkey(key):
    kbits = str_to_bits(key)
    kbits = [kbits[x-1] for x in PC_1]
    left = kbits[:28]
    right = kbits[28:]
    subkeys = []
    for i in range(ROUNDS):
        left = left[R[i]:]+left[:R[i]]
        right = right[R[i]:]+right[:R[i]]
        cur = left+right
        subkeys.append([cur[x-1] for x in PC_2])
    if subkeys[0] == subkeys[1] or subkeys[0] == subkeys[2]:
        raise Exception("Boom")
    return subkeys

def encrypt(pt, key):
    assert len(pt)%8==0
    subkeys = gen_subkey(key)
    ct = ''
    for i in range(0, len(pt), 8):
        ct += encrypt_block(pt[i:i+8], subkeys)
    return ct

def decrypt_block(blk, subkeys):
    assert len(blk)==8
    bits = str_to_bits(blk)
    bits = [bits[x-1] for x in IP]  # 置换IP
    for i in range(ROUNDS):
        left = bits[:32]
        right = bits[32:]
        left = xor_bits(left, F(right, subkeys[ROUNDS-1-i]))  # R的XOR
        bits = right + left
    bits = left + right  # 左右对调
    bits = [bits[x-1] for x in IP_1]  # 逆置换IP
    return bits_to_str(bits)

def decrypt(ct, key):
    assert len(ct)%8==0
    subkeys = gen_subkey(key)
    pt = ''
    for i in range(0, len(ct), 8):
        pt += decrypt_block(ct[i:i+8], subkeys)
    return pt
def task():
    from secret import key,flag
    assert len(flag)==32
    #flag: HITCTF2021{xxxxxxxxxxxxxxxxxx}
    print encrypt(flag,key).encode('hex')
    #e8e2d4985cbe22055041bba9dab1b5bb4ce2d6de4e27bdec4e648ebd3b5112f4
    # get key, solve game.
    # 通过 明文 'HITCTF20' 和 对应密文 获得key
    # 用key 解密 完整密文

题解

https://crypto.stackexchange.com/questions/53751/non-linearity-of-an-sbox

在题目代码下附加

import os
from Crypto.Util.strxor import strxor
key = os.urandom(16)
m='nefuyyds'
m1='HITCTF20'
c1='e8e2d4985cbe2205'.decode('hex')
c2='5041bba9dab1b5bb'.decode('hex')
c3='4ce2d6de4e27bdec'.decode('hexy')
c4='4e648ebd3b5112f4'.decode('hex')
#e8e2d4985cbe22055041bba9dab1b5bb4ce2d6de4e27bdec4e648ebd3b5112f4
y=encrypt(m,key)
m2=strxor(m1,strxor(m,decrypt(strxor(y,strxor(str(c1),str(c2))),key)))
m3=strxor(m1,strxor(m,decrypt(strxor(y,strxor(str(c1),str(c3))),key)))
m4=strxor(m1,strxor(m,decrypt(strxor(y,strxor(str(c1),str(c4))),key)))
m = m1+m2+m3+m4
print(m)

DES算法学习笔记

密钥处理

置换选择 ｜ Permuted Choice 1

例：

循环左移 ｜ Left shift

例:

压缩置换 ｜ Permuted Choice 2

例：

明文处理

置换IP ｜ Initial Permutation

例:

轮操作 ｜ F

扩展置换 | E table

例:

异或 ｜ XOR

S盒置换 | S-box

例:

P盒置换 ｜ P

例:

异或 ｜ XOR

左右32bit互换 ｜ 32-bit Swap

即

逆置换IP ｜ Inverse Initial Permutation

例

梳理一下

参考

例题

N1DES

题目

题解

注意

HITCTF2021·baby_des

题目

题解

置换选择｜ Permuted Choice 1

循环左移｜ Left shift

压缩置换｜ Permuted Choice 2

轮操作｜ F

异或｜ XOR

P盒置换｜ P

异或｜ XOR

左右32bit互换｜ 32-bit Swap