对称加密算法之DES介绍

      DES(Data Encryption Standard)是分组对称密码算法。DES采用了64位的分组长度和56位的密钥长度，它将64位的输入经过一系列变换得到64位的输出。解密则使用了相同的步骤和相同的密钥。DES的密钥长度为64位，由于第n*8(n=1,2,…8)是校验位，因此实际参与加密的长度为56位，密钥空间含有2^56个密钥。

      DES算法利用多次组合替代算法和换位算法，分散和错乱的相互作用，把明文编制成密码强度很高的密文，它的加密和解密用的是同一算法。

      DES算法，是一种乘积密码，其在算法结构上主要采用了置换、代替、模二相加等函数，通过轮函数迭代的方式来进行计算和工作。

      DES算法也会使用到数据置换技术，主要有初始置换IP和逆初始置换IP^-1两种类型。DES算法使用置换运算的目的是将原始明文的所有格式及所有数据全部打乱重排。而在轮加密函数中，即将数据全部打乱重排，同时在数据格式方面，将原有的32位数据格式，扩展成为48位数据格式，目的是为了满足S盒组对数据长度和数据格式规范的要求。

      一组数据信息经过一系列的非线性变换以后，很难从中推导出其计算的过程和使用的非线性组合；但是如果这组数据信息使用的是线性变换，计算就容易的多。在DES算法中，属于非线性变换的计算过程只有S盒，其余的数据计算和变换都是属于线性变换，所以DES算法安全的关键在于S盒的安全强度。此外，S盒和置换IP相互配合，形成了很强的抗差分攻击和抗线性攻击能力，其中抗差分攻击能力更强一些。

      DES算法是一种分组加密机制，将明文分成N个组，然后对各个组进行加密，形成各自的密文，最后把所有的分组密文进行合并，形成最终的密文。

      DES加密是对每个分组进行加密，所以输入的参数为分组明文和密钥，明文分组需要置换和迭代，密钥也需要置换和循环移位。在初始置换IP中，根据一张8*8的置换表，将64位的明文打乱、打杂，从而提高加密的强度；再经过16次的迭代运算，在这些迭代运算中，要运用到子密钥；每组形成的初始密文，再次经过初始逆置换IP^-1，它是初始置换的逆运算，最后得到分组的最终密文。

图1 DES流程图

      图1左半部分，DES对明文的处理经过了三个阶段。首先，64位的明文经过初始置换(IP)而被重新排列。而后进行16轮的相同函数的作用，每轮的作用都有置换和代换。最后一轮迭代的输出有64位，它是输入明文和密钥的函数。将其左半部分和右半部分互换产生预输出。最后，预输出再与初始置换(IP)互逆的逆初始置换(IP^-1)作用产生64位的密文。

      图2右半部分，给出了作用56比特密钥的过程。DES算法的加密密钥是64比特，但是由于密钥的第n*8(n=1,2…8)是校验(保证含有奇数个1)，因此实际参与加密的的密钥只有56比特。开始时，密钥经过一个置换，然后经过循环左移和另一个置换分别得到子密钥ki，供每一轮的迭代加密使用。每轮的置换函数都一样，但是由于密钥位的重复迭代使得子密钥互不相同。

      DES算法利用多次组合替代算法和换位算法，分散和错乱的相互作用，把明文编制成密码强度很高的密文，它的加密和解密用的是同一算法。

      DES算法详述：DES对64位明文分组(密钥56bit)进行操作。

      1. 初始置换函数IP：64位明文分组x经过一个初始置换函数IP，产生64位的输出x0，再将分组x0分成左半部分L0和右半部分R0：即将输入的第58位换到第一位，第50位换到第2位，…，依次类推，最后一位是原来的第7位。L0、R0则是换位输出后的两部分，L0是输出的左32位，R0是右32位。例，设置换前的输入值为D1D2D3…D64，则经过初始置换后的结果为：L0=D58D50…D8；R0=D57D49…D7.其置换规则如表1所示。

      DES加密过程最后的逆置换IP^-1，是表1的逆过程。就是把原来的每一位都恢复过去，即把第1位的数据，放回到第58位，把第2位的数据，放回到第50位。

表 1

      2. 获取子密钥Ki：DES加密算法的密钥长度为56位，一般表示为64位(每个第8位用于奇偶校验)，将用户提供的64位初始密钥经过一系列的处理得到K1,K2,…,K16，分别作为1~16轮运算的16个子密钥。

      (1). 将64位密钥去掉8个校验位，用密钥置换PC-1(表2)置换剩下的56位密钥；

表2

      (2). 将56位分成前28位C0和后28位D0，即PC-1(K56)=C0D0;

      (3). 根据轮数，这两部分分别循环左移1位或2位，表3：

表3

      (4). 移动后，将两部分合并成56位后通过压缩置换PC-2(表4)后得到48位子密钥，即Ki=PC-2(CiDi).

表4

      子密钥产生如图2所示：

图2 子密钥产生流程图

      3. 密码函数F(非线性的)

      (1). 函数F的操作步骤：密码函数F 的输入是32比特数据和48比特的子密钥：

      A．扩展置换(E):将数据的右半部分Ri从32位扩展为48位。位选择函数(也称E盒)，如表5所示：

表 5

      B．异或：扩展后的48位输出E(Ri)与压缩后的48位密钥Ki作异或运算；

      C．S盒替代：将异或得到的48位结果分成八个6位的块，每一块通过对应的一个S盒产生一个4位的输出。

      S盒的具体置换过程(行和列均从0开始计数)：某个Si盒的6位输入的第1位和第6位形成一个2位的二进制数，对应表中的某一行；输入的中间4位构成4位二进制数对应表中的某一列；第8个S盒的输入为001011，对应第8个S盒的第1行第5列(数为6)，就用6(0110)代替原输入001011.

      下面给出选择函数Si(i=1,2,…….,8)的功能表：

表 6  S1盒

表 7 S2盒

      在此以S1为例说明其功能，在S1中，共有4行数据，命名为0，1，2，3行；每行有16列，命名为0，1，2，3，….，14，15列。现设输入为：D=D1D2D3D4D5D6，令：列=D2D3D4D5，行=D1D6；然后在S1表中查的对应的数，以4位二进制表示，此即为选择函数S1的输出。

      (2)、D、P盒置换：将八个S盒的输出连在一起生成一个32位的输出，输出结果再通过置换P产生一个32位的输出即：F(Ri,Ki)，F(Ri,Ki)算法描述如图3，最后，将P盒置换的结果与最初的64位分组的左半部分异或，然后，左、右半部分交换，开始下一轮计算。

图 3 F(Ri, Ki)计算

      4. 密文输出：经过16次迭代运算后，得到L16、R16，将此作为输入，进行逆置换，即得到密文输出。逆置换正好是初始置的逆运算。例如，第1位经过初始置换后，处于第40位，而通过逆置换，又将第40位换回到第1位，其逆置换规则如表8所示：

表 8 逆置换规则

      图4为DES算法加密原理图：

图 4 DES算法加密原理图

      DES算法加密和解密过程采用相同的算法，并采用相同的加密密钥和解密密钥，两者的区别是：(1)、DES加密是从L0、R0到L15、R15进行变换，而解密时是从L15、R15到L0、R0进行变换的；(2)、加密时各轮的加密密钥为K0K1…K15，而解密时各轮的解密密钥为K15K14…K0；(3)、加密时密钥循环左移，解密时密钥循环右移。

      DES加密过程分析：

      (1)、首先要生成64位密钥，这64位的密钥经过“子密钥算法”换转后，将得到总共16个子密钥。将这些子密钥标识为Kn(n=1,2,…,16)。这些子密钥主要用于总共十六次的加密迭代过程中的加密工具。

      (2)、其次要将明文信息按64位数据格式为一组，对所有明文信息进行分组处理。每一段的64位明文都要经过初试置换IP，置换的目的是将数据信息全部打乱重排。然后将打乱的数据分为左右两块，左边一块共32位为一组，标识为L0；右边一块也是32位为一组，标识为R0.

      (3)、置换后的数据块总共要进行总共十六次的加密迭代过程。加密迭代主要由加密函数f来实现。首先使用子密钥K1对右边32位的R0进行加密处理，得到的结果也是32位的；然后再将这个32位的结果数据与左边32位的L0进行模2处理，从而再次得到一个32位的数据组。我们将最终得到的这个32位组数据，作为第二次加密迭代的R1，往后的每一次迭代过程都与上述过程相同。

      (4)、在结束了最后一轮加密迭代之后，会产生一个64位的数据信息组，然后我们将这个64位数据信息组按原有的数据排列顺序平均分为左右两等分，然后将左右两等分的部分进行位置调换，即原来左等分的数据整体位移至右侧，而原来右等分的数据则整体位移至左侧，这样经过合并后的数据将再次经过逆初始置换IP^-1的计算，我们最终将得到一组64位的密文。

      DES解密过程分析：DES的解密过程与它的加密过程是一样的，这是由于DES算法本身属于对称密码体制算法，其加密和解密的过程可以共用同一个过程和运算。

      DES加密函数f：在DES算法中，要将64位的明文顺利加密输出成64位的密文，而完成这项任务的核心部分就是加密函数f。加密函数f的主要作用是在第m次的加密迭代中使用子密钥Km对Km-1进行加密操作。加密函数f在加密过程中总共需要运行16轮。

      十六轮迭代算法：它先将经过置换后的明文分成两组，每组32位；同时密钥也被分成了两组，每组28位，两组密钥经过运算，再联合成一个48位的密钥，参与到明文加密的运算当中。S盒子，它由8个4*16的矩阵构成，每一行放着0到15的数据，顺序各个不同，是由IBM公司设计好的。经过异或运算的明文，是一个48位的数据，在送入到S盒子的时候，被分成了8份，每份6位，每一份经过一个S盒子，经过运算后输出为4位，即是一个0到15的数字的二进制表示形式。具体运算过程为，将输入的6位中的第1位为第6位合并成一个二进制数，表示行号，其余4位也合并成一个二进制数，表示列号。在当前S盒子中，以这个行号和列号为准，取出相应的数，并以二进制的形式表示，输出，即得到4位的输出，8个S盒子共计32位。

      DES算法优缺点：

      (1)、产生密钥简单，但密钥必须高度保密，因而难以做到一次一密；

      (2)、DES的安全性依赖于密钥的保密。攻击破解DES算法的一个主要方法是通过密钥搜索，使用运算速度非常高的计算机通过排列组合枚举的方式不断尝试各种可能的密钥，直到破解为止。一般，DES算法使用56位长的密钥，通过简单计算可知所有可能的密钥数量最多是2^56个。随着巨型计算机运算速度的不断提高，DES算法的安全性也将随之下降，然而在一般的民用商业场合，DES的安全性仍是足够可信赖的。

      (3)、DES算法加密解密速度比较快，密钥比较短，加密效率很高但通信双方都要保持密钥的秘密性，为了安全还需要经常更换DES密钥。

      openssl, include/des.h(des_old.h)文件中函数说明：

      1. DES_random_key:generates a random key. The PRNG must be seeded prior to using this function(see L<rand(3)|rand(3)>).  If thePRNG could not generate a secure key, 0 is returned.

      2.DES_set_key_checked: Before a DES key can beused, it must be converted into the architecture dependentI<DES_key_schedule> via the DES_set_key_checked() orDES_set_key_unchecked() function. DES_set_key_checked() will check that the keypassed is of odd parity and is not a week or semi-weak key.  If the parity is wrong, then -1 isreturned.  If the key is a weak key, then-2 is returned.  If an error is returned,the key schedule is not generated.

      3. DES_set_key:works like DES_set_key_checked() if the I<DES_check_key> flag isnon-zero, otherwise like DES_set_key_unchecked().

      4. DES_set_odd_parity:sets the parity of the passed I<key> to odd.

      5. DES_is_weak_key:returns 1 is the passed key is a weak key, 0 if it is ok.

      6. DES_ecb_encrypt:the basic DES encryption routine that encrypts or decrypts a single 8-byteI<DES_cblock> in I<electronic code book> (ECB) mode.

      7. DES_ecb3_encrypt:encrypts/decrypts the I<input> block by using three-key Triple-DESencryption in ECB mode. This involves encrypting the input with I<ks1>,decrypting with the key schedule I<ks2>, and then encrypting withI<ks3>.  This routine greatlyreduces the chances of brute force breaking of DES and has the advantage of ifI<ks1>, I<ks2> and I<ks3> are the same, it is equivalent tojust encryption using ECB mode and I<ks1> as the key.

      8. DES_ecb2_encrypt:The macro is provided to perform two-key Triple-DES encryption by usingI<ks1> for the final encryption.

      9. DES_ncbc_encrypt:encrypts/decrypts using the I<cipher-block-chaining> (CBC) mode of DES. If theI<encrypt> argument is non-zero, the routine cipher-block-chain encryptsthe cleartext data pointed to by the I<input> argument into theciphertext pointed to by the I<output> argument, using the key scheduleprovided by the I<schedule> argument, and initialization vector providedby the I<ivec> argument.  If the I<length>argument is not an integral multiple of eight bytes, the last block is copiedto a temporary area and zero filled.  Theoutput is always an integral multiple of eight bytes.

      10. DES_xcbc_encrypt:is RSA's DESX(DESX是DES的一个改进版本，原理是利用一个随机的二进制数与加密前的数据以及解密后的数据异或) mode of DES. It usesI<inw> and I<outw> to 'whiten' the encryption.  I<inw> and I<outw> are secret (unlikethe iv) and are as such, part of the key. So the key is sort of 24 bytes. This is much better than CBC DES.

      11. DES_ede3_cbc_encrypt:implements outer triple CBC DES encryption with three keys. This mode is usedby SSL.

      12. DES_ede2_cbc_encrypt:The macro implements two-key Triple-DES by reusing I<ks1> for the finalencryption. This form of Triple-DES is used by the RSAREF library.

      13. DES_pcbc_encrypt:encrypt/decrypts using the propagating cipher block chaining mode used byKerberos v4. Its parameters are the same as DES_ncbc_encrypt.

      14. DES_cfb_encrypt:encrypt/decrypts using cipher feedback mode. This method takes an array of characters as input and outputs and arrayof characters.  It does not require anypadding to 8 character groups. Note: the I<ivec> variable is changed andthe new changed value needs to be passed to the next call to this function.  Since this function runs a complete DES ECBencryption per I<numbits>, this function is only suggested for use whensending small numbers of characters.

      15. DES_cfb64_encrypt:implements CFB mode of DES with 64bit feedback. this routine will allow you toencrypt an arbitrary number of bytes, no 8 byte padding.  Each call to this routine will encrypt theinput bytes to output and then update ivec and num.

      16. DES_ede3_cfb64_encrypt:is the same as DES_cfb64_encrypt except that Triple-DES is used.

      17. DES_ede2_cfb64_encrypt:is the same as DES_cfb64_encrypt except that Triple-DES is used.

      18. DES_ofb_encrypt: encrypts using output feedbackmode.  This method takes an array ofcharacters as input and outputs and array of characters.  It does not require any padding to 8character groups. Note: the I<ivec> variable is changed and the newchanged value needs to be passed to the next call to this function.  Since this function runs a complete DES ECBencryption per numbits, this function is only suggested for use when sendingsmall numbers of characters.

      19. DES_ofb64_encrypt:is the same as DES_cfb64_encrypt using Output Feed Back mode.

      20. DES_ede3_ofb64_encrypt:is the same as DES_ofb64_encrypt, using Triple-DES.

      21. DES_ede2_ofb64_encrypt:is the same as DES_ofb64_encrypt, using Triple-DES.

      22. DES_cbc_cksum:produces an 8 byte checksum based on the input stream (via CBCencryption).  The last 4 bytes of thechecksum are returned and the complete 8 bytes are placed in I<output>.This function is used by Kerberos(网络认证协议) v4.

      23. DES_quad_cksum:is a Kerberos v4 function.  It returns a4 byte checksum from the input bytes. The algorithm can be iterated over the input, depending onI<out_count>, 1, 2, 3 or 4 times. If I<output> is non-NULL, the 8 bytes generated by each pass arewritten into I<output>.

      24. DES_fcrypt:is a fast version of the Unix crypt(3) function.  This version takes only a small amount ofspace relative to other fast crypt() implementations.  This is different to the normal crypt in thatthe third parameter is the buffer that the return value is written into.  It needs to be at least 14 bytes long.  This function is thread safe, unlike thenormal crypt.

      25. DES_crypt:is a faster replacement for the normal system crypt(). This function callsDES_fcrypt() with a static array passed as the third parameter.  This emulates the normal non-thread safesemantics of crypt(3).

      26. DES_enc_write:writes I<len> bytes to file descriptor I<fd> from bufferI<buf>. The data is encrypted via I<pcbc_encrypt> (default) usingI<sched> for the key and I<iv> as a starting vector.  The actual data send down I<fd>consists of 4 bytes (in network byte order) containing the length of thefollowing encrypted data.  The encrypted datathen follows, padded with random data out to a multiple of 8 bytes.

      27. DES_enc_read:is used to read I<len> bytes from file descriptor I<fd> into bufferI<buf>. The data being read from I<fd> is assumed to have come fromDES_enc_write() and is decrypted using I<sched> for the key schedule andI<iv> for the initial vector.

      Note: (1).ECB mode is not suitable for mostapplications; (2). DES_3cbc_encrypt is flawed and must not beused in applications. (3).DES_cbc_encrypt does not modify B<ivec>; useDES_ncbc_encrypt instead. (4). In OpenSSL 0.9.7, all des_ functions wererenamed to DES_ to avoid clashes with older versions of libdes.

      Des modes: the variants of DES and othercrypto algorithms of OpenSSL.

      Several crypto algorithms for OpenSSL can beused in a number of modes.  Those areused for using block ciphers in a way similar to stream ciphers, among otherthings.

      1、 ElectronicCodebook Mode (ECB): (1). Normally, this is found as the functionI<algorithm>_ecb_encrypt();(2). 64 bits are enciphered at a time;(3). The order of the blocks can be rearranged without detection; (4). The sameplaintext block always produces the same ciphertext block(for the same key)making it vulnerable to a 'dictionary attack'; (5). An error will only affect oneciphertext block.

      2、 CipherBlock Chaining Mode (CBC): (1). Normally, this is found as the functionI<algorithm>_cbc_encrypt(). Be aware that des_cbc_encrypt() is not reallyDES CBC (it does not update the IV); use des_ncbc_encrypt() instead; (2). amultiple of 64 bits are enciphered at a time; (3). The CBC mode produces the sameciphertext whenever the same plaintext is encrypted using the same key andstarting variable; (3). The chaining operation makes the ciphertextblocks dependent on the current and all preceding plaintext blocks andtherefore blocks can not be rearranged; (4). The use of different startingvariables prevents the same plaintext enciphering to the same ciphertext; (5). An errorwill affect the current and the following ciphertext blocks.

      3、 CipherFeedback Mode (CFB): (1). Normally, this is found as the functionI<algorithm>_cfb_encrypt(); (2). a number of bits (j) <= 64 areenciphered at a time; (3). The CFB mode produces the same ciphertextwhenever the same plaintext is encrypted using the same key and startingvariable; (4). The chaining operation makes the ciphertextvariables dependent on the current and all preceding variables and thereforej-bit variables are chained together and can not be rearranged; (5). The useof different starting variables prevents the same plaintext enciphering to thesame ciphertext; (6). The strength of the CFB mode depends on thesize of k (maximal if j == k).  In myimplementation this is always the case; (7). Selection of a small value for jwill require more cycles through the encipherment algorithm per unit ofplaintext and thus cause greater processing overheads; (8). Onlymultiples of j bits can be enciphered; (9). An error will affect the currentand the following ciphertext variables.

      4、 OutputFeedback Mode (OFB): (1). Normally, this is found as the functionI<algorithm>_ofb_encrypt(); (2). a number of bits (j) <= 64 areenciphered at a time; (3). The OFB mode produces the same ciphertextwhenever the same plaintext enciphered using the same key and startingvariable.  Moreover, in the OFB mode thesame key stream is produced when the same key and start variable are used.  Consequently, for security reasons a specificstart variable should be used only once for a given key; (4). Theabsence of chaining makes the OFB more vulnerable to specific attacks; (5). The useof different start variables values prevents the same plaintext enciphering tothe same ciphertext, by producing different key streams; (6). Selectionof a small value for j will require more cycles through the enciphermentalgorithm per unit of plaintext and thus cause greater processing overheads;(7). Only multiples of j bits can be enciphered; (8). OFB modeof operation does not extend ciphertext errors in the resultant plaintextoutput.  Every bit error in theciphertext causes only one bit to be in error in the deciphered plaintext; (9). OFB modeis not self-synchronizing.  If the twooperation of encipherment and decipherment get out of synchronism, the systemneeds to be re-initialized; (10). Each re-initialization should usea value of the start variable different from the start variable values usedbefore with the same key.  The reason forthis is that an identical bit stream would be produced each time from the sameparameters.  This would be susceptible toa 'known plaintext' attack.

      5、 TripleECB Mode: (1). Normally, this is found as the functionI<algorithm>_ecb3_encrypt(); (2). Encrypt with key1, decrypt withkey2 and encrypt with key3 again; (2). As for ECB encryption butincreases the key length to 168 bits. There are theoretic attacks that can beused that make the effective key length 112 bits, but this attack also requires2^56 blocks of memory, not very likely, even for the NSA; (3). If bothkeys are the same it is equivalent to encrypting once with just one key; (4). If thefirst and last key are the same, the key length is 112 bits. There are attacksthat could reduce the effective key strength to only slightly more than 56bits, but these require a lot of memory; (5). If all 3 keys are the same, thisis effectively the same as normal ecb mode.

      6、 TripleCBC Mode: (1). Normally, this is found as the functionI<algorithm>_ede3_cbc_encrypt(); (2). Encrypt with key1, decrypt withkey2 and then encrypt with key3; (3). As for CBC encryption butincreases the key length to 168 bits with the same restrictions as for tripleecb mode.

      参考文献：

      1、 《基于DES和ECC混合加密算法的数字签名研究与应用》

      2、 openssl/doc