本站原创
摘 要：提出了一种安全的LZW编码算法——SLZW。该算法在改进的LZW编码过程中嵌入加密，从而能够同时完成压缩和加密。SLZW编码利用动态Huffman树作为LZW的字典，并且通过耦合映像格子（CML）产生的密钥流对字典的构建和更新进行控制，编码输出进一步和密钥流进行异或后产生密文。并且，该算法被应用于GIF图像加密中，实验结果和分析表明，该算法不仅具有较好的安全性，同时也将标准LZW算法的压缩效率提高了10%左右，具有广泛的实用性。
关键词：数据压缩；图像加密；Huffman编码；耦合映像格子
：A
Secure LZW coding algorithm and its application in GIF image encryption
XIANG Tao*， WANG An
School of Computer Science， Chongqing University， Chongqing 400030， China
Abstract：
This paper proposed a Secure LZW （SLZW） coding algorithm， where encryption was embedded into the improved LZW coding process， and SLZW can fulfill compression and encryption in a single step. In SLZW algorithm， dynamic Huffman tree was utilized to code the dictionary of LZW， and the initialization and updating of Huffman tree were controlled by a sequence of keystream generated by Coupled Map Lattcie （CML）. The code words were further XORed with the keystream to generate the ciphertext. The SLZW was applied to GIF image encryption. The experimental results and their analyses indicate that the proposed SLZW algorithm not only has good security， but can also improves the compression ratio by about 10%. Therefore， SLZW can find its wide applications in practice.
英文关键词 Key words：
data compression； image encryption； Huffman coding； Coupled Map Lattcie （CML）
0 引言
随着信息的高度数字化，计算机需要处理越来越多的海量数据。特别是多媒体数据的广泛应用和普及，使得压缩成为数据存储和传输过程中一项必不可少的技术。同时，在日益复杂的网络环境下，信息的安全性也面临着日益严峻的考验，而加密是解决信息安全的重要手段。因此，在实际应用场合往往需要同时考虑数据压缩和数据加密。但是由于压缩和加密原本是两项相对独立的数据处理技术，传统的做法是分两步进行，即先对数据进行压缩，然后对压缩后的数据进行加密。这样做的问题在于处理时间开销较大，而且压缩和加密之间的速度同步也是一个问题。最新的研究表明，将压缩和加密结合起来考虑，即在数据压缩的同时对数据进行加密，将两个独立的步骤合并成为一个步骤，可以有效地减少处理的时间，特别是在图像等多媒体数据处理和实时传输方面有着非常显著的效果[1-2]。
LZW是由Abraham Lempel、Jacob Ziv与Terry Welch创造的一种优秀的无损数据压缩算法[3]，在GIF等文件格式中得到了广泛的应用。目前国际上已有学者针对LZW压缩算法在压缩编码的同时引入加密机制方面展开了研究。文献[4]提出了一种基于LZ78的加密方案，该方案采用随机字典表（Randomized Dictionary Table， RDT）的方式在LZW压缩过程中实现加密。文献[5]也对基于LZW的加密方案进行了研究，通过利用随机字典插入、字典置乱和二进制异或操作，实现对明文的压缩和加密。然而，这两个方案在安全性和压缩率方面存在缺陷：文献[5]指出文献[4]所提出的方案易受选择明文攻击；文献[6]分析了文献[5]所提出的加密算法的安全性，分别给出了选择明文和选择密文攻击的方法，同时还指出文献[5]中的算法对LZW算法本身的压缩效果有影响。
本文基于LZW压缩提出了一种安全的LZW（Secure LZW， SLZW）编码算法，SLZW编码算法利用动态增长的Huffman树[7]作为字典，有效地将LZW和动态Huffman编码结合为一个整体，能显著提高压缩率。在编码的过程，利用基于混沌的耦合映像格子（Coupled Map Lattcie， CML）产生随机比特流控制Huffman树的编码，实现在压缩过程中进行加密，达到较好的安全性。
LZW编码的主题思想是用较短的字符串代替较长的字符串实现数据压缩，具体做法为：用一定的规则选择一些字符串放进字符串表（字典）中，当字典中的字符串再次出现时，就可以用字典中的位置索引值代替该字符串。LZW在解码时可以构建出同编码方同样的字典，因此，编码方构建的字典没有必要发送给解码方。LZW的编码和解码过程请参考文献[3]。
动态Huffman编码在对数据进行编码时不必事先统计数据出现的概率信息，它采用的是根据数据输入动态构建Huffman树的技术。更为重要的是，解码方在解码时不必事先拥有编码方构建出的Huffman树，解码方可以根据得到的压缩码流动态构建出与编码方一样的Huffman树，从而恢复出被编码的消息。这也是它和LZW编码结合起来
研究表明，将LZW与Huffman编码结合能取得更好的压缩效果，文献[9]就介绍了一种将LZW与Huffman编码结合进行压缩的方法。然而，这些方法均存在一个显著缺陷，就是没有将两个压缩过程无缝地合并为一个压缩过程，它们采用的思想都是在LZW压缩过程中计算出输出数据的概率，然后根据这些概率再对结果数据进行Huffman编码。本文将动态Huffman树结构作为LZW的字典，无需统计数据概率信息，一次LZW编码后即实现了总体压缩的效果。
关键词：数据压缩；图像加密；Huffman编码；耦合映像格子
：A
Secure LZW coding algorithm and its application in GIF image encryption
XIANG Tao*， WANG An
School of Computer Science， Chongqing University， Chongqing 400030， China
Abstract：
This paper proposed a Secure LZW （SLZW） coding algorithm， where encryption was embedded into the improved LZW coding process， and SLZW can fulfill compression and encryption in a single step. In SLZW algorithm， dynamic Huffman tree was utilized to code the dictionary of LZW， and the initialization and updating of Huffman tree were controlled by a sequence of keystream generated by Coupled Map Lattcie （CML）. The code words were further XORed with the keystream to generate the ciphertext. The SLZW was applied to GIF image encryption. The experimental results and their analyses indicate that the proposed SLZW algorithm not only has good security， but can also improves the compression ratio by about 10%. Therefore， SLZW can find its wide applications in practice.
英文关键词 Key words：
data compression； image encryption； Huffman coding； Coupled Map Lattcie （CML）
0 引言
随着信息的高度数字化，计算机需要处理越来越多的海量数据。特别是多媒体数据的广泛应用和普及，使得压缩成为数据存储和传输过程中一项必不可少的技术。同时，在日益复杂的网络环境下，信息的安全性也面临着日益严峻的考验，而加密是解决信息安全的重要手段。因此，在实际应用场合往往需要同时考虑数据压缩和数据加密。但是由于压缩和加密原本是两项相对独立的数据处理技术，传统的做法是分两步进行，即先对数据进行压缩，然后对压缩后的数据进行加密。这样做的问题在于处理时间开销较大，而且压缩和加密之间的速度同步也是一个问题。最新的研究表明，将压缩和加密结合起来考虑，即在数据压缩的同时对数据进行加密，将两个独立的步骤合并成为一个步骤，可以有效地减少处理的时间，特别是在图像等多媒体数据处理和实时传输方面有着非常显著的效果[1-2]。
LZW是由Abraham Lempel、Jacob Ziv与Terry Welch创造的一种优秀的无损数据压缩算法[3]，在GIF等文件格式中得到了广泛的应用。目前国际上已有学者针对LZW压缩算法在压缩编码的同时引入加密机制方面展开了研究。文献[4]提出了一种基于LZ78的加密方案，该方案采用随机字典表（Randomized Dictionary Table， RDT）的方式在LZW压缩过程中实现加密。文献[5]也对基于LZW的加密方案进行了研究，通过利用随机字典插入、字典置乱和二进制异或操作，实现对明文的压缩和加密。然而，这两个方案在安全性和压缩率方面存在缺陷：文献[5]指出文献[4]所提出的方案易受选择明文攻击；文献[6]分析了文献[5]所提出的加密算法的安全性，分别给出了选择明文和选择密文攻击的方法，同时还指出文献[5]中的算法对LZW算法本身的压缩效果有影响。
本文基于LZW压缩提出了一种安全的LZW（Secure LZW， SLZW）编码算法，SLZW编码算法利用动态增长的Huffman树[7]作为字典，有效地将LZW和动态Huffman编码结合为一个整体，能显著提高压缩率。在编码的过程，利用基于混沌的耦合映像格子（Coupled Map Lattcie， CML）产生随机比特流控制Huffman树的编码，实现在压缩过程中进行加密，达到较好的安全性。
1 LZW编码和动态Huffman编码
SLZW编码的思想是建立在LZW编码和动态Huffman编码的基础上的，下面首先对这两种编码作简单介绍。LZW编码的主题思想是用较短的字符串代替较长的字符串实现数据压缩，具体做法为：用一定的规则选择一些字符串放进字符串表（字典）中，当字典中的字符串再次出现时，就可以用字典中的位置索引值代替该字符串。LZW在解码时可以构建出同编码方同样的字典，因此，编码方构建的字典没有必要发送给解码方。LZW的编码和解码过程请参考文献[3]。
动态Huffman编码在对数据进行编码时不必事先统计数据出现的概率信息，它采用的是根据数据输入动态构建Huffman树的技术。更为重要的是，解码方在解码时不必事先拥有编码方构建出的Huffman树，解码方可以根据得到的压缩码流动态构建出与编码方一样的Huffman树，从而恢复出被编码的消息。这也是它和LZW编码结合起来
摘自：本科毕业论文www.udooo.com
后解码方能完全恢复出编码方字典的关键。文献[8]给出了一种动态Huffman实现的技术。研究表明，将LZW与Huffman编码结合能取得更好的压缩效果，文献[9]就介绍了一种将LZW与Huffman编码结合进行压缩的方法。然而，这些方法均存在一个显著缺陷，就是没有将两个压缩过程无缝地合并为一个压缩过程，它们采用的思想都是在LZW压缩过程中计算出输出数据的概率，然后根据这些概率再对结果数据进行Huffman编码。本文将动态Huffman树结构作为LZW的字典，无需统计数据概率信息，一次LZW编码后即实现了总体压缩的效果。