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

作者: 杨临风_05d1 | 来源:发表于2018-10-13 14:46 被阅读0次

一. 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. 缺陷

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

信息安全

密码学

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）