DES

DES是上世纪八十年代主流的加密算法，DES为分组密码，也就是块密码，块长度为64位，密钥长度为64位，但有8位为校验位，实际长度只有56位，明文按每组64位分组。

结构

DES采用feistel结构，也就是加密和解密的过程相同

块大小越大，密钥长度越长，轮数越多，轮函数越复杂，安全性越高

DES中对明文会进行16轮的加密运算，每一轮都有一个相应的子密钥参与，在开头和结尾还会有初始置换和最终置换的操作

置换

初始置换和最终置换就是简单地根据置换表在一个64bit的块中进行变换

例如表中第一个数字是58，那就将第一个字节和第58个字节进行置换
代码实现:

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     
]
FP_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
]

def IP(block):
result=[]
for i in range(len(IP_table)):
  result.append(block[IP_table[i]-1])
return result

def FP(block):
result=[]
for i in range(len(FP_table)):
  result.append(block[FP_table[i]-1])
return result

轮加密

每一轮加密运算时，先将明文分成左右两块L0，R0，在每一轮中，进行如下运算
Li+1=Ri
Ri+1=Li⊕F(Ri,Ki)
F为轮函数

根据图片可以看到R0直接变成L1，而L0与轮函数中产生的32位数据异或得到R1，轮函数需要R0和子密钥作为输入
代码实现:

m=IP(m)
Li,Ri=m[:32],m[32:]
for i in range(16):
    Li,Ri=Ri,BlockXor(Li,Feistel(Ri,subkey[i]))
    m=Ri+Li
    m=FP(m)

轮函数结构

先通过Expansion将32bit扩展为48bit，再与48bit的子密钥混合作异或运算,然后将48bit分别分为8组，每组6bit，经过S盒替换，输出8组4bit，即32bit。最后对这32bit进行移位置换P

下图为S盒:

代码实现：

def Feistel(HalfBlock, subkey):
   eHalfBlock = Expansion(HalfBlock)
   xHalfBlock = Blockxor(eHalfBlock, subkey)
   sHalfBlock = Substitution(xHalfBlock)
return Permutation(sHalfBlock)

密钥扩展

由于子密钥需要16组，所以我们需要用初始64bit密钥进行密钥扩展，得到16组子密钥：
1.先通过PC-1置换去除64bit密钥中的校验位，得到56位密钥
2.将56位密钥对半分，得到两个28位
3.连续16轮运算，每一轮分别先对左右两半循环移位，再经过PC-2置换生成一个48bit的子密钥
4.最终得到16组48bit的子密钥，用于加解密

代码实现:

subkey=[]
if len(key)==64:
bkey=PC_1(bkey)
elif len(bkey) !=56:
  raise ValueError("key must be 56-bit or 64-bit in length")
  Ci,Di=bkey[:28],bkey[28:]
  for i in range(16):
  Ci,Di=LR(Ci,Di,i)
  subkey.append(PC_2(Ci+Di))
  return subkey