DES算法分析

美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准,于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。加密算法要达到的目的(通常称为DES 密码算法要求)主要为以下四点:

  • 提供高质量的数据保护,防止数据未经授权的泄露和未被察觉的修改;
  • 具有相当高的复杂性,使得破译的开销超过可能获得的利益,同时又要便于理解和掌握;
  • DES密码体制的安全性应该不依赖于算法的保密,其安全性仅以加密密钥的保密为基础;
  • 实现经济,运行有效,并且适用于多种完全不同的应用。

1977年1月,美国政府颁布:采纳IBM公司设计的方案作为非机密数据的正式数据加密标准(DES Data Encryption Standard)。

DES全称为Data Encryption Standard,即数据加密标准,是一种使用密钥加密的块算法,1977年被美国联邦政府的国家标准局确定为联邦资料处理标准(FIPS),并授权在非密级政府通信中使用,随后该算法在国际上广泛流传开来。它基于使用56位密钥的对称算法。这个算法因为包含一些机密设计元素,相对短的密钥长度以及怀疑内含美国国家安全局(NSA)的后门而在开始时有争议,DES因此受到了强烈的学院派式的审查,并以此推动了现代的块密码及其密码分析的发展。

DES现在已经不是一种安全的加密方法,主要因为它使用的56位密钥过短。1999年1月,distributed.net与电子前哨基金会合作,在22小时15分钟内即公开破解了一个DES密钥。也有一些分析报告提出了该算法的理论上的弱点,虽然在实际中难以应用。为了提供实用所需的安全性,可以使用DES的派生算法3DES来进行加密,虽然3DES也存在理论上的攻击方法。在2001年,DES作为一个标准已经被高级加密标准(AES)所取代。另外,DES已经不再作为国家标准科技协会(前国家标准局)的一个标准。

对称密码算法

网络安全通信中要用到两类密码算法,一类是对称密码算法,另一类是非对称密码算法。对称密码算法的加密密钥能够从解密密钥中推算出来,反过来也成立。在大多数对称算法中,加密解密密钥是相同的。它要求发送者和接收者在安全通信之前,商定一个密钥。对称算法的安全性依赖于密钥,泄漏密钥就意味着任何人都能对消息进行加密解密。只要通信需要保密,密钥就必须保密。

img

对称算法又可分为两类。一次只对明文中的单个位(有时对字节)运算的算法称为序列算法或序列密码。另一类算法是对明文的一组位进行运算,这些位组称为分组,相应的算法称为分组算法或分组密码。现代计算机密码算法的典型分组长度为64位――这个长度既考虑到分析破译密码的难度,又考虑到使用的方便性。后来,随着破译能力的发展,分组长度又提高到128位或更长。

常用的采用对称密码术的加密方案有5个组成部分:

  • 明文:原始信息。
  • 加密算法:以密钥为参数,对明文进行多种置换和转换的规则和步骤,变换结果为密文。
  • 密钥:加密与解密算法的参数,直接影响对明文进行变换的结果。
  • 密文:对明文进行变换的结果。
  • 解密算法:加密算法的逆变换,以密文为输入、密钥为参数,变换结果为明文。

对称密码当中有几种常用到的数学运算。这些运算的共同目的就是把被加密的明文数码尽可能深地打乱,从而加大破译的难度。

  • 移位和循环移位:移位就是将一段数码按照规定的位数整体性地左移或右移。循环右移就是当右移时,把数码的最后的位移到数码的最前头,循环左移正相反。例如,对十进制数码12345678循环右移1位(十进制位)的结果为81234567,而循环左移1位的结果则为23456781。
  • 置换:就是将数码中的某一位的值根据置换表的规定,用另一位代替。它不像移位操作那样整齐有序,看上去杂乱无章。这正是加密所需,被经常应用。
  • 扩展:就是将一段数码扩展成比原来位数更长的数码。扩展方法有多种,例如,可以用置换的方法,以扩展置换表来规定扩展后的数码每一位的替代值。
  • 压缩:就是将一段数码压缩成比原来位数更短的数码。压缩方法有多种,例如,也可以用置换的方法,以表来规定压缩后的数码每一位的替代值。
  • 异或:这是一种二进制布尔代数运算。也可以简单地理解为,参与异或运算的两数位如相等,则结果为0,不等则为1。异或的数学符号为⊕。
  • 迭代:迭代就是多次重复相同的运算,这在密码算法中经常使用,以使得形成的密文更加难以破解。

DES算法简介

DES是一种典型的分组密码—一种将固定长度的明文通过一系列复杂的操作变成同样长度的密文的算法。对DES而言,块长度为64位。同时,DES使用密钥来自定义变换过程,因此算法认为只有持有加密所用的密钥的用户才能解密密文。密钥表面上是64位的,然而只有其中的56位被实际用于算法,其余8位可以被用于奇偶校验,并在算法中被丢弃。因此,DES的有效密钥长度仅为56位。

DES设计中使用了分组密码设计的两个原则:混淆(confusion)和扩散(diffusion),其目的是抗击敌手对密码系统的统计分析。混淆是使密文的统计特性与密钥的取值之间的关系尽可能复杂化,以使密钥和明文以及密文之间的依赖性对密码分析者来说是无法利用的。扩散的作用就是将每一位明文的影响尽可能迅速地作用到较多的输出密文位中,以便在大量的密文中消除明文的统计结构,并且使每一位密钥的影响尽可能迅速地扩展到较多的密文位中,以防对密钥进行逐段破译。

DES加密的算法框架如下:

img

  • 首先要生成一套加密密钥,从用户处取得一个64位长的密码口令,然后通过等分、移位、选取和迭代形成一套16个加密密钥,分别供每一轮运算中使用。
  • DES对64位(bit)的明文分组M进行操作,M经过一个初始置换IP,置换成m0。将m0明文分成左半部分和右半部分m0 = (L0,R0),各32位长。然后进行16轮完全相同的运算(迭代),这些运算被称为函数f,在每一轮运算过程中数据与相应的密钥结合。
  • 在每一轮中,密钥位移位,然后再从密钥的56位中选出48位。通过一个扩展置换将数据的右半部分扩展成48位,并通过一个异或操作替代成新的48位数据,再将其压缩置换成32位。这四步运算构成了函数f。然后,通过另一个异或运算,函数f的输出与左半部分结合,其结果成为新的右半部分,原来的右半部分成为新的左半部分。将该操作重复16次。
  • 经过16轮迭代后,左,右半部分合在一起经过一个末置换(数据整理),这样就完成了加密过程。

分组加密中的工作模式

分组加密算法是按分组大小来进行加解密操作的,如DES算法的分组是64位,而AES是128位,但实际明文的长度一般要远大于分组大小,这样的情况如何处理呢?这正是”mode of operation”即工作模式要解决的问题:明文数据流怎样按分组大小切分,数据不对齐的情况怎么处理等等。早在1981年,DES算法公布之后,NIST在标准文献FIPS 81中公布了4种工作模式:

  • 电子密码本:Electronic Code Book Mode (ECB)

  • 密码分组链接:Cipher Block Chaining Mode (CBC)

  • 密文反馈:Cipher Feedback Mode (CFB)

  • 输出反馈:Output Feedback Mode (OFB)

    2001年又针对AES加入了新的工作模式:

  • 计数器模式:Counter Mode (CTR)

    后来又陆续引入其它新的工作模式。在此仅介绍几种常用的:

ECB:电子密码本模式(electronic codebook mode)

ECB模式只是将明文按分组大小切分,然后用同样的密钥正常加密切分好的明文分组。

img

ECB的理想应用场景是短数据(如加密密钥)的加密。此模式的问题是无法隐藏原明文数据的模式,因为同样的明文分组加密得到的密文也是一样的。举例来说明:

img

从ECB的工作原理可以看出,如果明文数据在等分后,两块数据相同则会产生相同的加密数据块,这会辅助攻击者快速判断加密算法的工作模式,而将攻击资源聚集在破解某一块数据即可,一旦成功则意味着全文破解,大大提升了攻击效率。为了解决这一缺陷,设计者提出了更多的分组密码工作模式,这些模式下各组数据的加密过程彼此产生关联,尽最大可能混淆数据。

CBC:密码分组链接模式(cipher block chaining Triple)

此模式是1976年由IBM所发明,引入了IV(初始化向量:Initialization Vector)的概念。IV是长度为分组大小的一组随机,通常情况下不用保密,不过在大多数情况下,针对同一密钥不应多次使用同一组IV。 CBC要求第一个分组的明文在加密运算前先与IV进行异或;从第二组开始,所有的明文先与前一分组加密后的密文进行异或。(原理有没有和区块链(blockchain)一致,可以算是区块链的鼻祖)

img

CBC模式相比ECB实现了更好的模式隐藏,但因为其将密文引入运算,加解密操作无法并行操作。同时引入的IV向量,还需要加、解密双方共同知晓方可。

CFB:密文反馈模式(Cipher FeedBack)

与CBC模式类似,但不同的地方在于,CFB模式先生成密码流字典,然后用密码字典与明文进行异或操作并最终生成密文。后一分组的密码字典的生成需要前一分组的密文参与运算。

img

CFB模式是用分组算法实现流算法,明文数据不需要按分组大小对齐。

OFB:输出反馈模式(Output Feedbaek)

OFB模式与CFB模式不同的地方是:生成字典的时候会采用明文参与运算,CFB采用的是密文。

img

CTR:计数器模式(counter mode)

上面的几种工作模式都存在一个共性:数据块彼此之间关联,当前块的解密依赖前面的密文块,因此不能随机访问任意加密块。这样会使得用户为了获取其中一点数据而不得不解密所有数据,当数据量大时效率较低。

CTR模式同样会产生流密码字典,但同是会引入一个计数,以保证任意长时间均不会产生重复输出。

img

CTR模式只需要实现加密算法以生成字典,明文数据与之异或后得到密文,反之便是解密过程。CTR模式可以采用并行算法处理以提升吞量,另外加密数据块的访问可以是随机的,与前后上下文无关。

CCM:Counter with CBC-MAC

CCM模式,全称是Counter with Cipher Block Chaining-Message Authentication Code,是CTR工作模式和CMAC认证算法的组合体,可以同时数据加密和鉴别服务。

明文数据通过CTR模式加密成密文,然后在密文后面再附加上认证数据,所以最终的密文会比明文要长。具体的加密流程如下描述:先对明文数据认证并产生一个tag,在后续加密过程中使用此tag和IV生成校验值U。然后用CTR模式来加密原输入明文数据,在密文的后面附上校验码U。

GCM:伽罗瓦计数器模式

类型CCM模式,GCM模式是CTR和GHASH的组合,GHASH操作定义为密文结果与密钥以及消息长度在GF(2^128)域上相乘。GCM比CCM的优势是在于更高并行度及更好的性能。TLS 1.2标准使用的就是AES-GCM算法,并且Intel CPU提供了GHASH的硬件加速功能

python实现DES

# -*- coding:utf-8 -*-

#初始化IP
PI = [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]

#初始化置换选择1
CP_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]

#初始化置换选择2
CP_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]

#选择运算E,将32位明文扩展成48位
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]

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

#初始化置换运算P, 将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]

#逆初始置换IP^-1,是初始置换IP的逆置换
PI_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]

#没产生子密钥所需的循环左移的位数
SHIFT = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]

ENCRYPT = 1
DECRYPT = 0

#将字符串转换为位列表
def string_to_bit_array(text):
    array = list()
    for char in text:
        binval = binvalue(char, 16) #得到字符的二进制位
        array.extend([int(x) for x in list(binval)])
    return array

# 将给定大小的字符串返回其二进制值
def binvalue(val, bitsize):
    if isinstance(val, int):
        binval = bin(val)[2:]
    else:
        binval = bin(ord(val))[2: ]
    if len(binval) > bitsize:
        raise 'binary value larger than the expected size'
    while len(binval) < bitsize:
        binval = '0'+binval
    return binval

#位数组重新生成字符串
def bit_array_to_string(array):
    res = ''.join([chr(int(y, 2)) for y in [''.join([str(x) for x in byte]) for byte in  nsplit(array,16)]])
    return res

#将列表拆分为长度为n的子序列
def nsplit(s, n):
    return [s[k:k+n] for k in range(0, len(s), n)]

class des():

    def __init__(self):
        self.password = None
        self.text = None
        self.keys = list()

    def run(self, key, text, action = ENCRYPT, padding = True):
        if len(key) < 8:
            raise 'Key Should be 8 bytes long'
        elif len(key) > 8:
            key = key[ :8] #如果key大于8个字符,取前面8个字符

        self.password = key  #密钥
        self.text = text     #明文

        if padding and action == ENCRYPT:
            self.addPadding()

        #生成是所有的字密钥
        self.generatekeys()
        text_blocks = nsplit(self.text, 4)
        result = list()
        for block in text_blocks:
            block = string_to_bit_array(block) #生成64位二进制位列表
            block = self.permut(block, PI)  #初始置换IP
            g, d = nsplit(block, 32)  #将明文分为左32位,右32位
            tmp = None
            for i in range(16):
                d_e = self.expend(d, E)
                if action == ENCRYPT:
                    tmp = self.xor(self.keys[i],d_e)
                else:
                    tmp = self.xor(self.keys[15-i],d_e)
                tmp = self.substitute(tmp) #sbox
                tmp = self.permut(tmp, P)
                tmp = self.xor(g, tmp)
                g = d
                d = tmp
            result += self.permut(d+g, PI_1)

        final_res = bit_array_to_string(result)
        if padding and action == DECRYPT:
            return self.removePadding(final_res)
        else:
            return final_res

    #置换选择函数
    def permut(self, block, table):
        return [block[x-1] for x in table]

    #将右边32位的明文输入经过选择运算E扩展成48位
    def expend(self, block, table):
        return [block[x-1] for x in table]

    def xor(self, t1, t2):
        return [x^y for x, y in zip(t1, t2)]

    #生成16个子密钥
    def generatekeys(self):
        self.keys = []
        key = string_to_bit_array(self.password)
        key = self.permut(key, CP_1)
        g, d = nsplit(key, 28)
        for i in range(16): #循环16次
            g, d = self.shift(g, d, SHIFT[i])
            tmp = g + d
            self.keys.append(self.permut(tmp, CP_2))


    #使用sbox代替函数
    def substitute(self, data):
        subblocks = nsplit(data, 6)
        result = []
        for i in range(len(subblocks)):
            block = subblocks[i]
            row = int(str(block[0])+str(block[5]),2) #行号
            column = int(''.join([str(x) for x in block[1:][:-1]]), 2) #列号
            val = S_BOX[i][row][column] #该位置的值
            bin = binvalue(val,4)
            result += [int(x) for x in bin]  #输入到列表
        return result

    #循环左移函数
    def shift(self, g, d, n):
        return g[n:] + g[:n], d[n:] + d[:n]

    #根据PKCS5规范填充位数
    def addPadding(self):
        pad_len = 8 - len(self.text) % 8
        self.text += pad_len*chr(pad_len)

    #移除填充的部分
    def removePadding(self, data):
        pad_len = ord(data[-1]) #最后的数字
        return data[:-pad_len]

    #加密函数
    def encrypt(self, key, text, padding=True):
        return self.run(key, text, ENCRYPT, padding)

    #解密函数
    def decrypt(self, key, text, padding=True):
        return self.run(key, text, DECRYPT, padding)

if __name__ == '__main__':
    key = 'password'
    text = 'test'
    d = des()
    r = d.encrypt(key, text)
    print('%r'% r)
    print(d.decrypt(key, r))

总结

ECB是不推荐的方式,Key相同时,相同的明文在不同的时候产生相同的明文,容易遭到字典攻击,CBC由于加入了向量参数,一定程度上抵御了字典工具,但缺点也随之而来,一旦中间一个数据出错或丢失,后面的数据将受到影响,CFB与CBC类似,好处是明文和密文不用是8bit的整数倍,中间一个数据出错,只影响后面的几个块的数据,OFB比CFB方式,一旦一个数据出错,不会影响后面的数据,但安全性降低;因此,推荐使用CFB方式,但每个数据包单独加密,否则一个数据包丢失,需要做很多容错处理;当然,具体问题也要具体分析,对于只需要“特定安全性”,不需要“计算安全性”以上的软件,也可以使用ECB模式,与其它块密码相似,DES自身并不是加密的实用手段,而必须以某种工作模式进行实际操作。