csdn_export_md

2024-03-30 18:05:27

DES算法设计与问题解决

山东大学网络空间安全学院

文章目录

一、DES算法介绍

1、历史背景

   数据加密标准DES( data encryption standard)是美国国家标准局(现美国国家标准和技术协会NST)为了满足计算机通信网络的发展对安全保密的要求，实现同一水平的安全性和兼容性，降低数据加密产品的生产成本，推广使用密码算法而公开征集的一种用于*部门及民间进行计算机数据加密的密码算法。
  NBS最初于1973年5月13日向社会公开发起征集，IBM公司提出的一种称为Lucifer的加密算法，被选为数据加密标准。1977年1月15日DES被正式批准作为美国联邦信息处理标准，即FIP-46，同年7月15日生效。1994年1月NSA(美国国家保密局)对DS进行评估后，決定1998年12月以后将不再使用DES，同时征集新的加密标准AES。

2、算法描述

   DES是一个16轮的Feistel型结构密码，它的分组长度为64比特，用一个56比特的密钥来加密一个64比特的明文串，输出一个64比特的密文串。其中，使用密钥为64比特，实用56比特，另8位用作奇偶校验。加密的过程是先对64位明文分组进行初始置换，然后分左、右两部分分别经过16轮迭代，然后再进行循环移位与变换，最后进行逆变换得出密文。加密与解密使用相同的密钥，因而它属于对称密码*。

  图1-1给出了DES过程框图。假设输入的明文数据是64比特。首先经过初始置换IP后把其左半部分32比特记为L0，右半部分32比特记为R0，即成了置换后的输入；然后把R0与密钥产生器产生的子密钥k1进行运算，其结果计为f (R0,k1);再与L0进行摸2加得到L0 ⨁ \bigoplus ⨁f (R0 , k1), 把R0记为L1放在左边，而把L0 ⨁ \bigoplus ⨁f (R0 , k1)记为R1放在右边，从而完成了第一轮迭代运算。在此基础上，重复上述的迭代过程，一直迭代至第16轮。所得的第16轮迭代结果左右不交换，即L15 ⨁ \bigoplus ⨁f (R15 , k16)记为R16,放在左边，而R15记为L16放在右边，成为预输出，最后经过初始置换的逆置换IP-1运算后得到密文。

csdn_export_md

1-1

3、具体实现

3.1、密钥处理

   DES算法共需进行16轮迭代运算，每轮迭代运算使用一个子密钥，共需要16个子密钥。
  首先输入的密码K为64位，但有8位是校验位(8,16,24,32,40,48,56，64),故实际的有效位为56位。
  其次根据PC_1置换表进行第一次的变换生成新的56位比特串,变换表如下所示代码：

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
]

   然后再将新得到的比特串分为左右两部分(C1和D1），C1左移k1位，C2左移k2位，其余根据left表的值一次左移相应的位数，同理Di也依次进行相同的变换，得到Ci和Di两组值。

left = [1, 1, 2, 2, 2, 2, 2, 
        2, 1, 2, 2, 2, 2, 2, 2, 1]

  最后将得到的Ci和Di拼接成CDi，然后再将CDi经过PC_2置换表置换得到F函数中使用的16个轮密钥Ki。

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
    ]

  密钥生成代码如下：

ef Subkey(key):    #生成子密钥
    keyresult = []
    key0 = [0 for i in range(56)]
    for i in range(len(key_table1)):
    for i in range(MaxTime):
        key1 = [0 for i in range(48)]
        #确定每次左移的步数
        if (i == 0 or i == 1 or i == 8 or i == 15):
           step = 1
        else:
       key0[i] = key[key_table1[i]-1]

   #生成16个密钥
            step = 2
        #分成两组
        tmp1 = key0[0:28]
        tmp2 = key0[28:56]
         #循环左移
        tmp1 = Listmove(tmp1, step)
        tmp2 = Listmove(tmp2, step)
        #左右连接
        key0 = tmp1 + tmp2
       #置换选择
        for i in range(len(key_table2)):
            key1[i] = key0[key_table2[i]-1]
        #生成密钥
        keyresult.append(key1)
    #返回的是一个集合包含了每次的密钥
    return keyresult

  生成密钥结果：

Ki = ['7833C320DA70', '2B1A74CA48D8', 
 '8C78D881D31D', '1667789316A0', 
 'CE5D01D80B25', '4BAB4D126A9C', 
 '09F48B713191', '710DEAA3202B', 
 '129AB83347C3', '9C38661E8103', 
 'A26E4CC66544', '48772468A3C8', 
 'C09D79F0D40B', 'C5E2634E162A',
 'A3DF829C7968', 'A6120B4D4C25']

3.2、明文加密过程

3.2.1、IP置换

  IP置换又称初始置换，在迭代运算之前，需要将输入的64位明文数据进行初始置换，将次序打乱。

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
]

3.2.2、16轮迭代运算

   在每一迭代中，每个64位的中结果被分成左右两部分，而且左右两部分作为相互独立的32位数据进行处理。每轮迭代的输入是上轮的结果Li-1和Ri-1。
   Ri-1先由32位扩展到48位，扩展后的48位结果与48位的密钥位的Ki进行异或，得到的结果经过一个S盒替代产生32位的输出，然后再经过一个P盒置换再将得到的结果与Li-1进行简单异或，最后的输出结果作为Ri，而是不经过变换的Ri-1直接得到的。
   Li = Ri -1
   Ri = Li -1 ⨁ \bigoplus ⨁F(Ri-1,ki)
   下面将具体介绍迭代运算的各个部分。

3.2.2.1、E扩展置换函数表和与子密钥异或

  扩展置换将前一轮迭代的结果Ri-1作为输入，根据扩展函数E将32位扩展到48位，扩展函数E将32位的明文每4位分成组，共有8组。每个分组由4位扩展为6位，扩展方法为:每个分组的4位作为6位输出分组的中间4位，6位输出分组中的第1位和第6位分别由相邻的两个4位小分组的最外面两位散进入到本分组产生，其中第1个小分组的左侧相邻分组位最后一个小分组。如E扩展置换表所示

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

  随机经过E盒扩展置换得到的48位输出与子密钥Ki-1进行异或运算。

3.2.2.2、S盒变换

  S盒变换是将与子密钥异或得到的结果作为S盒变换的输入，经过变换得到32位的输出，DES加密函数*有8个S盒每个S盒有4行16列。
  S盒变换的过程为:将与子密钥异或得到48位，每6比特一组，共分成8组，分别作为8个S盒的输入;每一个分组将对应于一个S盒进行变换运算:分组1由S盒1进行变换操作，分组2由盒2操作。。。。。。而且8个S盒所表示的变换运算各不相同。
  如果第i个盒的输入为:Bi=b1b2b3b4b5b6,则S盒变换得到4位输出的过程为:将b1b6和b2b3b4b5作为二进制数，令r=b1b6和c=b2b3b4b5，设第i个S盒中的第r行、c列对应的整数为N，则N的二进制表示就是该s盒在输入为Bi=b1b2b3b4b5b6时对应的4位输出。

S=[
    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
]
3.2.2.3、P盒变换

  P盒变换是将输出的32位比特串根据固定的置换p置换到相应的位置。P盒变换运算后得到的输出即为函数F(Ri-1,Ki)的最终结果。

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
]

3.2.3、IP-1置换

  IP-1置换又称为逆初始置换，结果这一步骤的置换过程即为DES加密算法的密文输出。

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
]

3.2.4、DES代码以及测试运行时间

  IP置换与IP-1置换：

def IP(text, op):   ##打乱顺序,op=0时为正，op=1时为逆
     tmp = [0 for i in range(64)]
     if op == 0:
         for i in range(64):
             tmp[i] = text[IP_table[i]-1]
         return tmp
     if op == 1:
         for i in range(64):
             tmp[i] = text[Inv_IP_table[i]-1]
         return tmp

  E扩展：

def Extend(text):   ##将32位扩展成48位
     extend = [0 for i in range(48)]
     for i in range(48):
         extend[i] = text[extend_table[i] - 1]
     return extend

  异或运算：

def XOR(bit1, bit2):    ##异或运算
     XORresult = [0 for i in range(len(bit1))]
     for i in range(len(bit1)):
         XORresult[i] = str(int(bit1[i]) ^ int(bit2[i]))
     return XORresult

  S盒变换：

def S_replace(text):       ##根据表将48bit->32bit   S盒变换
     Sresult = [0 for k in range(32)]
     for k in range(8):
         row = 2*int(text[k*6]) + int(text[k*6+5])
         column = 8*int(text[k*6+1]) + 4*int(text[k*6+2]) + 2*int(text[k*6+3]) + int(text[k*6+4])
         tmp = S[k][row*16+column]
         for i in range(4):
             Sresult[4*k + i] = int2bit(tmp)[i]
     return Sresult

  P盒变换：

def P_replace(text):
     Presult = [0 for i in range(32)]
     for i in range(32):
         Presult[i] = text[P_table[i]-1]
     return Presult

  经过多次运行代码，得到平均运行速度为0.00606536865234375s，对比之下，加密效率较高。

4、体会混乱、扩散的概念

4.1、问题1：DES原轮函数

csdn_export_md
  在原轮函数下，明文1bit的变化，在6轮加密之后，导致了密文将近32位的变化（这无疑是最好的可以隐藏改变的位数的我们所期待的数据），并且这些变化基本上都是均匀分布的，所以DES加密的扩散和混淆是很好的。

4.2、问题2：删除E扩散

csdn_export_md

  在删除E扩散的情况下，明文1bit的变化，在6轮加密之后，导致了密文将近32位的变化，但是这些变化看上去像是均匀分布的，所以在删除E扩散的情况下，扩散效应保持的不错，混淆做的也不差，但是有了E扩散，虽然扩散和混淆的作用并没有显著的提高，但是这加强了我们加密过程的安全性。

4.3、问题3：删除S-box

csdn_export_md

  在删除S盒之后，明文1bit的变化，在6轮加密之后，导致了密文很少位数的变化，很明显，在删除了S盒之后，DES加密的扩散功能受到了很大的削弱，由于变化的位数过少，我们也不能很容易地判断混淆的作用是否有所影响。换而言之，S盒在DES加密中，对于扩散有着必不可少的作用。

4.4、问题4：删除P置换

csdn_export_md
  在删除P置换之后，明文1bit的变化，在6轮加密之后，导致了密文将近32位的变化，但是我们通过图可以发现变化的密文位数集中在了明文改变的位数的附近，这样就代表了在删除P置换之后，DES加密混淆效果并不好。换而言之，P置换在DES加密中能够起到很大的混淆作用。

上一篇：打卡（10）


下一篇：2020-11-27