DES加密算法原理及使用Java不导包的实现

一. DES概述

数据加密标准（Data Encryption Standard），一种使用密钥加密的块算法，1977年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），并授权在非密级政府通信中使用，随后该算法在国际上广泛流传开来。需要注意的是，在某些文献中，作为算法的DES称为数据加密算法（Data Encryption Algorithm,DEA），已与作为标准的DES区分开来。

1. 几个重要的历史时间

1973年美国国家标准局（NBS）向社会公开征集加密算法，以制定加密算法标准；
1974年第二次征集；
1975年选中IBM的算法，并公布征求意见；
1977年1月15日正式颁布；
1998年底以后停用；
1999年颁布3DES为新标准。

2. 标准加密算法的目标

用于加密保护政府机构和商业部门的非机密的敏感数据。
用于加密保护静态存储和传输信道中的数据。
安全使用10 ~ 15年。

3.密码的整体特点

分组密码，明文、密文和密钥的分组长度都是64位。
面向二进制的密码算法，因而能够加解密任何形式的计算机数据。
对合运算:
- f = f^-1
加密和解密共用同一算法，使工程实现的工作量减半。
综合运用了置换、代替、代数等基本密码技术。
基本结构属于Feistel结构。

4. 应用

在全世界范围得到广泛应用。
许多国际组织采用为标准。
产品形式：软件（嵌入式，应用软件）硬件（芯片，插卡）

5. 结论

用于其设计目标是安全的。
设计精巧、实现容易、使用方便，堪称典范。
为国际信息安全发挥了重要作用。

二. 加密过程

64位密钥经子密钥产生算法产生出16个子密钥： K1, K2, ..., K16 ，分别供第一次, 第二次, ..., 第十六次加密迭代使用。
64位明文经初始置换IP，将数据打乱重排并分成左右两半。左边32位构成L0 ，右边2位构成R0 。
第一次加密迭代：由加密函数f实现子密钥k1对R0的加密，得到32位的f(R0, K1)，然后L0⊕f(R0, K1)，32位的结果作为第二次加密迭代的R1，以R0作为第二次加密迭代的L1。
第二次加密迭代至第十六次加密迭代分别用子密钥K2 ,..., K16进行，其过程与第一次加密迭代相同。
第十六次加密迭代结束后，产生一个64位的数据组，以其左边32位作为R16，以其右边32位作为L16 。
R16与L16合并，再经过逆初始置换IP ^–1，将数据重新排列，便得到64位密文。

image

1. 子密钥的产生

64位密钥经过置换选择1、循环左移、置换选择2等变换，产生16个子密钥 K1，K2。… K16，分别供各次加密迭代使用。

image

( 1 ). 置换选择1 (Permuted Choice 1)

64位的密钥分为8字节，每个字节的第八位是奇偶校验位，前七位才是真正的密钥位。奇偶校验位用于密钥检错，确保其完整性；它不是随机的，可由前七位密钥位算得。因此，DES真正的密钥只有56位。

置换选择1的作用：

去掉密钥中的8个奇偶校验位。
把其余的56位打乱重排，将前28位作为C0，后28位作为D0 。

置换规则：C0的各位依次为原密钥的第57, 49, ..., 1, ..., 44, 36位；D0的各位依次为原密钥的第63, 55, ..., 7, ..., 12, 4位。

image

( 2 ). 循环左移（Left Shift）

对Ci ， Di分别循环左移n位，其中n是会随着迭代次数变化的，其与迭代次数映射表如下所示

image

( 3 ). 置换选择2 （Permuted Choice 2）

64位的密钥分成32位的两份，进过置换选择后各成为28位的数据（即C0和D0），就是说Ci和Di都是28位的数据。将Ci和Di合并成一个56位的数据，置换选择2从中选出一个48位的子密钥Ki。规定子密钥Ki的56位依次是该56位中间数据的第14, 17, ..., 5, 3, ..., 29, 32位，其置换表如下所示

image

( 4 ). 代码实现

为了方便理清生成子密钥的逻辑，其中的打印输出的代码并没有给出，完整源码见该项目Github仓库

/**
* 生成16个48位的子密钥
* @param keyBytes 64位原密钥，用字符数组存储其比特串
* @return 子密钥数组，用二维字符数组表示
*/
private char[][] generateSubKeys(char[] keyBytes) {
    char[][] subKeys = newchar[16][48];
    // 置换选择 1
    char[] c = ArrayUtil.disruptArray(keyBytes,DESConstants.replace1C);
    char[] d = ArrayUtil.disruptArray(keyBytes,DESConstants.replace1D);

    // 循环左移
    for(int i = 0;i < 16; i++) {
      c = ArrayUtil.leftShift(c,DESConstants.moveBit[i]);
      d = ArrayUtil.leftShift(d,DESConstants.moveBit[i]);
      // 将Ci和Di合并得到56位的中间数据
      char[] concatChars = ArrayUtil.concat(c,d);
      // 置换选择 2，得到48位的子密钥Ki
      char[] key = ArrayUtil.disruptArray(concatChars,
                    DESConstants.replace2);
      subKeys[i] = key;
   }
    return subKeys;
}

2. 初始置换IP

初始置换是DES算法的第一步密码变换，它的作用是将64位的明文打乱重排，并分成左右两半。左边32位作为L0，右边32位作为R0，供后面迭代使用。规定置换后的64位数据的各位依次是原明文数据的第58, 50, ..., 2, 60, ..., 15, 7位，其置换表如下所示

image

3. 加密函数

加密函数是DES的核心，它的租用是在第i次迭代中用子密钥Ki对R(i-1)进行加密。其运行规则是：在第i次迭代加密中选择运算E对32位的R(i-1)的各位进行选择排列，产生48位的结果，此结果与48位的子密钥进行异或运算，然后送入替代函数组S。S由8个替代函数（替代盒，Substitute Box）组成，每个S盒有6位输入和4位输出。8个S盒的输出合并得到一个32位的数组，此数据组经过置换运算P，将各位打乱重排，得到的结果便是加密函数的返回值f(R(i-1), Ki)。

image

1. 选择运算 E

该过程对32位的数据组Half Block的各位进行选择和排列，产生一个48位的结果，可见该运算是一个扩展运算，它将32位的数据扩展成了48位的数据，以便与48位的子密钥进行异或运算，下面是选择运算的运算矩阵，可见它是通过重复选择某些数据位来达到数据扩展的目的的。

image

2. 替代函数组 S

由8个S盒（S1, S2, S3, S4, S5, S6, S7, S8）组成，S的输入是一个48位的数据，从1到48位依次加到8个S盒的输入端。每个S盒有一个替代矩阵，规定了其输入输出的替代规则。替代矩阵有4行16列，每行都是0到15这16个数字，但每行数字的排列都不同，且8个替代矩阵彼此不同。每个S盒有6位输入，4位输出，S盒的运算结果是用输出数据替代输入数据，故称为替代函数。

S盒的替代规则为：6位输入的第1位和第6位组成二进制数b1b6代表对应矩阵中被选中的行号，其余四位数字b2b3b4b5组成的二进制数代表对应矩阵中被选中的列号。以S1为例，假设输入数据为b1b2b3b4b5b6 = 101011，则第1位和第6位组成二进制数b1b6 = 11 = 3，表示选中行号为3的那行；b2b3b4b5 = 0101 = 5，表示选中列号为5的那列，行列交点为9，则S1的输出为1001。替代函数组 S中各S盒矩阵如下所示

image

3. 置换运算 P

该过程是把S盒输出的32位数据打乱重排，得到32位的加密函数输出，用P置换来扩散，将S盒的混淆租用扩散开来，正是置换P与S盒的互相配合提高了DES的安全性，置换矩阵P如下所示

image

4. 代码实现

/**
* DES核心加密函数
* 包括扩展、替代、选择等操作
* @param right R(i-1)
* @param subKey Ki
* @return result 运算结果
*/
private char[] coreEncrypt(char[] right, char[] subKey) {
    // 1\. 选择运算 E
    char[] extendedRight = ArrayUtil.disruptArray(right, DESConstants.E);
    // 2\. 将晋国选择运算E扩展得到的48位的数据与子密钥进行异或
    char[] xorResult = ArrayUtil.xor(extendedRight,subKey);

    // 3\. 用替代函数组进行替代
    // 为便于处理，将上述1x48位的数据矩阵转换成8x6的数据矩阵
    char[][] twoDimensionArray = ArrayUtil.segmentDimension(xorResult,8,6);

    StringBuilder outputBuilder = new StringBuilder();

    // 根据替代规则进行替代
    for(inti=0;i<twoDimensionArray.length;i++) {
        char[] rowBits = {
                twoDimensionArray[i][0],
                twoDimensionArray[i][5]
        };
        char[]columnBits = {
          twoDimensionArray[i][1], twoDimensionArray[i][2],
          twoDimensionArray[i][3], twoDimensionArray[i][4]
        };

        // 获取对应S盒的输出的坐标
        int rowIndex = Integer.parseInt(String.valueOf(rowBits), 2);
        int columnIndex = Integer.parseInt(String.
                      valueOf(columnBits), 2);

        // 获取对应S盒的输出
        short output = DESConstants.SUBSTITUTE_BOX[i][rowIndex][columnIndex];
        outputBuilder.append(Integer.toBinaryString((output&0x0f) + 0x10).substring(1));
   }
    char[] substitutedResult = outputBuilder.toString().toCharArray();

    // 4\. 进行置换运算 P，返回28位的数据
    return ArrayUtil.disruptArray(substitutedResult,DESConstants.P);
}

4. 整个加密过程

回顾DES的总体加密过程

64位密钥经子密钥产生算法产生出16个子密钥： K1, K2, ..., K16 ，分别供第一次, 第二次, ..., 第十六次加密迭代使用。
64位明文经初始置换IP，将数据打乱重排并分成左右两半。左边32位构成L0 ，右边2位构成R0 。
第一次加密迭代：由加密函数f实现子密钥k1对R0的加密，得到32位的f(R0, K1)，然后L0⊕f(R0, K1)，32位的结果作为第二次加密迭代的R1，以R0作为第二次加密迭代的L1。
第二次加密迭代至第十六次加密迭代分别用子密钥K2 ,..., K16进行，其过程与第一次加密迭代相同。
第十六次加密迭代结束后，产生一个64位的数据组，以其左边32位作为R16，以其右边32位作为L16 。
R16与L16合并，再经过逆初始置换IP ^–1，将数据重新排列，便得到64位密文。

image

整体的加密过程函数

/**
* 对外的加密接口，主要逻辑封装在encode方法中
* @param plaintext 明文
* @param key 密钥
* @return encrypted text
* @throws UnsupportedEncodingException caused by String.getBytes()
*/
public Stringencrypt(String plaintext,String key) throws UnsupportedEncodingException {
    // 获取明文及密钥对应的比特串，用字符数组存储
    char[] plaintextBytes = ArrayUtil.bytesToChars(
        plaintext.getBytes("UTF-8"));

    char[]keyBytes=ArrayUtil.bytesToChars(
        key.getBytes("UTF-8"));

    // 子密钥的生成
    char[][] subKeys = generateSubKeys(keyBytes);
    char[] result = encode(plaintextBytes,subKeys);

    // 使用Base64编码对不可见及非打印字符进行编码
    returnBase64Util.encode(result);
}

/**
* 主体加密逻辑
* @param plaintextBytes 用字符数组存放的明文的比特串
* @param subKeys 子密钥数组
* @return encryption 64位加密结果
*/
private char[] encode(char[] plaintextBytes, char[][] subKeys) {
    // 初始置换 IP
    char[] chars = ArrayUtil.disruptArray(plaintextBytes,DESConstants.IP);

    // 将明文分成两半
    int length = chars.length;
    String binaryArrayStr = String.valueOf(chars);
    char[] left = binaryArrayStr.substring(0, length/2).toCharArray();
    char[] right=binaryArrayStr.substring(length/2).toCharArray();

    char[]coreEncrypted,xorResult;

    for(inti=0;i<16;i++) {
        // 调用核心加密函数，用子密钥Ki对R(i-1)进行加密，得到28位数据
        coreEncrypted = coreEncrypt(right, subKeys[i]);

        // L(i - 1)与f(R(i - 1), Ki)进行异或运算
        xorResult = String.valueOf(ArrayUtil.xor(left, coreEncrypted))
                     .substring(16).toCharArray();

        left=right;
        right=xorResult;
     }
    char[] calResult = ArrayUtil.concat(right,left);
    // 逆初始置换
    return ArrayUtil.disruptArray(calResult,DESConstants.inverseIP);
}

三. 解密过程

通过数学推理可证明DES具有可逆性和对合性的（限于蝙蝠，在此不作证明），即加密和解密可共用同一个运算，只是子密钥的使用顺序调转而已，即第一次解密迭代使用子密钥K16，第十六次解密迭代使用子密钥K1。

代码实现

基于上述的思想，我们可以将通过密钥获取到的子密钥数组逆转，然后调用encode方法即可

/**
* 解密
* @param encryptedText 加密数据
* @param key  密钥
* @return decrypted origin plaintext
* @throws UnsupportedEncodingException caused by String.getBytes()
*/
@Override
public String decrypt(String encryptedText,String key) throws UnsupportedEncodingException {
    // 将已使用Base64编码的密文解码
    char[] encryptedTextBytes = Base64Util.decode(encryptedText);
    char[]keyBytes = ArrayUtil.bytesToChars(
              key.getBytes("UTF-8"));

    // 将通过密钥获取到的子密钥数组逆转
    char[][] inverseKeys = inverseSubKeys(generateSubKeys(keyBytes));
    // 解密
    char[] result = encode(encryptedTextBytes, inverseKeys);

    // 将比特串还原为字符串明文
    return ArrayUtil.segmentAndPrintChars("decrypt plaintext text", result);
}

/**
* 将通过密钥获取到的子密钥数组逆转
* @param subKeys 原子密钥数组
* @return  翻转的子密钥数组
*/
private char[][] inverseSubKeys(char[][] subKeys) {
    char[][] inverseKeys = new char[subKeys.length][];
    for(inti = 0; i < subKeys.length; i++) {
        inverseKeys[i] = subKeys[subKeys.length - 1 - i];
   }
    returninverseKeys;
}

四. 测试

1. 测试代码

使用Junit进行单元测试

@Test
public void testService() {
    Stringplaintext = "01234567", key = "12345678";
    CipherService cipherService = new DESCipherService();
    try{
        String encryptedText = cipherService.encrypt(plaintext, key);
        cipherService.decrypt(encryptedText,key);
    }catch(UnsupportedEncodingExceptione) {
        e.printStackTrace();
   }
}

由于简书文章的字数限制，测试结果请见Github仓库

五. 代码说明

1. 源码

本文中的代码已发布到Github仓库供学习讨论，如果你觉得写得还不错，欢迎star和fork; 如果对代码有疑惑，欢迎通过邮箱与我讨论。

2. 缺陷

该DES实现旨在理解DES的原理，在软件工程的视角它存在一些实用性上的不足，例如

明文小于64位应该进行填充
明文大于64位应该进行分组，待加密完成后进行密文的合并
没有就数据编码进行扩展，暂不支持中文数据加密

DES加密算法原理及使用Java不导包的实现

一. DES概述

1. 几个重要的历史时间

2. 标准加密算法的目标

3.密码的整体特点

4. 应用

5. 结论

二. 加密过程

1. 子密钥的产生

( 1 ). 置换选择1 (Permuted Choice 1)

( 2 ). 循环左移 （Left Shift）

( 3 ). 置换选择2 （Permuted Choice 2）

( 4 ). 代码实现

2. 初始置换IP

3. 加密函数

1. 选择运算 E

2. 替代函数组 S

3. 置换运算 P

4. 代码实现

4. 整个加密过程

三. 解密过程

代码实现

四. 测试

五. 代码说明

1. 源码

2. 缺陷

( 2 ). 循环左移（Left Shift）