沃通(WoSign)数字证书
EmailGoogleTwitterFacebook

DES算法详解与源码 – 小虾ff

        网上关于DES算法的讲述有很多,大致思路一致。但是很多细节的处理上没有交代清楚,源码质量也参差不齐,为此也花了很多时间研究了一下,现在把完整思路和源码整理如下。

        1. DES算法简介:

        DES算法为密码体制中的对称密码体制,又被称为美国数据加密标准,是1972年美国IBM公司研制的对称密码体制加密算法。 明文按64位进行分组,密钥长64位,密钥事实上是56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1)分组后的明文组和56位的密钥按位替代或交换的方法形成密文组的加密方法。

        2. DES步骤:

        1.首先输入一个8字节的密钥M8。将8字节的密钥转换成成64位的二进制位M64。其中第8,16,24,32,40,48,56,64位是校验位, 使得每个密钥都有奇数个1。所以密钥事实上是56位,储存时可以先储存64位,在下一步骤中的PC1置换中可以扣除。

        这里注意高低位问题:比如’L’的ASCII为75,转换为二进制为’01001011’,在这里二进制从左到右为从高到低位,在密钥转换时,则从低位向高位储存

        如:’L’的ASCII为75,二进制为’01001011’,转换至数组内为:char a = {0,1,0,0,1,0,1,1};

        网上各源代码对此处的处理有所不同,这种处理办法能够获得正确的解析结果。

        2. 将64位M64经过PC1置换转换为56位(扣除奇偶校验位)。

        对这56位密钥进行如下表的换位。

        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,

        表的意思是第57位移到第1位,第49位移到第2位,…… 以此类推。

        3. 变换后得到56位数据M56,将它分成两部分,C[0][28], D[0][28]。

        4. 计算16个子密钥。计算方法C[i][28] D[i][28]为对前一个C[i-1][28], D[i-1][28]做循环左移操作。16次的左移位数如下表:

        1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 (左移位数)

        在这里的16次循环中,每一次循环中,左移后,将C[i][28],D[i][28]重新凑成56位后,对这56位进行一次PC2置换,得到48位的子密钥sub[i][48]。16次循环后就有16个子密钥。PC2变换如下:

        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,

        表的意思是第14位移到第1位,第17位移到第2位,以此类推。在此过程中,发现第9,18,22,25, 35,38,43,54位丢弃。

*********************************************************************

        5.得到子密钥以后,就是对明文进行加密和解密操作了,加密和解密操作具有对称性,因此介绍加密操作:

        6.输入明文,要求达到8字节,若没有达到8字节则进行扩展,扩展至8字节(补0或补’\0’)。

        7.将8字节的明文转换成成64位的二进制位。

        8. 对64bit的明文输入进行换位变换。换位表如下:

        58, 50, 12, 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

        表的意思就是第一次变换时,第58位移到第1位,第50位移到第2位,…… 依此类推。得到64位数据data[64]。

        9.接下来将进入循环处理阶段,总共进行16次循环,每次循环遵循如下操作:

        for(int i=0;i<16;i++) { 10.将64位数据data[64]前后分成两块L[i][32], R[i][32]。 11. 对R[i][32]进行扩展变换成48位数,方法如下, 记为E(R[i][32]) 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, 12.将E(R[i][32])与sub[i][48](由密钥处理获得的子密钥,见步骤4)作异或运算,得到48位数B[48]。 13.将48位数顺序分成8份,6位一份,B[48]->B[8][6]。

        14.使用8个S盒对分成8份的B[8][6]进行替换,步骤如下:

        a) 取出B[j][6]的第1位和第6位连成一个2位二进制数m,范围(0-3),转换成十进制数后作为第j个S盒的行标

        如:假设B[0]为’010011’,则取出第一位0和第六位1,组成01,01转换为十进制为1,因此m代表了第0个S盒中的第2行(数组下标从0开始)

        b) 取出B[j][6]的第2、3、4、5位连成一个4位二进制数n,范围(0-15),转换成十进制数后作为第j个S盒的列标

        如:假设B[0]为’010011’,则取出’1001’,转换成十进制为9,因此n代表了第0个S盒中的第10列(数组下标从0开始)

        c) 有了行标和列表则进入第j个S盒中查找对应的数字

        接上例,第0个S盒中第二行第十列获得数字:6

        d) 将获得的数字转换成二进制,替换48位的B中的前4位。

        接上例,6转换为二进制为0110,这样B的前四位就为0110,循环后从第5位继续。

        e) 经过8次循环,每次替换4位,最终B的前32位则为我们新获得的加密数据B[32]

        15.对B[32]进行如下变换得到B'[32]:

        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,

        16.B'[32]与L[i][32]作异或运算,把结果覆盖data[64]的左半部分,若i!=15,则交换data[64]的左右部分(即异或运算结果作为下一次循环的右边,原来的右边作为下 一次运算结果的左边)。若i=15,则不进行交换。

}

        17. 结束循环后,将16次处理过后的data[64]进行一次逆初始置换,这是对第8步的逆变换

        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

        这样就得到了最终的密文了QUQ~

        解密过程同加密过程完全相同,不同的是对子密钥的异或顺序不同,加密过程 i 从0-15与子密钥配对,解密过程中则从15-0与子密钥进行异或。

        源代码见链接:

        http://pan.baidu.com/s/1c0D1RAo

        5.1.cpp为字符char与8位二进制char之间的转换

        5.2&5.3.cpp为DES的加密程序,其中输出中间过程如下:

        a. 密钥对应密钥的64位比特(8X8形式输出,使用5.1中的函数进行转换);

        b. 经过置换选择1后,分别输出的C 0 (28位)和D 0 (28位)对应的比特;

        c. 输出第5次迭代时,产生的子密钥K 5 所对应的48位比特;

        d. 原文对应的64位2进制比特序列;

        e. 64比特序列经过初始置换IP后,得到新的64位比特;

        f. 乘积变换需要进行16次迭代,输出经过5次迭代后,得到的64位比特;

        g. 输出完成乘积变换(16次迭代)后得到的64位比特;

        h. 输出加密后的密文的64位比特;

        5.4.cpp是针对一段指定的密文进行解密的程序。

        5.5.cpp,将给定的文本文件“DES.txt”进行加密,密钥依旧是“KEYMIYAO”,把密文保存在另一个文本文件(“DES_Encrypt.txt”)中,然后对这个文件进行解密,得到的原文保存到文本文件(“DES_Final.txt”)中。其中包括了字符不足时的扩展。将此文件加入vs中后要自己创建以上提到的3个txt资源文件。

        DESc版本.cpp,是DES的c语言实现,效率高,写的好。别看我我是从信息安全专业那里扒来的捂脸QUQ。

        在低版本的VS中可能会出现for循环中不允许声明int的问题,自行修改int变量提至函数开头。

        有空再来补充3DES算法了··

发表评论