Raw Implementation of DES Algorithm


 

Raw Implementation of DES Algorithm

DES加密算法原理及原生实现

0x00. 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. 结论

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

0x01. 加密过程

  • 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, 将数据重新排列,便得到64位密文。

img

1. 子密钥的产生

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

img

( 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位。

img

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

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

img

( 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位,其置换表如下所示

img

( 4 ). 代码实现

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

/**
 * 生成16个48位的子密钥
 * @param keyBytes 64位原密钥,用字符数组存储其比特串
 * @return 子密钥数组,用二维字符数组表示
 */
private char[][] generateSubKeys(char[] keyBytes) {
    char[][] subKeys = new char[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 (Initial Permutation)

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

img

3. 加密函数

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

img

1. 选择运算 E

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

img

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盒矩阵如下所示

img

3. 置换运算 P

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

img

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 (int i = 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, 将数据重新排列,便得到64位密文。

上面我们已经进行了子密钥的生成、初始置换和核心加密函数,接下来是进行中Li⊕f(Ri-1), Ki)以及确定下一趟迭代的L和R。在16次迭代完之后再进行逆初始置换就可以得到加密的64位结果。

img

整体的加密过程主要函数的代码实现如下

/**
 * 对外的加密接口,主要逻辑封装在encode方法中
 * @param plaintext 明文
 * @param key 密钥
 * @return encrypted text
 * @throws UnsupportedEncodingException caused by String.getBytes()
 */
public String encrypt(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编码对不可见及非打印字符进行编码
    return Base64Util.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 (int i = 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);
}

0x02. 解密过程

通过数学推理可证明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 (int i = 0; i < subKeys.length; i++) {
        inverseKeys[i] = subKeys[subKeys.length - 1 - i];
    }
    return inverseKeys;
}

0x03. 测试

使用Junit进行单元测试,测试结果的输出较长,为不影响阅读请见Github仓库

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

0x04. 填充方式、工作模式及图形化界面的实现

1. 填充方式

实现最简单的末字节计数器填充方式,即最后一个分组的最后一个字节用来记录填充的位数,解密后读取该字节并去掉相应长度的数据

/**
 * 明文填充,最后一组的最后8位表示填充长度
 */
private char[][] padPlaintext(String plaintext) {
    char[] plaintextBytes = ArrayUtil.bytesToChars(
        plaintext.getBytes());
    int length = plaintextBytes.length;
    int lastBlockBits = length % 64;
    // 现有块数
    int blockCount = length / 64;

    // 待伪随机填充位数
    int randPadCount = 64 - lastBlockBits - 8;
    char[] padded = new char[(blockCount + 1) * 64];
    System.arraycopy(plaintextBytes, 0, padded, 0, length);

    // 伪随机填充
    for (int i = length; i < padded.length - 8; i++) {
        padded[i] = new Random().nextBoolean() ? '1' : '0';
    }
    // 填充最后一个字节比特串
    char[] padCountVal = Integer.toBinaryString(
        (randPadCount & 0xff) + 0x0100).substring(1).toCharArray();
    System.arraycopy(padCountVal, 0, padded, padded.length - 8, 8);

    // 将填充完比特穿分组
    char[][] blocks = new char[blockCount + 1][64];
    for (int i = 0; i < blockCount + 1; i++) {
        System.arraycopy(padded, i * 64, blocks[i], 0, 64);
    }
    return blocks;
}

( 1 ). 单元测试

使用JUnit进行单元测试

@Test
public void testPadPlaintext() {
    DESCipherService desCipherService = new DESCipherService(false);
    desCipherService.padPlaintext("password1");
}

( 2 ). 测试结果

明文:password1
填充前的比特串: 011100000110000101110011011100110111011101101111011100100110010000110001
填充后的比特串: 01110000011000010111001101110011011101110110111101110010011001000011000100101000001000010111101000100111101110010010110100110000

2. 工作方式

实现ECBCBCCTR三种工作模式,为了实现这些,需要将上述的加解密主逻辑代码进行部分调整,调整后的代码可以见DESCipherService.java

3. GUI图形界面

将加密文件和加密字符串的代码进行分离,使用JFrame进行实现GUI界面,详细代码见DESView.java

(1). 加密明文串效果

img

(2). 加密文件效果

img

0x05. 参考

  • 《密码学引论》(第三版,张焕国、唐明编著,武汉大学出版社)

0x06. 相关文章