DES加密与实现

发表于 2019-03-25 更新于 2021-11-17 分类于密码学本文字数： 4.5k 阅读时长 ≈ 4 分钟

DES加密基本上属于学习加密算法的必修内容，这里也来梳理一下整个算法

背景

DES全称Data Encryption Standard，也就是数据加密标准，也被称作Data Encryption ALgorithm，DEA，数据加密算法。分类上，它属于对称秘钥加密块密码。1976年被被美国联邦政府的国家标准局确定为联邦资料处理标准，随后再全世界广泛应用，成为一种通用加密算法。虽然现在这种算法已经不安全了，但是它使用的一些思想和理念深深影响可后来许多加密算法。这个算法的官方文档见这里

基本原理

首先这是一种块加密算法，以64位为一块，输出的密文也是64位，加解密使用相同的秘钥，秘钥的长度是56位。对于秘钥，最初是64位的，不过在算法开始前会丢弃8位（第8,16,24,32,40,48,56,64位）。

之后算法的主要思想是对明文进行替换和变换（也称混淆和扩散），这是香农提出的思想，对后世的密码算法有重要影响。混淆是为了保证密文中不会出现明文线索，扩散则是增加明文的冗余度。

DES主要步骤如下：

将明文进行初始置换（IP）
将置换后的块分为左右两部分
对每一部分进行16轮加密
将加密后的两部分拼接起来，进行最终置换（FP），得到密文

如下图：

详细过程

初始置换

在加密前需要进行一次初始置换，称为IP，结束后有一个最终置换，FP，这两个操作在密码学上几乎没有任何意义，只是在最初设计时，为了简化输入输出数据库的过程而被纳入加密流程。

初始置换借助的是一个置换表，如下表：

表中数字代表明文中该位的位置，如第一个是58，则代表将明文中的第58位放到置换后的第一位，依次类推

DES的一轮

每一轮包含秘钥变换，扩展置换，S盒替换，P盒替换和异或交换这几步。也被统称为费斯妥函数，也就是开始那张图中的F函数

秘钥变换

首先秘钥有56位，这一步是从这56位中选取48位，作为这一轮的子秘钥。变换的基本规则是，将56位分为两部分，各28位，每一轮循环左移一位或两位，具体情况如下表：

移位后，具体如何挑选48位，是根据下表挑选：

和初始置换类似，表中数字也是表示的该位在原秘钥中的位置，如第一位14表示将秘钥的第14位写在这里，后面依次类推

由于是将56位变为48位，这一步也称为压缩置换

扩展置换

经过初始置换后，得到两个32位的明文部分，称为左右明文，而这一步就是将右明文扩展到48位。具体过程如下

将32位明文分为8组，每组4位
将每组的4位扩展为6位，实际上是重复每组的第一和第4位，但不是简单的重复，每组之间是有依赖的，简单描述就是，原来每位右移移位，第一位由上一组的第四位填充（第一组由最后一组填充），第六位由下一组的第一位填充（最后一组由第一组填充）

由于这一步极有规律，可以表示为下面的变换表：

这个表使用和前面的一样，不在赘述

S盒替换

前一步将32位明文变为48位，这样就可以和秘钥进行异或操作，最后得到48位的输出，S盒的作用就是将这48位变为32位，总共有8个S盒，每个盒接受6位输入，产生4位输出，随后将48位变为32位。

8个S盒如下

关于S盒的使用如下，首先把一个S和看做4行16列的表格，首先输入有6位，将其中间四位看做列号，首尾两位看做行号。如输入101101，则行号就是11=3，列号就是0110=6，则就取s盒第3行第6位（行列都从0开始计数），如使用第二个S盒就输出2，转为4位二进制就是0010

P盒替换

经s盒替换后，输出32位结果，之后进行一次简单的P和置换，置换表如下：

异或与交换

P和置换不改变位数，输出还是32位，之后将输出的32位与左明文进行异或（前面一系列步骤都是再对右明文处理），运算结果成为下一轮的右明文，而原来的有明文变成下一轮的左明文，这就是所谓的交换

最后一张图总结这几步：

最终置换

这样重复16轮之后，得到一个64位的密文。然后在进行最终置换，置换表如下：

解密

通过前文可知，加密过程是极其繁琐和复杂的，许多替换不深入研究是不能了解其意义的，但是对于解密而言，就体现了DES算法的强大之处，它的加密算法和解密算法是一样的，唯一区别就是那16轮中用的秘钥要反过来，如第1轮解密要用第16轮加密秘钥。不过由于秘钥是独立运算的，所以可以事先计算好16轮加密所使用的全部秘钥。

DES变体

双重DES

从字面意思很好理解，就是使用两个秘钥，进行两次加密。解密时反向操作两次即可。如果说单一DES加密破解需要搜索2^56个秘钥，则双重DES就需要搜索2^112个秘钥

双重DES的中间人攻击

这是一种理论上的攻击，我们假设攻击者知道明文和密文，需要找到加密的两个秘钥。首先创建两张表，第一张表存储所有可能的密码对明文块加密后的结果，第二张表存储所有可能的密码对密文块解密后的结果，比对两张表的结果，相同的那两行所用的秘钥就是加密过程中用的秘钥。

三重DES

三个秘钥的三重DES

比较简单，就是用三个秘钥，加密三次

两个秘钥的三重DES

使用两个秘钥，首先用秘钥K1执行加密，再用K2解密，再用K1加密，这种模式成为加解加模式（EDE）

DES的实现

我们这里用java实现一下DES，完整源码见这里

注意在下面移位操作中，对于二进制字符串，我们认为最左边为第1位。

构造函数和构造密钥组

对于构造函数要求出入一个字节数组作为密钥，长度必须是8字节，然后准备两个long类型数组存储加密和解密子密钥，由于子密钥是48位，所以用64位的long类型存储

private long[] encryptKeys = new long[16];
private long[] decryptKeys = new long[16];
MyDES(byte[] bytes) throws Exception {
    if (bytes.length!=8)
        throw new Exception("密钥长度错误");
    generateSubKey(bytes);
}

private void generateSubKey(byte[] keyBytes) {
    long key = bytesToLong(keyBytes); //64位密钥转为64位long类型表示
    long pc1Result = permute(PC1,key,64); //从64位中选56位
    int l = (int) (pc1Result >>> 28); //密钥左半部分
    int r = (int) (pc1Result & 0xfffffff); //密钥右半部分

    for (int i = 0; i<16;i++){
        //左右部分分别循环左移
        l = (l << KEY_ROTATE[i]) | (l >>> (28-KEY_ROTATE[i]));
        r = (r << KEY_ROTATE[i]) | (r >>> (28-KEY_ROTATE[i]));
        //拼接密钥
        long temp = ((l & 0xfffffffL) << 28) | (r & 0xfffffffL);
        //从56位密钥中选择48位
        encryptKeys[i] = permute(PC2,temp,56);
        //解密密钥组是加密密钥组的倒序
        decryptKeys[15-i] = encryptKeys[i];
    }
}

轮次操作

详细代码如下，关键步骤见注释

private byte[] des(byte[] bytes,long[] subkeys){
    long msg = bytesToLong(bytes); //将64位明文块用long类型表示
    long IPResult = permute(IP,msg,64); //初始置换
    //明文块分为左右两部分
    int l = (int) (IPResult >>> 32); 
    int r = (int) (IPResult & 0xffffffff);
    int temp = 0;
    for (int i = 0;i<16;i++){
        temp = r; //暂存右半部分，作为下一轮的左半部分输入
        r = l ^ f(r, subkeys[i]); //左半部分和右半部分经费斯妥函数运算后异或
        l = temp; //新一轮的左半部分为该轮输入的右半部分
    }
    
    //最终置换，注意由于最后一轮不需要左右交换，
    //而我们上面代码进行了左右交换，所以这里要在进行一次左右交换
    long FPResult = permute(FP,((r & 0xffffffffL) << 32) | (l & 0xffffffffL),64);
    //将long类型转换为64位字节数组
    return longTobytes(FPResult);
}

//费斯妥函数
private int f(int src, long subkey) {
    //32位扩展为48位
    long rExpand = permute(EXPAND,src&0xffffffffL,32);
    //与子密钥异或
    long sIn = rExpand ^ subkey;
    //s盒置换
    long sOut = sBox(sIn);
    //P盒置换
    int pResult = (int) permute(P,sOut,32);
    return pResult;
}

//S盒置换
private long sBox(long sIn) {
    long result = 0;
    int r = 0,c = 0;
    for (int i = 0; i< 8;i++){
        //取低6位
        byte input = (byte) (sIn & 0x3f);
        //取6位输入的首位两位计算行数
        r = ((input & 0x20)>>>4) | (input &0x1);
        //取6位输入的中间4位计算列数
        c = (input & 0x1e) >>> 1;
        //生成的4位输出进行适当移位
        result |= (S[7-i][r][c] & 0xffL) << (i*4);
        //输出右移6位，一般下一次循环取低6位
        sIn >>>= 6;
    }
    return result;
}

测试与验证

public static void main(String[] args) throws Exception {
    MyDES myDES = new MyDES("12345678".getBytes());
    byte[] enc = myDES.encrypt("abcdefgh".getBytes());
    System.out.println(byteToHexString(enc));
    byte[] dec = myDES.decrypt(enc);
    System.out.println(new String(dec));
}

上面加密结果转为16进制字符串之后为94d4436bc3b5b693，与网上在线加密（注意比对时要选择ECB模式，而且大多数都会默认填充，即使明文已经达到了64位，所以要将网上结果去除尾部16个十六进制字符）测试结果一致，解密也可以正常得出原文。

题图来自unsplash：https://unsplash.com/photos/E7PlRr9ZfoM