摘 要

为了减少数据存储和传输所需要的空间和带宽资源，同时保障隐私数据的安全性，本文设计并实现了一种改进的无损压缩和分组加密算法。无损压缩技术让大型数据的存储和传播具有可行性，满足了特殊行业和人群对数据无失真的要求；加密技术则目前已经关系到国家安全到个人隐私的方方面面。

论文主要研究了压缩和加密算法的设计方案和实现细节。本文给出了LZ77字典的Hash表索引结构，使得查找字典的复杂度接近O(1)。为了进一步提高压缩比，本文还给出了Golomb码和区间编码对二元组基于分段策略的变长编码方案。另外，本论文针对AES的S盒和密钥扩展算法可能存在的安全缺陷，对这两个密码部件进行了改进，依靠Feistel-3结构，组合成了一种新的分组加密算法。此外，本论文从算法的代码实现角度出发，对内存的bit级操作、复杂的数学运算、文件结构的定义以及加密算法的工作模式和口令等问题提出了解决方案。最后通过测试压缩算法的压缩比和压缩速度，观察加密文件的雪崩效应，给出本文方案的性能。

研究结果表明本文所给出的压缩方案对文本文件、未经压缩的图片、音频和视频文件均有较好的压缩比，同时拥有较快的运行速度。加密文件也可以观察到雪崩效应，说明加密算法具有很好的扩散性质。

本文的特色：设计了LZ77的索引结构和不定长编码，整合改进的AES密码部件到Feistel结构中，并使用C 验证了算法。

关键词：无损压缩；LZ77；分组密码；S盒；密钥扩展

Abstract

To reduce the space and bandwidth resources which are required for data storage and transmission, and ensure the security of private data, this thesis designs and implements a new lossless compression and block encryption algorithm. Lossless compression technology makes the storage and transmission of large date feasible, which meets the requirements of special industries and people for data without distortion. And encryption is now linked to almost everything from national security to personal privacy.

This thesis mainly studies the design scheme and implementation details of compression and encryption algorithm. This thesis gives presents the Hash table index structure of LZ77 dictionary, which makes the complexity of dictionary looking up close to O(1). In order to further improve the compression ratio, this thesis also gives a variable length coding scheme of two-tuples which based on segmentation strategy with Golomb encoding and range encoding. Besides, this thesis improves S-box and key extension algorithm to prevent from the security defects, and combines them into a new block encryption based on Feistel-3 structure. In addition, from the perspective of algorithm implementation, gives solution schemes of memory bit-level operation, complex mathematical operations, the definition of the file structure and encryption mode. Finally, this thesis gives the performance of the algorithm by testing the compression ratio and compression speed of the compression algorithm and observing avalanche effect of the encrypted file.

The research results show that the compression scheme proposed in this thesis has a good compression ratio for text files, uncompressed images, audio and video files, having a fast running speed. Besides, The avalanche effect can also be observed in the encrypted file, indicating that the encryption algorithm has a good diffusion property.

Features of this thesis: designed the index structure and variable length coding of LZ77, integrated the improved AES cipher components into Feistel structure, and used C to complement the algorithm. 

Key Words：lossless compression; LZ77; block cipher; S-box; key extension

目 录

第1章 绪论 1

1.1研究目的和意义 1

1.2国内外研究现状 1

1.3本文的主要工作内容 2

第2章 压缩算法设计 4

2.1概率模型的基本类型 4

2.1.1 静态模型 4

2.1.2 自适应模型 4

2.2基础编码方式 5

2.2.1区间编码 5

2.2.2 Golomb-Rice码 7

2.2.3 LZ77压缩算法 8

2.3 算法设计过程 8

2.3.1 字典查找方法 9

2.3.2 滑动窗口的改进 11

2.3.3 字典大小 11

2.3.4 二元组和单字符的区分 11

2.3.5 二元组的不定长编码 12

2.3.6 频率统计模型 14

第3章 加密算法设计 17

3.1分组加密结构 17

3.2 SP轮函数 18

3.2.1 扩散层 18

3.2.2 混淆层 19

3.3 密钥扩展算法 19

第4章 压缩加密算法的C 实现 23

4.1 压缩算法实现的重要细节 23

4.1.1 内存bit位读写 23

4.1.2 字典索引的更新和查找 24

4.1.3区间编码的归一化实现 25

4.2 文件加密过程的重要细节 26

4.2.1 有限域GF(2⁸)上的乘法 27

4.2.2工作模式和短块处理 28

4.2.4加密口令散列 29

4.3 文件结构 29

4.3.1压缩文件块结构 29

4.3.2文件头结构 30

第5章 压缩加密算法测试与分析 32

5.1压缩比和压缩速度 32

5.1.1测试数据 32

5.1.2测试结果分析 32

5.2雪崩效应 33

第6章 总结与展望 34

6.1全文总结 34

6.2 工作展望 34

参考文献 35

致谢 36

第1章 绪论

1.1研究目的和意义

信息的压缩和加密均有着古老的历史。三千年前商朝甲骨上所刻的卜辞有明显刻意压缩字数的迹象，这是依托于自然语言的最古朴的信息压缩技术；两千年前古罗马凯撒皇帝使用字母表移位的方式创造出了凯撒密码，是最早的表单密码。然而这些古典的压缩和加密方式早已不适应现代信息技术的发展，目前以数字形式存储和传输的信息亮爆炸般增长，并包含大量保密和隐私信息，数据的压缩技术和加密已经影响到每个人的生活。尤其是近年来移动互联网的发展更是对移动设备的数据的存储方式以及通信手段提出了挑战。一张未经过任何压缩的图像，其大小动辄高达几十兆字节；一段没有经过任何压缩的高清视频，其大小甚至能达到上万兆字节。这种严重冗余的数据将占用巨大的存储资源，并难以有效率地传输。有损压缩技术虽然压缩比较高，但随着硬件水平的提高，人们对高质量图像、音频和视频的追求趋势也开始显现，无损压缩技术再次变得重要起来。此外随着信息技术深入到人类社会和生活的各个领域，信息的安全性也愈发重要，不断发生的危害信息安全的事件让信息安全形势变的更加严峻。目前，小到个人隐私，大到国家安全，都离不开加密技术的保护。因此加密算法的设计就成为了很重要的课题。本文的目的就是设计并实现一种数据压缩和加密算法，减少数据存储和传输负担，并保证数据安全。

1.2国内外研究现状

1948年香农提出的信息论为数据压缩提供了理论基础，是现代数据压缩理论的开山之作。紧接着香农和范诺在1949年分别提出了第一种变长压缩编码，香农-范诺编码。在这之后基于概率统计的编码理论进入了飞速发展时期，这期间的研究成果以1952年提出的Huffman编码最为突出。这之后20年，概率统计编码的发展进入瓶颈期后，Jacob Ziv和Abraham Lempel在1977年发表的一篇里程碑论文为无损压缩算法的发展注入了新鲜血液，LZ77作为第一个字典编码为后来的压缩算法打开了全新的思路，紧接着两人在1978年发表了LZ78算法。LZ77与LZ78算法作为基石，衍生出大量基于二者的新理论，这些

新的压缩算法被统一称为LZ系列压缩算法^[1]。

随着新算法不断提出，目前的压缩技术在速度和压缩率这两个重要指标上已经取得不错的平衡，发展速度在近年来也开始放缓。较新的研究成果有支持多线程的LZMA2算法，该算法是目前平衡性最好的算法之一。使用优化PPM技术的PAQ压缩算法在一定程度上舍弃压缩速度的情况下，平均压缩率在目前达到了最优^[2]。除此之外，在FPGA等对硬件规格有所限制的应用场合，并行PPLZW和优化LZO等改进算法也相继出现^[3]。LZ系列算法目前也已经被广泛应用到计算机系统中，例如目前广泛使用的基于Deflate算法的zip文件。LZSS和PPM被应用到rar文件中，7z格式的压缩文件则支持Deflate、LZMA、LZMA2等多种算法。除此之外，一些无损图片压缩格式也使用到了LZ系列算法，GIF格式应用了LZW算法，PNG格式则是基于Deflate算法设计的^[4]。

图1.1 LZ系列压缩算法的衍生

现代密码学同样是由香农创立的，1949年，他证明了当密钥和明文长度相同时，密码是理论上不可破译的。虽然一字一密已经达到了加密算法所追求的的终极安全性，这种加密方式却无法在实践中广泛应用。紧接着，依托香农的密码学原理，分组密码、序列密码和公钥密码等加密理论纷纷被提出和应用。

对称加密体制中的分组密码是目前广泛使用的密码类型，它结构简单、并易于软硬件的实现，在文件存储和通信系统中是最受青睐的加密方法之一。最早提出并得以应用的分组密码是DES算法。进入90年代，DES由于弱密钥和密钥过短面临安全问题，被AES全面替代。AES标准的征集促进了一大批密码学者设计出大量的分组密码，例如IDEA、Camellia，以及被日本和欧洲广泛应用的MISTY1^[5]。我国也推出了SM4分组加密算法。分组密码设计领域进入繁荣阶段的同时，中间相遇攻击、截断分析以及不可能差分分析等分析技术也随之被提出，目前已经有针对9轮AES-192/256的理论分析方法^[6]。

近年来分组密码的研究方向逐渐由大型加密标准的争夺转入轻量级密码的设计。例如2013年的SIMON加密算法，是目前加密速度最快的算法之一^[7]。由于分组密码在结构设计上没有新的突破^[6]，依旧以Feistel、SPN为主，研究者将目光更多地转向了密码部件的设计。由此产生了一系列S盒和密钥扩展的研究成果。2014年，一种基于Feistel结构构造轻量级S盒的理论被提出，同年我国的黄佳琳分析了密码安全性分析中密钥拓展可能带来的影响。尤其是近年来的加密算法设计有只使用主密钥，取消密钥拓展的趋势^[6]。如此一来与密钥拓展相关的研究显得更为有价值。

1.3本文的主要工作内容

本文的工作是在已有的压缩和加密算法的基础上改进并设计一种新的数据压缩和加密算法。在数据压缩方面，首先学习和阅读LZ77、范式Huffman编码、区间编码、Golomb-Rice编码相关的文献，对以上几种编码的特性进行了分析后提出组合方案，通过测试不断优化该方案，最终设计出一种无损压缩算法，并使用C 在计算机上实现并验证该算法。最后通过测试文件对压缩性能进行测试和对比，并对测试结果进行分析。在数据加密方面，通过阅读Feistel结构、SPN结构以及AES加密算法的相关文献，了解AES轮函数的弱点，重新设计并替换密码部件，改进轮函数的密码学特性，并用C 实现了改进后的加密算法。最后通过观察测试文件雪崩效应验证加密算法的安全性。

本论文的主要结构如下：

第1章是绪论，阐述本文所做研究的目的和意义，并对压缩和加密技术的发展以及目前国内外研究成果进行总结，接着指出本文所做的主要工作和内容。

第2章首先对压缩模型的类型进行说明，分析区间编码、Golomb-Rice码以及LZ77编码的特性，依托这些基础的编码方式组合设计出一种改进的压缩算法，对算法中字典搜索方式、滑动窗口的改进、概率表的建立以及二元组的区分和编码等内容进行详细的说明。

第3章首先给出加密算法的结构，在这个结构上嵌入合适的扩散层和混淆层，通过寻找仿射变换对改进AES轮函数S盒，并修改轮密钥等密码部件，构造出一种新的加密算法。

第4章对算法的C 实现过程中一些重要细节进行说明，包括内存bit级读写、索引更新、区间归一化、GF(2⁸)上的乘法、加密算法的工作模式、文件结构、图形界面的实现等内容。

第5章使用测试文件对压缩算法的压缩比、压缩时间进行测试，并与单一的范式Huffman编码和算术编码进行比较，分析出本文给出的压缩算法的优势和缺点。另外通过观察加密文件的雪崩效应，对加密算法的扩散指标进行验证。

第6章是总结，归纳本文所完成的工作，并对结果进行总结，指出尚可改进之处。

第2章 压缩算法设计

2.1概率模型的基本类型

要实现一个特定的压缩算法，首先需要对目标数据进行建模。建模的过程就是对信源先验知识的获取和分析过程，不管最后使用何种编码方式，对目标数据建模的准确度直接影响到压缩算法最终的压缩性能。建模的重要性在对图像和音视频等数据的压缩上尤为突出。虽然本文重点讨论对通用数据的压缩算法，并不对这种具有特定形式的数据进行单独讨论，但建模仍然是个不可缺少的过程。一般而言，数据压缩需要对信源的概率分布进行统计，这就需要建立概率统计模型。概率统计模型可以分为两大类：静态模型和自适应模型^[8]。

2.1.1 静态模型

静态模型就是在编码前事先对目标序列的概率分布进行统计，一次获得整个序列的概率分布情况。静态模型并非一定要对目标序列的符号集进行概率统计，如果能得知信源本身的概率分布情况，基于这种先验知识的概率模型也属于静态模型的一种。对于Huffman编码等基于概率统计的编码方式而言，使用静态概率统计模型往往能得到最优压缩结果。因此对于一些有规律的信源，或者有条件对目标压缩序列进行符号统计的情况下，静态模型是最佳选择。

但是对于通用数据的压缩而言，有时无法使用静态模型。例如计算机需要发送一段动态生成的字符串，这需要不断地对这段字符串进行动态压缩，从而无从得知整段字符串的概率统计结果。或者对于一段超大的数据，强行使用静态模型会导致时间或空间资源有难以承受的开销，也可以认为在工程实现上无法使用静态概率统计模型。所以一个通用性强的压缩算法，应该使用自适应概率统计模型。

2.1.2 自适应模型

自适应概率统计模型根据已经遍历过的数据，进行符号概率分布的动态统计。例如对于字符串“this_is_a_file”，整段字符串的长度为14，字符“i”的频度为3，如果使用静态概率统计模型，可以认为字符“i”出现的概率约为0.214。如果使用自适应模型，假设无法得知还未遍历的字符串内容，当前光标遍历到第6个字符，则字符串总长度为6，字符“i”的频度为2，所以当前字符“i”的概率约为0.333。使用自适应模型的压缩器的总体压缩性能一般要小于使用静态模型的压缩器，但是自适应模型的动态特性往往能让局部数据的压缩性能更好，这个特点也能让压缩算法更加灵活。例如上面给出的比较静态模型和自适应模型的例子，如果希望能临时将数据分为长度分别为7的两个数据块，则自适应模型将拥有更好的表现。

自适应模型的另外一个优点是不需要在压缩数据上附带一份符号集对应的频率表，从而节省了空间。使用静态模型的压缩算法在解压时，由于无法从压缩数据得知原先待压缩序列中每一个符号出现的频率，所以在压缩时必须附上一份记录着每个符号对应频率的频率表，字符集越大，这份额外的空间开销就越大。而由于自适应模型对符号出现的频率进行动态统计，只需要对每个符号的频度进行初始化，就可以不依赖频率表实现动态解压。

自适应模型可以按照所依赖的上下文长度分为零阶自适应模型和高阶自适应模型^[8]。零阶自适应模型不依赖于上下文，可以看作是最基础的自适应概率统计模型。高阶自适应模型是一种基于上下文的模型，其中最有名的是马尔科夫链模型，这种模型在文本压缩中效果尤其出色。例如，在一般的英语文本中，字母“g”出现的概率排名第7，仅为2.015%。但是在字母“n”，尤其是在字符串“in”后，字母“g”出现的概率飙升，因为“ing”这种字符组合在英语中很常见。一般来说，阶数越高，压缩性能越好，但这一点在工程实现上不是绝对的，为了解决零频率问题，即出现了没有出现过的字符或字符组合，需要引入转义字符，阶数越高，则相对引入的转义字符数量也越多，降低压缩性能。另外，阶数越高也意味着需要提供更大的存储空间来保存频率表。如果使用n阶自适应模型对一串8bit字节进行压缩，符号集大小为256，则频率表需记录256ⁿ个组合，仅仅当n为4的时候，频率表的大小就达到了约8.6GByte（假设每个符号的频率仅占用2字节）。所以在设计算法时，需要综合考虑目标数据的特点，选用合适的阶数。

2.2基础编码方式

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：