现代编码技术精品文稿.ppt

现代编码技术现代编码技术第1页，本讲稿共100页 8.1 传统信源编码的应用传统信源编码的应用根据信源编码技术的发展可以将其分为传统编码技术与现代编码技术两大类。传统编码技术主要有脉码调制(PCM，PulseCodeModulation)、量化法(Quantization)、空间和时间子抽样编码(SpatialandTemporalSubsamplingCoding)、熵编码(EntropyCoding)、预测编码(PredictiveCoding)、变换编码(TransformCoding)、矢量量化(VQ，VectorQuantization)、子带编码(SBC，SubbandCoding)等方法。第2页，本讲稿共100页这些方法前面已经介绍过，下面以图像信源为例简述传统信源编码技术的应用。采用脉码调制方法进行信源编码时，输入的连续信号通常以Nyquist速率采样，然后均匀量化。因此，它只是原始模拟信号的一种数字表示。量化器通常有N个电平，其中N是2的乘方(N2b)，每个采样由一个具有b比特的固定长度的二进制码示。使用PCM对像素编码所需的比特数取决于被编码信源的类型。通常来说，单色广播或会议电视图像用8比特就足够了；而医学图像则可能需要10比特或更多，以保证足够的幅度分辨率。第3页，本讲稿共100页对于彩色图像，每个彩色分量通常需要8比特，因而表示一个彩色像素共要使用24比特。PCM编码的效率是不高的，原因之一是PCM忽视了像素之间的空间和时间相关性；之二是它对所有量化幅度电平进行同样处理，即均匀量化；另外一个原因是它没有利用人眼的视觉特性。第4页，本讲稿共100页量化是一个相当直观的数据压缩方法，其过程相当于将输入数据的取值范围加以限制。比如，图像像素，即图像中的一个采样点的灰度值是用8比特二进制数表示，将其灰度量化至2比特，即用2比特二进制数来表现原8比特的数据。显然，在数据量上，量化后的比特数是原来的025倍，相应压缩比为41。量化过程的实际做法是利用量化查找表使一个输出值对应于若干个输入值。量化算法利用人的视觉对不同亮度值域的敏感程度不一样的特点，在一定输出图像质量的前提下，调节量化查找表达到最佳的压缩比。根据量化查找表的性质，量化算法分为线性与非线性两类。第5页，本讲稿共100页在电视、电话等某些应用中，全分辨率不是必需的。这时，可以使用空间和时间子抽样来降低数据速率。在编码器中，从每几个像素中选择一个像素，从每几帧中选择一帧，然后加以传输。在译码器中，可根据接收的像素和帧内插丢失的像素和帧，再生出分辨率较低的原始视频序列。如果像素是由色度和亮度分量表示的，那么可以以较高的比率对色度分量进行子抽样，量化更粗略一些，这是因为人眼对色度分量的敏感性低一些。这种技术非常简单，但十分有效。第6页，本讲稿共100页熵编码是纯粹基于信号统计特性的编码技术。它是一种无损编码，解码后能无失真地恢复原信息。熵编码的基本原理是给出现概率较大的符号一个短码字，而给出现概率较小的符号一个长码字，这样使得最终的平均码长很小。一个精心设计的熵编码器，其输出的平均码长接近信源的信息熵，即码长的下限。常用的熵编码方法有游程编码、霍夫曼编码和算术编码三种。游程编码主要用于量化后出现大量零系数的情形，利用游程来表示连零码，降低为表示零码所用的数据量。霍夫曼编码是一种不等长最佳编码方法。所谓最佳是指对于相同概率分布的信源这种编码的平均码长比其他任何一种有效编码的平均码长都短。霍夫曼编码必须知道信源的概率分布，这一般是无法做到的。通常采用对大量数据进行统计后得到的近似分布来代替实际的概率分布。第7页，本讲稿共100页算术编码是20世纪80年代发展起来的一种熵编码方法，已渐渐受到人们的注意。它的基本原理是，任何一个数据序列均可表示成0和1之间的一个间隔，该间隔的位置与输入数据的概率分布有关。可以根据信源的统计特性来设计具体的编码器，也可以针对未知概型的信源来设计能够自适应适配其分布的算术编码器，并且这两种形式的编码器均可以用硬件实现。有关的实验数据表明，在未知信源概率分布的大部分情形下，算术编码要优于霍夫曼编码。上述三种熵编码方法均已被各种编码标准采纳。第8页，本讲稿共100页预测编码有线性预测和非线性预测两类，它们可以在一幅图像内进行(帧内预测编码)，也可以在多幅图像之间进行(帧间预测编码)。预测编码基于图像数据的空间和时间冗余特性，用相邻的已知像素(或图像块)来预测当前像素(或图像块)的取值，然后再对预测误差进行量化和编码。这些相邻像素(或图像块)可以是同行扫描的，也可以是前几行或前几帧的，相应的预测编码分别称为一维、二维和三维预测，其中一维和二维预测是帧内预测，三维预测是帧间预测。预测编码的关键在于预测算法的选取，这与图像信号的概率分布很有关系。第9页，本讲稿共100页实际中常根据大量的统计结果采用简化的概率分布形式来设计最佳的预测器，有时还使用自应预测器以较好地刻画图像信号的局部特性，提高预测效率。线性预测编码又称为差分脉冲编码调制，即DPCM(DifferentialPulseCodeModulation)。帧内预测编码一般采用像素预测形式的DPCM，其优点是算法简单，易于硬件实现，缺点是对信道噪声及误码很敏感，会产生误码扩散，使图像质量大大下降。同时，帧内DPCM的编码压缩比很低，因此现在已很少独立使用，一般要结合其他的编码方法。帧间预测编码主要利用活动图像序列相邻帧间的相关性，即图像数据的时间冗余进行压缩，可以获得比帧内预测编码高得多的压缩比。第10页，本讲稿共100页帧间预测编码作为消除图像序列帧间相关性的主要手段之一，在视频图像编码方法中占有很重要的地位。帧间预测编码一般是针对图像块的预测编码，它采用的技术有帧重复法、阈值法、帧内插法、运动补偿法和自适应交替帧内帧间编码法等，其中运动补偿预测编码现已被各种视频图像编码标准采用，得到了很好的结果。这类图像编码方法的主要缺点在于对图像序列不同的区域，预测性能不一样，特别是在快运动区，预测效率很差。而且为了降低预测算法的运算复杂度和提高预测精度，一般先对图像进行分块，然后再预测，这势必造成分块边缘的不连续。第11页，本讲稿共100页与预测编码技术相比，消除图像数据空间相关性的一种更有效的方法是进行信号变换，使图像数据在变换域上最大限度的不相关。尽管图像变换本身对数据并未进行压缩，但由于变换后系数之间的相关性明显降低，图像的大部分能量只集中到少数几个变换系数上，采用适当的量化和熵编码可以有效地压缩图像的数据量。而且图像经某些变换后，系数的空间分布和频率特性有可能与人眼的视觉特性匹配，第12页，本讲稿共100页因此可以利用人类视觉系统的生理和心理特点而得到较好的编码系统。变换编码通常是将空间域相关的像素点通过变换映射到另一个频域上。在变换后的频域上应满足：所有的系数相互独立；能量集中于少数几个系数上；这些系数集中于一个最小的区域内。保留少数重要的系数就能够很好地恢复出图像，人眼几乎觉察不出那些损失的系数。第13页，本讲稿共100页KLT变换是在以上思路下构造出来的最佳线性变换方案。它是用数据本身的相关矩对角化后构成的，这种变换将产生完全不相关的变换系数。如果图像数据之间是高度相关的，经过KLT变换，系数将出现多个零值；同时，某些系数的值会很小。KLT变换的变换矩阵是由图像数据本身求得的，不同的图像数据有不同的变换矩阵。如此造成反变换矩阵的不惟一性；加之KLT变换矩阵的构造计算量很大，因而它不是一种实用的变换方法。第14页，本讲稿共100页尽管如此，KLT变换毕竟是线性变换压缩编码方法的一个最佳方案，通常可作为衡量其他线性变换性能的基准。就数据压缩而言，所选择的变换方法最好能与图像信号的特征匹配，此外还应从失真要求、实现的复杂度以及编码比特率等多方面进行综合考虑。KLT变换虽然是均方误差准则下的最佳变换，但在实际编码工作中，人们更常采用离散余弦变换DCT。第15页，本讲稿共100页在现行变换编码方法中，对大多数图像信源来说，DCT变换是最接近KLT变换的方法。对变换后图像系数的编码一般采用门限编码加区域编码的形式。以DCT为例，根据变换系数的能量分布，可以将图像划分为不同的区域。其中变换后幅值较大的图像系数大多集中于图像块的左上角。与其他系数相比，这些低频系数具有的能量最大，包括了图像的大部分内容，在变换图像中的地位最重要，应使它们的量化误差最小。同样，对于图像块的其他区域，也应采用与该区域相匹配的量化和编码形式。这种根据能量分布对不同区域采用不同量化编码的技术称为区域编码。第16页，本讲稿共100页另一方面，变换后图像的许多系数很小，仅占原图像能量的很小比例，对图像质量影响甚微，因此一般通过设定阈值的方法，将小于阈值的变换系数置零，从而大大提高编码效率。经门限和区域编码后，变换后图像的大部分系数为零，如何采用有效的方法将非零系数和零系数组织起来，在保证最少冗余的同时使连零系数出现概率最大，是变换图像编码面临的又一关键问题。在DCT图像编码方法中，对变换系数进行的Zigzag排序非常巧妙地解决了这一问题，但对有些图像变换方法，这种技术并非最佳。第17页，本讲稿共100页在一般图像中，对应轮廓边缘位置附近含有大量高频信息，它们相对于原图像是非常局部的，代表了图像数据的精细结构。按人眼的视觉特性，这些轮廓边缘信息对于图像的主观质量很重要，在编码时应给予特别考虑。然而由于传统的正交变换的时频局域性很差，变换后的系数失去了对原图像精细结构的描述，从变换图像得不到图像轮廓边缘的局部信息，因此在量化编码时无法采用特殊的方法。而且在传统的变换图像编码方法中，大多是靠丢弃高频系数来提高压缩比的，从而导致图像的轮廓边缘模糊，严重影响复原图像的主观质量，这是传统变换编码方法的缺点之一。第18页，本讲稿共100页传统变换编码方法的另一缺点是提高编码压缩比时会出现块效应。这是因为为降低变换算法的运算复杂度和提高编码效率，传统图像变换方法均采用分块变换技术。图像块大，相关性就高，压缩比也就大。但是块的尺寸太大又会丢失数据的平稳性，从而引入误差，包括失去高频细节、引入沿物体边界的噪声和可见的DCT图块边界。第19页，本讲稿共100页传统的变换图像编码方法的这些缺点使得它们不适合于需要较高压缩比的应用场合。究其根本原因，在于变换方法不具有良好时频局域性和全局变换的特点。实现实用的变换编码系统，主要分四个步骤。第一步是选择变换类型，DCT变换是应用最广泛的一种类型。第二步是选择方块的大小，较好的方块尺寸是88或1616。第三步是选择变换系数，并对其进行高效的量化，以便传输或存储。第四步是对量化系数进行比特分配，通常使用霍夫曼编码或游程编码。第20页，本讲稿共100页8.2 现代信源编码技术现代信源编码技术 20世纪80年代中后期，相关学科的迅速发展和新兴学科的不断出现为信源编码的发展注入了新的活力。人们对信源信息需求的剧增也有力地促进了信源压缩编码技术的进步。许多学者结合模式识别、计算机图形学、计算机视觉、神经网络、小波分析和分形几何等理论开始探索信源信号压缩编码的新途径。第21页，本讲稿共100页现代信源编码方法是针对传统编码方法中没有考虑人眼对轮廓、边缘的特殊敏感性和方向感知特性而提出的。它认为传统的编码技术以信息论和数字信号处理技术为理论基础，出发点是消除信源数据的线性相关性等统计冗余信息，其编码压缩信源数据的能力已接近极限，压缩比难以提高，例如对静止图像而言，这类方法的编码压缩比一般为1020倍左右。现代信源编码方法不局限于香农信息论的框架，要求充分利用人类视觉系统的生理和心理特性以及信源的各种性质以期获得高压缩比。第22页，本讲稿共100页8.2.1分形编码自然界由许许多多形状复杂的图形而构成，归纳起来它的形状和各种图形可分为两类：一类是有特征长度的图形，可用欧几里德几何学来描述和构造，例如房屋、汽车、足球、人等等，它们都是由具有特征长度的图形构造的，像房屋的高、宽，汽车的长度，足球的直径，人的身高等都是特征长度；另一类是没有特征长度的图形，例如海岸线、云彩、蛋糕的空穴等等，如果没有人工参照物，很难测量其尺度。第23页，本讲稿共100页如何构造这些无规则的复杂现象和物体直到20世纪70年代才得以解决。1975年波兰出生的美国数学家曼德尔布诺特(MandelbrotBB)首先研究了这种不规则形状和过程的性质，建立了自然界的分形几何理论。分形就是那些没有特征长度的图形的总称。曼德尔布诺特认为分形是几何外形，它与欧几里德几何外形相反，是没有规则的。首先它们处处无规则可言，其次它们在各种尺度上都有同样的不规则性。第24页，本讲稿共100页即分形几何研究的对象是无规则的图形，且这种无规则图形从整体到局部变化，虽然均属无规则性，但具有自相似性(Selfsimilarity)。换言之，无论几何尺度怎样变化，事物任何一小部分的形状都与较大部分的形状极其相似。这种尺度不变性(Scaleinvariance)在自然界中广泛存在。分形中最显著的特点是自相似性，如弯弯曲曲的海岸线，洁白无瑕的晶状雪花，变换无穷的云彩，蕨类植物的叶子，排列成格状的峰窝等，它们都是自相似性的典型例子。第25页，本讲稿共100页分形图之美丽，分形几何学之奇妙就在于它的自相似性，而从编码的角度，正是要恰当地、最大限度地利用这种自相似性。分形方法可以用于压缩编码的原因之一就是分形的自相似性。根据分形理论，不少复杂的图形，从信息论和计算观点来看，其信息含量并不大，一般只需要不多的数据，利用迭代函数系统迭代这全反馈的动态过程，在计算机上利用简单的算法和程序就可以产生相当复杂的自然图形。复杂的图形寓于简单算法之中，这是分形方法可以用于压缩的另一个主要依据之一。第26页，本讲稿共100页自然界许多事物的发展过程，如生长、凝聚、进化等形成多种多样的分形结构。例如人体的血液循环系统，从主动脉到毛细血管，直到血球细胞只能排单行滑行等分支都呈现一种分形结构。又如树木的枝叶也呈分形形态，用以获取阳光、空气，吸入二氧化碳排出氧气和抵抗风力。生物学家对植物种子基因研究发现，种子内只有一定的信息为植物编码，有限的基因产生了复杂的生物界，人类也是如此，所以植物等的复杂程度是有限的。它只不过是在生长过程中新陈代谢而形成的复杂分形形态。因此，分形意味着自然界许多复杂形态中潜藏着有组织的结构。如果能找到这些有效的信息，就能简单地表述自然界复杂的景象。这是能够采用分形方法进行压缩的又一个依据。第27页，本讲稿共100页8.2.2模型编码基于模型的信源编码技术是近几年发展起来的一种很有前途的低比特率编码方法。它利用了计算机视觉和计算机图形学中的方法和理论。其基本出发点是在编、解码两端分别建立起相同的模型。基于模型的编码器并不压缩实际的量化数据，而是采用一个表示景物(一般是人、人脸等)的模型，传送的信息是告诉接收方如何改变模型以匹配输入景物(如眨眼、扭头等)。基于模型的解码器也有一个与对应编码器相同的模型，解码器利用收到的数据调整其模型，然后生成供显示的图像。模型编码根据输入的图像提取模型参数，并根据模型参数重建图像。第28页，本讲稿共100页显然，模型编码方法的核心是建模和提取模型参数，其中模型的选取、描述和建立是决定模型编码质量的关键因素。从信息抽取功能的角度看，已经提出的模型包括：图像模型回答目标图像如何被模型化才会有效的问题；视觉模型描述重建图像后，人类视觉系统感知误差的形式和能力。这两种模型中，前者是模型法主要研究的对象，后者则偏重于在编码过程中引入人的视觉特性以便得到更好图像质量。从建立图像模型的复杂度和灵活性等角度考虑，三维线框模型(即用很多三角曲面片来逼近目标图像)是最好的，其他模型则因计算复杂和缺乏灵活性而很少使用。第29页，本讲稿共100页为了对图像数据建模，一般要求对输入图像要有某些先验知识。目前研究最多、进展最快的是针对可视电话应用中的图像序列编码，这类应用中的图像大多为人的头肩像。实质上此时的编码器是一个特征检测器，译码器是一个三维显示程序。基于模型的图像编码方法利用先验模型来抽取图像中的主要信息，并以模型参数的形式表示它们，因此可以获得很高的压缩比。在模型编码(ModelbasedCoding)方法的研究中还存在很多问题，例如：第30页，本讲稿共100页(1)模型法需要先验知识，不适合于一般的应用；(2)对不同应用所建模型是不一样的；(3)在线框模型中，控制点的个数不易确定，还未找到有效的方法能根据图像内容来选取；(4)即使对头肩模型，也存在很多问题，例如由特定人模型推广到非特定人、模型参数的快速抽取、表情运动参数的计算等都没有很令人满意的解决方法，大部分系统还依赖于FACS(FacialActionCodingSystem)中对表情块AU(ActionUnit)的描述，需要专用交互式系统，运算的复杂度极高；第31页，本讲稿共100页(5)由于复原图像是用图形学的方法产生的，看起来不够自然，尽管有纹理映射的方法，但结果仍有待进一步改进；(6)传统的误差评估准则不适合于对模型编码的评价。除此之外，如何利用人的视觉特性也是这种编码方法中一个没有解决的问题。模型图像编码方法的上述缺陷使得它的应用范围受很大限制，而且走向实用还需要一段时间。第32页，本讲稿共100页8.2.3小波编码小波变换的发展经历了一个漫长的过程。1910年Haar提出了小波规范正交基，这是最早的小波基，当时并没有出现“小波”这个词。1936年Littlewood和Paley对Fourier级数建立了二进制频率分量分组理论：对频率按2j进行划分，其Fourier变换的相位变化并不影响函数的大小，这是多尺度分析思想的最早来源。1946年Gabor提出的加窗Fourier变换(或称为短时Fourier变换)对弥补Fourier变换的不足起到了一定的作用，但并没有彻底解决这个问题。后来，Calderon、Zygmund、Stern和Weiss等人将LCD*2P理论推广到高维，并建立了奇异积分算子理论。1965年，Calderon给出了再生公式。第33页，本讲稿共100页1989年，S.G.Mallat首先将小波变换用于多分辨率图像的描述。这个多分辨率的图像描述叫做图像的小波分解。小波的图像分解方案实际上属于子带分解的一个特例，小波变换特别要求滤波器的正则性。小波分解是完备的、正交的，且是多分辨率的分解。在空间域里，小波分解将信号分解为不同层次，每一层次的分辨率不同。由于小波分解方法本身的正交性，分解后不同层次数据之间的相关性完全由数据本身的相关性所决定。由此排除了由于分解方法内在的相关性而造成数据之间呈现相关性的混淆。第34页，本讲稿共100页小波变换在空间域中进行多层次分解运算的同时形成了频率域中的多层次分解。在频率域中的每个层次上，高频分量与低频分量的分布与原数据中频率分布的方向有关。第35页，本讲稿共100页8.3 密码学研究现状及趋势密码学研究现状及趋势 密码理论与技术分成两大类，一类是基于数学的密码理论与技术，包括公钥密码、分组密码、序列密码、认证码、数字签名、Hash函数、身份识别、密钥管理、PKI技术、VPN技术等；另一类是非数学的密码理论与技术，包括信息隐藏、量子密码、基于生物特征的识别理论与技术等。下面介绍冯登国给出的关于这些理论及技术的研究现状和发展趋势。第36页，本讲稿共100页8.3.1公钥密码自从1976年公钥密码的思想提出以来，国际上已经提出了许多种公钥密码体制，如基于大整数因子分解问题的RSA体制和Rabin体制、基于有限域上的离散对数问题的DiffieHellman公钥体制和ElGamal体制、基于椭圆曲线上的离散对数问题的DiffieHellman公钥体制和ElGamal体制、基于背包问题的MerkleHellman体制和ChorRivest体制、基于代数编码理论的MeEliece体制、基于有限自动机理论的公钥体制等等。第37页，本讲稿共100页用抽象的观点来看，公钥密码体制就是一种陷门单向函数。一个函数f是单向函数，若对它的定义域中的任意x都易于计算f(x)，而对f值域中的几乎所有的y，即使f已知,求f-1(y)在计算上也是不可行的。若给定某些辅助信息(陷门信息)时易于计算f-1(y)，就称单向函数f是一个陷门单向函数。公钥密码体制就是基于这一原理而设计的，将辅助信息(陷门信息)作为秘密密钥。这类密码的安全强度取决于它所依据的问题的计算复杂性。第38页，本讲稿共100页比较流行的公钥密码体制主要有两类：一类是基于大整数因子分解问题的，其中最典型的代表是RSA体制。另一类是基于离散对数问题的，如ElGamal公钥密码体制和影响比较大的椭圆曲线公钥密码体制。由于分解大整数的能力日益增强，因此为保证RSA体制的安全性总要增加模长。目前768bit模长的RSA体制已不安全。一般建议使用1024bit模长，预计要保证20年的安全性就要选择2048bit的模长。增大模长带来了实现上的难度。而基于离散对数问题的公钥密码在目前技术下512bit模长就能够保证其安全性。第39页，本讲稿共100页特别是椭圆曲线上的离散对数的计算要比有限域上的离散对数的计算更困难，目前技术下只需要160bit模长即可保证其安全性，适合于智能卡的实现，因而受到国际上的广泛关注。国际上制定了椭圆曲线公钥密码标准IEEEP1363。第40页，本讲稿共100页公钥密码的重点研究方向如下：(1)用于设计公钥密码的新的数学模型和陷门单向函数的研究;(2)针对实际应用环境的公钥密码的设计;(3)公钥密码的快速实现研究，包括算法优化和程序优化、软件实现和硬件实现；(4)公钥密码的安全性评估问题，特别是椭圆曲线公钥密码的安全性评估问题。第41页，本讲稿共100页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页AES活动使得国际上又掀起了一次研究分组密码的新高潮。继美国征集AES活动之后，欧洲(称之为Nessie计划)和日本也不甘落后，启动了相关标准的征集和制定，这些计划看起来比美国的计划更宏伟。同时美国等一些国家为适应技术发展的需求也加快了其他密码标准的更新，比如SHA-1和FIPSl40-1。我国在国家“863”计划中也将制定密码的标准化问题列入了议程。第43页，本讲稿共100页分组密码的重点研究方向如下：(1)新型分组密码的研究；(2)分组密码安全性综合评估原理与准则的研究；(3)分组密码的实现研究，包括软件优化、硬件实现和专用芯片等；(4)用于设计分组密码的各种组件的研究；(5)AES的分析及其应用研究。第44页，本讲稿共100页8.3.3序列密码序列密码虽然主要用于政府、军方等国家要害部门，而且用于这些部门的理论和技术都是保密的，但由于一些数学工具(比如代数、数论、概率等)可用于研究序列密码，其理论和技术相对而言比较成熟。从20世纪80年代中期到90年代初，序列密码的研究非常热，特别是在序列密码的设计方法、序列密码的安全性度量指标、序列密码的分析方法、用于设计序列密码的各种组件(如密码布尔函数的构造与分析、非线性资源的生成和分析)等方面取得了一大批有理论和应用价值的成果。第45页，本讲稿共100页在序列密码的设计方法方面，人们将设计序列密码的方法归纳为四种，系统论方法、复杂性理论方法、信息论方法和随机化方法；将同步流密码的密钥流生成器分解成驱动部分和非线性组合部分，这样做不仅结构简单，而且便于从理论上分析这类生成器；提出了非线性组合生成器、非线性滤波生成器和钟控生成器等多种具体设计方法。第46页，本讲稿共100页在序列密码的安全性度量指标方面，人们提出了线性复杂度轮廓、跃复杂度、K-错误复杂度(球复杂度)、球周期、非线性复杂度等多种度量序列随机性和稳定性的指标，并对指标进行了深入研究。在序列密码的分析方法方面，提出了分别征服攻击方法、线性攻击方法、线性伴随式攻击方法、线性一致性攻击方法、快速相关攻击方法、线性时序逻辑逼近方法、熵漏分析方法等多种有效的分析方法。第47页，本讲稿共100页在密码布尔函数的构造与分析方面，提出了构造布尔函数的多种设计准则，如相关免疫性、线性结构、严格雪崩特性、扩散特性、平衡性、非线性性、差分均匀性等，构造了一大批满足上述若干准则的布尔函数，同时，对这些准则之间的关系也进行了深入研究。在非线性资源的生成和分析方面，对环上序列的生成和结构进行了深入研究和刻画，诱导出的二元序列具有良好的密码学特性。在研究方法方面，将谱技术、概率统计方法、纠错编码技术、有限域理论等有效地用于序列密码的研究。第48页，本讲稿共100页近年来，序列密码的研究虽然不像原来那么热，但有很多有价值的公开问题需要进一步研究，比如自同步流密码的研究、有记忆前馈网络密码系统的研究、多输出密码函数的研究、混沌序列密码和新研究方法的探索等。另外，虽然没有制定序列密码标准，但在一些系统中广泛使用了序列密码，例如RC4，用于存储加密。事实上，欧洲的Nessie计划中已经包括了序列密码标准的制定。第49页，本讲稿共100页8.3.4Hash函数Hash函数(也称杂凑函数或杂凑算法)就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一个安全的杂凑函数应该至少满足以下几个条件：(1)输入长度是任意的；(2)输出长度是固定的，根据目前的计算技术应至少取128比特长，以便抵抗生日攻击；(3)对每一个给定的输入，计算输出即杂凑值是很容易的;第50页，本讲稿共100页(4)给定杂凑函数的描述，找到两个不同的输入消息杂凑到同一个值是计算上不可行的，或给定杂凑函数的描述和一个随机选择的消息，找到另一个与该消息不同的消息使得它们杂凑到同一个值是计算上不可行的。攻击杂凑函数的典型方法是生日攻击方法。理论上，安全的杂凑函数的存在性依赖于单向函数的存在性，已形成一套理论。第51页，本讲稿共100页Hash函数主要用于完整性校验和提高数字签名的有效性，现已有很多方案。这些算法都是伪随机函数，任何杂凑值都是等可能的。输出并不以可辨别的方式依赖于输入。在任何输入串中单个比特的变化，将会导致输出比特串中大约一半的比特发生变化。设计杂凑函数的基本方法有：第52页，本讲稿共100页(1)利用某些数学难题比如因子分解问题、离散对数问题等设计杂凑函数。已设计出的算法有DaviesPrice平方杂凑算法、CCITT建议、Jueneman杂凑算法、Damgard平方杂凑算法、Damgard背包杂凑算法和Schnorr的FFT杂凑算法等。(2)利用某些私钥密码体制比如DES等设计杂凑函数。这种杂凑函数的安全性与所使用的基础密码算法有关。这类杂凑算法有Rabin杂凑算法、Winternitz杂凑算法、QuisquaterGirault杂凑算法、Merkle杂凑算法和NHash算法等。第53页，本讲稿共100页(3)直接设计杂凑函数。这类算法不基于任何假设和密码体制。这种方法受到人们的广泛关注和青睐，是当今比较流行的一种设计方法。美国的安全杂凑算法(SHA)就是这类算法，此 类 算 法 还 有 MD4、MD5、MD2、RIPEMD、HAVAL等。第54页，本讲稿共100页美国国家标准技术研究所与美国国家安全局共同设计了一个与美国数字签名算法(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页8.3.5密钥管理在密钥管理方面，国际上都有一些大的举动，也制定了一些标准。比如1993年美国提出的密钥托管理论和技术、国际标准组织制定的X.509标准(已经发展到第4版本)以及麻省理工学院开发的Kerboros协议(已经发展到第5版本)等。密钥管理中还有一种很重要的技术就是秘密共享技术，它是一种分割秘密的技术，目的是阻止秘密过于集中，自从1979年Shamir提出这种思想以来，秘密共享理论和技术达到了空前的发展和应用，特别是其应用至今人们仍十分关注。第56页，本讲稿共100页密钥分配是密钥管理中的一个关键因素，目前已有很多密钥分配协议，但其安全性分析是一个很重要的问题。除了经验分析之外，最重要的分析方法是形式化分析方法，它的研究始于20世纪80年代初，目前正处于百花齐放、充满活力的状态之中。许多一流大学和公司的介入，使这一领域成为研究热点。随着各种有效方法及思想的不断涌现，这一领域在理论上正在走向成熟。目前，在密钥管理方面讨论最多最热的是密钥管理基础设施(KMl)。第57页，本讲稿共100页8.3.6PKI和VPN公开密钥基础设施PKI(PublicKeyInfrastructure)技术和虚拟专用网VPN(VirtualPrivateNetwork)技术是目前最为人们关注的两种基于密码的技术。所谓PKI就是一个用公钥概念和技术实施和提供安全服务的具有普适性的安全基础设施，但PKI的定义在不断地延伸和扩展。PKI涉及到多个实体之间的协作过程，如注册机构(RA)、证书库、密钥恢复服务器和终端用户。国外的PKI应用已经开始，开发PKI的厂商也很多。第58页，本讲稿共100页许多厂家，如Baltimor、Entrust等推出了可以应用的PKI产品，有些公司如VerySign等已经开始提供PKI服务。许多网络应用已经在使用PKI技术以保证网络的认证、不可否认、加解密和密钥管理等。尽管如此，总的说来PKI技术仍在发展中。第59页，本讲稿共100页VPN是利用接入服务器、广域网上的路由器或VPN专用设备在公用的WAN上实现虚拟专用网的技术。也就是说，用户觉察不到他在利用公用WAN获得专用网的服务这里所说的公用网包括Internet、电信部门提供的公用电话网、帧中继网及ATM网络等。如果强调其安全性，可以认为VPN是综合利用了认证和加密技术，在公共网络上搭建只属于自己的虚拟专用安全传输网络，为关键应用的通信提供认证和数据加密等安全服务。如果将VPN的概念推广一步，可以认为凡是在公共网络中实现了安全通信的协议都可以称之为VPN协议。到目前为止，VPN已经在网络协议的多个层次上实现，从数据链路层、网络层、传输层一直到应用层。第60页，本讲稿共100页8.3.7量子密码美国科学家威斯纳首先将量子物理用于密码学的研究之中。他于1970年提出可利用单量子态制造不可伪造的“电子钞票”。但这个设想的实现需要长时间保存单量子态，不太现实。贝内特和布拉萨德在研究中发现，单量子态虽然不好保存但可用于传输信息。1984年，贝内特和布拉萨德提出了第一个量子密码方案，称为BB84方案。1992年，贝内特又提出一种更简单但效率减半的方案，即B92方案。第61页，本讲稿共100页8.4 多媒体信息伪装多媒体信息伪装 随着信息安全重要性的不断升级，信息安全领域内“攻”与“守”之间的对抗也越来越激烈。新思想不断涌现，新方法不断诞生。信息伪装就是最近“热起来”的一种信息安全新手段。第62页，本讲稿共100页加密是保证“黑客”无法读取机要信息的最重要手段，但是，加密却有助于“黑客”阻止合法接收者读取机要信息，因为，“黑客”可以稳、准、狠地破坏被加密的机要信息。信息伪装可以在很大程度上弥补加密的这种缺点。实际上，机要信息经过巧妙的伪装之后，可以麻痹“黑客”，使“黑客”感觉不到机要信息的存在，当然“黑客”就无法读取或破坏这些机要信息了，从而达到保护信息安全的目的。第63页，本讲稿共100页信息伪装是一门既古老又年轻的学科。说它古老，是因为早在远古时代就有人将机要信息写在信使的光头上，然后等头发长出来掩蔽这些机要信息的存在，最后信使到达接收者处后将头发再次剃光就得到了机要信息。至于古今中外的间谍们所使用的包括不可见墨水、缩微术、暗语等等间谍技术更是典型的信息伪装手段。随着数字化技术的迅速发展，形形色色的数字化伪装手段和技术变得越来越成熟，有些已经进入实用阶段。第64页，本讲稿共100页8.4.1信息隐藏信息隐藏是把机密信息隐藏在大量信息中不让对手发觉的一种方法。信息隐藏是信息伪装的主体，以至于人们经常将信息隐藏与信息伪装视为同一回事。形象地说，信息隐藏实际上就是将机密信息隐藏在普通的信息之中而不露破绽。根据隐藏信息的载体不同，可以分为在图像、视频、声音、文本等中的信息隐藏，所隐藏的信息也可以是以上各种形式，只是在隐藏时都将它们视为比特流来处理。第65页，本讲稿共100页信息隐藏的基本原理是利用了人类感官系统对某些细节的不敏感性，对载体做某些微小变动，而不引起观察者的怀疑。而不同的载体又有不同的特点，如图像和视频信息隐藏利用了人的视觉特性，而对静止图像和视频，视觉的不敏感性又有所不同。声音信号的隐藏利用了人耳的听觉特性。因此，在不同载体中的信息隐藏有其不同的特点。第66页，本讲稿共100页信息隐藏的主要方法包括在时间域、空间域、变换域的隐藏，另外还有基于文件格式和载体生成技术的隐藏。目前研究得最多和最深入的是在静止图像中的隐藏，一方面是由于图像具有较大的冗余空间来隐藏信息，另一方面图像处理工具较多且隐藏效果很直观。第67页，本讲稿共100页在图像中信息隐藏的方法主要有：位平面替换、基于调色板的隐藏、DCT域隐藏、小波域隐藏、图像变形技术等，另外还有基于视觉掩蔽效应的隐藏。以位平面为代表的空间域信息隐藏技术具有容量大、处理简单的优点，但隐藏信息抵抗各种处理(如滤波、压缩等)的能力比较弱。而以DCT域隐藏为代表的基于变换域隐藏的特点是，隐藏信息的安全性比较强，能够抵抗各种压缩处理，但隐藏的数据容量有限。第68页，本讲稿共100页视频信号可以看成是由一帧帧静止图像组成的视频流。这样的原始视频流的数据量很大，因此一般都是以视频压缩的方式来保存。视频的信息隐藏一般分为三种。第一种是在原始视频流中隐藏信息，可以直接使用静止图像的隐藏算法，但是处理的数据量很大，并且抵抗压缩的能力较弱。第二种是在MPEG2视频压缩算法中嵌入隐藏算法，在压缩的同时进行信息隐藏。第三种是在压缩后的视频信号中进行隐藏，这类算法对视频质量影响不大，稳健性好，但是可以隐藏的数据量不大。第69页，本讲稿共100页声音信号中的信息隐藏又不同于图像和视频。声音信号的特点是，采样的低电平对听觉影响较大，并且采样点间具有相关性，并且还可以利用人耳对某些声音频段的不敏感性以及对相位的不敏感性来进行信息的隐藏。在声音中的信息隐藏算法主要包括在时域、频域和压缩域中的信息隐藏。具体来讲有在时域中的回声隐藏,在DFT中的相位隐藏,在DWT中的频域隐藏,还有利用听觉掩蔽效应的弱音隐藏等算法。第70页，本讲稿共100页在声音中隐藏信息的难点在于，一方面人的听觉比视觉更敏感，因此对隐藏算法的健壮性要求更高;另一方面，对声音信号的评价还没有一个比较有效的标准。一般常用的是主观评价，但是主观评价受到的限制较多，如不同专业水平的人有不同的评价结果，需要做大量的评价实验。而一些信噪比衡量标准同主观感觉之间存在较大的差异。因此还没有一个比较简单有效的评价准则，这方面的研究还有待进一步