现代编码技术

现代编码技术第1页，课件共100页，创作于2023年2月

8.1传统信源编码的应用根据信源编码技术的发展可以将其分为传统编码技术与现代编码技术两大类。传统编码技术主要有脉码调制(PCM，PulseCodeModulation)、量化法(Quantization)、空间和时间子抽样编码(SpatialandTemporalSubsamplingCoding)、熵编码(EntropyCoding)、预测编码(PredictiveCoding)、变换编码(TransformCoding)、矢量量化(VQ，VectorQuantization)、子带编码(SBC，SubbandCoding)等方法。第2页，课件共100页，创作于2023年2月这些方法前面已经介绍过，下面以图像信源为例简述传统信源编码技术的应用。采用脉码调制方法进行信源编码时，输入的连续信号通常以Nyquist速率采样，然后均匀量化。因此，它只是原始模拟信号的一种数字表示。量化器通常有N个电平，其中N是2的乘方(N＝2b)，每个采样由一个具有b比特的固定长度的二进制码示。使用PCM对像素编码所需的比特数取决于被编码信源的类型。通常来说，单色广播或会议电视图像用8比特就足够了；而医学图像则可能需要10比特或更多，以保证足够的幅度分辨率。第3页，课件共100页，创作于2023年2月对于彩色图像，每个彩色分量通常需要8比特，因而表示一个彩色像素共要使用24比特。PCM编码的效率是不高的，原因之一是PCM忽视了像素之间的空间和时间相关性；之二是它对所有量化幅度电平进行同样处理，即均匀量化；另外一个原因是它没有利用人眼的视觉特性。第4页，课件共100页，创作于2023年2月量化是一个相当直观的数据压缩方法，其过程相当于将输入数据的取值范围加以限制。比如，图像像素，即图像中的一个采样点的灰度值是用8比特二进制数表示，将其灰度量化至2比特，即用2比特二进制数来表现原8比特的数据。显然，在数据量上，量化后的比特数是原来的0．25倍，相应压缩比为4∶1。量化过程的实际做法是利用量化查找表使一个输出值对应于若干个输入值。量化算法利用人的视觉对不同亮度值域的敏感程度不一样的特点，在一定输出图像质量的前提下，调节量化查找表达到最佳的压缩比。根据量化查找表的性质，量化算法分为线性与非线性两类。第5页，课件共100页，创作于2023年2月在电视、电话等某些应用中，全分辨率不是必需的。这时，可以使用空间和时间子抽样来降低数据速率。在编码器中，从每几个像素中选择一个像素，从每几帧中选择一帧，然后加以传输。在译码器中，可根据接收的像素和帧内插丢失的像素和帧，再生出分辨率较低的原始视频序列。如果像素是由色度和亮度分量表示的，那么可以以较高的比率对色度分量进行子抽样，量化更粗略一些，这是因为人眼对色度分量的敏感性低一些。这种技术非常简单，但十分有效。第6页，课件共100页，创作于2023年2月熵编码是纯粹基于信号统计特性的编码技术。它是一种无损编码，解码后能无失真地恢复原信息。熵编码的基本原理是给出现概率较大的符号一个短码字，而给出现概率较小的符号一个长码字，这样使得最终的平均码长很小。一个精心设计的熵编码器，其输出的平均码长接近信源的信息熵，即码长的下限。常用的熵编码方法有游程编码、霍夫曼编码和算术编码三种。游程编码主要用于量化后出现大量零系数的情形，利用游程来表示连零码，降低为表示零码所用的数据量。霍夫曼编码是一种不等长最佳编码方法。所谓最佳是指对于相同概率分布的信源这种编码的平均码长比其他任何一种有效编码的平均码长都短。霍夫曼编码必须知道信源的概率分布，这一般是无法做到的。通常采用对大量数据进行统计后得到的近似分布来代替实际的概率分布。第7页，课件共100页，创作于2023年2月算术编码是20世纪80年代发展起来的一种熵编码方法，已渐渐受到人们的注意。它的基本原理是，任何一个数据序列均可表示成0和1之间的一个间隔，该间隔的位置与输入数据的概率分布有关。可以根据信源的统计特性来设计具体的编码器，也可以针对未知概型的信源来设计能够自适应适配其分布的算术编码器，并且这两种形式的编码器均可以用硬件实现。有关的实验数据表明，在未知信源概率分布的大部分情形下，算术编码要优于霍夫曼编码。上述三种熵编码方法均已被各种编码标准采纳。第8页，课件共100页，创作于2023年2月预测编码有线性预测和非线性预测两类，它们可以在一幅图像内进行(帧内预测编码)，也可以在多幅图像之间进行(帧间预测编码)。预测编码基于图像数据的空间和时间冗余特性，用相邻的已知像素(或图像块)来预测当前像素(或图像块)的取值，然后再对预测误差进行量化和编码。这些相邻像素(或图像块)可以是同行扫描的，也可以是前几行或前几帧的，相应的预测编码分别称为一维、二维和三维预测，其中一维和二维预测是帧内预测，三维预测是帧间预测。预测编码的关键在于预测算法的选取，这与图像信号的概率分布很有关系。第9页，课件共100页，创作于2023年2月实际中常根据大量的统计结果采用简化的概率分布形式来设计最佳的预测器，有时还使用自应预测器以较好地刻画图像信号的局部特性，提高预测效率。线性预测编码又称为差分脉冲编码调制，即DPCM(DifferentialPulseCodeModulation)。帧内预测编码一般采用像素预测形式的DPCM，其优点是算法简单，易于硬件实现，缺点是对信道噪声及误码很敏感，会产生误码扩散，使图像质量大大下降。同时，帧内DPCM的编码压缩比很低，因此现在已很少独立使用，一般要结合其他的编码方法。帧间预测编码主要利用活动图像序列相邻帧间的相关性，即图像数据的时间冗余进行压缩，可以获得比帧内预测编码高得多的压缩比。第10页，课件共100页，创作于2023年2月帧间预测编码作为消除图像序列帧间相关性的主要手段之一，在视频图像编码方法中占有很重要的地位。帧间预测编码一般是针对图像块的预测编码，它采用的技术有帧重复法、阈值法、帧内插法、运动补偿法和自适应交替帧内／帧间编码法等，其中运动补偿预测编码现已被各种视频图像编码标准采用，得到了很好的结果。这类图像编码方法的主要缺点在于对图像序列不同的区域，预测性能不一样，特别是在快运动区，预测效率很差。而且为了降低预测算法的运算复杂度和提高预测精度，一般先对图像进行分块，然后再预测，这势必造成分块边缘的不连续。第11页，课件共100页，创作于2023年2月与预测编码技术相比，消除图像数据空间相关性的一种更有效的方法是进行信号变换，使图像数据在变换域上最大限度的不相关。尽管图像变换本身对数据并未进行压缩，但由于变换后系数之间的相关性明显降低，图像的大部分能量只集中到少数几个变换系数上，采用适当的量化和熵编码可以有效地压缩图像的数据量。而且图像经某些变换后，系数的空间分布和频率特性有可能与人眼的视觉特性匹配，第12页，课件共100页，创作于2023年2月因此可以利用人类视觉系统的生理和心理特点而得到较好的编码系统。变换编码通常是将空间域相关的像素点通过变换映射到另一个频域上。在变换后的频域上应满足：所有的系数相互独立；能量集中于少数几个系数上；这些系数集中于一个最小的区域内。保留少数重要的系数就能够很好地恢复出图像，人眼几乎觉察不出那些损失的系数。第13页，课件共100页，创作于2023年2月

KLT变换是在以上思路下构造出来的最佳线性变换方案。它是用数据本身的相关矩对角化后构成的，这种变换将产生完全不相关的变换系数。如果图像数据之间是高度相关的，经过KLT变换，系数将出现多个零值；同时，某些系数的值会很小。KLT变换的变换矩阵是由图像数据本身求得的，不同的图像数据有不同的变换矩阵。如此造成反变换矩阵的不惟一性；加之KLT变换矩阵的构造计算量很大，因而它不是一种实用的变换方法。第14页，课件共100页，创作于2023年2月尽管如此，KLT变换毕竟是线性变换压缩编码方法的一个最佳方案，通常可作为衡量其他线性变换性能的基准。就数据压缩而言，所选择的变换方法最好能与图像信号的特征匹配，此外还应从失真要求、实现的复杂度以及编码比特率等多方面进行综合考虑。KLT变换虽然是均方误差准则下的最佳变换，但在实际编码工作中，人们更常采用离散余弦变换DCT。第15页，课件共100页，创作于2023年2月在现行变换编码方法中，对大多数图像信源来说，DCT变换是最接近KLT变换的方法。对变换后图像系数的编码一般采用门限编码加区域编码的形式。以DCT为例，根据变换系数的能量分布，可以将图像划分为不同的区域。其中变换后幅值较大的图像系数大多集中于图像块的左上角。与其他系数相比，这些低频系数具有的能量最大，包括了图像的大部分内容，在变换图像中的地位最重要，应使它们的量化误差最小。同样，对于图像块的其他区域，也应采用与该区域相匹配的量化和编码形式。这种根据能量分布对不同区域采用不同量化编码的技术称为区域编码。第16页，课件共100页，创作于2023年2月另一方面，变换后图像的许多系数很小，仅占原图像能量的很小比例，对图像质量影响甚微，因此一般通过设定阈值的方法，将小于阈值的变换系数置零，从而大大提高编码效率。经门限和区域编码后，变换后图像的大部分系数为零，如何采用有效的方法将非零系数和零系数组织起来，在保证最少冗余的同时使连零系数出现概率最大，是变换图像编码面临的又一关键问题。在DCT图像编码方法中，对变换系数进行的Zigzag排序非常巧妙地解决了这一问题，但对有些图像变换方法，这种技术并非最佳。第17页，课件共100页，创作于2023年2月在一般图像中，对应轮廓边缘位置附近含有大量高频信息，它们相对于原图像是非常局部的，代表了图像数据的精细结构。按人眼的视觉特性，这些轮廓边缘信息对于图像的主观质量很重要，在编码时应给予特别考虑。然而由于传统的正交变换的时频局域性很差，变换后的系数失去了对原图像精细结构的描述，从变换图像得不到图像轮廓边缘的局部信息，因此在量化编码时无法采用特殊的方法。而且在传统的变换图像编码方法中，大多是靠丢弃高频系数来提高压缩比的，从而导致图像的轮廓边缘模糊，严重影响复原图像的主观质量，这是传统变换编码方法的缺点之一。第18页，课件共100页，创作于2023年2月传统变换编码方法的另一缺点是提高编码压缩比时会出现块效应。这是因为为降低变换算法的运算复杂度和提高编码效率，传统图像变换方法均采用分块变换技术。图像块大，相关性就高，压缩比也就大。但是块的尺寸太大又会丢失数据的平稳性，从而引入误差，包括失去高频细节、引入沿物体边界的噪声和可见的DCT图块边界。第19页，课件共100页，创作于2023年2月传统的变换图像编码方法的这些缺点使得它们不适合于需要较高压缩比的应用场合。究其根本原因，在于变换方法不具有良好时频局域性和全局变换的特点。实现实用的变换编码系统，主要分四个步骤。第一步是选择变换类型，DCT变换是应用最广泛的一种类型。第二步是选择方块的大小，较好的方块尺寸是8×8或16×16。第三步是选择变换系数，并对其进行高效的量化，以便传输或存储。第四步是对量化系数进行比特分配，通常使用霍夫曼编码或游程编码。第20页，课件共100页，创作于2023年2月8.2现代信源编码技术

20世纪80年代中后期，相关学科的迅速发展和新兴学科的不断出现为信源编码的发展注入了新的活力。人们对信源信息需求的剧增也有力地促进了信源压缩编码技术的进步。许多学者结合模式识别、计算机图形学、计算机视觉、神经网络、小波分析和分形几何等理论开始探索信源信号压缩编码的新途径。第21页，课件共100页，创作于2023年2月现代信源编码方法是针对传统编码方法中没有考虑人眼对轮廓、边缘的特殊敏感性和方向感知特性而提出的。它认为传统的编码技术以信息论和数字信号处理技术为理论基础，出发点是消除信源数据的线性相关性等统计冗余信息，其编码压缩信源数据的能力已接近极限，压缩比难以提高，例如对静止图像而言，这类方法的编码压缩比一般为10～20倍左右。现代信源编码方法不局限于香农信息论的框架，要求充分利用人类视觉系统的生理和心理特性以及信源的各种性质以期获得高压缩比。第22页，课件共100页，创作于2023年2月

8.2.1分形编码自然界由许许多多形状复杂的图形而构成，归纳起来它的形状和各种图形可分为两类：一类是有特征长度的图形，可用欧几里德几何学来描述和构造，例如房屋、汽车、足球、人等等，它们都是由具有特征长度的图形构造的，像房屋的高、宽，汽车的长度，足球的直径，人的身高等都是特征长度；另一类是没有特征长度的图形，例如海岸线、云彩、蛋糕的空穴等等，如果没有人工参照物，很难测量其尺度。第23页，课件共100页，创作于2023年2月如何构造这些无规则的复杂现象和物体直到20世纪70年代才得以解决。1975年波兰出生的美国数学家曼德尔布诺特(MandelbrotBB)首先研究了这种不规则形状和过程的性质，建立了自然界的分形几何理论。分形就是那些没有特征长度的图形的总称。曼德尔布诺特认为分形是几何外形，它与欧几里德几何外形相反，是没有规则的。首先它们处处无规则可言，其次它们在各种尺度上都有同样的不规则性。第24页，课件共100页，创作于2023年2月即分形几何研究的对象是无规则的图形，且这种无规则图形从整体到局部变化，虽然均属无规则性，但具有自相似性(Selfsimilarity)。换言之，无论几何尺度怎样变化，事物任何一小部分的形状都与较大部分的形状极其相似。这种尺度不变性(Scaleinvariance)在自然界中广泛存在。分形中最显著的特点是自相似性，如弯弯曲曲的海岸线，洁白无瑕的晶状雪花，变换无穷的云彩，蕨类植物的叶子，排列成格状的峰窝等，它们都是自相似性的典型例子。第25页，课件共100页，创作于2023年2月分形图之美丽，分形几何学之奇妙就在于它的自相似性，而从编码的角度，正是要恰当地、最大限度地利用这种自相似性。分形方法可以用于压缩编码的原因之一就是分形的自相似性。根据分形理论，不少复杂的图形，从信息论和计算观点来看，其信息含量并不大，一般只需要不多的数据，利用迭代函数系统迭代这全反馈的动态过程，在计算机上利用简单的算法和程序就可以产生相当复杂的自然图形。复杂的图形寓于简单算法之中，这是分形方法可以用于压缩的另一个主要依据之一。第26页，课件共100页，创作于2023年2月自然界许多事物的发展过程，如生长、凝聚、进化等形成多种多样的分形结构。例如人体的血液循环系统，从主动脉到毛细血管，直到血球细胞只能排单行滑行等分支都呈现一种分形结构。又如树木的枝叶也呈分形形态，用以获取阳光、空气，吸入二氧化碳排出氧气和抵抗风力。生物学家对植物种子基因研究发现，种子内只有一定的信息为植物编码，有限的基因产生了复杂的生物界，人类也是如此，所以植物等的复杂程度是有限的。它只不过是在生长过程中新陈代谢而形成的复杂分形形态。因此，分形意味着自然界许多复杂形态中潜藏着有组织的结构。如果能找到这些有效的信息，就能简单地表述自然界复杂的景象。这是能够采用分形方法进行压缩的又一个依据。第27页，课件共100页，创作于2023年2月

8.2.2模型编码基于模型的信源编码技术是近几年发展起来的一种很有前途的低比特率编码方法。它利用了计算机视觉和计算机图形学中的方法和理论。其基本出发点是在编、解码两端分别建立起相同的模型。基于模型的编码器并不压缩实际的量化数据，而是采用一个表示景物(一般是人、人脸等)的模型，传送的信息是告诉接收方如何改变模型以匹配输入景物(如眨眼、扭头等)。基于模型的解码器也有一个与对应编码器相同的模型，解码器利用收到的数据调整其模型，然后生成供显示的图像。模型编码根据输入的图像提取模型参数，并根据模型参数重建图像。第28页，课件共100页，创作于2023年2月显然，模型编码方法的核心是建模和提取模型参数，其中模型的选取、描述和建立是决定模型编码质量的关键因素。从信息抽取功能的角度看，已经提出的模型包括：图像模型——回答目标图像如何被模型化才会有效的问题；视觉模型——描述重建图像后，人类视觉系统感知误差的形式和能力。这两种模型中，前者是模型法主要研究的对象，后者则偏重于在编码过程中引入人的视觉特性以便得到更好图像质量。从建立图像模型的复杂度和灵活性等角度考虑，三维线框模型(即用很多三角曲面片来逼近目标图像)是最好的，其他模型则因计算复杂和缺乏灵活性而很少使用。第29页，课件共100页，创作于2023年2月为了对图像数据建模，一般要求对输入图像要有某些先验知识。目前研究最多、进展最快的是针对可视电话应用中的图像序列编码，这类应用中的图像大多为人的头肩像。实质上此时的编码器是一个特征检测器，译码器是一个三维显示程序。基于模型的图像编码方法利用先验模型来抽取图像中的主要信息，并以模型参数的形式表示它们，因此可以获得很高的压缩比。在模型编码(ModelbasedCoding)方法的研究中还存在很多问题，例如：第30页，课件共100页，创作于2023年2月

(1)模型法需要先验知识，不适合于一般的应用；

(2)对不同应用所建模型是不一样的；

(3)在线框模型中，控制点的个数不易确定，还未找到有效的方法能根据图像内容来选取；

(4)即使对头肩模型，也存在很多问题，例如由特定人模型推广到非特定人、模型参数的快速抽取、表情运动参数的计算等都没有很令人满意的解决方法，大部分系统还依赖于FACS(FacialActionCodingSystem)中对表情块AU(ActionUnit)的描述，需要专用交互式系统，运算的复杂度极高；第31页，课件共100页，创作于2023年2月

(5)由于复原图像是用图形学的方法产生的，看起来不够自然，尽管有纹理映射的方法，但结果仍有待进一步改进；

(6)传统的误差评估准则不适合于对模型编码的评价。除此之外，如何利用人的视觉特性也是这种编码方法中一个没有解决的问题。模型图像编码方法的上述缺陷使得它的应用范围受很大限制，而且走向实用还需要一段时间。第32页，课件共100页，创作于2023年2月

8.2.3小波编码小波变换的发展经历了一个漫长的过程。1910年Haar提出了小波规范正交基，这是最早的小波基，当时并没有出现“小波”这个词。1936年Littlewood和Paley对Fourier级数建立了二进制频率分量分组理论：对频率按2j进行划分，其Fourier变换的相位变化并不影响函数的大小，这是多尺度分析思想的最早来源。1946年Gabor提出的加窗Fourier变换(或称为短时Fourier变换)对弥补Fourier变换的不足起到了一定的作用，但并没有彻底解决这个问题。后来，Calderon、Zygmund、Stern和Weiss等人将L[CD*2]P理论推广到高维，并建立了奇异积分算子理论。1965年，Calderon给出了再生公式。第33页，课件共100页，创作于2023年2月

1989年，S.G.Mallat首先将小波变换用于多分辨率图像的描述。这个多分辨率的图像描述叫做图像的小波分解。小波的图像分解方案实际上属于子带分解的一个特例，小波变换特别要求滤波器的正则性。小波分解是完备的、正交的，且是多分辨率的分解。在空间域里，小波分解将信号分解为不同层次，每一层次的分辨率不同。由于小波分解方法本身的正交性，分解后不同层次数据之间的相关性完全由数据本身的相关性所决定。由此排除了由于分解方法内在的相关性而造成数据之间呈现相关性的混淆。第34页，课件共100页，创作于2023年2月小波变换在空间域中进行多层次分解运算的同时形成了频率域中的多层次分解。在频率域中的每个层次上，高频分量与低频分量的分布与原数据中频率分布的方向有关。第35页，课件共100页，创作于2023年2月8.3密码学研究现状及趋势密码理论与技术分成两大类，一类是基于数学的密码理论与技术，包括公钥密码、分组密码、序列密码、认证码、数字签名、Hash函数、身份识别、密钥管理、PKI技术、VPN技术等；另一类是非数学的密码理论与技术，包括信息隐藏、量子密码、基于生物特征的识别理论与技术等。下面介绍冯登国给出的关于这些理论及技术的研究现状和发展趋势。第36页，课件共100页，创作于2023年2月

8.3.1公钥密码自从1976年公钥密码的思想提出以来，国际上已经提出了许多种公钥密码体制，如基于大整数因子分解问题的RSA体制和Rabin体制、基于有限域上的离散对数问题的DiffieHellman公钥体制和ElGamal体制、基于椭圆曲线上的离散对数问题的DiffieHellman公钥体制和ElGamal体制、基于背包问题的MerkleHellman体制和ChorRivest体制、基于代数编码理论的MeEliece体制、基于有限自动机理论的公钥体制等等。第37页，课件共100页，创作于2023年2月用抽象的观点来看，公钥密码体制就是一种陷门单向函数。一个函数f是单向函数，若对它的定义域中的任意x都易于计算f(x)，而对f值域中的几乎所有的y，即使f已知,求f-1(y)在计算上也是不可行的。若给定某些辅助信息(陷门信息)时易于计算f-1(y)，就称单向函数f是一个陷门单向函数。公钥密码体制就是基于这一原理而设计的，将辅助信息(陷门信息)作为秘密密钥。这类密码的安全强度取决于它所依据的问题的计算复杂性。

第38页，课件共100页，创作于2023年2月比较流行的公钥密码体制主要有两类：一类是基于大整数因子分解问题的，其中最典型的代表是RSA体制。另一类是基于离散对数问题的，如ElGamal公钥密码体制和影响比较大的椭圆曲线公钥密码体制。由于分解大整数的能力日益增强，因此为保证RSA体制的安全性总要增加模长。目前768bit模长的RSA体制已不安全。一般建议使用1024bit模长，预计要保证20年的安全性就要选择2048bit的模长。增大模长带来了实现上的难度。而基于离散对数问题的公钥密码在目前技术下512bit模长就能够保证其安全性。第39页，课件共100页，创作于2023年2月特别是椭圆曲线上的离散对数的计算要比有限域上的离散对数的计算更困难，目前技术下只需要160bit模长即可保证其安全性，适合于智能卡的实现，因而受到国际上的广泛关注。国际上制定了椭圆曲线公钥密码标准IEEEP1363。第40页，课件共100页，创作于2023年2月公钥密码的重点研究方向如下：

(1)用于设计公钥密码的新的数学模型和陷门单向函数的研究;(2)针对实际应用环境的公钥密码的设计;(3)公钥密码的快速实现研究，包括算法优化和程序优化、软件实现和硬件实现；

(4)公钥密码的安全性评估问题，特别是椭圆曲线公钥密码的安全性评估问题。

第41页，课件共100页，创作于2023年2月

8.3.2分组密码美国早在1977年就制定了自己的数据加密标准DES。随着DES的出现，人们对分组密码展开了深入的研究和讨论。现已有大量的分组密码，如DES的各种变形、IDEA算法、SAFER系列算法、RC系列算法、Skipjack算法、Rijndael算法、FEAL系列算法、REDOC系列算法、LOKI系列算法，CAST系列算法、Khufu、Khafre、MMB、3-WAY、TEA、MacGuffin、SHARK、BEAR、LION、CA.1.1、CRAB、Blowfish、GOST、SQUARE、MISTY等等。第42页，课件共100页，创作于2023年2月AES活动使得国际上又掀起了一次研究分组密码的新高潮。继美国征集AES活动之后，欧洲(称之为Nessie计划)和日本也不甘落后，启动了相关标准的征集和制定，这些计划看起来比美国的计划更宏伟。同时美国等一些国家为适应技术发展的需求也加快了其他密码标准的更新，比如SHA-1和FIPSl40-1。我国在国家“863”计划中也将制定密码的标准化问题列入了议程。第43页，课件共100页，创作于2023年2月分组密码的重点研究方向如下：(1)新型分组密码的研究；(2)分组密码安全性综合评估原理与准则的研究；(3)分组密码的实现研究，包括软件优化、硬件实现和专用芯片等；(4)用于设计分组密码的各种组件的研究；(5)AES的分析及其应用研究。第44页，课件共100页，创作于2023年2月

8.3.3序列密码序列密码虽然主要用于政府、军方等国家要害部门，而且用于这些部门的理论和技术都是保密的，但由于一些数学工具(比如代数、数论、概率等)可用于研究序列密码，其理论和技术相对而言比较成熟。从20世纪80年代中期到90年代初，序列密码的研究非常热，特别是在序列密码的设计方法、序列密码的安全性度量指标、序列密码的分析方法、用于设计序列密码的各种组件(如密码布尔函数的构造与分析、非线性资源的生成和分析)等方面取得了一大批有理论和应用价值的成果。第45页，课件共100页，创作于2023年2月在序列密码的设计方法方面，人们将设计序列密码的方法归纳为四种，系统论方法、复杂性理论方法、信息论方法和随机化方法；将同步流密码的密钥流生成器分解成驱动部分和非线性组合部分，这样做不仅结构简单，而且便于从理论上分析这类生成器；提出了非线性组合生成器、非线性滤波生成器和钟控生成器等多种具体设计方法。第46页，课件共100页，创作于2023年2月在序列密码的安全性度量指标方面，人们提出了线性复杂度轮廓、跃复杂度、K-错误复杂度(球复杂度)、球周期、非线性复杂度等多种度量序列随机性和稳定性的指标，并对指标进行了深入研究。在序列密码的分析方法方面，提出了分别征服攻击方法、线性攻击方法、线性伴随式攻击方法、线性一致性攻击方法、快速相关攻击方法、线性时序逻辑逼近方法、熵漏分析方法等多种有效的分析方法。第47页，课件共100页，创作于2023年2月在密码布尔函数的构造与分析方面，提出了构造布尔函数的多种设计准则，如相关免疫性、线性结构、严格雪崩特性、扩散特性、平衡性、非线性性、差分均匀性等，构造了一大批满足上述若干准则的布尔函数，同时，对这些准则之间的关系也进行了深入研究。在非线性资源的生成和分析方面，对环上序列的生成和结构进行了深入研究和刻画，诱导出的二元序列具有良好的密码学特性。在研究方法方面，将谱技术、概率统计方法、纠错编码技术、有限域理论等有效地用于序列密码的研究。第48页，课件共100页，创作于2023年2月近年来，序列密码的研究虽然不像原来那么热，但有很多有价值的公开问题需要进一步研究，比如自同步流密码的研究、有记忆前馈网络密码系统的研究、多输出密码函数的研究、混沌序列密码和新研究方法的探索等。另外，虽然没有制定序列密码标准，但在一些系统中广泛使用了序列密码，例如RC4，用于存储加密。事实上，欧洲的Nessie计划中已经包括了序列密码标准的制定。第49页，课件共100页，创作于2023年2月

8.3.4Hash函数

Hash函数(也称杂凑函数或杂凑算法)就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一个安全的杂凑函数应该至少满足以下几个条件：

(1)输入长度是任意的；

(2)输出长度是固定的，根据目前的计算技术应至少取128比特长，以便抵抗生日攻击；

(3)对每一个给定的输入，计算输出即杂凑值是很容易的;第50页，课件共100页，创作于2023年2月

(4)给定杂凑函数的描述，找到两个不同的输入消息杂凑到同一个值是计算上不可行的，或给定杂凑函数的描述和一个随机选择的消息，找到另一个与该消息不同的消息使得它们杂凑到同一个值是计算上不可行的。攻击杂凑函数的典型方法是生日攻击方法。理论上，安全的杂凑函数的存在性依赖于单向函数的存在性，已形成一套理论。第51页，课件共100页，创作于2023年2月

Hash函数主要用于完整性校验和提高数字签名的有效性，现已有很多方案。这些算法都是伪随机函数，任何杂凑值都是等可能的。输出并不以可辨别的方式依赖于输入。在任何输入串中单个比特的变化，将会导致输出比特串中大约一半的比特发生变化。设计杂凑函数的基本方法有：第52页，课件共100页，创作于2023年2月

(1)利用某些数学难题比如因子分解问题、离散对数问题等设计杂凑函数。已设计出的算法有DaviesPrice平方杂凑算法、CCITT建议、Jueneman杂凑算法、Damgard平方杂凑算法、Damgard背包杂凑算法和Schnorr的FFT杂凑算法等。

(2)利用某些私钥密码体制比如DES等设计杂凑函数。这种杂凑函数的安全性与所使用的基础密码算法有关。这类杂凑算法有Rabin杂凑算法、Winternitz杂凑算法、QuisquaterGirault杂凑算法、Merkle杂凑算法和NHash算法等。第53页，课件共100页，创作于2023年2月

(3)直接设计杂凑函数。这类算法不基于任何假设和密码体制。这种方法受到人们的广泛关注和青睐，是当今比较流行的一种设计方法。美国的安全杂凑算法(SHA)就是这类算法，此类算法还有MD4、MD5、MD2、RIPEMD、HAVAL等。第54页，课件共100页，创作于2023年2月美国国家标准技术研究所与美国国家安全局共同设计了一个与美国数字签名算法(DSA)一起使用的安全杂凑算法(SHA)，标准是安全杂凑标准(SHS)，SHA是用于该标准的算法。SHA于1992年1月31日在联邦记录中公布，1993年5月11日起被采纳为标准。1994年7月11日做了一次修改，1995年4月17日正式公布。SHA的设计原则与MD4算法的设计原则极其相似，它很像是MD4算法的一种变形，但SHA的设计者没有公开SHA的详细设计准则。SHA的输入的长度限制在264比特之内，输出长度为160比特。由于技术的原因，美国目前正准备更新其Hash标准，加之欧洲也要制定Hash标准，这必然导致Hash函数的研究特别是实用技术的研究成为热点。第55页，课件共100页，创作于2023年2月

8.3.5密钥管理在密钥管理方面，国际上都有一些大的举动，也制定了一些标准。比如1993年美国提出的密钥托管理论和技术、国际标准组织制定的X.509标准(已经发展到第4版本)以及麻省理工学院开发的Kerboros协议(已经发展到第5版本)等。密钥管理中还有一种很重要的技术就是秘密共享技术，它是一种分割秘密的技术，目的是阻止秘密过于集中，自从1979年Shamir提出这种思想以来，秘密共享理论和技术达到了空前的发展和应用，特别是其应用至今人们仍十分关注。第56页，课件共100页，创作于2023年2月密钥分配是密钥管理中的一个关键因素，目前已有很多密钥分配协议，但其安全性分析是一个很重要的问题。除了经验分析之外，最重要的分析方法是形式化分析方法，它的研究始于20世纪80年代初，目前正处于百花齐放、充满活力的状态之中。许多一流大学和公司的介入，使这一领域成为研究热点。随着各种有效方法及思想的不断涌现，这一领域在理论上正在走向成熟。目前，在密钥管理方面讨论最多最热的是密钥管理基础设施(KMl)。第57页，课件共100页，创作于2023年2月

8.3.6PKI和VPN

公开密钥基础设施PKI(PublicKeyInfrastructure)技术和虚拟专用网VPN(VirtualPrivateNetwork)技术是目前最为人们关注的两种基于密码的技术。所谓PKI就是一个用公钥概念和技术实施和提供安全服务的具有普适性的安全基础设施，但PKI的定义在不断地延伸和扩展。PKI涉及到多个实体之间的协作过程，如注册机构(RA)、证书库、密钥恢复服务器和终端用户。国外的PKI应用已经开始，开发PKI的厂商也很多。第58页，课件共100页，创作于2023年2月许多厂家，如Baltimor、Entrust等推出了可以应用的PKI产品，有些公司如VerySign等已经开始提供PKI服务。许多网络应用已经在使用PKI技术以保证网络的认证、不可否认、加解密和密钥管理等。尽管如此，总的说来PKI技术仍在发展中。第59页，课件共100页，创作于2023年2月

VPN是利用接入服务器、广域网上的路由器或VPN专用设备在公用的WAN上实现虚拟专用网的技术。也就是说，用户觉察不到他在利用公用WAN获得专用网的服务这里所说的公用网包括Internet、电信部门提供的公用电话网、帧中继网及ATM网络等。如果强调其安全性，可以认为VPN是综合利用了认证和加密技术，在公共网络上搭建只属于自己的虚拟专用安全传输网络，为关键应用的通信提供认证和数据加密等安全服务。如果将VPN的概念推广一步，可以认为凡是在公共网络中实现了安全通信的协议都可以称之为VPN协议。到目前为止，VPN已经在网络协议的多个层次上实现，从数据链路层、网络层、传输层一直到应用层。第60页，课件共100页，创作于2023年2月

8.3.7量子密码美国科学家威斯纳首先将量子物理用于密码学的研究之中。他于1970年提出可利用单量子态制造不可伪造的“电子钞票”。但这个设想的实现需要长时间保存单量子态，不太现实。贝内特和布拉萨德在研究中发现，单量子态虽然不好保存但可用于传输信息。1984年，贝内特和布拉萨德提出了第一个量子密码方案，称为BB84方案。1992年，贝内特又提出一种更简单但效率减半的方案，即B92方案。第61页，课件共100页，创作于2023年2月8.4多媒体信息伪装随着信息安全重要性的不断升级，信息安全领域内“攻”与“守”之间的对抗也越来越激烈。新思想不断涌现，新方法不断诞生。信息伪装就是最近“热起来”的一种信息安全新手段。

第62页，课件共100页，创作于2023年2月加密是保证“黑客”无法读取机要信息的最重要手段，但是，加密却有助于“黑客”阻止合法接收者读取机要信息，因为，“黑客”可以稳、准、狠地破坏被加密的机要信息。信息伪装可以在很大程度上弥补加密的这种缺点。实际上，机要信息经过巧妙的伪装之后，可以麻痹“黑客”，使“黑客”感觉不到机要信息的存在，当然“黑客”就无法读取或破坏这些机要信息了，从而达到保护信息安全的目的。第63页，课件共100页，创作于2023年2月信息伪装是一门既古老又年轻的学科。说它古老，是因为早在远古时代就有人将机要信息写在信使的光头上，然后等头发长出来掩蔽这些机要信息的存在，最后信使到达接收者处后将头发再次剃光就得到了机要信息。至于古今中外的间谍们所使用的包括不可见墨水、缩微术、暗语等等间谍技术更是典型的信息伪装手段。随着数字化技术的迅速发展，形形色色的数字化伪装手段和技术变得越来越成熟，有些已经进入实用阶段。第64页，课件共100页，创作于2023年2月

8.4.1信息隐藏信息隐藏是把机密信息隐藏在大量信息中不让对手发觉的一种方法。信息隐藏是信息伪装的主体，以至于人们经常将信息隐藏与信息伪装视为同一回事。形象地说，信息隐藏实际上就是将机密信息隐藏在普通的信息之中而不露破绽。根据隐藏信息的载体不同，可以分为在图像、视频、声音、文本等中的信息隐藏，所隐藏的信息也可以是以上各种形式，只是在隐藏时都将它们视为比特流来处理。第65页，课件共100页，创作于2023年2月信息隐藏的基本原理是利用了人类感官系统对某些细节的不敏感性，对载体做某些微小变动，而不引起观察者的怀疑。而不同的载体又有不同的特点，如图像和视频信息隐藏利用了人的视觉特性，而对静止图像和视频，视觉的不敏感性又有所不同。声音信号的隐藏利用了人耳的听觉特性。因此，在不同载体中的信息隐藏有其不同的特点。第66页，课件共100页，创作于2023年2月信息隐藏的主要方法包括在时间域、空间域、变换域的隐藏，另外还有基于文件格式和载体生成技术的隐藏。目前研究得最多和最深入的是在静止图像中的隐藏，一方面是由于图像具有较大的冗余空间来隐藏信息，另一方面图像处理工具较多且隐藏效果很直观。第67页，课件共100页，创作于2023年2月在图像中信息隐藏的方法主要有：位平面替换、基于调色板的隐藏、DCT域隐藏、小波域隐藏、图像变形技术等，另外还有基于视觉掩蔽效应的隐藏。以位平面为代表的空间域信息隐藏技术具有容量大、处理简单的优点，但隐藏信息抵抗各种处理(如滤波、压缩等)的能力比较弱。而以DCT域隐藏为代表的基于变换域隐藏的特点是，隐藏信息的安全性比较强，能够抵抗各种压缩处理，但隐藏的数据容量有限。第68页，课件共100页，创作于2023年2月视频信号可以看成是由一帧帧静止图像组成的视频流。这样的原始视频流的数据量很大，因此一般都是以视频压缩的方式来保存。视频的信息隐藏一般分为三种。第一种是在原始视频流中隐藏信息，可以直接使用静止图像的隐藏算法，但是处理的数据量很大，并且抵抗压缩的能力较弱。第二种是在MPEG2视频压缩算法中嵌入隐藏算法，在压缩的同时进行信息隐藏。第三种是在压缩后的视频信号中进行隐藏，这类算法对视频质量影响不大，稳健性好，但是可以隐藏的数据量不大。第69页，课件共100页，创作于2023年2月声音信号中的信息隐藏又不同于图像和视频。声音信号的特点是，采样的低电平对听觉影响较大，并且采样点间具有相关性，并且还可以利用人耳对某些声音频段的不敏感性以及对相位的不敏感性来进行信息的隐藏。在声音中的信息隐藏算法主要包括在时域、频域和压缩域中的信息隐藏。具体来讲有在时域中的回声隐藏,在DFT中的相位隐藏,在DWT中的频域隐藏,还有利用听觉掩蔽效应的弱音隐藏等算法。第70页，课件共100页，创作于2023年2月在声音中隐藏信息的难点在于，一方面人的听觉比视觉更敏感，因此对隐藏算法的健壮性要求更高;另一方面，对声音信号的评价还没有一个比较有效的标准。一般常用的是主观评价，但是主观评价受到的限制较多，如不同专业水平的人有不同的评价结果，需要做大量的评价实验。而一些信噪比衡量标准同主观感觉之间存在较大的差异。因此还没有一个比较简单有效的评价准则，这方面的研究还有待进一步深入。第71页，课件共100页，创作于2023年2月隐写术就是将秘密信息隐藏到看上去普通的信息(如数字图像)中进行传送。目前，隐写术主要分以下几种：利用高空间频率的图像数据隐藏信息,采用最低有效位将信息隐藏到宿主信号中,使用信号的色度隐藏信息,在数字图像的像素亮度的统计模型上隐藏信息以及Patchwork方法等等。第72页，课件共100页，创作于2023年2月可视密码技术是Naor和Shamir于1994年首次提出的，其主要特点是恢复秘密图像时不需要任何复杂的密码学计算，利用人的视觉即可将秘密图像辨别出来。其做法是产生n张不具有任何意义的胶片，任取其中t张胶片叠合在一起即可还原出隐藏在其中的秘密信息。其后，人们又对该方案进行了改进和发展。主要的改进办法有：使产生的n张胶片都具有一定的意义。这样做更具有迷惑性，改进了相关集合的构造方法；将针对黑白图像的可视秘密共享扩展到基于灰度和彩色图像的可视秘密共享。第73页，课件共100页，创作于2023年2月

8.4.2数字水印数字水印是信息伪装最重要的一个分支，也是国际学术界研究的一个前沿热门方向。数字水印是永久镶嵌在宿主数据中具有可鉴别性的数字信息，并且它不影响宿主数据的可用性。数字水印为计算机网络上的多媒体产品的版权保护等问题提供了一个潜在的有效解决方法。数字水印是向多媒体数据(如图像、声音、视频信号等)中添加某些数字信息以达到版权保护等作用。如果没有稳健性的要求，水印与信息隐藏技术的处理在本质上是完全一致的。第74页，课件共100页，创作于2023年2月在绝大多数情况下，希望添加的信息是不可感知的，但在某些使用可见数字水印的场合，要求版权保护标志是可见的，并希望攻击者在不破坏数据本身质量的前提下无法去掉水印。

不同的应用,对数字水印的要求不尽相同，一般认为数字水印应具有如下特点：

(1)安全性：数字水印中的信息应是安全的，难以窜改或伪造的。

(2)可证明性：水印应能为数字产品的版权提供完全和可靠的证据。第75页，课件共100页，创作于2023年2月

(3)不可感知性：不可感知性包含两方面的意思。一方面是指视觉上的不可见性，即因嵌入水印导致图像的变化对观察者的视觉系统来讲应该是不可察觉的；另一方面水印用统计方法也是不能恢复的。

(4)稳健性：数字水印必须难以或不可能被清除。特别地，一个实用的水印算法应该对信号处理，通常的几何变形以及恶意攻击具有稳健性。第76页，课件共100页，创作于2023年2月数字水印算法通常包含水印的嵌入和水印的提取或检测两个基本方面。水印可由多种模型构成，如随机数字序列、数字标识、文本以及图像等。从稳健性和安全性考虑，常常需要对水印进行随机化处理和加密处理。

根据数字水印的加载方法的不同，水印可分为空间域水印和变换域水印两大类。空间域水印包括最低有效位法、Patchwork法和纹理映射法、文档结构微调法等；变换域水印一般采用DCT变换、小波变换、DFT变换等。与空间域方法相比，变换域的方法具有三个优点：第77页，课件共100页，创作于2023年2月

(1)在变换域中嵌入的水印信号能量可以散布到空间域的所有像素上，有利于保证水印的不可见性；

(2)在变换域，人类视觉系统的某些特性(如频率掩蔽效应)可以更方便地结合到水印编码过程中；

(3)变换域的方法可与国际数据压缩标准兼容，从而实现在压缩域内的水印算法，同时，也能抵抗相应的有损压缩。第78页，课件共100页，创作于2023年2月水印从外观上可分为可见水印和不可见水印。可见水印最常见的例子是有线电视频道上所特有的半透明标识，其主要目的在于明确标识版权，防止非法使用。不可见水印往往用在商业用的高质量图像上，而且往往配合数据解密技术一同使用。不可见水印根据稳健性可再细分为稳健的不可见水印和脆弱的不可见水印。稳健的不可见水印是嵌入载体中的数字信息，它必须能经受各种信号处理的操作。脆弱的不可见水印的特点是数字图像经处理后，所加载的水印就会被改变或毁掉。脆弱的不可见水印往往用于证明图像的真实性，检测或确定图像内容的微小篡改。第79页，课件共100页，创作于2023年2月

8.4.3数字指纹数字指纹是在数字产品的每一份拷贝中加入一个惟一的标志，通过这样的标志，可以区分一个数字产品所售出的每一份拷贝。它与数字水印的区别在于，数字水印是在数字产品中加入标识，表示数字产品的所有者，当发生版权纠纷时可以据此确定数字产品的原始作者，而数字指纹则侧重于对所售出的每一份拷贝的跟踪。如果发现非法复制的产品，可以根据其中的数字指纹指认是由哪一个用户进行的非法复制。利用数字指纹技术可以有效防止合法用户对数字产品进行非法传播而非法牟利。数字指纹的应用范围包括数字图像、影视、音乐、程序以及文本等。第80页，课件共100页，创作于2023年2月数字指纹的研究主要集中在数字图像中，利用这个技术，可以查出非法盗版的图像产品以及制造非法盗版的源头。在实际应用中，非法盗版者可能串通起来试图合谋擦除每个拷贝中的数字指纹，如两个用户串通起来，对他们所购买的数字图像产品进行对比，找到图像中数字指纹隐藏的位置，然后擦除它们，这样就可能制造出不包含数字指纹的图像，因此达到了盗版的目的。针对这样的问题，有人已经提出了一种新的算法，它可以防止用户串通的非法复制，并且可以跟踪到是哪两个或多个用户合谋进行的非法复制。有关内容详见有关文献。第81页，课件共100页，创作于2023年2月

8.4.4叠像术叠像术是由可视化密码技术发展而来的一种新的信息伪装技术。叠像术的思想是把要隐藏的机密信息通过算法隐藏到两个或多个子密钥图片中。这些图片可以存在磁盘上，或印刷到透明胶片上。在每一张图片上都有随机分布的黑点和白点。由于黑、白点的随机分布，持有单张图片的人不论用什么方法，都无法分析出任何有用的信息。而若把所有的图片叠加在一起，则能恢复出原有的机密信息。由于该方法简单有效，其恢复只要通过人的视觉系统就可识别，而无须大量的计算和密码学知识，所以其应用更为广泛。第82页，课件共100页，创作于2023年2月通过该技术产生的每一张图像也可以不是随机噪声图像，而是常人能看懂的图像，图像上有不同的文字或图画，与一般资料无异，只要将一定数量的图像叠加在一起，则原来每一张图像上的内容都将消失，而被隐藏的秘密内容将出现。至于单个图像无论是失窃还是被泄露，都不会给信息的安全带来灾难性的破坏。由于每一张图像的“可读性”，使其达到了更好的伪装效果，可以十分容易地逃过拦截者、攻击者的破解，而且，在一定的条件下，从理论上可以证明该技术是不可破译的，能够达到最优安全性。第83页，课件共100页，创作于2023年2月与以往的密码技术、密钥分享技术相比较，叠像技术有四个突出的特点：

(1)隐蔽性：这是数据伪装的基本要求，隐藏的秘密不能被常人看见；

(2)安全性：无论用任何方法任何手段对单张图像进行分析，都不能得到任何有用的信息。从数学上也可以证明，叠像技术能达到最优安全性，因而是不可破译的；第84页，课件共100页，创作于2023年2月

(3)秘密恢复的简单性：不同于其他任何一种信息伪装技术，叠像技术在恢复秘密时无须任何计算，只要将图像简单的叠加即能恢复秘密；

(4)通用性：使用者无需密码学的知识，任何人都可以使用该技术，这也是与其他技术不同的一个重要方面。第85页，课件共100页，创作于2023年2月

8.4.5潜信道潜信道又名隐信道，顾名思义，就是指普通人感觉不到此种信道的存在，从而“黑客”可以利用这些感觉不到而又真实存在的信道来传送(或存储)机密信息。潜信道的种类很多，有些潜信道是设计者有意打下的埋伏，有些潜信道则是无意之中构建的。目前，潜信道研究的系统理论还未形成，下面仅介绍一些常见的潜信道例子。第86页，课件共100页，创作于2023年2月

(1)在计算机时代，几乎任何消息都可以作为秘密通信的载体，如在普通电话交谈中，机密信息可以隐藏在话音中进行传递；视频会议系统中，将消息隐藏在基于DCT压缩的视频流中；在可执行文件中加入一段特定代码，不影响原来软件的执行，而这段特定代码代表了某些机密信息。第87页，课件共100页，创作于2023年2月

(2)在操作系统中也存在隐蔽信道，如恶意程序可以利用隐蔽信道将敏感信息从高安全级的系统区域传递到低安全级的系统区域。另外，在OSI网络模型中，存在许多可能用来传输秘密信息的隐蔽信道，如数据链路层中数据帧的未使用部分，IP包的时间戳部分等都可以被巧妙地用来传递信息。第88页，课件共100页，创作于2023年2月

(3)在以ElGamal数字签名方案和DSS数字签名方案等为代表的绝大多数数字签名方案中也都存在着潜信道。数字签名方案中的潜信道是由Simmons首先在1985年发现的，他还基于这种潜信道证明了当时美国用于“第二阶段限制战略武器会谈条约”核查系统中的安全协议的基本缺陷。利用数字签名方案中的潜信道，收、发双方可以避开监视者而进行隐蔽通信，实际上只需按以下协议就可以达到目的：发方生成一个无意义的消息M；发方利用与收方共享的密钥对M进行签名，同时将潜信息嵌入签名之中；监视者虽然可以获得签名消息，但是他无法发现可疑之处；收方验证发方的签名；收方用与发方共享的密钥从接收的无意义消息中提取出潜信息。第89页，课件共100页，创作于2023年2月

(4)网络设计与实现中的疏忽也可以用来建立潜信道。例如，滥用文件名就可以建立潜信道。假如允许高级用户与低级用户都可列出在给定时间系统中所有正在工作用户的名字，则高级用户就可用用户名进行编码建立一个潜信道来递送潜信息，而低级用户可根据用户名登录表译出潜信息。

(5)接入控制机制中的漏洞、收发双方存在的共享资源、特洛伊木马等都可以用来构造各种各样的潜信道。第90页，课件共100页，创作于2023年2月8.5人工神经网络利用人工神经网络(ArtificialNeuralNetworks，简写为ANN)进行压缩编码便是当今和未来若干年内一项十分新颖且处于探索研究阶段的技术。至今正在使用的计算机均属冯·诺伊曼型计算机，它具有强大的运算能力，但其形象思维能力与人脑相差甚远，即使一台巨型并行计算机也无法与一个三岁儿童的思维、语言、识别、听觉能力相比较。一代一代的科学家在不断地探索人脑功能和智慧的奥秘所在。第91页，课件共100页，创作于2023年2月从人脑的结构来看，它是由大量的神经细胞组合而成的，这些细胞相互连接着，每个细胞有其基本功能，如兴奋与抑制。从整体上看，它们相互整合完成一种复杂的、并行的、关联的思维活动。研究表明，虽然人的神经系统的处理速度仅在毫秒级，但由于神经元(Neurons)的巨量并行性，因此，表现出了极其优越的运算性能。西班牙解剖学家Cajal创立神经元学说后，Cajal和Golgi等发现，大脑存在着由神经细胞结合而成的神经网络。神经细胞是构成神经网