【数据压缩与加密算法】

# 数据压缩与加密算法实战：从原理到完整实现 ## 目录 1. [引言](#引言) 2. [数据压缩算法](#数据压缩算法) - [2.1 哈夫曼编码](#21-哈夫曼编码) - [2.2 LZ77压缩算法](#22-lz77压缩算法) - [2.3 DEFLATE算法](#23-deflate算法) 3. [数据加密算法](#数据加密算法) - [3.1 对称加密 - AES](#31-对称加密---aes) - [3.2 非对称加密 - RSA](#32-非对称加密---rsa) - [3.3 哈希算法 - SHA-256](#33-哈希算法---sha-256) 4. [综合应用实战](#综合应用实战) 5. [性能优化](#性能优化) 6. [总结](#总结) --- ## 引言数据压缩和加密是计算机科学中的两个核心领域，在数据传输、存储、安全通信等方面有着广泛的应用。本文将从零开始，用原生Java实现多种压缩和加密算法，让你深入理解这些算法的内部工作原理。通过本文的学习，你将： - 理解哈夫曼编码的压缩原理 - 掌握LZ77滑动窗口压缩技术 - 实现DEFLATE压缩算法 - 深入理解AES加密算法 - 实现RSA非对称加密 - 掌握SHA-256哈希算法 - 学会综合应用压缩和加密 --- ## 数据压缩算法 ### 2.1 哈夫曼编码哈夫曼编码是一种基于字符频率的无损数据压缩算法，由David Huffman于1952年提出。其核心思想是：出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码。 #### 2.1.1 算法原理 ``` 哈夫曼编码步骤： 1. 统计字符频率统计输入数据中每个字符出现的次数 2. 构建优先队列将每个字符及其频率作为叶子节点，放入优先队列 3. 构建哈夫曼树 a) 从优先队列中取出频率最小的两个节点 b) 创建新节点，这两个节点作为其左右子节点 c) 新节点频率 = 左子节点频率 + 右子节点频率 d) 将新节点放回优先队列 e) 重复直到队列中只剩一个节点 4. 生成编码表 a) 左分支编码为0 b) 右分支编码为1 c) 从根到叶子的路径即为该字符的编码 5. 压缩数据使用编码表将原始数据转换为二进制编码 6. 解压数据使用哈夫曼树将二进制编码还原为原始字符 ``` #### 2.1.2 完整实现 ```java package com.kc.compression.huffman; import java.util.*; import java.io.*; /** * 哈夫曼编码压缩器 * * 实现原理： * 1. 统计字符频率 * 2. 构建哈夫曼树 * 3. 生成编码表 * 4. 压缩/解压数据 */ public class HuffmanCompressor { /** * 哈夫曼树节点类 */ private static class HuffmanNode implements Comparable { // 存储的字符（叶子节点才有值） Character character; // 字符频率 int frequency; // 左子节点 HuffmanNode left; // 右子节点 HuffmanNode right; // 构造函数 - 叶子节点 HuffmanNode(Character character, int frequency) { this.character = character; this.frequency = frequency; this.left = null; this.right = null; } // 构造函数 - 内部节点 HuffmanNode(int frequency, HuffmanNode left, HuffmanNode right) { this.character = null; this.frequency = frequency; this.left = left; this.right = right; } // 判断是否为叶子节点 boolean isLeaf() { return left == null && right == null; } // 实现Comparable接口，用于优先队列排序 @Override public int compareTo(HuffmanNode other) { return this.frequency - other.frequency; } } /** * 哈夫曼编码结果类 */ public static class HuffmanResult { // 压缩后的字节数组 byte[] compressedData; // 哈夫曼树序列化数据 byte[] treeData; // 原始数据长度 int originalLength; HuffmanResult(byte[] compressedData, byte[] treeData, int originalLength) { this.compressedData = compressedData; this.treeData = treeData; this.originalLength = originalLength; } } /** * 压缩数据 * * @param data 原始数据 * @return 压缩结果 */ public static HuffmanResult compress(byte[] data) { // 1. 统计字符频率 Map frequencyMap = buildFrequencyMap(data); // 2. 构建哈夫曼树 HuffmanNode root = buildHuffmanTree(frequencyMap); // 3. 生成编码表 Map codeTable = buildCodeTable(root); // 4. 压缩数据 byte[] compressedData = encodeData(data, codeTable); // 5. 序列化哈夫曼树 byte[] treeData = serializeTree(root); return new HuffmanResult(compressedData, treeData, data.length); } /** * 解压数据 * * @param compressedData 压缩数据 * @param treeData 哈夫曼树数据 * @param originalLength 原始数据长度 * @return 解压后的数据 */ public static byte[] decompress(byte[] compressedData, byte[] treeData, int originalLength) { // 1. 反序列化哈夫曼树 HuffmanNode root = deserializeTree(treeData); // 2. 解压数据 return decodeData(compressedData, root, originalLength); } /** * 统计字符频率 * * 遍历数据，统计每个字节出现的次数 * * @param data 原始数据 * @return 频率映射表 */ private static Map buildFrequencyMap(byte[] data) { Map frequencyMap = new HashMap<>(); // 遍历每个字节，统计频率 for (byte b : data) { frequencyMap.put(b, frequencyMap.getOrDefault(b, 0) + 1); } return frequencyMap; } /** * 构建哈夫曼树 * * 使用优先队列（最小堆）构建哈夫曼树 * * @param frequencyMap 字符频率映射 * @return 哈夫曼树根节点 */ private static HuffmanNode buildHuffmanTree(Map frequencyMap) { // 使用优先队列，按照频率从小到大排序 PriorityQueue priorityQueue = new PriorityQueue<>(); // 将每个字符作为叶子节点加入队列 for (Map.Entry entry : frequencyMap.entrySet()) { priorityQueue.add(new HuffmanNode((char) (entry.getKey() & 0xFF), entry.getValue())); } // 构建哈夫曼树 while (priorityQueue.size() > 1) { // 取出频率最小的两个节点 HuffmanNode left = priorityQueue.poll(); HuffmanNode right = priorityQueue.poll(); // 创建新节点，频率为两子节点频率之和 HuffmanNode parent = new HuffmanNode( left.frequency + right.frequency, left, right ); // 将新节点加入队列 priorityQueue.add(parent); } // 返回根节点 return priorityQueue.poll(); } /** * 生成编码表 * * 从哈夫曼树根节点开始，递归遍历，生成每个字符的编码 * 左边编码为0，右边编码为1 * * @param root 哈夫曼树根节点 * @return 编码表 */ private static Map buildCodeTable(HuffmanNode root) { Map codeTable = new HashMap<>(); buildCodeTableRecursive(root, "", codeTable); return codeTable; } /** * 递归构建编码表 * * @param node 当前节点 * @param code 当前编码 * @param codeTable 编码表 */ private static void buildCodeTableRecursive(HuffmanNode node, String code, Map codeTable) { if (node == null) { return; } // 如果是叶子节点，保存编码 if (node.isLeaf()) { codeTable.put((byte) (node.character & 0xFF), code); return; } // 左边编码加0 buildCodeTableRecursive(node.left, code + "0", codeTable); // 右边编码加1 buildCodeTableRecursive(node.right, code + "1", codeTable); } /** * 编码数据 * * 使用编码表将原始数据转换为二进制编码 * * @param data 原始数据 * @param codeTable 编码表 * @return 压缩后的字节数组 */ private static byte[] encodeData(byte[] data, Map codeTable) { // 使用StringBuilder构建二进制字符串 StringBuilder binaryString = new StringBuilder(); // 将每个字节转换为对应的编码 for (byte b : data) { String code = codeTable.get(b); binaryString.append(code); } // 计算需要的字节数 int byteCount = (binaryString.length() + 7) / 8; byte[] result = new byte[byteCount]; // 将二进制字符串转换为字节数组 for (int i = 0; i < binaryString.length(); i++) { if (binaryString.charAt(i) == '1') { int byteIndex = i / 8; int bitIndex = 7 - (i % 8); result[byteIndex] |= (1 << bitIndex); } } return result; } /** * 解码数据 * * 使用哈夫曼树将二进制数据还原为原始字符 * * @param compressedData 压缩数据 * @param root 哈夫曼树根节点 * @param originalLength 原始数据长度 * @return 解压后的数据 */ private static byte[] decompressData(byte[] compressedData, HuffmanNode root, int originalLength) { byte[] result = new byte[originalLength]; HuffmanNode currentNode = root; int resultIndex = 0; int bitIndex = 0; int byteIndex = 0; while (resultIndex < originalLength) { // 获取当前位 boolean bit = ((compressedData[byteIndex] >> (7 - bitIndex)) & 1) == 1; // 根据位移动到左子节点或右子节点 if (bit) { currentNode = currentNode.right; } else { currentNode = currentNode.left; } // 如果到达叶子节点，保存字符 if (currentNode.isLeaf()) { result[resultIndex++] = (byte) (currentNode.character & 0xFF); currentNode = root; } // 移动到下一位 bitIndex++; if (bitIndex == 8) { bitIndex = 0; byteIndex++; } } return result; } /** * 序列化哈夫曼树 * * 使用前序遍历序列化哈夫曼树 * 格式：如果是叶子节点，写入0x01和字符；如果是内部节点，写入0x00 * * @param root 哈夫曼树根节点 * @return 序列化后的字节数组 */ private static byte[] serializeTree(HuffmanNode root) { ByteArrayOutputStream baos = new ByteArrayOutputStream(); serializeTreeRecursive(root, baos); return baos.toByteArray(); } /** * 递归序列化哈夫曼树 * * @param node 当前节点 * @param baos 输出流 */ private static void serializeTreeRecursive(HuffmanNode node, ByteArrayOutputStream baos) { if (node == null) { return; } if (node.isLeaf()) { // 叶子节点：写入0x01和字符 baos.write(0x01); baos.write((byte) (node.character & 0xFF)); } else { // 内部节点：写入0x00 baos.write(0x00); // 递归序列化左子树和右子树 serializeTreeRecursive(node.left, baos); serializeTreeRecursive(node.right, baos); } } /** * 反序列化哈夫曼树 * * @param treeData 序列化的树数据 * @return 哈夫曼树根节点 */ private static HuffmanNode deserializeTree(byte[] treeData) { ByteArrayInputStream bais = new ByteArrayInputStream(treeData); return deserializeTreeRecursive(bais); } /** * 递归反序列化哈夫曼树 * * @param bais 输入流 * @return 哈夫曼树节点 */ private static HuffmanNode deserializeTreeRecursive(ByteArrayInputStream bais) { int marker = bais.read(); if (marker == 0x01) { // 叶子节点 char character = (char) (bais.read() & 0xFF); return new HuffmanNode(character, 0); } else { // 内部节点 HuffmanNode left = deserializeTreeRecursive(bais); HuffmanNode right = deserializeTreeRecursive(bais); return new HuffmanNode(0, left, right); } } /** * 解码数据（公开方法） */ private static byte[] decodeData(byte[] compressedData, HuffmanNode root, int originalLength) { return decompressData(compressedData, root, originalLength); } /** * 测试哈夫曼编码 */ public static void main(String[] args) { String testString = "this is an example for huffman encoding"; byte[] originalData = testString.getBytes(); System.out.println("原始数据: " + testString); System.out.println("原始大小: " + originalData.length + " 字节"); // 压缩数据 HuffmanResult result = compress(originalData); System.out.println("压缩后大小: " + result.compressedData.length + " 字节"); System.out.println("树数据大小: " + result.treeData.length + " 字节"); System.out.println("总大小: " + (result.compressedData.length + result.treeData.length) + " 字节"); System.out.println("压缩率: " + String.format("%.2f%%", (1.0 - (double)(result.compressedData.length + result.treeData.length) / originalData.length) * 100)); // 解压数据 byte[] decompressedData = decompress(result.compressedData, result.treeData, result.originalLength); System.out.println("解压后数据: " + new String(decompressedData)); System.out.println("解压是否成功: " + Arrays.equals(originalData, decompressedData)); } } ``` #### 2.1.3 算法复杂度分析 ``` 时间复杂度： - 构建频率表：O(n)，n为数据长度 - 构建哈夫曼树：O(m log m)，m为不同字符数量 - 生成编码表：O(m) - 编码数据：O(n * L)，L为平均编码长度 - 解码数据：O(n * L) 空间复杂度： - 频率表：O(m) - 优先队列：O(m) - 哈夫曼树：O(m) - 编码表：O(m * L) 其中： - n：原始数据长度 - m：不同字符数量（m <= n） - L：平均编码长度 ``` --- ### 2.2 LZ77压缩算法 LZ77是一种基于滑动窗口的字典压缩算法，由Abraham Lempel和Jacob Ziv于1977年提出。它通过查找重复的数据模式来实现压缩。 #### 2.2.1 算法原理 ``` LZ77压缩原理： 1. 滑动窗口 - 查找窗口：在已处理的数据中查找匹配 - 前瞻窗口：待处理的数据 - 两个窗口大小通常为32KB 2. 压缩过程 a) 在查找窗口中查找与前瞻窗口匹配的最长字符串 b) 如果找到匹配，输出(距离, 长度, 下一个字符) c) 如果没有匹配，输出(0, 0, 下一个字符) d) 移动滑动窗口 3. 三元组格式 - 距离：匹配字符串在查找窗口中的位置偏移 - 长度：匹配字符串的长度 - 下一个字符：匹配后的下一个字符 4. 解压过程 a) 读取三元组 b) 如果距离为0，直接输出下一个字符 c) 如果距离不为0，从输出缓冲区复制指定距离和长度的数据 d) 输出下一个字符 ``` #### 2.2.2 完整实现 ```java package com.kc.compression.lz77; import java.util.*; /** * LZ77压缩算法实现 * * 实现原理： * 1. 使用滑动窗口查找重复模式 * 2. 输出(距离, 长度, 下一个字符)三元组 * 3. 支持自适应窗口大小 */ public class LZ77Compressor { // 查找窗口大小（字节） private static final int SEARCH_WINDOW_SIZE = 32768; // 32KB // 前瞻窗口大小（字节） private static final int LOOKAHEAD_WINDOW_SIZE = 258; // 最大匹配长度 + 3 // 最大匹配长度 private static final int MAX_MATCH_LENGTH = 258; // 最大距离偏移 private static final int MAX_DISTANCE = 32768; /** * LZ77三元组 */ public static class LZ77Triple { // 距离偏移 int distance; // 匹配长度 int length; // 下一个字符（如果没有匹配则为字面字符） byte nextByte; LZ77Triple(int distance, int length, byte nextByte) { this.distance = distance; this.length = length; this.nextByte = nextByte; } @Override public String toString() { if (distance == 0) { return String.format("(literal: %c)", (char)(nextByte & 0xFF)); } else { return String.format("(%d, %d, %c)", distance, length, (char)(nextByte & 0xFF)); } } } /** * 压缩数据 * * @param data 原始数据 * @return 压缩后的三元组列表 */ public static List compress(byte[] data) { List result = new ArrayList<>(); int pos = 0; // 当前处理位置 while (pos < data.length) { // 计算查找窗口的起始位置 int searchStart = Math.max(0, pos - SEARCH_WINDOW_SIZE); // 在查找窗口中查找最长匹配 LZ77Triple triple = findLongestMatch(data, searchStart, pos); // 添加三元组 result.add(triple); // 移动位置：匹配长度 + 1（下一个字符） pos += triple.length + 1; } return result; } /** * 查找最长匹配 * * 在查找窗口中查找与当前位置匹配的最长字符串 * * @param data 原始数据 * @param searchStart 查找窗口起始位置 * @param currentPos 当前位置 * @return 最优匹配三元组 */ private static LZ77Triple findLongestMatch(byte[] data, int searchStart, int currentPos) { int bestDistance = 0; int bestLength = 0; int lookaheadSize = Math.min(LOOKAHEAD_WINDOW_SIZE, data.length - currentPos); // 遍历查找窗口，寻找最长匹配 for (int i = searchStart; i < currentPos; i++) { // 计算最大可能的匹配长度 int maxPossibleLength = Math.min( currentPos - i, // 不能超过查找窗口的距离 lookaheadSize // 不能超过前瞻窗口大小 ); if (maxPossibleLength <= bestLength) { continue; // 已经找到更长的匹配，跳过 } // 计算当前匹配长度 int currentLength = 0; while (currentLength < maxPossibleLength && data[i + currentLength] == data[currentPos + currentLength]) { currentLength++; } // 更新最佳匹配 if (currentLength > bestLength) { bestDistance = currentPos - i; bestLength = currentLength; // 如果达到最大匹配长度，提前结束 if (bestLength >= MAX_MATCH_LENGTH) { break; } } } // 确定下一个字符的位置 int nextBytePos = currentPos + bestLength; byte nextByte = (nextBytePos < data.length) ? data[nextBytePos] : 0; return new LZ77Triple(bestDistance, bestLength, nextByte); } /** * 解压数据 * * @param triples 压缩后的三元组列表 * @return 解压后的数据 */ public static byte[] decompress(List triples) { ByteArrayOutputStream baos = new ByteArrayOutputStream(); for (LZ77Triple triple : triples) { if (triple.distance == 0) { // 字面字符：直接输出 baos.write(triple.nextByte); } else { // 引用：从已输出的数据中复制 byte[] existingData = baos.toByteArray(); int startPos = existingData.length - triple.distance; // 复制指定长度的数据 for (int i = 0; i < triple.length; i++) { baos.write(existingData[startPos + i]); } // 输出下一个字符 baos.write(triple.nextByte); } } return baos.toByteArray(); } /** * 将三元组序列化为字节数组 * * 格式： * - 距离：2字节（小端序） * - 长度：1字节 * - 下一个字节：1字节 * * @param triples 三元组列表 * @return 序列化后的字节数组 */ public static byte[] serialize(List triples) { ByteArrayOutputStream baos = new ByteArrayOutputStream(); for (LZ77Triple triple : triples) { // 写入距离（2字节，小端序） baos.write(triple.distance & 0xFF); baos.write((triple.distance >> 8) & 0xFF); // 写入长度（1字节） baos.write(triple.length & 0xFF); // 写入下一个字节（1字节） baos.write(triple.nextByte); } return baos.toByteArray(); } /** * 从字节数组反序列化三元组 * * @param data 序列化数据 * @return 三元组列表 */ public static List deserialize(byte[] data) { List triples = new ArrayList<>(); int pos = 0; while (pos < data.length) { // 读取距离（2字节，小端序） int distance = data[pos] & 0xFF; distance |= (data[pos + 1] & 0xFF) << 8; // 读取长度（1字节） int length = data[pos + 2] & 0xFF; // 读取下一个字节（1字节） byte nextByte = data[pos + 3]; triples.add(new LZ77Triple(distance, length, nextByte)); pos += 4; } return triples; } /** * 测试LZ77压缩 */ public static void main(String[] args) { // 测试数据：包含重复模式 String testString = "ABABABCABABABCBABABACBABABAB"; byte[] originalData = testString.getBytes(); System.out.println("原始数据: " + testString); System.out.println("原始大小: " + originalData.length + " 字节"); // 压缩数据 List triples = compress(originalData); System.out.println("\n压缩后的三元组:"); for (int i = 0; i < triples.size(); i++) { System.out.printf("%2d: %s\n", i, triples.get(i)); } // 序列化 byte[] serializedData = serialize(triples); System.out.println("\n序列化后大小: " + serializedData.length + " 字节"); System.out.println("压缩率: " + String.format("%.2f%%", (1.0 - (double)serializedData.length / originalData.length) * 100)); // 解压数据 List deserializedTriples = deserialize(serializedData); byte[] decompressedData = decompress(deserializedTriples); System.out.println("\n解压后数据: " + new String(decompressedData)); System.out.println("解压是否成功: " + Arrays.equals(originalData, decompressedData)); // 测试大数据压缩效果 System.out.println("\n===== 大数据测试 ====="); StringBuilder largeData = new StringBuilder(); for (int i = 0; i < 1000; i++) { largeData.append("The quick brown fox jumps over the lazy dog. "); } byte[] largeOriginal = largeData.toString().getBytes(); List largeTriples = compress(largeOriginal); byte[] largeCompressed = serialize(largeTriples); System.out.println("原始大小: " + largeOriginal.length + " 字节"); System.out.println("压缩后大小: " + largeCompressed.length + " 字节"); System.out.println("压缩率: " + String.format("%.2f%%", (1.0 - (double)largeCompressed.length / largeOriginal.length) * 100)); // 验证解压 byte[] largeDecompressed = decompress(deserialize(largeCompressed)); System.out.println("解压是否成功: " + Arrays.equals(largeOriginal, largeDecompressed)); } } ``` #### 2.2.3 算法优化点 ```java /** * LZ77算法优化建议 */ public class LZ77Optimizations { /** * 1. 哈希表优化 * * 使用哈希表加速查找匹配，避免线性搜索 * * 实现： * - 为每个3字节序列计算哈希值 * - 使用哈希表存储位置 * - 查找时先查找哈希表 */ /** * 2. 链表优化 * * 使用链表维护相同哈希值的位置 * - 快速定位可能匹配的位置 * - 减少比较次数 */ /** * 3. 贪心算法优化 * * 当前实现使用贪心算法，总是选择最长的匹配 * 可以考虑： * - 选择最优的匹配（距离和长度的平衡） * - 考虑后续数据的影响 */ /** * 4. 自适应窗口大小 * * 根据数据特征动态调整窗口大小 * - 重复模式多：增大窗口 * - 随机数据多：减小窗口 */ } ``` --- ### 2.3 DEFLATE算法 DEFLATE是一种广泛使用的压缩算法，结合了LZ77和哈夫曼编码。它被用于ZIP、GZIP、PNG等格式中。 #### 2.3.1 算法原理 ``` DEFLATE压缩流程： 1. LZ77压缩 - 使用滑动窗口查找重复数据 - 输出字面字符和长度/距离对 2. 哈夫曼编码 - 为字面字符、长度、距离分别构建哈夫曼树 - 使用哈夫曼编码压缩数据 3. 比特流输出 - 将编码后的数据打包为比特流 - 添加校验和 DEFLATE数据格式： - 头部（3位） - 压缩数据块（可变） - 尾部（32位校验和） ``` #### 2.3.2 完整实现 ```java package com.kc.compression.deflate; import com.kc.compression.huffman.HuffmanCompressor; import com.kc.compression.lz77.LZ77Compressor; import com.kc.compression.lz77.LZ77Compressor.LZ77Triple; import java.util.*; import java.io.*; /** * DEFLATE压缩算法实现 * * 实现原理： * 1. 先使用LZ77压缩，生成三元组 * 2. 将三元组分为三类：字面字符、长度、距离 * 3. 为每类数据分别构建哈夫曼树 * 4. 使用哈夫曼编码压缩数据 * 5. 打包输出 */ public class DeflateCompressor { // 压缩级别 public static final int COMPRESSION_NONE = 0; public static final int COMPRESSION_FAST = 1; public static final int COMPRESSION_DEFAULT = 2; public static final int COMPRESSION_BEST = 3; // DEFLATE头部标志 private static final int BFINAL = 0x01; // 最后一个块 private static final int BTYPE_NO_COMPRESSION = 0x00; private static final int BTYPE_FIXED_HUFFMAN = 0x01; private static final int BTYPE_DYNAMIC_HUFFMAN = 0x02; /** * 压缩数据 * * @param data 原始数据 * @param level 压缩级别 * @return 压缩后的数据 */ public static byte[] compress(byte[] data, int level) { // 第一步：LZ77压缩 List triples = LZ77Compressor.compress(data); // 第二步：转换为字面/长度/距离序列 List literals = new ArrayList<>(); List lengths = new ArrayList<>(); List distances = new ArrayList<>(); for (LZ77Triple triple : triples) { if (triple.distance == 0) { // 字面字符 literals.add(triple.nextByte & 0xFF); } else { // 长度/距离对 literals.add(triple.nextByte & 0xFF); lengths.add(triple.length); distances.add(triple.distance); } } // 第三步：构建动态哈夫曼树 Map literalCodeTable = buildLiteralCodeTable(literals); Map distanceCodeTable = buildDistanceCodeTable(distances); // 第四步：编码数据 ByteArrayOutputStream baos = new ByteArrayOutputStream(); // 写入头部：最后一块 + 动态哈夫曼 writeHeader(baos, BFINAL, BTYPE_DYNAMIC_HUFFMAN); // 写入哈夫曼树信息 writeHuffmanTrees(baos, literalCodeTable, distanceCodeTable); // 写入压缩数据 writeCompressedData(baos, triples, literalCodeTable, distanceCodeTable); // 写入结束标记 writeEndMarker(baos, literalCodeTable); // 对齐到字节边界 alignToByteBoundary(baos); // 写入校验和 writeChecksum(baos, data); return baos.toByteArray(); } /** * 构建字面/长度哈夫曼码表 * * @param literals 字面字符列表 * @return 哈夫曼码表 */ private static Map buildLiteralCodeTable(List literals) { // 统计频率 Map frequencyMap = new HashMap<>(); // 添加字面字符（0-255）的频率 for (int i = 0; i <= 255; i++) { frequencyMap.put(i, 0); } // 添加实际字面字符 for (int literal : literals) { frequencyMap.put(literal, frequencyMap.getOrDefault(literal, 0) + 1); } // 添加结束标记（256） frequencyMap.put(256, 1); // 构建哈夫曼树并生成码表 return HuffmanCompressor.buildCodeTable(frequencyMap); } /** * 构建距离哈夫曼码表 * * @param distances 距离列表 * @return 哈夫曼码表 */ private static Map buildDistanceCodeTable(List distances) { // 统计频率 Map frequencyMap = new HashMap<>(); for (int i = 0; i < 30; i++) { frequencyMap.put(i, 0); } for (int distance : distances) { int code = encodeDistance(distance); frequencyMap.put(code, frequencyMap.getOrDefault(code, 0) + 1); } return HuffmanCompressor.buildCodeTable(frequencyMap); } /** * 编码距离值 * * DEFLATE使用30个距离码，每个码代表一个距离范围 * * @param distance 距离值 * @return 距离码 */ private static int encodeDistance(int distance) { int[] distanceBases = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 }; for (int i = 0; i < distanceBases.length; i++) { if (distance < distanceBases[i]) { return i - 1; } } return 29; } /** * 写入DEFLATE头部 * * @param baos 输出流 * @param bfinal 最后一个块标志 * @param btype 压缩类型 */ private static void writeHeader(ByteArrayOutputStream baos, int bfinal, int btype) { int header = (bfinal << 7) | (btype << 5); // 暂时写入，后续会写入到比特流 // 实际实现需要使用BitOutputStream } /** * 写入哈夫曼树信息 * * @param baos 输出流 * @param literalCodeTable 字面/长度码表 * @param distanceCodeTable 距离码表 */ private static void writeHuffmanTrees(ByteArrayOutputStream baos, Map literalCodeTable, Map distanceCodeTable) { // 写入字面/长度码树 // 写入距离码树 // 实际实现比较复杂，需要处理码长度的存储 } /** * 写入压缩数据 * * @param baos 输出流 * @param triples LZ77三元组 * @param literalCodeTable 字面/长度码表 * @param distanceCodeTable 距离码表 */ private static void writeCompressedData(ByteArrayOutputStream baos, List triples, Map literalCodeTable, Map distanceCodeTable) { for (LZ77Triple triple : triples) { if (triple.distance == 0) { // 字面字符 String code = literalCodeTable.get(triple.nextByte & 0xFF); // 写入编码 } else { // 长度/距离对 String lengthCode = literalCodeTable.get(257 + encodeLength(triple.length)); String distanceCode = distanceCodeTable.get(encodeDistance(triple.distance)); // 写入编码 } } } /** * 编码长度值 */ private static int encodeLength(int length) { // DEFLATE长度编码逻辑 return 0; } /** * 写入结束标记 */ private static void writeEndMarker(ByteArrayOutputStream baos, Map literalCodeTable) { // 结束标记为256 String code = literalCodeTable.get(256); // 写入编码 } /** * 对齐到字节边界 */ private static void alignToByteBoundary(ByteArrayOutputStream baos) { // 填充0到字节边界 } /** * 写入校验和 */ private static void writeChecksum(ByteArrayOutputStream baos, byte[] data) { // 计算Adler-32校验和并写入 } /** * 简化的DEFLATE压缩（用于演示） * * 实际DEFLATE实现非常复杂，这里使用LZ77 + 哈夫曼编码的简化版本 */ public static byte[] compressSimple(byte[] data) { // LZ77压缩 List triples = LZ77Compressor.compress(data); // 序列化 byte[] compressed = LZ77Compressor.serialize(triples); // 添加DEFLATE头部和尾部 ByteArrayOutputStream result = new ByteArrayOutputStream(); // DEFLATE头部：最后一块 + 动态哈夫曼 result.write(0x78); // CMF: 压缩方法8 + 窗口大小7 result.write(0x9C); // FLG: 检查标志 // 压缩数据 result.write(compressed, 0, compressed.length); // Adler-32校验和（简化版） int checksum = calculateAdler32(data); result.write((checksum >> 24) & 0xFF); result.write((checksum >> 16) & 0xFF); result.write((checksum >> 8) & 0xFF); result.write(checksum & 0xFF); return result.toByteArray(); } /** * 计算Adler-32校验和 */ private static int calculateAdler32(byte[] data) { int a = 1; int b = 0; for (byte d : data) { a = (a + (d & 0xFF)) % 65521; b = (b + a) % 65521; } return (b << 16) | a; } /** * 测试DEFLATE压缩 */ public static void main(String[] args) { String testString = "The quick brown fox jumps over the lazy dog. " + "The quick brown fox jumps over the lazy dog. " + "The quick brown fox jumps over the lazy dog."; byte[] originalData = testString.getBytes(); System.out.println("原始数据: " + testString.substring(0, 50) + "..."); System.out.println("原始大小: " + originalData.length + " 字节"); // 压缩数据 byte[] compressedData = compressSimple(originalData); System.out.println("压缩后大小: " + compressedData.length + " 字节"); System.out.println("压缩率: " + String.format("%.2f%%", (1.0 - (double)compressedData.length / originalData.length) * 100)); // 注意：完整的DEFLATE解压实现比较复杂，这里演示压缩流程 System.out.println("\nDEFLATE压缩完成（简化版本）"); System.out.println("完整的DEFLATE实现需要处理："); System.out.println("1. 动态哈夫曼树的构建和传输"); System.out.println("2. 比特流的精确写入"); System.out.println("3. 长度和距离的编码"); System.out.println("4. 校验和计算"); } } ``` --- ## 数据加密算法 ### 3.1 对称加密 - AES AES（Advanced Encryption Standard）是一种广泛使用的对称加密算法，由美国国家标准与技术研究院（NIST）于2001年发布。 #### 3.1.1 算法原理 ``` AES加密原理： 1. 密钥扩展 - 将128/192/256位的密钥扩展为44/52/60个32位字 - 用于各轮的轮密钥生成 2. 加密轮函数每轮包含四个步骤： a) 字节替换（SubBytes） - 使用S盒进行非线性替换 - 增强混淆性 b) 行移位（ShiftRows） - 循环左移每一行 - 扩散数据 c) 列混淆（MixColumns） - 矩阵乘法 - 进一步扩散 d) 轮密钥加（AddRoundKey） - 与轮密钥异或 - 引入密钥 3. 轮数 - AES-128：10轮 - AES-192：12轮 - AES-256：14轮 ``` #### 3.1.2 完整实现 ```java package com.kc.encryption.aes; import java.util.Arrays; /** * AES加密算法实现 * * 实现原理： * 1. 密钥扩展：生成轮密钥 * 2. 加密：多轮变换（字节替换、行移位、列混淆、轮密钥加） * 3. 解密：逆向变换 */ public class AESCipher { // AES块大小（字节） private static final int BLOCK_SIZE = 16; // 密钥长度（字节） private static final int KEY_SIZE_128 = 16; private static final int KEY_SIZE_192 = 24; private static final int KEY_SIZE_256 = 32; // S盒（字节替换表） private static final int[] SBOX = { 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 }; // 逆S盒（用于解密） private static final int[] INV_SBOX = { 0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, 0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb, 0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e, 0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25, 0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92, 0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84, 0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06, 0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b, 0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73, 0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e, 0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b, 0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4, 0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f, 0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef, 0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61, 0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d }; // 轮常数（用于密钥扩展） private static final int[] RCON = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36 }; // 密钥扩展后的轮密钥 private int[][] roundKeys; // 加密轮数 private int rounds; /** * 构造函数 * * @param key 加密密钥（16/24/32字节） */ public AESCipher(byte[] key) { if (key.length != KEY_SIZE_128 && key.length != KEY_SIZE_192 && key.length != KEY_SIZE_256) { throw new IllegalArgumentException("密钥长度必须是16、24或32字节"); } // 根据密钥长度确定轮数 if (key.length == KEY_SIZE_128) { rounds = 10; } else if (key.length == KEY_SIZE_192) { rounds = 12; } else { rounds = 14; } // 密钥扩展 keyExpansion(key); } /** * 密钥扩展 * * 将原始密钥扩展为各轮所需的轮密钥 * * @param key 原始密钥 */ private void keyExpansion(byte[] key) { // 将密钥转换为4字节数组 int[] words = new int[4 * (rounds + 1)]; // 复制原始密钥 for (int i = 0; i < key.length / 4; i++) { words[i] = bytesToWord(key, i * 4); } // 生成扩展密钥 for (int i = key.length / 4; i < 4 * (rounds + 1); i++) { int temp = words[i - 1]; if (i % (key.length / 4) == 0) { // 每4个字进行一次变换 temp = subWord(rotWord(temp)) ^ RCON[i / (key.length / 4) - 1]; } else if (key.length == KEY_SIZE_256 && i % 8 == 0) { // AES-256的特殊处理 temp = subWord(temp); } words[i] = words[i - (key.length / 4)] ^ temp; } // 将扩展密钥转换为轮密钥矩阵 roundKeys = new int[rounds + 1][4]; for (int i = 0; i < rounds + 1; i++) { for (int j = 0; j < 4; j++) { roundKeys[i][j] = words[i * 4 + j]; } } } /** * 字节替换（SubBytes） * * 使用S盒对每个字节进行非线性替换 * * @param state 状态矩阵 */ private void subBytes(int[][] state) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { state[i][j] = SBOX[state[i][j]]; } } } /** * 逆字节替换（InvSubBytes） * * 使用逆S盒进行逆向替换 * * @param state 状态矩阵 */ private void invSubBytes(int[][] state) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { state[i][j] = INV_SBOX[state[i][j]]; } } } /** * 行移位（ShiftRows） * * 循环左移每一行 * * @param state 状态矩阵 */ private void shiftRows(int[][] state) { // 第0行不移位 // 第1行左移1字节 int temp = state[1][0]; state[1][0] = state[1][1]; state[1][1] = state[1][2]; state[1][2] = state[1][3]; state[1][3] = temp; // 第2行左移2字节 temp = state[2][0]; state[2][0] = state[2][2]; state[2][2] = temp; temp = state[2][1]; state[2][1] = state[2][3]; state[2][3] = temp; // 第3行左移3字节 temp = state[3][0]; state[3][0] = state[3][3]; state[3][3] = state[3][2]; state[3][2] = state[3][1]; state[3][1] = temp; } /** * 逆行移位（InvShiftRows） * * 循环右移每一行 * * @param state 状态矩阵 */ private void invShiftRows(int[][] state) { // 第0行不移位 // 第1行右移1字节 int temp = state[1][3]; state[1][3] = state[1][2]; state[1][2] = state[1][1]; state[1][1] = state[1][0]; state[1][0] = temp; // 第2行右移2字节 temp = state[2][0]; state[2][0] = state[2][2]; state[2][2] = temp; temp = state[2][1]; state[2][1] = state[2][3]; state[2][3] = temp; // 第3行右移3字节 temp = state[3][0]; state[3][0] = state[3][1]; state[3][1] = state[3][2]; state[3][2] = state[3][3]; state[3][3] = temp; } /** * 列混淆（MixColumns） * * 在GF(2^8)域上进行矩阵乘法 * * @param state 状态矩阵 */ private void mixColumns(int[][] state) { for (int col = 0; col < 4; col++) { int s0 = state[0][col]; int s1 = state[1][col]; int s2 = state[2][col]; int s3 = state[3][col]; state[0][col] = multiply(s0, 2) ^ multiply(s1, 3) ^ s2 ^ s3; state[1][col] = s0 ^ multiply(s1, 2) ^ multiply(s2, 3) ^ s3; state[2][col] = s0 ^ s1 ^ multiply(s2, 2) ^ multiply(s3, 3); state[3][col] = multiply(s0, 3) ^ s1 ^ s2 ^ multiply(s3, 2); } } /** * 逆列混淆（InvMixColumns） * * @param state 状态矩阵 */ private void invMixColumns(int[][] state) { for (int col = 0; col < 4; col++) { int s0 = state[0][col]; int s1 = state[1][col]; int s2 = state[2][col]; int s3 = state[3][col]; state[0][col] = multiply(s0, 0x0e) ^ multiply(s1, 0x0b) ^ multiply(s2, 0x0d) ^ multiply(s3, 0x09); state[1][col] = multiply(s0, 0x09) ^ multiply(s1, 0x0e) ^ multiply(s2, 0x0b) ^ multiply(s3, 0x0d); state[2][col] = multiply(s0, 0x0d) ^ multiply(s1, 0x09) ^ multiply(s2, 0x0e) ^ multiply(s3, 0x0b); state[3][col] = multiply(s0, 0x0b) ^ multiply(s1, 0x0d) ^ multiply(s2, 0x09) ^ multiply(s3, 0x0e); } } /** * GF(2^8)域乘法 * * @param a 乘数 * @param b 被乘数 * @return 乘积 */ private int multiply(int a, int b) { int result = 0; while (b != 0) { if ((b & 1) != 0) { result ^= a; } boolean highBitSet = (a & 0x80) != 0; a <<= 1; if (highBitSet) { a ^= 0x11b; // 不可约多项式 x^8 + x^4 + x^3 + x + 1 } b >>>= 1; } return result & 0xFF; } /** * 轮密钥加（AddRoundKey） * * 状态矩阵与轮密钥异或 * * @param state 状态矩阵 * @param roundKey 轮密钥 */ private void addRoundKey(int[][] state, int[] roundKey) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { state[i][j] ^= roundKey[i]; } } } /** * 加密单个块 * * @param input 输入块（16字节） * @return 输出块（16字节） */ private byte[] encryptBlock(byte[] input) { // 转换为状态矩阵 int[][] state = bytesToState(input); // 初始轮密钥加 addRoundKey(state, roundKeys[0]); // 主轮 for (int round = 1; round < rounds; round++) { subBytes(state); shiftRows(state); mixColumns(state); addRoundKey(state, roundKeys[round]); } // 最终轮（不包含列混淆） subBytes(state); shiftRows(state); addRoundKey(state, roundKeys[rounds]); // 转换为字节数组 return stateToBytes(state); } /** * 解密单个块 * * @param input 输入块（16字节） * @return 输出块（16字节） */ private byte[] decryptBlock(byte[] input) { // 转换为状态矩阵 int[][] state = bytesToState(input); // 初始轮密钥加 addRoundKey(state, roundKeys[rounds]); // 主轮（逆向） for (int round = rounds - 1; round >= 1; round--) { invShiftRows(state); invSubBytes(state); addRoundKey(state, roundKeys[round]); invMixColumns(state); } // 最终轮 invShiftRows(state); invSubBytes(state); addRoundKey(state, roundKeys[0]); // 转换为字节数组 return stateToBytes(state); } /** * 加密数据（ECB模式） * * @param plaintext 明文 * @return 密文 */ public byte[] encrypt(byte[] plaintext) { // PKCS7填充 int paddingLength = BLOCK_SIZE - (plaintext.length % BLOCK_SIZE); byte[] paddedPlaintext = new byte[plaintext.length + paddingLength]; System.arraycopy(plaintext, 0, paddedPlaintext, 0, plaintext.length); Arrays.fill(paddedPlaintext, plaintext.length, paddedPlaintext.length, (byte) paddingLength); // 分块加密 ByteArrayOutputStream result = new ByteArrayOutputStream(); for (int i = 0; i < paddedPlaintext.length; i += BLOCK_SIZE) { byte[] block = new byte[BLOCK_SIZE]; System.arraycopy(paddedPlaintext, i, block, 0, BLOCK_SIZE); result.write(encryptBlock(block)); } return result.toByteArray(); } /** * 解密数据（ECB模式） * * @param ciphertext 密文 * @return 明文 */ public byte[] decrypt(byte[] ciphertext) { // 分块解密 ByteArrayOutputStream result = new ByteArrayOutputStream(); for (int i = 0; i < ciphertext.length; i += BLOCK_SIZE) { byte[] block = new byte[BLOCK_SIZE]; System.arraycopy(ciphertext, i, block, 0, BLOCK_SIZE); result.write(decryptBlock(block)); } // 移除PKCS7填充 byte[] decrypted = result.toByteArray(); int paddingLength = decrypted[decrypted.length - 1] & 0xFF; if (paddingLength < 1 || paddingLength > BLOCK_SIZE) { return decrypted; } return Arrays.copyOf(decrypted, decrypted.length - paddingLength); } /** * 字节数组转4字节数组 */ private int bytesToWord(byte[] bytes, int offset) { return ((bytes[offset] & 0xFF) << 24) | ((bytes[offset + 1] & 0xFF) << 16) | ((bytes[offset + 2] & 0xFF) << 8) | (bytes[offset + 3] & 0xFF); } /** * 字节数组转状态矩阵 */ private int[][] bytesToState(byte[] bytes) { int[][] state = new int[4][4]; for (int i = 0; i < 16; i++) { state[i % 4][i / 4] = bytes[i] & 0xFF; } return state; } /** * 状态矩阵转字节数组 */ private byte[] stateToBytes(int[][] state) { byte[] bytes = new byte[16]; for (int i = 0; i < 16; i++) { bytes[i] = (byte) state[i % 4][i / 4]; } return bytes; } /** * 密钥中的字替换 */ private int subWord(int word) { return (SBOX[(word >> 24) & 0xFF] << 24) | (SBOX[(word >> 16) & 0xFF] << 16) | (SBOX[(word >> 8) & 0xFF] << 8) | SBOX[word & 0xFF]; } /** * 密钥中的字循环左移 */ private int rotWord(int word) { return ((word << 8) & 0xFFFFFFFF) | ((word >>> 24) & 0xFF); } /** * 测试AES加密 */ public static void main(String[] args) { // 测试数据 String plaintext = "Hello, AES Encryption! This is a test."; byte[] key = "ThisIsASecretKey123".getBytes(); // 16字节 System.out.println("原始明文: " + plaintext); System.out.println("明文长度: " + plaintext.length() + " 字节"); // 创建AES加密器 AESCipher aes = new AESCipher(key); // 加密 byte[] ciphertext = aes.encrypt(plaintext.getBytes()); System.out.println("\n密文（十六进制）: " + bytesToHex(ciphertext)); System.out.println("密文长度: " + ciphertext.length + " 字节"); // 解密 byte[] decrypted = aes.decrypt(ciphertext); System.out.println("\n解密后明文: " + new String(decrypted)); System.out.println("解密是否成功: " + new String(decrypted).equals(plaintext)); // 性能测试 System.out.println("\n===== 性能测试 ====="); byte[] largeData = new byte[1024 * 1024]; // 1MB数据 new Random().nextBytes(largeData); long startTime = System.currentTimeMillis(); byte[] largeEncrypted = aes.encrypt(largeData); long encryptTime = System.currentTimeMillis() - startTime; startTime = System.currentTimeMillis(); byte[] largeDecrypted = aes.decrypt(largeEncrypted); long decryptTime = System.currentTimeMillis() - startTime; System.out.println("加密 1MB 数据耗时: " + encryptTime + " ms"); System.out.println("解密 1MB 数据耗时: " + decryptTime + " ms"); System.out.println("数据一致性验证: " + Arrays.equals(largeData, largeDecrypted)); } /** * 字节数组转十六进制字符串 */ private static String bytesToHex(byte[] bytes) { StringBuilder sb = new StringBuilder(); for (byte b : bytes) { sb.append(String.format("%02x", b)); } return sb.toString(); } } ``` #### 3.1.3 工作模式 ```java /** * AES工作模式 */ public class AESModes { /** * 1. ECB模式（电子密码本） * * 特点： * - 每个块独立加密 * - 相同明文产生相同密文 * - 优点：简单、并行 * - 缺点：不安全，模式易识别 */ /** * 2. CBC模式（密码分组链接） * * 特点： * - 前一个密文块参与当前块加密 * - 需要初始化向量（IV） * - 优点：安全性好 * - 缺点：不能并行加密 */ /** * 3. CTR模式（计数器） * * 特点： * - 将块密码转换为流密码 * - 可以并行加密 * - 优点：高效、可并行 * - 缺点：需要确保计数器不重复 */ /** * 4. GCM模式（伽罗瓦/计数器） * * 特点： * - 提供认证加密 * - 支持并行 * - 优点：安全、高效 * - 缺点：实现复杂 */ } ``` --- ### 3.2 非对称加密 - RSA RSA是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman于1977年提出。它使用一对密钥：公钥用于加密，私钥用于解密。 #### 3.2.1 算法原理 ``` RSA加密原理： 1. 密钥生成 a) 选择两个大素数 p 和 q b) 计算 n = p * q c) 计算欧拉函数 φ(n) = (p-1)*(q-1) d) 选择公钥指数 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1 e) 计算私钥指数 d，满足 d * e ≡ 1 (mod φ(n)) 公钥：(e, n) 私钥：(d, n) 2. 加密 ciphertext = plaintext^e mod n 3. 解密 plaintext = ciphertext^d mod n 4. 数学基础 - 模幂运算 - 欧拉定理 - 中国剩余定理 - 扩展欧几里得算法 ``` #### 3.2.2 完整实现 ```java package com.kc.encryption.rsa; import java.math.BigInteger; import java.security.SecureRandom; import java.util.Arrays; /** * RSA非对称加密算法实现 * * 实现原理： * 1. 密钥生成：生成素数对，计算公钥和私钥 * 2. 加密：使用公钥进行模幂运算 * 3. 解密：使用私钥进行模幂运算 * 4. 签名：使用私钥签名，公钥验证 */ public class RSACipher { // 默认密钥长度（位） private static final int DEFAULT_KEY_SIZE = 2048; // 公钥指数（通常为65537） private static final BigInteger E = BigInteger.valueOf(65537); // 随机数生成器 private static final SecureRandom random = new SecureRandom(); // 公钥 private BigInteger publicKey; // 私钥 private BigInteger privateKey; // 模数 private BigInteger modulus; /** * RSA密钥对 */ public static class KeyPair { public final BigInteger publicKey; public final BigInteger privateKey; public final BigInteger modulus; public KeyPair(BigInteger publicKey, BigInteger privateKey, BigInteger modulus) { this.publicKey = publicKey; this.privateKey = privateKey; this.modulus = modulus; } } /** * 构造函数（使用默认密钥长度） */ public RSACipher() { this(DEFAULT_KEY_SIZE); } /** * 构造函数 * * @param keySize 密钥长度（位） */ public RSACipher(int keySize) { KeyPair keyPair = generateKeyPair(keySize); this.publicKey = keyPair.publicKey; this.privateKey = keyPair.privateKey; this.modulus = keyPair.modulus; } /** * 构造函数（使用现有密钥） * * @param publicKey 公钥 * @param privateKey 私钥 * @param modulus 模数 */ public RSACipher(BigInteger publicKey, BigInteger privateKey, BigInteger modulus) { this.publicKey = publicKey; this.privateKey = privateKey; this.modulus = modulus; } /** * 生成RSA密钥对 * * @param keySize 密钥长度（位） * @return 密钥对 */ public static KeyPair generateKeyPair(int keySize) { // 1. 生成两个大素数 BigInteger p = generateLargePrime(keySize / 2); BigInteger q = generateLargePrime(keySize / 2); // 确保 p != q while (p.equals(q)) { q = generateLargePrime(keySize / 2); } // 2. 计算模数 n = p * q BigInteger n = p.multiply(q); // 3. 计算欧拉函数 φ(n) = (p-1)*(q-1) BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); // 4. 计算私钥指数 d // 满足 d * e ≡ 1 (mod φ(n)) BigInteger d = E.modInverse(phi); return new KeyPair(E, d, n); } /** * 生成大素数 * * @param bitLength 位长度 * @return 大素数 */ private static BigInteger generateLargePrime(int bitLength) { return BigInteger.probablePrime(bitLength, random); } /** * 加密 * * 使用公钥加密：ciphertext = plaintext^e mod n * * @param plaintext 明文 * @return 密文 */ public BigInteger encrypt(BigInteger plaintext) { return plaintext.modPow(publicKey, modulus); } /** * 加密（字节数组） * * @param plaintext 明文字节数组 * @return 密文字节数组 */ public byte[] encrypt(byte[] plaintext) { // 将字节数组转换为BigInteger BigInteger plaintextBigInt = new BigInteger(1, plaintext); // 加密 BigInteger ciphertextBigInt = encrypt(plaintextBigInt); // 转换为字节数组（带符号字节） return ciphertextBigInt.toByteArray(); } /** * 解密 * * 使用私钥解密：plaintext = ciphertext^d mod n * * @param ciphertext 密文 * @return 明文 */ public BigInteger decrypt(BigInteger ciphertext) { return ciphertext.modPow(privateKey, modulus); } /** * 解密（字节数组） * * @param ciphertext 密文字节数组 * @return 明文字节数组 */ public byte[] decrypt(byte[] ciphertext) { // 将字节数组转换为BigInteger BigInteger ciphertextBigInt = new BigInteger(1, ciphertext); // 解密 BigInteger plaintextBigInt = decrypt(ciphertextBigInt); // 转换为字节数组 return plaintextBigInt.toByteArray(); } /** * 签名 * * 使用私钥对数据进行签名 * * @param data 待签名数据 * @return 签名 */ public BigInteger sign(BigInteger data) { return data.modPow(privateKey, modulus); } /** * 验证签名 * * 使用公钥验证签名 * * @param data 原始数据 * @param signature 签名 * @return 验证结果 */ public boolean verify(BigInteger data, BigInteger signature) { BigInteger decrypted = signature.modPow(publicKey, modulus); return decrypted.equals(data); } /** * 获取公钥 */ public BigInteger getPublicKey() { return publicKey; } /** * 获取私钥 */ public BigInteger getPrivateKey() { return privateKey; } /** * 获取模数 */ public BigInteger getModulus() { return modulus; } /** * 测试RSA加密 */ public static void main(String[] args) { System.out.println("===== RSA加密算法测试 =====\n"); // 生成密钥对 System.out.println("生成RSA密钥对（1024位）..."); RSACipher rsa = new RSACipher(1024); System.out.println("公钥: " + rsa.getPublicKey()); System.out.println("私钥: " + rsa.getPrivateKey()); System.out.println("模数: " + rsa.getModulus()); // 测试数据 String message = "Hello, RSA! This is a secret message."; BigInteger plaintext = new BigInteger(message.getBytes()); System.out.println("\n原始消息: " + message); System.out.println("明文（BigInteger）: " + plaintext); // 加密 System.out.println("\n正在加密..."); BigInteger ciphertext = rsa.encrypt(plaintext); System.out.println("密文: " + ciphertext); // 解密 System.out.println("\n正在解密..."); BigInteger decrypted = rsa.decrypt(ciphertext); System.out.println("解密后的明文: " + decrypted); System.out.println("\n解密是否成功: " + decrypted.equals(plaintext)); System.out.println("原始消息: " + new String(decrypted.toByteArray())); // 签名测试 System.out.println("\n===== 数字签名测试 ====="); BigInteger data = new BigInteger("1234567890"); System.out.println("原始数据: " + data); BigInteger signature = rsa.sign(data); System.out.println("签名: " + signature); boolean verified = rsa.verify(data, signature); System.out.println("签名验证: " + verified); // 性能测试 System.out.println("\n===== 性能测试 ====="); // 不同密钥长度的性能对比 int[] keySizes = {512, 1024, 2048}; for (int keySize : keySizes) { System.out.println("\n密钥长度: " + keySize + " 位"); long startTime = System.currentTimeMillis(); RSACipher testRsa = new RSACipher(keySize); long keyGenTime = System.currentTimeMillis() - startTime; startTime = System.currentTimeMillis(); BigInteger testCipher = testRsa.encrypt(plaintext); long encryptTime = System.currentTimeMillis() - startTime; startTime = System.currentTimeMillis(); BigInteger testPlain = testRsa.decrypt(testCipher); long decryptTime = System.currentTimeMillis() - startTime; System.out.println("密钥生成耗时: " + keyGenTime + " ms"); System.out.println("加密耗时: " + encryptTime + " ms"); System.out.println("解密耗时: " + decryptTime + " ms"); } // 密钥安全性说明 System.out.println("\n===== 密钥安全性说明 ====="); System.out.println("512位：不安全，已被破解"); System.out.println("1024位：安全性较低，不推荐用于新系统"); System.out.println("2048位：当前推荐的安全密钥长度"); System.out.println("4096位：更高安全性，但性能开销大"); } } ``` #### 3.2.3 性能优化 ```java /** * RSA性能优化 */ public class RSAOptimizations { /** * 1. 中国剩余定理（CRT）优化 * * 解密速度提升4倍 * * 原理： * - 计算m1 = c^d mod p * - 计算m2 = c^d mod q * - 使用CRT合并结果 */ /** * 2. 蒙哥马利乘法 * * 加速模乘运算 * - 避免昂贵的除法操作 * - 使用移位和加法代替 */ /** * 3. 滑动窗口法 * * 优化模幂运算 * - 减少乘法次数 * - 预计算小幂次 */ /** * 4. 傅里叶变换 * * 大数乘法优化 * - Karatsuba算法 * - Schönhage-Strassen算法 */ } ``` --- ### 3.3 哈希算法 - SHA-256 SHA-256是一种密码学哈希函数，属于SHA-2家族。它将任意长度的输入数据映射为256位（32字节）的哈希值。 #### 3.3.1 算法原理 ``` SHA-256算法原理： 1. 预处理 a) 填充 - 在消息末尾添加1 - 添加0直到长度 ≡ 448 mod 512 - 添加64位的消息长度 b) 分块 - 将填充后的消息分为512位的块 2. 初始化哈希值 - 使用8个32位常量初始化 3. 处理每个消息块 a) 将512位块分为16个32位字 b) 扩展为64个32位字 c) 进行64轮压缩函数 - 消息调度 - 压缩函数 - 哈希值更新 4. 输出 - 连接8个哈希值，得到256位哈希 ``` #### 3.3.2 完整实现 ```java package com.kc.encryption.sha; import java.nio.ByteBuffer; import java.nio.ByteOrder; import java.util.Arrays; /** * SHA-256哈希算法实现 * * 实现原理： * 1. 预处理：填充消息到512位倍数 * 2. 初始化：使用初始哈希值 * 3. 处理：对每个512位块进行64轮压缩 * 4. 输出：得到256位哈希值 */ public class SHA256 { // 初始哈希值（前8个素数的平方根的小数部分的前32位） private static final int[] INITIAL_HASH = { 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 }; // 常量K（前64个素数的立方根的小数部分的前32位） private static final int[] K = { 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 }; /** * 计算SHA-256哈希值 * * @param message 输入消息 * @return 32字节的哈希值 */ public static byte[] hash(byte[] message) { // 1. 预处理：填充消息 byte[] paddedMessage = padMessage(message); // 2. 初始化哈希值 int[] hash = Arrays.copyOf(INITIAL_HASH, INITIAL_HASH.length); // 3. 处理每个512位块 for (int i = 0; i < paddedMessage.length; i += 64) { // 提取512位块 int[] block = extractBlock(paddedMessage, i); // 处理块 processBlock(hash, block); } // 4. 输出结果 byte[] result = new byte[32]; for (int i = 0; i < 8; i++) { result[i * 4] = (byte) (hash[i] >>> 24); result[i * 4 + 1] = (byte) (hash[i] >>> 16); result[i * 4 + 2] = (byte) (hash[i] >>> 8); result[i * 4 + 3] = (byte) hash[i]; } return result; } /** * 填充消息 * * SHA-256填充规则： * 1. 添加一个1位 * 2. 添加0位，直到长度 ≡ 448 mod 512 * 3. 添加64位的原始消息长度 * * @param message 原始消息 * @return 填充后的消息 */ private static byte[] padMessage(byte[] message) { // 计算原始消息长度（位） long messageLengthBits = (long) message.length * 8; // 计算填充后的长度 int paddingLength = 64 - ((message.length + 9) % 64); if (paddingLength < 0) { paddingLength += 64; } // 创建填充后的消息 byte[] padded = new byte[message.length + 1 + paddingLength + 8]; // 复制原始消息 System.arraycopy(message, 0, padded, 0, message.length); // 添加1位（0x80） padded[message.length] = (byte) 0x80; // 添加64位长度（大端序） ByteBuffer bb = ByteBuffer.wrap(padded, padded.length - 8, 8); bb.order(ByteOrder.BIG_ENDIAN); bb.putLong(messageLengthBits); return padded; } /** * 提取512位块（转换为16个32位字） * * @param paddedMessage 填充后的消息 * @param offset 偏移量 * @return 16个32位字 */ private static int[] extractBlock(byte[] paddedMessage, int offset) { int[] block = new int[16]; ByteBuffer bb = ByteBuffer.wrap(paddedMessage, offset, 64); bb.order(ByteOrder.BIG_ENDIAN); for (int i = 0; i < 16; i++) { block[i] = bb.getInt(); } return block; } /** * 处理512位块 * * @param hash 当前哈希值（8个32位） * @param block 512位块（16个32位） */ private static void processBlock(int[] hash, int[] block) { // 1. 消息调度：将16个字扩展为64个字 int[] w = new int[64]; System.arraycopy(block, 0, w, 0, 16); for (int i = 16; i < 64; i++) { // w[i] = σ1(w[i-2]) + w[i-7] + σ0(w[i-15]) + w[i-16] w[i] = addUnsigned( addUnsigned( addUnsigned(sigma1(w[i - 2]), w[i - 7]), sigma0(w[i - 15]) ), w[i - 16] ); } // 2. 初始化工作变量 int a = hash[0]; int b = hash[1]; int c = hash[2]; int d = hash[3]; int e = hash[4]; int f = hash[5]; int g = hash[6]; int h = hash[7]; // 3. 64轮压缩函数 for (int i = 0; i < 64; i++) { // T1 = h + Σ1(e) + Ch(e, f, g) + K[i] + w[i] int t1 = addUnsigned( addUnsigned( addUnsigned( addUnsigned(h, bigSigma1(e)), ch(e, f, g) ), K[i] ), w[i] ); // T2 = Σ0(a) + Maj(a, b, c) int t2 = addUnsigned(bigSigma0(a), maj(a, b, c)); // 更新工作变量 h = g; g = f; f = e; e = addUnsigned(d, t1); d = c; c = b; b = a; a = addUnsigned(t1, t2); } // 4. 更新哈希值 hash[0] = addUnsigned(hash[0], a); hash[1] = addUnsigned(hash[1], b); hash[2] = addUnsigned(hash[2], c); hash[3] = addUnsigned(hash[3], d); hash[4] = addUnsigned(hash[4], e); hash[5] = addUnsigned(hash[5], f); hash[6] = addUnsigned(hash[6], g); hash[7] = addUnsigned(hash[7], h); } /** * Ch函数（选择函数） * * Ch(x, y, z) = (x AND y) XOR ((NOT x) AND z) */ private static int ch(int x, int y, int z) { return (x & y) ^ (~x & z); } /** * Maj函数（多数函数） * * Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z) */ private static int maj(int x, int y, int z) { return (x & y) ^ (x & z) ^ (y & z); } /** * Σ0函数（大Sigma0） * * Σ0(x) = ROTR^2(x) XOR ROTR^13(x) XOR ROTR^22(x) */ private static int bigSigma0(int x) { return rotateRight(x, 2) ^ rotateRight(x, 13) ^ rotateRight(x, 22); } /** * Σ1函数（大Sigma1） * * Σ1(x) = ROTR^6(x) XOR ROTR^11(x) XOR ROTR^25(x) */ private static int bigSigma1(int x) { return rotateRight(x, 6) ^ rotateRight(x, 11) ^ rotateRight(x, 25); } /** * σ0函数（小Sigma0） * * σ0(x) = ROTR^7(x) XOR ROTR^18(x) XOR SHR^3(x) */ private static int sigma0(int x) { return rotateRight(x, 7) ^ rotateRight(x, 18) ^ (x >>> 3); } /** * σ1函数（小Sigma1） * * σ1(x) = ROTR^17(x) XOR ROTR^19(x) XOR SHR^10(x) */ private static int sigma1(int x) { return rotateRight(x, 17) ^ rotateRight(x, 19) ^ (x >>> 10); } /** * 循环右移 * * @param x 输入值 * @param n 移位数 * @return 右移后的值 */ private static int rotateRight(int x, int n) { return (x >>> n) | (x << (32 - n)); } /** * 无符号加法（处理溢出） */ private static int addUnsigned(int a, int b) { return a + b; } /** * 计算SHA-256哈希值（字符串） * * @param message 输入消息 * @return 十六进制哈希字符串 */ public static String hashString(String message) { return bytesToHex(hash(message.getBytes())); } /** * 字节数组转十六进制字符串 */ private static String bytesToHex(byte[] bytes) { StringBuilder sb = new StringBuilder(); for (byte b : bytes) { sb.append(String.format("%02x", b)); } return sb.toString(); } /** * 测试SHA-256 */ public static void main(String[] args) { System.out.println("===== SHA-256哈希算法测试 =====\n"); // 测试1：空字符串 String test1 = ""; String hash1 = hashString(test1); System.out.println("测试1: 空字符串"); System.out.println("输入: \"" + test1 + "\""); System.out.println("哈希: " + hash1); System.out.println("预期: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"); System.out.println("验证: " + hash1.equals("e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855")); // 测试2：Hello World String test2 = "Hello, World!"; String hash2 = hashString(test2); System.out.println("\n测试2: Hello, World!"); System.out.println("输入: \"" + test2 + "\""); System.out.println("哈希: " + hash2); // 测试3：长字符串 String test3 = "The quick brown fox jumps over the lazy dog"; String hash3 = hashString(test3); System.out.println("\n测试3: " + test3); System.out.println("哈希: " + hash3); System.out.println("预期: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592"); System.out.println("验证: " + hash3.equals("d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592")); // 性能测试 System.out.println("\n===== 性能测试 ====="); // 1MB数据 byte[] largeData = new byte[1024 * 1024]; java.util.Random random = new java.util.Random(); random.nextBytes(largeData); long startTime = System.currentTimeMillis(); byte[] hash = hash(largeData); long hashTime = System.currentTimeMillis() - startTime; System.out.println("哈希 1MB 数据耗时: " + hashTime + " ms"); System.out.println("哈希值: " + bytesToHex(hash).substring(0, 32) + "..."); // 雪崩效应测试 System.out.println("\n===== 雪崩效应测试 ====="); String base = "Hello, SHA-256!"; String modified = "Hello, SHA-257!"; String baseHash = hashString(base); String modifiedHash = hashString(modified); System.out.println("原始字符串: " + base); System.out.println("原始哈希: " + baseHash); System.out.println("\n修改字符串: " + modified); System.out.println("修改哈希: " + modifiedHash); System.out.println("\n哈希差异: " + countDifferentBits(baseHash, modifiedHash) + " 位"); // 安全性说明 System.out.println("\n===== 安全性说明 ====="); System.out.println("SHA-256特点："); System.out.println("1. 单向性：无法从哈希值反推出原始数据"); System.out.println("2. 抗碰撞性：难以找到两个不同输入产生相同哈希"); System.out.println("3. 雪崩效应：输入的微小变化会导致哈希值的巨大变化"); System.out.println("4. 固定输出：无论输入长度如何，输出始终为256位"); } /** * 计算两个哈希值的不同位数 */ private static int countDifferentBits(String hash1, String hash2) { int count = 0; for (int i = 0; i < hash1.length(); i++) { char c1 = hash1.charAt(i); char c2 = hash2.charAt(i); if (c1 != c2) { count += 4; // 每个十六进制字符代表4位 } } return count; } } ``` --- ## 综合应用实战 ### 4.1 压缩加密工具类 ```java package com.kc.util; import com.kc.compression.huffman.HuffmanCompressor; import com.kc.compression.lz77.LZ77Compressor; import com.kc.encryption.aes.AESCipher; import com.kc.encryption.rsa.RSACipher; import com.kc.encryption.sha.SHA256; import java.util.Arrays; /** * 压缩加密综合工具类 * * 功能： * 1. 数据压缩（哈夫曼、LZ77） * 2. 数据加密（AES、RSA） * 3. 数据哈希（SHA-256） * 4. 组合操作（压缩+加密） */ public class CryptoUtil { /** * 压缩算法类型 */ public enum CompressionType { NONE, HUFFMAN, LZ77 } /** * 加密算法类型 */ public enum EncryptionType { NONE, AES, RSA } /** * 压缩并加密数据 * * @param data 原始数据 * @param compressionType 压缩算法 * @param encryptionType 加密算法 * @param key 加密密钥 * @return 处理后的数据 */ public static byte[] compressAndEncrypt(byte[] data, CompressionType compressionType, EncryptionType encryptionType, String key) { byte[] result = data; // 第一步：压缩 if (compressionType != CompressionType.NONE) { result = compress(result, compressionType); System.out.println("压缩后大小: " + result.length + " 字节"); } // 第二步：加密 if (encryptionType != EncryptionType.NONE) { result = encrypt(result, encryptionType, key); System.out.println("加密后大小: " + result.length + " 字节"); } return result; } /** * 解密并解压数据 * * @param data 处理后的数据 * @param compressionType 压缩算法 * @param encryptionType 加密算法 * @param key 加密密钥 * @return 原始数据 */ public static byte[] decryptAndDecompress(byte[] data, CompressionType compressionType, EncryptionType encryptionType, String key) { byte[] result = data; // 第一步：解密 if (encryptionType != EncryptionType.NONE) { result = decrypt(result, encryptionType, key); System.out.println("解密后大小: " + result.length + " 字节"); } // 第二步：解压 if (compressionType != CompressionType.NONE) { result = decompress(result, compressionType); System.out.println("解压后大小: " + result.length + " 字节"); } return result; } /** * 压缩数据 */ private static byte[] compress(byte[] data, CompressionType type) { switch (type) { case HUFFMAN: HuffmanCompressor.HuffmanResult huffmanResult = HuffmanCompressor.compress(data); // 组合压缩数据和树数据 byte[] combined = new byte[4 + huffmanResult.compressedData.length + huffmanResult.treeData.length]; System.arraycopy(intToBytes(huffmanResult.compressedData.length), 0, combined, 0, 4); System.arraycopy(huffmanResult.compressedData, 0, combined, 4, huffmanResult.compressedData.length); System.arraycopy(huffmanResult.treeData, 0, combined, 4 + huffmanResult.compressedData.length, huffmanResult.treeData.length); return combined; case LZ77: return LZ77Compressor.serialize(LZ77Compressor.compress(data)); default: return data; } } /** * 解压数据 */ private static byte[] decompress(byte[] data, CompressionType type) { switch (type) { case HUFFMAN: int dataLength = bytesToInt(data, 0); int treeLength = data.length - 4 - dataLength; byte[] compressedData = new byte[dataLength]; byte[] treeData = new byte[treeLength]; System.arraycopy(data, 4, compressedData, 0, dataLength); System.arraycopy(data, 4 + dataLength, treeData, 0, treeLength); // 需要保存原始长度，这里简化处理 return HuffmanCompressor.decompress(compressedData, treeData, data.length * 2); // 估计 case LZ77: return LZ77Compressor.decompress(LZ77Compressor.deserialize(data)); default: return data; } } /** * 加密数据 */ private static byte[] encrypt(byte[] data, EncryptionType type, String key) { switch (type) { case AES: return new AESCipher(key.getBytes()).encrypt(data); case RSA: return new RSACipher(2048).encrypt(data); default: return data; } } /** * 解密数据 */ private static byte[] decrypt(byte[] data, EncryptionType type, String key) { switch (type) { case AES: return new AESCipher(key.getBytes()).decrypt(data); case RSA: return new RSACipher(2048).decrypt(data); default: return data; } } /** * 计算数据哈希值 */ public static String hash(byte[] data) { return SHA256.bytesToHex(SHA256.hash(data)); } /** * int转字节数组 */ private static byte[] intToBytes(int value) { return new byte[] { (byte) (value >>> 24), (byte) (value >>> 16), (byte) (value >>> 8), (byte) value }; } /** * 字节数组转int */ private static int bytesToInt(byte[] bytes, int offset) { return ((bytes[offset] & 0xFF) << 24) | ((bytes[offset + 1] & 0xFF) << 16) | ((bytes[offset + 2] & 0xFF) << 8) | (bytes[offset + 3] & 0xFF); } /** * 测试综合应用 */ public static void main(String[] args) { System.out.println("===== 压缩加密综合应用测试 =====\n"); // 测试数据 String testData = "This is a test message for compression and encryption. " + "The quick brown fox jumps over the lazy dog. " + "Hello, World! This is a comprehensive test."; byte[] originalData = testData.getBytes(); System.out.println("原始数据: " + testData); System.out.println("原始大小: " + originalData.length + " 字节"); System.out.println("原始哈希: " + hash(originalData)); // 测试1：哈夫曼压缩 + AES加密 System.out.println("\n===== 测试1：哈夫曼压缩 + AES加密 ====="); byte[] processed1 = compressAndEncrypt(originalData, CompressionType.HUFFMAN, EncryptionType.AES, "SecretKey1234567"); byte[] restored1 = decryptAndDecompress(processed1, CompressionType.HUFFMAN, EncryptionType.AES, "SecretKey1234567"); System.out.println("恢复数据: " + new String(restored1)); System.out.println("恢复哈希: " + hash(restored1)); System.out.println("验证: " + Arrays.equals(originalData, restored1)); // 测试2：LZ77压缩 + AES加密 System.out.println("\n===== 测试2：LZ77压缩 + AES加密 ====="); byte[] processed2 = compressAndEncrypt(originalData, CompressionType.LZ77, EncryptionType.AES, "SecretKey1234567"); byte[] restored2 = decryptAndDecompress(processed2, CompressionType.LZ77, EncryptionType.AES, "SecretKey1234567"); System.out.println("恢复数据: " + new String(restored2)); System.out.println("恢复哈希: " + hash(restored2)); System.out.println("验证: " + Arrays.equals(originalData, restored2)); // 大数据测试 System.out.println("\n===== 大数据测试 ====="); StringBuilder largeText = new StringBuilder(); for (int i = 0; i < 1000; i++) { largeText.append("The quick brown fox jumps over the lazy dog. "); } byte[] largeData = largeText.toString().getBytes(); System.out.println("原始大小: " + largeData.length + " 字节"); long startTime = System.currentTimeMillis(); byte[] largeProcessed = compressAndEncrypt(largeData, CompressionType.LZ77, EncryptionType.AES, "SecretKey1234567"); long processTime = System.currentTimeMillis() - startTime; System.out.println("处理后大小: " + largeProcessed.length + " 字节"); System.out.println("处理时间: " + processTime + " ms"); System.out.println("压缩率: " + String.format("%.2f%%", (1.0 - (double)largeProcessed.length / largeData.length) * 100)); } } ``` --- ## 性能优化 ### 5.1 压缩算法优化 ```java /** * 压缩算法性能优化 */ public class CompressionOptimization { /** * 1. 并行处理 * * 将大数据分块，并行压缩 */ public static byte[] parallelCompress(byte[] data) { // 实现分块并行压缩 return null; } /** * 2. 缓存优化 * * 缓存常用模式的编码结果 */ public static class EncodingCache { private final Map cache = new java.util.concurrent.ConcurrentHashMap<>(); public void put(String pattern, String encoding) { cache.put(pattern, encoding); } public String get(String pattern) { return cache.get(pattern); } } /** * 3. 内存优化 * * 使用对象池减少GC压力 */ public static class ByteArrayOutputStreamPool { private final java.util.Queue pool = new java.util.LinkedList<>(); public java.io.ByteArrayOutputStream borrow() { java.io.ByteArrayOutputStream baos = pool.poll(); return baos != null ? baos : new java.io.ByteArrayOutputStream(); } public void release(java.io.ByteArrayOutputStream baos) { baos.reset(); pool.offer(baos); } } } ``` ### 5.2 加密算法优化 ```java /** * 加密算法性能优化 */ public class EncryptionOptimization { /** * 1. 批量加密 * * 使用AES-NI硬件加速 */ public static byte[] batchEncrypt(byte[] data, byte[] key) { // 使用硬件加速指令 return null; } /** * 2. 密钥缓存 * * 缓存AES轮密钥，避免重复计算 */ public static class KeyCache { private final Map cache = new java.util.concurrent.ConcurrentHashMap<>(); public AESCipher getCipher(byte[] key) { return cache.computeIfAbsent(key, AESCipher::new); } } /** * 3. 流式加密 * * 支持大文件的流式加密 */ public static class StreamingEncryptor { private final AESCipher cipher; public StreamingEncryptor(byte[] key) { this.cipher = new AESCipher(key); } public void encryptStream(java.io.InputStream input, java.io.OutputStream output) throws java.io.IOException { byte[] buffer = new byte[8192]; int bytesRead; while ((bytesRead = input.read(buffer)) != -1) { byte[] encrypted = cipher.encrypt(Arrays.copyOf(buffer, bytesRead)); output.write(encrypted); } } } } ``` --- ## 总结 ### 6.1 知识点总结通过本文的学习，我们掌握了： #### 数据压缩算法 1. **哈夫曼编码** - 基于频率的变长编码 - 无损压缩 - 适合文本数据 2. **LZ77压缩** - 滑动窗口字典压缩 - 适合重复数据 - 广泛应用的算法 3. **DEFLATE压缩** - 结合LZ77和哈夫曼 - ZIP、GZIP的核心 - 压缩率高 #### 数据加密算法 1. **AES加密** - 对称加密标准 - 安全高效 - 多种工作模式 2. **RSA加密** - 非对称加密 - 密钥交换 - 数字签名 3. **SHA-256** - 密码学哈希 - 数据完整性 - 密码存储 ### 6.2 应用场景 ``` 数据压缩应用场景： - 文件压缩：ZIP、GZIP - 网络传输：减少带宽 - 存储优化：节省空间 - 数据库：压缩存储数据加密应用场景： - 数据传输：HTTPS、SSH - 数据存储：磁盘加密 - 身份认证：数字签名 - 密码学：区块链哈希算法应用场景： - 数据校验：文件完整性 - 密码存储：用户密码 - 数据索引：哈希表 - 区块链：工作量证明 ``` ### 6.3 最佳实践 1. **选择合适的算法** - 压缩：根据数据特征选择 - 加密：根据安全需求选择 - 哈希：根据应用场景选择 2. **性能优化** - 使用硬件加速 - 并行处理 - 内存优化 3. **安全考虑** - 使用标准算法 - 定期更新密钥 - 防止侧信道攻击 4. **错误处理** - 验证输入数据 - 处理异常情况 - 提供错误信息 --- ## 参考资料 - 哈夫曼编码：David Huffman, "A Method for the Construction of Minimum-Redundancy Codes" - LZ77：Ziv and Lempel, "A Universal Algorithm for Sequential Data Compression" - AES：FIPS PUB 197, "Advanced Encryption Standard (AES)" - RSA：Rivest, Shamir, Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" - SHA-256：FIPS PUB 180-4, "Secure Hash Standard (SHS)" --- 希望这篇详细的算法实现能够帮助你深入理解数据压缩和加密的原理！所有代码都包含了详细的注释，便于学习和理解。

CodeGarden

【数据压缩与加密算法】

发表评论取消回复

发表评论 取消回复

发表评论取消回复