信息安全论文

1、宁夏大学课题论文姓    名：  王磊 学    号：  12010244020指导教师：杨绍华  专    业： 软件工程课 程： 信息安全学 院： 数学计算机学院题 目： 图像加密算法的设计与实现图像加密算法的设计与实现摘    要随着计算机多媒体技术和网络通信技术的迅速发展，人们对多媒体信息的需求不断增长。而由于多媒体信息量巨大和信息安全需求，图像数据压缩编码技术和数字图像信息加密

2、技术都己成为多媒体及通讯领域中的关键技术。 本设计研究并实现一种应用广泛的数据编码方法，即算术编码，并利用算术编码的特性设计图像加密算法。  为了解决算术编码计算过程的精度需求问题，本设计实现了整数型算术编码，并结合静态概率模型和自适应概率模型的编码实验总结出自适应概率模型具有最优的编码效率。 本设计为了达到图像信息的高效、实时和安全传输，利用算术编码对错误以及概率敏感的特点，总结了一种随机置换图像信息数据块的加密算法。当设置一个初始密钥，就可以利用组合的线形反馈移位寄存器产生的密钥序列决定信息数据的分块与置换。解密算法中只要通过初始密钥得到相同的随机序

3、列，即可恢复原始数据信息。 通过实验数据分析，该算法既可以不对编码效率产生负面影响，又实现实时传输。 关键词：数据压缩，整数型算术编码，自适应模型，图像加密，块交换目   录第一章  绪论 1.1数据压缩 1.1.1数据压缩的基本概念   1.1.2数据压缩分类 1.1.3数据压缩与编码  1.2数据压缩的现状和发展趋势  1.2.1数据压缩在多媒体领域的应用 1.2.2数据压缩的发展趋势1.3 数字图像加密技术1.

4、3.1图像加密技术的内容 1.3.2 图像加密安全性的要求  1.3.3 图像加密技术的现状和发展 1.4 课题研究的意义第二章  算术编码的原理及特点 2.1算术编码原理 2.2算术编码的特点 2.3常用的算术编码类型 2.3.1算术编码静态概率模型 2.3.2算术编码自适应概率模型 第三章  算术编码的设计和实现 3.1功能模块的划分 3.2功能模块的具体实现 3.2.1图像读取模块和还原模块

5、的实现  3.2.2输入输出模块的实现  3.2.3编码和解码模块的实现3.3 三种概率模型性能的比较分析 3.3.1压缩效率   3.3.2执行时间第四章  基于算术编码的图像加密算法的设计和实现 4.1 加密算法的设计 4.2 功能模块的具体实现  4.2.1 密钥管理模块的实现 4.2.2 加密模块的实现4.2.3 解密模块的实现第五章  总结和心得第一章 &#

6、160;绪论1.1数据压缩 1.1.1数据压缩的基本概念    数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。简单的说，就是用尽量少的数码来表示信号，即将字符串的一种表示方式转换为另一种表示方式，一些新的表示方式包含相同的信息量，但是长度比原来的方式尽可能的短1。 1.1.2数据压缩分类    数据之所以能够被压缩是基于数据的以下几点特性：首先，数据中间常存在一些多余成分，既冗余度。如在一份计算机文件中，某些符号会重复出现、某些符号比其他符号出现得

7、更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分便可在数据编码中除去或减少。冗余度压缩是一个可逆过程，因此叫做无失真压缩，或者称为保持型编码。 其次，数据中间尤其是相邻的数据之间，常存在着相关性。如图片中常常有色彩均匀的背影，电视信号的相邻两帧之间可能只有少量的变化影物是不同的，声音信号有时具有一定的规律性和周期性等等。因此，有可能利用某些变换来尽可能地去掉这些相关性。但这种变换有时会带来不可恢复的损失和误差，因此叫做不可逆压缩，或称有失真编码、摘压缩等。 此外，人们在欣赏音像节目时，由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限，如人眼对影

8、视节目有视觉暂留效应，人眼或人耳对低于某一极限的幅度变化已无法感知等，故可将信号中这部分感觉不出的分量压缩掉或“掩蔽掉”。这种压缩方法同样是一种不可逆压缩。 1.1.3数据压缩与编码      数据压缩跟编码技术联系紧密，压缩的实质就是根据数据的内在联系将数据从一种编码映射为另一种编码。压缩前的数据要被划分为一个一个的基本单元。基本单元既可以是单个字符，也可以是多个字符组成的字符串。这些基本单元称为源消息，所有的源消息构成源消息集，源消息集映射的结果为码字集。换言之，压缩前的数据是源消息序列，压缩后的数据是码字序列。对于数据压缩技术而

9、言，最基本的要求就是要尽量降低数字化的码字量，同时仍保持一定的信号质量2。1.2数据压缩的现状和发展趋势 1.2.1数据压缩在多媒体领域的应用 在图像压缩领域，著名的JPEG标准是有损压缩算法中的经典。JPEG标准由静态图像联合专家组于1986年开始制定，1994年后成为国际标准。JPEG以离散余弦变换（DCT）为核心算法，通过调整质量系数控制图像的精度和大小3。CCITT(国际电报电话咨询委员会)于1988年制定了电视电话和会议电视H.261建议草案。在此基础上，1993年ISO（国际标准化组织）通过了动态图像专家组提出的MPEG-1标准。MPEG-1可以对普通质量的视频

10、数据进行有效编码。为了支持更清晰的视频图像，特别是支持数字电视等高端应用，ISO于1994年提出了新的MPEG-2标准。随着Internet的发展对视频压缩提出了更高的要求，ISO于1999年通过了MPEG-4 标准。MPEG-4标准拥有更高的压缩比率，支持并发数据流的编码、基于内容的交互操作、增强的时间域随机存取、容错、基于内容的尺度可变性等先进特性4。而音频数据的压缩技术最早是由无线电广播、语音通信等领域里的技术人员发展起来的。这其中又以语音编码和压缩技术的研究最为活跃。人们陆续发明了脉冲编码调制、线性预测、矢量量化、自适应变换编码等语音分析与处理技术。这些语音技术在采集语音特征

11、，获取数字信号的同时，通常也可以起到降低信息冗余度的作用。 1.2.2数据压缩的发展趋势 很显然，在多媒体信息日益成为主流信息形态的数字化时代里，数据压缩技术特别是专用于图像、音频、视频的数据压缩技术还有相当大的发展空间。毕竟，人们对信息数量和信息质量的追求是永无止境的。 分形压缩技术是图像压缩领域近几年来的一个热点。这一技术起源于 B. Mandelbrot于1977年创建的分形几何学。M.Barnsley在20世纪80年代后期为分形压缩奠定了理论基础。今天，很多人相信，分形压缩是图像压缩领域里最有潜力的一种技术体系。无论其前景如何，分形压缩

12、技术的研究与发展都提示我们需要一种新的理论，或是几种更有效的数学模型，以支撑和推动数据压缩技术继续向前跃进。 人工智能是另一个可能对数据压缩的未来产生重大影响的关键词。既然 Shannon认为，信息能否被压缩以及能在多大程度上被压缩与信息的不确定性有直接关系，假设人工智能技术在某一天成熟起来，假设计算机可以像人一样根据已知的少量上下文猜测后续的信息，那么，将信息压缩到原大小的万分之一乃至十万分之一，恐怕就指日可待了。1.3 数字图像加密技术  1.3.1图像加密技术的内容 数字图像信息安全, 是伴随着计算机网络和多媒体技术的

13、迅速发展而产生的新问题。近年来, 数字图像技术由于克服了以前因存储量过大带来的困难成为了信息表达方式的主流。研究数字图像信息安全中的隐藏和伪装算法, 归纳如下：      一种是数字图像置乱：数字图像置乱通过对数字图像的空间域进行置换或者修改数字图像的变换域参数使生成的图像变为完全看不懂的杂乱图像, 从而保护了数字图像所要表达的真实内容。学者们也提出了基于数学变换技巧的几种新算法, 包括Arnold变换、生命模型等, 被有效地应用于数字图像信息安全处理过程的预处理和后处理, 更大程度地

14、保证数字图像的信息安全。 另一种是数字图像信息隐藏：数字图像信息隐藏与经典密码学的信息隐藏类似, 将需要保密的数字图像信息隐藏在另外一幅公开图像中, 充分利用公开图像本身所具有的迷惑性, 降低攻击者的注意力, 减少遭受攻击的机会, 从而在很大程度上保护了数字图像的安全性。 1.3.2 图像加密安全性的要求  数字图像的安全性需求包含以下四个方面：（1)保密性，指图像的内容不允许被未授权用户或实体访问或利用；（2)完整性，指图像在存储或传输过程中保持不被非法修改、破坏或丢失；（3)鉴别性，指能证实

15、接收到的图像就是来自所要求的源方；（4)不可抵赖性，指接收方可以证明发送方确实发送了其接收到的图像，或者发送方不能否认其曾发送过图像。 1.3.3 图像加密技术的现状和发展       考虑到图像信息的一些特性，近年来发展了几种图像加密系统。他们按照加密时有无数据压缩可分为两大类，即加密的同时有数据压缩以及只有加密而无数据压缩两类。而按照加密的对象来分，可分为直接对图像数据进行加密和对图像数据编码的辅助信息进行加密。而按照加密的手段来讲也可以分为两大类：一类是应用图像数据的特点再加上现代密码技术来达到加密的目的，另

16、一类是建立一种完全新式的密码体制来达到对图像数据加密的目的。 这些分类方法实际体现在某一具体的算法上时实际是相互交叉的，具体来讲主要有记下几种技术：基于矩阵变换/像素置换的图像加密技术；基于伪随机序列的加密技术；基于SCAN语言的加密技术；基于图像的矢量量化压缩编码技术以及商业密码加密技术。图像加密技术沿着进一步提高保密性、加解密速度和压缩比同时降低计算的复杂度的方向发展。一类方法是将研究重点转移到基于小波等技术的压缩加密领域；另一类方法是对高维混沌序列的研究。今后可以进一步研究混沌技术与现有标准算法相融合的方法，利用标准算法的健壮性实用性，结合混沌现象优点提高系统的安全性和抗破译性

17、。1.4 课题研究的意义 近年来，随着计算机多媒体技术和网络通信技术的迅速发展，人们对图像和多媒体信息的需求不断增长。未经处理的图像信号的数据量是巨大的，使得图像信息的传输、处理和存储都受到限制。如何在相同的空间存储更多的信息以及在已有的带宽情况下，更快捷的传输更多的信息，研究高效的图像数据压缩编码方法，即怎样处理、组织图像数据，在应用领域中的作用将是至关重要的，图像数据压缩编码技术己经成为多媒体及通讯领域中的关键技术之一。如果没有数据压缩技术，那我们每次对数据信息进行提取和操作，与现在相比，将是个漫长复杂的过程，更无法在短时间内对海量信息进行检索。  

18、由于通信传输和接受设备的充分发展，通过无线电和一般的通信网络非法获取数据已经变得越来越容易9。因此，信息安全已经成为一个关键而迫切的问题，数字图像加密技术已经成为一项非常实用而又亟待快速发展的关键技术。一些非法分子利用网络截取第二代身份证信息犯罪，成为公安机关面临的一大挑战。要从根本上解决这个问题，就要在图像传输前，对它们进行压缩和加密。这样不仅实现图像的存储和快速传输图像，而且可以防止犯罪分子在截取图像的时候不能解密，无法获取原图像。 算术编码作为一种高效的数据编码方法在文本，图像，音频等压缩中有广泛的应用，研究算术编码以更好的利用它是非常必要的。另外，对于数字图像信息加密，需要设

19、计适合数字图像数据特点的图像加密算法，才能达到高效的目的。目前，为进一步减少在实时通讯中对数字图像的总体处理时间，将压缩编码和加密技术结合的方案已被提出。本课题旨在设计利用了算术编码特性的图像加密算法。第二章  算术编码的原理及特点2.1算术编码原理算术编码的基本原理是：根据信源可能发现的不同符号序列的概率，把0，1 区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率。这样信源发出的不同符号序列将与各子区间一一对应，因此每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。算术编码是一种无损数据压缩方法，也是一种熵编码的方法,

20、其每个符号所对应的码长被认为是分数10。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0  n < 1.0)的小数n。显然，一串符号序列发生的概率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因而相应的码字就越短。在传输任何符号串之前，0符号串的完整范围设为0,1。当一个符号被处理时，这一范围就依据分配给这一符号的那一范围变窄。算术编码的过程，实际上就是依据信源符号的发生概率对码区间分割的过程。举例说明算术编码工作过程如下，假

21、设有一符号集a,b,c,d,e,f具有如下的概率分布：从表中可以清楚的看到，某个符号的累计概率其实就是这个符号概率区间的下届，我们把概率符号统计出来是为了方便下面的计算。假设要传输消息“beacfd”。初始化时，编码器和解码器都知道初始的范围是0到1。消息的第一个符号b出现之后，编码器就会把初始区间由原来的0,1)缩小到0.2,0.5)。第二个符号e出现之后，因为e的概率范围是0.75,0.95)，所以刚刚得到的新的区间0.2,0.5)就会缩小到它0.75到0.95，即得到区间0.425，0.485)，以此类推，利用以下公式更新区间：其中，low和high分别是区间的下届和上届，range是当

22、前区间的范围，cum_freq是累计概率值，i是当前符号的编号，显然i+1就是下一个符号的编号。图2.1是以图形的方式展示算术编码的过程，带有刻度的竖线代表该示例中规定的符号概率分部。当第一个符号b被处理之后，区间的范围缩小到0.2, 0.5),当处理了第二个符号a之后，区间范围进一步缩小。但是这样不便于我们观察了，在图2.2中，我们把缩小的区间放大到竖线最大长度，数线的上下端标注了新区间的上下界值，这样这个示例的整个过程就一目了然了：解码是编码的逆过程，了解了编码过程后，理解解码过程的操作就相对容易了。通过编码，0.432176，0.432185)就是“beacfd”的唯一编码。可

23、以立即知道第一个符号是b，因为这个最终的区间完全落在这个示例中b的概率范围内。接下来，解码器就可以依照编码器的过程进行：初始0,1)确定了b之后，缩小范围到0.2,0.5)这样就可以清楚地知道第二个符号是e，因为之后只有是e才可以产生后来缩小的范围。确定了e之后，缩小范围到0.425，0.485)。依照这样的方法进行，译码器就可以解码出所有的符号。其实解码的时候没有必要知道编码之后区间精确地上下界，比如这个示例中，0.43218就足够可以正确解码，其他在最终区间里的数，例如0.432182，甚至是0.4321766都一样可以。但是译码器会遇到一个问题，就是如何判断何时结束解码。所以我们为每条消

24、息的末尾加上一个结束符EOF，这样一来编码器和解码器都知道何时结束工作。模型的效率可以用熵（平均信息量）来衡量。香农的信息论指出信息编码的比特量不可能少于信息的熵。哈弗曼编码对于all symbol probabilities are integral powers of 1/2的情况可以达到最小冗余，但是实际上并不总是这样，最差的情况是每个信号都有probability approaching unity。而算术编码并不需要将每个信号都编码成整数比特值。根据以上示例，具有六个符号的消息abcdef的熵是

25、 log0.2log0.3log0.1log0.15log0.2log0.05log0.0000095.046因为以上的编码用小数表示，所以底数取10。这就解释了为什么用了五个小数位对消息进行编码。事实上，最终的区间是0.432176-0.432185=0.000009，而且熵就是这个数的负对数。当然我们通常都是用二进制表示，用二进制传输而且用比特来度量熵值。用5个小数位来表示有六个元音字母的消息，看起来并没有起到很好的压缩效果。但是，不同的模型会得到不同的压缩效率。越复杂的模型，概率预测更精准。2.2算术编码的特点对以上论述进行归纳，我们可以得到算术编码的特点是： 概率模

26、型系统和编码是分离的； 信源符号概率接近时，此时算术编码效率高于其他编码方法。 算术编码绕过了用一个特定的代码替代一个输入符号的想法，用一个浮点输出数值代替一个符号流的输入。 算术编码虽然具有其独特的优点，但我们仍需要注意下面几个问题： 术编码器对整个消息只产生一个码字，这个码字是在间隔0, 1)中的一个实数，因此如上所述的编码器只有在对整条消息编码完成之后才会进行传输，译码器也只有在接受到表示这个实数的所有位之后才能进行译码。这个问题在下文3.2.3编码和解码模块的实现（2）增量传输和接收中解决。 消息的长度越长，对于区间的上下界精度要求就越高，由于实

27、际的计算机的精度不可能无限长，运算中出现溢出（包括上溢和下溢）是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。这个问题在下文3.2.3编码和解码模块的实现（2）下溢问题的解决以及（3）上溢问题的解决中细述。 要想提高算术编码的效率，就应该选择优化的概率统计模型，减少解码算法确定下一个符号的操作时间。对于优化的概率模型也要想办法尽量减少概率重排消耗。 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错 。2.3常用的算术编码类型首先要确定消息内容的符号集，在编码之前就确定了符号集的概率分布，而且统计好了每个

28、符号的累计概率。在压缩过程中不必再更新此概率分布，每次对区间的划分都依照此分布即可，解压时也用同样的概率统计。符号集的概率分布可以细分为两种，一种普遍适用于所有文本本件中符号的统计概率；另一种是对要编码的文件中的符号的统计概率，这一种在解码的时候就必须先知道原始文件中符号的统计概率。其实静态模型无法适应信息的多样性，例如，我们上面说到的第二种概率分布没法在所有待压缩信息上使用，为了能正确解压缩，我们必须再消耗一定的空间保存静态模型统计出的概率分布，保存模型所用的空间将使我们重新远离熵值。其次，静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编

29、码压缩更加缓慢。2.3.2算术编码自适应概率模型与静态概率模型不同，自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率，换句话说，自适应模型边编码边统计，编码器模型随着每一个信号的传输而改变，解码器模型随着每一个收到的信号改变。得到的概率分布将有利于对信息的压缩。每当完成对一个符号的编码之后，要更新概率模型，重新统计累计概率，这必然会有时间和空间的消耗，所以要设计高效的处理方法，以便很好的利用自适应概率模型。第三章  算术编码的设计和实现3.1功能模块的划分首先，介绍完整的工作流程如下：  取图像文件：首先浏览选择磁盘上的图像文件

30、，读取图像信息的方式是将bmp文件头，信息头，调色板以及像素信息读取到orbmp_info_stream.txt文件。   压缩数据文件：选择不同的概率模型，编码过程以字符为 单位进行算术编码，编码结果也以字符为单位输出到encoded_text.txt文件，并在界面返回压缩比例。 压数据文件：以编码时相同的概率模型，读进encoded_text.txt文件，以字符为单位解码文件，输出到decoded_text.txt文件。解压的过程完全是压缩的逆过程，因为算术编码是一种无损压缩，并且其压缩处理的模式也决定了它解压生成的将是与压缩前完全一样的数据文件，因此，通过解压最后生成的文件即是

31、与原文件完全一致的文件，即decoded_text.txt和orbmp_info_stream.txt应有完全相同的内容 原图像文件：decoded_text.txt已经包含了原bmp所有的文件信息，所以只需将它们以bmp的存储格式保存，即可还原图像文件。然后指定保存路径进行保存。本设计用MFC进行界面的设计编写，主界面如图3.1所示。 所以综合以上步骤，本设计分为图像读取模块、输入模块、压缩模块、解压模块、输出模块、图像还原模块几大模块。3.2功能模块的具体实现 按照软件模块的划分，本软件共分为图像读取模块、输入模块、压缩模块、解压模块、输出模块、图像还原模块。图像读取模

32、块和图像还原模块是利用bmp处理类Class CDib，C+类库中的方法实现bmp图的数据获取和图像还原；输入模块和输出模块主要是用程序设计语言类库中的方法执行对文本文件的确认/建立、读取/写入、以及对文件的相关位置进行标记等；而压缩模块和解压模块的主要功能则是用算术编码的方法对指定的文件进行编码和解码的操作，同时还要解决精度和溢出的问题，具体实现下面分读取还原、输入输出、编码解码三个部分进行说明。3.2.1图像读取模块和还原模块的实现 bmp格式简介  BMP是英文Bitmap（位图）的简写，它是Windows操作系统中的标准图像文件格式，能够被多种W

33、indows应用程序所支持。这种格式的特点是包含的图像信息较丰富，几乎不进行压缩，也因此导致占用磁盘空间过大。所以，我们选择对bmp文件进行算术编码，研究算术编码的压缩效率12。位图主要有三部分组成：位图文件头，文件信息和像素数据信息。其中文件信息又包括文件信息头和调色办板信息。需要说明的是不是所有得位图都是很有调色板的，只有深度在16（包括16）才有调色板信息，所以在非数据区域，应该分两种情况讨论：第一种是位深度为1，2，4，8得，其中有调色板，所以一副完整得位图应该是14字节得位图文件头加上40字节得文件信息加上2得位深度次幂乘4（调色板颜色数据）加上数据信息（如8位得一个象素一个字节，代

34、表调色板中颜色信息，然后到调色板中寻找颜色）。第二种情况是16，24，32位深度得位图，其中没有调色板信息，使用得是系统的调色板，所以位图中不需要存储。这样一副完整得位图应该是14字节得位图文件头加上40字节的文件信息加上数据信息（一个象素分别由3，4个字节表示）。 因为文件头和信息头的数据会影响像素数据信息的统计概率，所以我们要根据具体的bmp格式保存不同大小的信息头和文件头，然后只对像素信息进行编码。 图像选择和读取       图像读取首先要在在浏览对话框中选择要处理的图像，如下图3.2所示。这里的实现设置了

35、文件格式过滤器。确认了选择好的文件之后，就获得了该文件的路径和文件名，并显示图片。读取图像文件的实质就是把图像文件的格式信息和像素信息写入一个文本文件，方便算术编码工作。首先创建bmp处理类的一个对象，把已经选择的文件加载到这个对象上，再调用该类的write(CFile* pFile)方法写入到指定的文本文件，pFile就是指向文本文件的指针。这个写入文件的方法原理很简单，首先定义位图文件头对象，并设置文件头对象各项的值，这样就可以调用系统的文件操作写函数把文件头写入文本文件；其次是信息头和调色板以及像素信息，这两个数据块的首地址和大小都已经得到，所以再调用两次文件操作写函数把这些数

36、据写入文本文件，读取图像文件完成。图像还原和保存       还原图片是读取图片的逆过程，是要把文本文件的内容重新读取出来。首先定义位图处理类的对象，调用该类的Read(CFile* pFile)方法。同中介绍的write(CFile* pFile)方法一样，Read(CFile* pFile)方法是分别处理由文件指针pFile指向的文件的文件头，信息头和调色板以及像素信息三个数据部分，在获得了三个部分大小等信息之后，分配内存并直接调用系统的读文件函数把数据信息读到指定的内存区域。 图像的保存首

37、先在保存对话框里选择路径和设置文件名，如图3.3显示。这里的实现同样设置了文件格式过滤器。确认之后，程序获得保存路径和文件名，并以此信息创建新的位图文件，位图处理类对象再次调用write(CFile* pFile)方法，把还原后的数据信息写入文件指针pFile指向的刚刚创建的新的位图文件，图像保存完成。图3.3 位图保存对话框界面 像的显示 在确定好要处理的文件和保存好还原之后的图片之后会调用图像显示的功能。对于图像的显示，在程序中定义了一个基于对话框的类Class ShowDialog。该类中增加了一个获取文件基本信息的方法，即获得文件的路径和文件名，

38、另外重写了OnPaint()方法，在对话框生成的时候，由于消息映射机制，重写的方法会自动调用，根据文件路径和文件名按照原图像的尺寸把位图显示在对话框中，对话框的位置在屏幕的中心如图3.4所示。3.2.2输入输出模块的实现比特输入模块 该模块与解码功能模块配合，从编码文件encoded_text.txt里逐个读取字节，向解码模块依次返回每个字节的比特位进行解码操作。以下是图3.5(a)比特输入模块的工作流程图，解码出的字符只需用库函数就可以输出到解码文件。 比特输出模块 该模块与编码模块配合，编码模块调用库函数就可以从图像信息的源文件orbmp_info_strea

39、m.txt中逐个读取字节，编码结果以比特为单位  暂存在比特输出缓冲区，该输出模块就是要将编码结果再以字符形式输出到编码文件encoded_text.txt。以下图3.5(b)是比特输出模块的工作流程图：3.2.3编码和解码模块的实现基本说明 根据1.1.3数据压缩与编码的介绍，数据在压缩即编码前，要被划分为一个一个的基本单元，基本单元既可以是单个字符，也可以是多个字符组成的字符串。在本文程序实现中，我们以字节作为基本单元，一个字节代表0到255的一个整数（字符型）。在程序中，信号的索引值设定为1，2，3 ,源消息集就是ASCII码对应的256个字符加上

40、文件结束符EOF，ASCII值加1就是每个符号的索引值，EOF的索引值是257。 在自适应模型中，概率模型不断更新，概率要重排序。为实现这种重排序，并且减少解码执行的循环量，要用到两个数组index_to_char和char_to_index，有利于符号和索引值的转换。虽然在静态模型当中，直接在字符加1就得到了索引值；但是在更复杂的自适应模型当中，为频繁使用的信号分配了小的索引值，两个数组的他们具体的工作流程在下文（5）两种概率模型的实现细述。  对于算术编码，消息的长度越长，对于区间的上下界精度要求就越高，由于实际的计算机的精度不可能无限长，所以我们用整数来表示

41、概率。在这两个模块的实现中，信号的概率存放在数组freq中，累计概率存放在cum_freq中，第i个信号的概率是cum_freqi到cum_freqi-1,即当i减少的时候，cum_freqi在增加，这样逆向的设置目的在于把概率总值存放在cum_freq0中来标准化所有的频率，同时也有利于累计概率的统计工作。增量传输和接收 在2.2算术编码的特性里我们知道，所有内容被编码之后才会传输，解码器接收完了内容之后才开始工作。而在实际中，我们希望编码和解码能有实时的传输。 如果编码区间一直缩小，精度会不够，所以有一个重整化的过程，也就是如果当前的编码区间小于某一个长度时，就把当前区

42、间扩大。例如，如果当前区间的上下界值low和high都大于区间总长度的二分之一，那么如果用二进制来表示的话，low和high的最高位就都是1，这时就把这个1输出，因为它们不会受到将来的缩小的影响，剩下的数字再构成新的区间，这样就相当于要把当前区间扩大，也达到了可以实时传输码字的效果。 对于编码，既然我们知道lowhigh，上下界值最高位有同为0或1两种情况，可以要求编码如下：其中，low和high就是编码区间的上下界值，Half是最大编码区间的二分之一的值，output_bit()就是3.2.2中介绍的比特输出模块。这样就可以保证在结束的时候，lowHalfhigh。对于解码，在解码

43、过程中，用变量value存放解码器收到的编码值，初始化工作时，读进16个比特进制转换之后给value赋值，一旦解码操作认定了下一个输入的信号，它就移出区间上下界值low和high中没有用了的高位比特，同时也将value减少相同数量的比特位，要求代码如下： for (;)   其中，low和high就是编码区间的上下界值，Half是最大编码区间的二分之一的值，input_bit()就是3.2.2中介绍的比特输入模块。下溢问题的解决      下溢的意思就是超出所能表示的最小数，算术编码过程中假设某一次区间缩

44、小之后，区间的上下界值high和low非常接近，以至于这个操作将不同的符号映射到low, high里的同一整数，这会导致编码不能继续进行。所以编码过程必须保证low, high足够大来避免这种情况。最简单的方法就是保证这个区间至少是最大累积概率值Max_frequency： 增量发送中介绍的方法保证了在当前区间的上下界值high和low同时在最大区间的上半区或是下半区，当彼此非常接近时下溢问题的解决方法。事实上还有一种情况： 其中，low和high就是编码区间的上下界值，First_qtr和Third_qtr分别是最大编码区间四分之一和四分之三的值。 这

45、时high和low非常接近了，那么接下来编码得到的两个比特的值肯定相反，而且一旦出现这种情况要把First_qtr, Third_qtr扩展到整个区间，所以实际的编码代码如下： 因为当是第三种情况，即编码区间在最大区间的中间半区时，区间经过一次缩放之后，有可能继续满足这个条件，所以要用一个变量来统计与下一比特值相反的的比特的数量，直到不满足这个条件为止。那么在接下来的比特输出后，要继续将刚刚用统计的相反值的比特输出，所以借助一个bits_ plus_follow（）函数，而不是直接用3.2.2中介绍的输出功能模块：其中output_bit( )就是3.2.2中介绍

46、的输出功能模块，bits_to_follow就是统计具有相反值的比特数量的变量。通过这种方法，编码器可以保证，在移位操作之后，会有下面两种情况：其中，high和low就是编码区间的上下界值，First_qtr，Half和Third_qtr分别是最大编码区间四分之一，二分之一和四分之三的值。所以，只要满足式(3.3)就不会有下溢的问题出现：因为Top_value的值是216-1（编码值code_value也可以设置为8位或者其他），所以最大概率值用14个比特位表示。若没有增加安排给code_value的比特数量，大于14比特位的值就不能用来表示累积函数值。概率值的上限Max_frequency可

47、以选择更少的比特位数，但是2141是在不溢出的情况下所取的最大的值，值越大精度越高。只要解码操作遵循同样的方法进行以上条件下的扩展，也会避免下溢的情况。上溢问题的解决 上溢就是超出所能表示的最大数，在编码和解码更新区间值做乘法的时候有可能出现上溢的情况： 编码解码过程编码区间更新方法相同：其中，high和low分别是当前区间的上下界，range是当前区间的范围，cum_freqi是信号的累计概率值，cum_fraq0存放累积概率总值,用于标准化所有概率， Max_frequency是概率值的上限。因为累计概率值不会超过Max_frequency，所以只要range

48、*Max_frequency在整数字长允许范围内就不会出现上溢。范围range可能会达到Top_value+1，所以程序里可能的最大乘积就是 (214-1)216。编码值Code_value 和区间范围range都是定义的长整型long，这就保证了乘法运算结果是32位的精度，避免了上溢问题的出现。两种概率模型的实现 （1） 静态的概率模型其实就是编码解码之前，概率统计完成，程序中有两种静态的概率统计，一种是统计需编码的文件中字符的出现概率；另一种是参考英文中字符概率，其中概率被标准化到总数8000（也可设置其他值）。那些不出现的字符被给定了数1表示他的概率。静态模

49、型的初始化工作就是建立符号和索引值的转换表，并计算这些符号的累积概率。其中，No_of_chars是字符的数量，值为256，No_of_symbols是符号总量，即字符加上文件结束符，值为257，freq和cum_freq分别是符号的概率表和累计概率表，index_to_char和char_to_index符号索引值和符号之间的转换表。在编码解码过程中，概率统计保持不变。（2） 自适应的概率模型的初始化工作仍然是建立符号和索引值的转换表，并将所有符号的概率设置为1，并计算这些符号的累积概率，建立转换表和计算累计概率的方法和静态模型是一样的。在码解码过程中，概率统计要不断更新，工作流程图如图3.

50、6所示：寻找新的索引值，然后更新索引值和符号转换表的作用就是实现了概率的重排序，这样可以保证概率表freq中的概率是从大到小排序的，这就意味着字符的排列已按照其出现频率重新排序，到下一次更新概率模型寻找新的索引值的时候，就变成了线性搜索，效率较高。 上几个问题解决了之后，可以总结编码、解码流程图如图3.7所示：解码过程步骤说明：已知了当前的区间范围range和上下界值high和low，通过以下式子就可以求出要解码出的符号的累计概率：其中，low是编码区间的下界，value就是编码值，cum_freq0保存了概率总值，减1是为了不包含上界。接下来很容易求取该符号的索引值symbol。 

51、因为三个概率模型中，初始化的时候让每个概率值至少都为1，所以他们的概率区间是不会重叠的，也就是说相邻的索引值对应的符号的累计概率是不会相等的，所以当前区间利用编码值value求得的累计概率一定落在两个累计概率之间，有以下关系：在式（3.6）和（3.7）中，high和low是编码区间的上下界，value就是编码值，cum_freq是符号的累积概率表，cum_freq0保存了概率总值。所以这就充分确定了解码操作正确的判断了每一个信号。3.3 三种概率模型性能的比较分析3.3.1压缩效率表3.1是选择了不同长度的文件，统计了三种概率模型的编码效率。我们可以看到，对于普通静态模型，随着处理的

52、数据量增加，它的压缩比在增加，即编码效率在降低。另外两种模型的压缩比例虽然也都有所增加，但是都逐渐保持了稳定的水平，而且自适应模型还要更优于基于内容的静态模型。为了更容易的比较，三种模型压缩概率比较的曲线图如图3.8所示：3.3.2执行时间虽然根据3.3.1分析，我们知道了自适应概率模型是相对来说最优的概率模型，有较好的压缩效率，但是为了实现概率重排，自适应的概率模型的更新过程会消耗时间，但是由表3.2我们可知，正是因为我们利用转换表实现重排功能有较高的时间效率，其他两种模型的执行时间优势并不明显，所以综合来说，自适应模型是最优的概率模型。第四章  基于算术编码的图像加密算

53、法的设计和实现4.1 加密算法的设计在密码学中，混乱与扩散是香农提出的设计密码系统的两个基本方法。混乱就是使密文和密钥之间的统计关系变得竟可能复杂，可以使解密者无法从明文与密文的对应关系中寻找不出它们与密钥之间的联系。扩散就是指将明文的统计特性散布到密文中去，明文或密钥某一位发生变化则对应的密文将面目全非。 对于基于算术编码的图像的加密算法的设计，首先值得考虑的一点是加密算法不能对编码效率产生较大的负面影响，否则算术编码的优越性不能体现13。其次，算术编码是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。 在很多传统的加密方案里，都是以扰乱原始信息的概率统计为基本思想14，例如对像素信息异或者更换，这虽然符合加密算法设计的要求，但是算术编码对概率敏感，可能会导致很差的编码效率。 结合这几点考虑，本文提出了一种基于算术编码的随机置换图像数据块的加密