Rick

深入理解DES加密算法

发布于 2021-02-26 | 标签: Cryptography | 11分钟 | 2616字数

数据加密标准（DES：Data Encryption Standard）属于对称分组密码算法，是1977年美国联邦信息处理标准（FIPS）中所采用的一种对称加密算法。随着算力的提高，现在DES已经可以被暴力破解了，因此不再建议使用DES算法。但在学习阶段，我们仍然要理解DES加密的算法思想。

算法概述


在学习DES加密算法之前，我们需要了解密码算法的体系结构如下：DES算法属于对称密码算法（加密密钥盒解密密钥相同，或实质上等同）

image-20210223163811837

典型的DES以64位为分组对数据加密，加密和解密用的是同一个算法

image-20210223172432598

DES加密


明文分组和IP置换


IP置换目的是将输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位。置换的规则按照置换表来进行置换

image-20210223173111368
  • 置换：表中的数字代表新数据中此位置的数据在原数据中的位置，即原数据块的第58位放到新数据的第1位，第50位放到第2位，……依此类推，第7位放到第64位
  • 置换后的数据分为L0和R0两部分，L0为新数据的左32位，R0为新数据的右32位

DES加密迭代


密钥编排


密钥K长64位，8比特，密钥事实上是56位参与DES运算（第8、16、24、32、40、48、56、64位是校验位，使得每个密钥都有奇数个1），分组后的明文组和56位的密钥按位替代或交换的方法形成密文组。

在DES的每一轮迭代中，都需要产生出不同的48位子密钥KiK_i，确定这些子密钥的方式如下：

  • 将56位（不考虑每个字节的第8位，DES的密钥由64位减至56位，每个字节的第8位作为奇偶校验位）的密钥进行置换选择（PC-1），然后将密钥分成两部分，每部分28位

  • 根据轮数，这两部分分别循环左移1位或2位。每轮移动的位数按子密钥计算逻辑表确定

  • 移动后，从56位中选出48位。这个过程中，既置换了每位的顺序，又选择了子密钥，因此称为压缩置换（PC-2）

image-20210223180048101

迭代运算


image-20210225141403051

  • 当明文通过分组和IP置换后，我们得到两个分组左32位Li−1L_{i-1}和右32位Ri−1R_{i-1}，接下来我们要经过16轮加密迭代，每一轮迭代的过程都是一样

  • 下一轮迭代的左32位LiL_{i}直接由上一轮迭代的右32位Ri−1R_{i-1}得到

  • 下一轮迭代的右32位RiR_{i}由上一轮迭代的左32位Li−1L_{i-1}和右32位Ri−1R_{i-1}得到

  • 假设输入为(x,y)(x, y)，则DES每一轮迭代的输出为：(y,x⊕f(k,y))(y, x \oplus f(k, y))

image-20210225224613117

接下来我们讨论ff函数中的细节实现


扩展置换

右32位Ri−1R_{i-1}首先通过扩展 / 置换表扩展成48位：表中的数字代表位，旁边两列数据是扩展的数据，可以看出，扩展的数据是从相邻两组分别取靠近的一位，4位变为6位。靠近32位的位为1，靠近1位的位为32。表中第二行的4取自上组中的末位，9取自下组中的首位


S盒代替

S盒代替时DES算法的关键步骤，所有的其他的运算都是线性的，易于分析，而S盒是非线性的

  • 压缩后的子密钥KiK_i与扩展分组异或以后得到48位的数据，将这个数据送入S盒，进行替代运算。替代由8个不同的S盒完成，每个S盒有6位输入4位输出。48位输入分为8个6位的分组，一个分组对应一个S盒，对应的S盒对各组进行代替操作
  • 一个S盒就是一个4行16列的表，盒中的每一项都是一个4位的数。S盒的6个输入确定了其对应的输出在哪一行哪一列，输入的高低两位做为行数H，中间四位做为列数L，在S-BOX中查找第H行L列对应的数据(<32)
image-20210223225040815 image-20210223234547147
  • 例如S1输入为101100，则行数和列数的二进制表示分别是10和1100，即第2行和第6列，然后去查S1盒对应的表，将查得数据转换位4位二进制数，依次类推，得到代换后的32比特
image-20210225141837885
P盒置换

image-20210225142516102

  • S盒代替运算的32位输出按照置换表进行置换。该置换把输入的每位映射到输出位，任何一位不能被映射两次，也不能被略去

  • 表中的数字代表原数据中此位置的数据在新数据中的位置，即原数据块的第16位放到新数据的第1位，第7位放到第2位，……依此类推，第25位放到第32位

  • 最后，置换的结果与最初的64位分组左半部分L0异或，然后左、右半部分交换，接着开始下一轮


IP逆置换


  • 逆置换是初始置换的逆过程，DES最后一轮后，左、右两半部分并未进行交换，而是两部分合并形成一个分组做为末置换的输入
image-20210223235452542
  • 表中的数字代表原数据中此位置的数据在新数据中的位置，即原数据块的第40位放到新数据的第1位，第8位放到第2位，……依此类推，第25位放到第64位

我们知道DES算法的第一步就是对明文进行分组，每一组64位，然后进行分组加密，这里就会出现两个问题

  • 对于每一个分组如何去使用密码算法组成整个密文，这就是我们要讨论的分组密码工作模式
  • 要加密的密文不一定都是64的倍数，那么当最后一个分组不足64位如何填充

DES解密


DES是一种对称密码算法，解密不是加密的逆序，而是使用同样的加密步骤，使用次序相反加密密钥。如果各轮加密密钥分别是{K1，K2，K3…K16}\{K_1，K_2，K_3…K_{16}\}，那么解密密钥就是{K16，K15，K14…K1}\{K_{16}，K_{15}，K_{14}…K_1\}


分组密码工作模式


接下来我们介绍两种常见的分组密码工作模式：ECB和CBC模式。除此以外，还有CFB、OFB和计数器模式，这里先不做介绍


电码本模式（ECB）

ECB模式对划分出的每一组使用DES加密，然后将这些密文进行组合即完成整段明文的加密

image-20210225144507226
  • 优点：实现简单，不同明文分组的加密可并行实施，硬件实施速度很快
  • 缺点：相同的明文分组对应相同的密文分组，不能隐藏铭文分组的统计规律和结构规律，不能抵抗替换攻击

密码分组链接模式（CBC）

这种模式先将明文分组与上一次的密文块进行按比特异或，然后再进行加密处理。这种模式必须选择一个初始8Byte的向量IV，用于加密第一块明文

image-20210225145037172
  • 优点：明文块的统计特性得到了隐蔽，各密文块不仅与当前明文块有关，而且还与以前的明文块及初始化向量有关，从而使明文的统计规律在密文中得到了较好的隐藏
  • 缺点：整个加密的过程是串行的，效率低于ECB模式

分组密码填充方式


NoPadding

不做任何填充，但是要求明文必须是8字节（AES加密16字节）的整数倍


PKCS5Padding（default）

如果明文块少于8个字节（64bit），在明文块末尾补足相应数量的字符，每个字节的值等于缺少的字符数

比如明文：{1,2,3,4,5}\{1,2,3,4,5\}，缺少2个字节，则补全为{1,2,3,4,5,2,2}\{1,2,3,4,5,2,2\}


ISO10126Padding

如果明文块少于8个字节（64bit），在明文块末尾补足相应数量的字节，最后一个字符值等于缺少的字符数，其他字符填充随机数

比如明文：{1,2,3,4,5}\{1,2,3,4,5\}，缺少2个字节，则可能补全为{1,2,3,4,5,a,b}\{1,2,3,4,5,a,b\}


DES in Java

/*
 * @Author: Kay_Rick@outlook.com
 * @Date: 2021-02-24 14:14:39
 * @LastEditors: Kay_Rick@outlook.com
 * @LastEditTime: 2021-02-25 22:07:13
 * @Description: DESEncryptionExample
 */
package Crypt;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.security.InvalidAlgorithmParameterException;
import java.security.InvalidKeyException;
import java.security.NoSuchAlgorithmException;
import java.security.spec.AlgorithmParameterSpec;

import javax.crypto.Cipher;
import javax.crypto.CipherInputStream;
import javax.crypto.CipherOutputStream;
import javax.crypto.KeyGenerator;
import javax.crypto.NoSuchPaddingException;
import javax.crypto.SecretKey;
import javax.crypto.spec.IvParameterSpec;

public class DESEncryptionExample {
    private static Cipher encryptCipher;
    private static Cipher decryptCipher;
    // DES 8Byte paramters
    private static final byte[] iv = { 11, 22, 33, 44, 99, 88, 77, 66};

    public static void main(String[] args) {
        String clearTextFile = "D:\\Server\\Cryption\\source.txt";
        String cipherTextFile = "D:\\Server\\Cryption\\cipher.txt";
        String clearTextNewFile = "D:\\Server\\Cryption\\source-new.txt";

        try {
            // create SecretKey using KeyGenerator
            SecretKey key = KeyGenerator.getInstance("DES").generateKey();
            // create iv parameter using CBC encrypt mode,
            // default ECB encrypt mode does not need iv parameters
            AlgorithmParameterSpec paramSpec = new IvParameterSpec(iv);

            // get Cipher instance and initiate in encrypt mode
            // this cipher instance using CBC encrypt mode and padding 8Byte when the datablock less than 8Byte
            encryptCipher = Cipher.getInstance("DES/CBC/PKCS5Padding");
            encryptCipher.init(Cipher.ENCRYPT_MODE, key, paramSpec);

            // get Cipher instance and initiate in decrypt mode
            decryptCipher = Cipher.getInstance("DES/CBC/PKCS5Padding");
            decryptCipher.init(Cipher.DECRYPT_MODE, key, paramSpec);

            // method to encrypt clear text file to encrypted file
            encrypt(new FileInputStream(clearTextFile), new FileOutputStream(cipherTextFile));

            // method to decrypt encrypted file to clear text file
            decrypt(new FileInputStream(cipherTextFile), new FileOutputStream(clearTextNewFile));
            System.out.println("done");
        } catch (NoSuchAlgorithmException | NoSuchPaddingException | InvalidKeyException
                | InvalidAlgorithmParameterException | IOException e) {
            e.printStackTrace();
        }
    }

    private static void encrypt(InputStream is, OutputStream os) throws IOException {
        // create CipherOutputStream to encrypt the data using encryptCipher
        os = new CipherOutputStream(os, encryptCipher);
        writeData(is, os);
    }

    private static void decrypt(InputStream is, OutputStream os) throws IOException {
        // create CipherOutputStream to decrypt the data using decryptCipher
        is = new CipherInputStream(is, decryptCipher);
        writeData(is, os);
    }

    // utility method to read data from input stream and write to output stream
    private static void writeData(InputStream is, OutputStream os) throws IOException {
        byte[] buf = new byte[1024];
        int numRead = 0;
        // read and write operation
        while ((numRead = is.read(buf)) >= 0) {
            os.write(buf, 0, numRead);
        }
        os.close();
        is.close();
    }

}
赞赏
# Cryptography
深入理解AES加密算法 上一篇
找父亲-并查集算法 下一篇
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%