信息技术--赵泽茂--第二章41492.pptx

《信息技术--赵泽茂--第二章41492.pptx》由会员分享，可在线阅读，更多相关《信息技术--赵泽茂--第二章41492.pptx（172页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 信息保密技术2.1 密码学的发展简史2.2 密码学中的基本术语2.3 古典密码2.4 对称密码体制2.5 非对称密码体制2.6 密码学的应用小结习题第2章 信息保密技术人类早在远古时期就有了相互隐瞒信息的想法，自从有了文字来表达人们的思想开始，人类就懂得了如何用文字与他人分享信息以及用文字秘密传递信息的方法，这就催生了信息保密科学的诞生和发展。密码学已有四千多年悠久而迷人的历史，它的发展大致经历了三个阶段:手工加密阶段、机械加密阶段和计算机加密阶段。2.1 密码学的发展简史第2章 信息保密技术1.手工加密阶段早在公元前1900年左右，一位佚名的埃及书吏在碑文中使用了非标准的象形文字。据

2、推测，这些“秘密书写”是为了给墓主的生活增加神秘气氛，从而提高他们的声望。这可能是最早有关密码的记载了。公元前1500年左右，美索不达米亚人在一块板上记录了被加密的陶器上釉规则。公元前600500 年左右，希伯来人开发了三种不同的加密方法，它们都以替换为基本原理。一个字母表的字母与另一个字母表的字母配对，通过用相配对的字母替换明文的每个字母，从而生成密文。第2章 信息保密技术公元前500年左右，古希腊斯巴达出现了原始的密码器，其方法是用一条带子缠绕在一根木棍上，沿木棍纵轴方向写上文字，解下来的带子上便是些杂乱无章的符号。解密者只需找到相同的木棍，再把带子绑上去，沿木棍纵方向即可读出原文。希腊人

3、曾使用的一种“秘密书写”方法是，先将奴隶的头发剃光，然后将消息刺在头上，等头发长好后，再派他上路，到另一部落后，再将这个奴隶的头发剃光，原文便可显示出来。第2章 信息保密技术据论要塞的防护(希腊人Aeneas Tacticus 著)一书记载，公元前2世纪，一个叫Polybius 的希腊人设计了一种表格，他使用了将字母编码成符号的方法，我们将该表称为Polybius 校验表，如图2-1-1 所示。将每个字母表示成两位数，其中第一个数字表示字母所在的行数，第二个数字表示字母所在的列数，如字母A 对应“11”，字母B 对应“12”，字母对应“13”等。明文“education”即被表示成一串数字15

4、1445131144243433。第2章 信息保密技术图 2-1-1 Polybius 校验表第2章 信息保密技术公元前100年左右，著名的恺撒(Caesar)密码被应用于战争中，它是最简单的一种加密办法，即用单字母来代替明文中的字母。公元800年左右，阿拉伯密码学家阿尔金迪提出解密的频率分析方法，即通过分析计算密文的字母出现的频率来破译密码。公元16世纪中期，意大利数学家卡尔达诺(Cardano，15011576)发明了卡尔达诺漏板，将其覆盖在密文上，可从漏板中读出明文，这是较早的一种分置式密码。第2章 信息保密技术我国很早就出现了藏头诗、藏尾诗、漏格诗及绘画等，人们将要表达的真正意思隐藏在

5、诗文或画卷中，一般人只注意诗或画自身表达的意境，而不会去注意或很难发现隐藏在其中的“诗外之音”。古典密码的加密方法一般是采用文字置换，主要使用手工方式实现，因此我们称这一时期为密码学发展的手工加密阶段。第2章 信息保密技术2.机械加密阶段到了20世纪20年代，机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备的一场革命转轮密码机的发明。转轮密码机的出现是密码学的重要标志之一。通过硬件卷绕可实现从转轮密码机的一边到另一边的单字母代替，将多个这样的转轮密码机连接起来，便可实现几乎任何复杂度的多个字母代替。随着转轮密码机的出现，传统密码学有了很大的进展，利用机械转轮密码机可以开发出极其

6、复杂的加密系统。第2章 信息保密技术1921年以后的几十年里，Hebern 构造了一系列稳步改进的转轮密码机，并将其投入到美国海军的试用评估中，申请了美国转轮密码机的专利。这种装置在随后的近50年里被指定为美军的主要密码设备。在Hebern 发明转轮密码机的同时，欧洲的工程师们(如荷兰的Hugo Koch、德国的ArthurScherbius)都独立地提出了转轮密码机的概念。Arthur Scherbius 于1919年设计了历史上著名的转轮密码机德国的Enigma 机。在第二次世界大战期间，Enigma 机曾作为德国海、陆、空三军中最高级的密码机。英军从1942年2月至12月都没能解出德国潜

7、艇发出的信号。因此，随后英国发明并使用了德国的Enigma 机的改进型密码机，它在英军通信中被广泛使用，并帮助英军破译了德军信号。第2章 信息保密技术转轮密码机的使用大大地提高了密码加密速度，但由于密钥量有限，在二战中后期，它引出了一场关于加密与破译的对抗。二战期间，波兰人和英国人破译了Enigma 密码，美国密码分析者破译了日本的RED、ORANGE 和PURPLE 密码，这对盟军获胜起到了关键的作用，是密码分析史上最伟大的成功。第2章 信息保密技术3.计算机加密阶段计算机科学的发展刺激和推动了密码学进入计算机加密阶段。一方面，电子计算机成为破译密码的有力武器;另一方面，计算机和电子学给密码

8、的设计带来了前所未有的自由，利用计算机可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用面对机械式转轮机实现方式的高额费用。利用计算机还可以设计出更为复杂的密码系统。第2章 信息保密技术在1949年以前出现的密码技术算不上真正的科学，那时的密码专家常常是凭借直觉进行密码设计和分析的。1949年，C.Shannon 发表了保密系统的通信理论，为密码学的发展奠定了理论基础，使密码学成为一门真正的科学。19491975年，密码学主要研究单钥密码体制，且发展比较缓慢。1976年，W.Diffie 和M.Hellman 发表了密码学的新方向一文，提出了一种新的密码设计思想，从而开创了公钥密码学

9、的新纪元。1977年，美国国家技术标准局(NIST)正式公布了数据加密标准(Data Encryption Standard，DES)，将DES 算法公开，揭开了密码学的神秘面纱，大大推动了密码学理论的发展和技术的应用。第2章 信息保密技术近十多年来，由于现实生活的实际需要及计算技术的发展，密码学的每一个研究领域都出现了许多新的课题。例如，在分组密码领域，以往人们认为安全的DES 算法，在新的分析法及计算技术面前已被证明不再安全了。于是，美国于1997年1月开始征集新一代数据加密标准，即高级数据加密标准(Advanced Encryption Standard，AES)。目前，AES 征集活动

10、已经选择了比利时密码学家设计的Rijndael 算法作为新一代数据加密标准，且该征集活动在密码界又掀起了一次分组密码研究的高潮。第2章 信息保密技术同时，在公钥密码领域，椭圆曲线密码体制由于具有安全性高、计算速度快等优点而引起了人们的普遍关注，一些新的公钥密码体制(如基于格的公钥体制NTRU、基于身份的和无证书的公钥密码体制)相继被提出。在数字签名方面，各种有不同实际应用背景的签名方案(如盲签名、群签名、环签名、指定验证人签名、聚合签名等)不断出现。第2章 信息保密技术在应用方面，各种有实用价值的密码体制的快速实现受到了专家的高度重视，许多密码标准、应用软件和产品被开发和应用。一些国家(如美国

11、、中国等)已经颁布了数字签名法，使数字签名在电子商务和电子政务等领域得到了法律的认可。随着其他技术的发展，一些具有潜在密码应用价值的技术也得到了密码学家的重视，出现了一些新的密码技术，如混沌密码、量子密码、DNA 密码等。现在，密码学的研究和应用已大规模地扩展到了民用方面。第2章 信息保密技术密码学(Cryptology)研究进行保密通信和如何实现信息保密的问题，具体指通信保密传输和信息存储加密等。它以认识密码变换的本质、研究密码保密与破译的基本规律为对象，主要以可靠的数学方法和理论为基础，对解决信息安全中的机密性、数据完整性、认证和身份识别，对信息的可控性及不可抵赖性等问题提供系统的理论、方

12、法和技术。密码学包括两个分支:密码编码学(Cryptography)和密码分析学(Cryptanalyst)。密码编码学研究怎样编码、如何对消息进行加密，密码分析学研究如何对密文进行破译。2.2 密码学中的基本术语 第2章 信息保密技术下面是密码学中一些常用的术语:明文(Message):指待加密的信息，用M 或P 表示。明文可能是文本文件、位图、数字化存储的语音流或数字化的视频图像的比特流等。明文的集合构成明文空间，记为SM=M。密文(Ciphertext):指明文经过加密处理后的形式，用表示。密文的集体构成密文空间，记为SC=C。密钥(Key):指用于加密或解密的参数，用K 表示。密钥的集

13、合构成密钥空间，记为SK=。加密(Encryption):指用某种方法伪装消息以隐藏它的内容的过程。第2章 信息保密技术加密算法(Encryption Algorithm):指将明文变换为密文的变换函数，通常用E 表示，即E:SMSC，表示为C=EK(M)。解密(Decryption):指把密文转换成明文的过程。解密算法(Decryption Algorithm):指将密文变换为明文的变换函数，通常用D 表示，即D:SCSM，表示为M=DK(C)。密码分析(Cryptanalysis):指截获密文者试图通过分析截获的密文从而推断出原来的明文或密钥的过程。第2章 信息保密技术密码分析员(Cryp

14、tanalyst):指从事密码分析的人。被动攻击(Passive Attack):指对一个保密系统采取截获密文并对其进行分析和攻击。这种攻击对密文没有破坏作用。主动攻击(Active Attack):指攻击者非法侵入一个密码系统，采用伪造、修改、删除等手段向系统注入假消息进行欺骗。这种攻击对密文具有破坏作用。第2章 信息保密技术密码体制:即由明文空间SM、密文空间SC、密钥空间SK、加密算法E 和解密算法D 构成的五元组 SM、SC、SK、E、D。实际上，密码体制可以理解为一个密码方案，这里特别强调了一个“密码方案”概念的完整性。通常所说的密码方案，一定要包含这五个组成部分。对于一个密码体制而

15、言，如果加密密钥和解密密钥相同，则称为对称密码体制或单钥密码体制，否则称其为非对称密码体制或双钥密码体制。第2章 信息保密技术密码系统(Cryptosystem):指用于加密和解密的系统。加密时，系统输入明文和加密密钥，加密变换后，输出密文;解密时，系统输入密文和解密密钥，解密变换后，输出明文。一个密码系统由信源、加密变换、解密变换、信宿和攻击者组成，如图2-2-1 所示。密码系统强调密码方案的实际应用，通常应当是一个包含软、硬件的系统。第2章 信息保密技术图 2-2-1 密码系统模型第2章 信息保密技术柯克霍夫(Kerckhoffs)原则:密码系统的安全性取决于密钥，而不是密码算法，即密码算

16、法要公开。柯克霍夫原则是荷兰密码学家Kerckhoff 于1883年在名著军事密码学中提出的基本假设。遵循这个假设的好处是:(1)它是评估算法安全性唯一可用的方式。因为如果密码算法保密，密码算法的安全强度就无法进行评估。第2章 信息保密技术(2)防止算法设计者在算法中隐藏后门。因为算法被公开后，密码学家可以研究分析其是否存在漏洞，同时也接受攻击者的检验。(3)有助于推广使用。当前网络应用十分普及，密码算法的应用不再局限于传统的军事领域，只有公开使用，密码算法才可能被大多数人接受并使用。同时，对用户而言，只需掌握密钥就可以使用了，非常方便。第2章 信息保密技术古典密码时期一般认为是从古代到19世

17、纪末，这个时期生产力水平低，加密、解密方法主要以纸、笔或者简单的器械来实现，在这个时期提出和使用的密码称为古典密码。古典密码是密码学发展史上的一个重要阶段，也是近代密码学产生的渊源。尽管古典密码大多比较简单，一般可用手工或机械方式实现其加密和解密过程，破译也比较容易，目前也很少采用，但了解它的设计原理，有助于理解、设计和分析现代密码。2.3 古 典 密 码第2章 信息保密技术例如，将英文中的每个字母固定地换成它后面第5个字母，换成，换成，换成，换成，最后换成。字母编码如表2-3-1 所示。第2章 信息保密技术表2-3-1 字母编码 第2章 信息保密技术 根据表2-3-1 可知，明文“I lov

18、e you”就变成了“n qtaj dtz”。明文有明确的信息，而经过编码后的字符串“n qtaj dtz”是一串乱码，从字面上看没有明确的信息，信息隐藏在其中，从而达到了保密的效果。1.移位密码顾名思义，移位密码的加密方法是将明文字母按某种方式进行移位。著名的恺撒密码就是移位密码的一种，它是将字母顺序向后移3位，如“I am nine”编码后的密文为“l dp qlqh”。在移位密码中，将26个英文字母依次与0，1，2，25对应，密文字母可以用明文字母m 和密钥k按如下算法得到，即 c=m+k(mod 26)第2章 信息保密技术 例如，明文字母为Y，密钥k=3 时，对应的密文字母为 c24+

19、31(mod 26)因此，明文字母Y 对应的密文字母为B。给定一个密文字母c，对应的明文字母m 可由c 和密钥k按如下算法得到，即 m=c-k(mod 26)例如，密钥k=3 时，对密文字母B 解密如下:m=1-324(mod 26)从而密文字母B 对应的明文字母为Y。按照密码体制的数学形式化定义，移位密码体制可以描述为五元组(P，C，K，E，D)，其中，P=C=K=Z26=0，1，2，25，E=ek:Z26Z26|ek(m)=m+k(mod 26)D=dk:Z26Z26|dk(c)=c-k(mod 26)第2章 信息保密技术 2.仿射密码仿射密码指明文、密文空间与移位密码相同，密钥空间为K=

20、(k1，k2)|k1，k2Z26，其中GCD(k1，26)=1(GCD 表示两个数的最大公因子，GCD(k1，26)=1 表示k1和26互素)。对任意的k=(k1，k2)K，加密变换为 ek(m)=k1m+k2(mod 26)相应的解密变换为 dk(c)=(c-k2)(mod 26)第2章 信息保密技术其中k1=1(mod 26)。例2-1 假设k1=9 和k2=2，明文字母为q，试用仿射密码对其加密。解 先把明文字母q转化为数字13。由加密算法得c=913+2=119=15(mod 26)再把c=15 转化为字母得到密文P。解密时，先计算。因为931(mod 26)，所以=3。再由解密算法得

21、m=(c-k2)=3(c-2)=3c-645+20=13(mod 26)对应的明文字母为q。第2章 信息保密技术3.维吉利亚(Vigenere)密码Vigenere 是法国的密码学专家，Vigenere 密码是以他的名字命名的。该密码体制有一个参数n，在加密解密时，把英文字母用数字代替进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合，因此可表示为P=C=K=(Z26)n。加密变换如下:设密钥k=(k1，k2，kn)，明文P=(m1，m2，mn)，加密函数为ek(P)=(c1，c2，cn),其中ci=(mi+ki)(mod 26)，i=1，2，n。第

22、2章 信息保密技术对密文c=(c1,c2,cn)，密钥k=(k1,k2,kn)，解密变换为dk(c)=(m1,m2,mn)，其中 mi=(ci-ki)(mod 26)，i=1，2，n。例2-2 设n=6，密钥是cipher，这相应于密钥k=(2，8，15，7，4，17)，明文是“thiscryptosystem is not secure”，试用Vigenere 密码对其加密。第2章 信息保密技术解 首先将明文按每6个分为一组，然后与密钥进行模26加得 19 7 8 18 2 17 24 15 19 14 18 24 2 8 15 7 4 17 2 8 15 7 4 17 21 15 23 2

23、5 6 8 0 23 8 21 22 15 18 19 4 12 8 18 13 14 19 18 4 2 2 8 15 7 4 17 2 8 15 7 4 17 20 1 19 19 12 9 15 22 8 25 8 19 20 17 4 2 8 15 22 25 19相应的密文是“VPXZGIAXIVWPUBTTMJPWIZITWZT”。第2章 信息保密技术4.置换密码置换密码是把明文中各字符的位置次序重新排列来得到密文的一种密码体制。它实现的方法多种多样，在这里，我们介绍一类较常见的置换密码。其加密方法如下:把明文字符以固定的宽度m(分组长度)水平地(按行)写在一张纸上(如果最后一行不

24、足m，则需要补充固定字符)，按1，2，m的一个置换 交换列的位置次序，再按垂直方向(即按列)读出，即可得到密文。解密方法如下:将密文按相同的宽度m 垂直地写在纸上，按置换 的逆置换交换列的位置次序，然后水平地读出，即可得到明文。置换 就是密钥。第2章 信息保密技术例2-3 设明文“Joker is a murderer”，密钥=(4 1)(3 2)(即(4)=1，(1)=4，(3)=2,(2)=3)，按4，3，2，1列的次序读出，即可得到密文，试写出加密与解密的过程及结果。解 加密时，把明文字母按长度为4进行分组，每组写成一行，这样明文字母“Joker isa murderer”被写成4行4列

25、，然后把这4行4列按4，3，2，1列的次序写出，即得到密文。过程与结果如图2-3-1 所示。第2章 信息保密技术图 2-3-1 置换密码举例第2章 信息保密技术解密时，把密文字母按4个一列写出，再按 的逆置换重排列的次序，最后按行写出，即得到明文。在现代密码学中，假定密码方案遵从Kerckhoffs 原则，则对密文的破解取决于加密密钥。就古典密码而言，由于算法相对简单，算法复杂度也不高，一种可能的攻击方法是对所有可能的密钥进行尝试的强力攻击，称为穷举搜索攻击。由于密钥空间非常有限，因此很难抵抗穷举搜索的攻击。另一方面，就英文而言，一些古典密码方案不能很好地隐藏明文消息的统计特征，攻击者也可以利

26、用这一弱点进行破译。第2章 信息保密技术移位密码的密钥空间为K=Z26=0，1，2，25，因此，最多尝试26次即可恢复明文。仿射密码的密钥空间为K=(k1，k2)|k1，k2Z26，其中GCD(k1，26)=1，k1可能的取值有“1，3，5，7，9，11，15，17，19，21，23，25”，因此，最多尝试1226 次即可恢复明文。由此可以得出结论:古典密码方案并不适合Kerckhoffs 原则，算法的保密性基于算法的保密。严格地说，现代密码学是从1949年开始的，由于计算机的出现，算法的计算变得十分复杂，因此算法的保密性不再依赖于算法，而是密钥。第2章 信息保密技术对称密码体制对于大多数算法

27、而言，解密算法是加密算法的逆运算，加密密钥和解密密钥相同，满足关系:M=DK(C)=DK(EK(M)。对称密码体制的开放性差，要求通信双方在通信之前商定一个共享密钥，彼此必须妥善保管。对称密码体制分为两类:一类是对明文的单个位(或字节)进行运算的算法，称为序列密码算法，也称为流密码算法(Stream Cipher);另一类算法是把明文信息划分成不同的块(或小组)结构，分别对每个块(或小组)进行加密和解密，称为分组密码算法(Block Cipher)。2.4 对称密码体制 第2章 信息保密技术2.4.1 序列密码序列密码是将明文划分成单个位(如数字0或1)作为加密单位产生明文序列，然后将其与密钥

28、流序列逐位进行模2加运算，用符号表示为，其结果作为密文的方法。加密过程如图2-4-1 所示。第2章 信息保密技术图 2-4-1 序列密码加密过程第2章 信息保密技术加密算法是:ci=mi+ki(mod 2)解密算法是:mi=ci+ki(mod 2)例如，设明文序列M 是一串二进制数据M=(101011001111000011111111)2，密钥K=(111100001111000011110000)2,则加密过程:C=M+K(mod 2)=(010111000000000000001111)2解密过程:M=C+K(mod 2)=(101011001111000011111111)2序列密码分

29、为同步序列密码和自同步序列密码两种。第2章 信息保密技术同步序列密码要求发送方和接收方必须是同步的，在同样的位置用同样的密钥才能保证正确地解密。如果在传输过程中密文序列有被篡改、删除、插入等错误导致同步失效，则不可能成功解密，只能通过重新同步来实现解密、恢复密文。在传输期间，一个密文位的改变只影响该位的恢复，不会对后继位产生影响。第2章 信息保密技术自同步序列密码的密钥的产生与密钥和已产生的固定数量的密文位有关，因此，密文中产生的一个错误会影响到后面有限位的正确解密。所以，自同步密码的密码分析比同步密码的密码分析更加困难。第2章 信息保密技术序列密码具有实现简单、便于硬件计算、加密与解密处理速

30、度快、低错误(没有或只有有限位的错误)传播等优点，但同时也暴露出对错误的产生不敏感的缺点。序列密码涉及大量的理论知识，许多研究成果并没有完全公开，这也许是因为序列密码目前主要用于军事和外交等机要部门的缘故。目前，公开的序列密码主要有RC4、SEAL等。序列密码的安全强度依赖于密钥流产生器所产生的密钥流序列的特性，关键是密钥生成器的设计及收发两端密钥流产生的同步技术。第2章 信息保密技术1.伪随机序列在序列密码中，一个好的密钥流序列应该满足:具有良好的伪随机性，如极大的周期、极大的线性复杂度、序列中0和1的分布均匀;产生的算法简单;硬件实现方便。产生密钥流序列的一种简单方法是使用自然现象随机生成

31、，如半导体电阻器的热噪声、公共场所的噪声源等。还有一种方法是使用软件以简单的数学函数来实现，如标准C 语言库函数中的rand()函数，它可以产生介于065 535 之间的任何一个整数，以此作为“种子”输入，随后再产生比特流。rand()建立在一个线性同余生成器的基础上，如kn=akn-1+b(mod m),k0作为初始值，a、b和m 都是整数。但这只能作为以实验为目的的例子，不能满足密码学意义上的要求。第2章 信息保密技术产生伪随机数的一个不错的选择是使用数论中的难题。最常用的是BBS 伪随机序列生成器，也就是二次方程式残数生成器。首先产生两个大素数p和q，且p=q=3(mod 4)，设n=p

32、q，并选择一个随机整数x，x与n是互素的，且设初始输入x0=x2(mod n)，BBS 通过如下过程产生一个随机序列b1，b2，:(1)xj=(mod n);(2)bj是xj的最低有效比特。第2章 信息保密技术例如，设p=24672462467892469787 和q=396736894567834589803，则 n=9788476140853110794168855217413715781961令x=873245647888478349013，则初始输入 x0=x2 mod n=8845298710478780097089917746010122863172x1，x2，x8的值分别如下:x

33、1=7118894281131329522745962455498123822408x2=3145174608888893164151380152060704518227x3=4898007782307156233272233185574899430355x4=3935457818935112922347093546189672310389x5=675099511510097048901761303198740246040 x6=4289914828771740133546190658266515171326x7=4431066711454378260890386385593817521668

34、x8=7336876124195046397414235333675005372436第2章 信息保密技术取上述任意一个比特串，当x的值为奇数时，b的值取1，当x的值为偶数时，b的值取0，故产生的随机序列b1，b2，b8=0，1，1，1，0，0，0，0。可见，产生密钥流序列的方法很多，常见的方法有线性同余法、线性反馈移位寄存器、非线性反馈移位寄存器、有限自动机和混沌密码等。2.线性反馈移位寄存器通常，产生密钥流序列的硬件是反馈移位寄存器。一个反馈移位寄存器由两部分组成:移位寄存器和反馈函数(如图2-4-2 所示)。第2章 信息保密技术图 2-4-2 反馈移位寄存器第2章 信息保密技术移位寄存器

35、由n个寄存器组成，每个寄存器只能存储一个位，在一个控制时钟周期内，根据寄存器当前的状态计算反馈函数f(a1，a2，an)作为下一时钟周期的内容，每次输出最右端一位a1，同时，寄存器中所有位都右移一位，最左端的位由反馈函数计算得到。用ai(t)表示t 时刻第i 个寄存器的内容，用ai(t+1)表示ai(t)下一时刻的内容，则有移位:ai(t+1)=ai+1(t)(i=1，2，n-1)反馈:an(t+1)=f(a1(t)，a2(t)，an(t)第2章 信息保密技术如果反馈函数f(a1，a2，an)=k1ank2an-1 kna1，其中ki0，1，则该反馈函数是a1，a2，an的线性函数，对应的反馈

36、移位寄存器称为线性反馈移位寄存器(Linear Feedback Shift Register，LFSR)。例如，设线性反馈移位寄存器为ai(t+1)=ai+1(t)(i=1，2，3，4)a4(t+1)=a1(t)a3(t)对应(k1，k2，k3，k4)=(0，1，0，1)，设初始状态为(a1，a2，a3，a4)=(0，1，1，1)，各个时刻的状态如表2-4-1 所示。第2章 信息保密技术表2-4-1 LFSR 在不同时刻的状态 第2章 信息保密技术 由表2-4-1 可知，t=6 时的状态恢复到t=0 时的状态，且往后循环。因此，该反馈移位寄存器的周期是6，输出序列为0111100，表中对应a

37、1的状态。本例中，若反馈函数为a4(t+1)=a1(t)a4(t)，则周期达到15，输出序列为0110010001111010。对于4级线性反馈移位寄存器而言，所有可能状态为24=16 种，除去全0状态，最大可能周期为15。对于n级线性反馈移位寄存器，不可能产生全0状态，因此，最大可能周期为2n-1，而能够产生最大周期的LFSR 是我们所需要的，这就要求线性反馈函数符合一定的条件。关于随机序列的周期及线性复杂度的有关知识，需要读者具备一定的数学基础，本书不再展开讨论。第2章 信息保密技术选择线性反馈移位寄存器作为密钥流生成器的主要原因有:适合硬件实现;能产生大的周期序列;能产生具有良好的统计特

38、性的序列;它的结构能够应用代数方法进行很好的分析。实际应用中，通常将多个LFSR 组合起来构造非线性反馈移位寄存器，n级非线性反馈移位寄存器产生伪随机序列的周期最大可达2n，因此，研究产生最大周期序列的方法具有重要意义。第2章 信息保密技术3.RC4 RC4 是由麻省理工学院的Ron Rivest 教授在1987年为RSA公司设计的一种可变密钥长度、面向字节流的序列密码。RC4 是目前使用最广泛的序列密码之一，已应用于Microsoft Windows、Lotus Notes 和其他应用软件中，特别是应用到SSL 协议和无线通信方面。RC4 算法很简单，它以一个数据表为基础，对表进行非线性变换

39、，从而产生密码流序列。RC4 包含两个主要算法:密钥调度算法(KeyScheduling Algorithm，KSA)和伪随机生成算法(Pseudo Random Generation Algorithm，PRGA)。第2章 信息保密技术KSA 的作用是将一个随机密钥(大小为40256 位)变换成一个初始置换表S。过程如下:(1)S 表中包含256个元素S 0S 255，对其初始化，令S i=i，0i255。(2)用主密钥填充字符表K，如果密钥的长度小于256个字节，则依次重复填充，直至将K 填满。K=K i，0i255。(3)令j=0。(4)对于i 从0到255循环:j=j+S i+K i(

40、mod 256);交换S i 和S j。第2章 信息保密技术PRGA 的作用是从S 表中随机选取元素，并产生密钥流。过程如下:(1)i=0，j=0。(2)i=i+1(mod 256)。(3)j=j+S i(mod 256)。(4)交换S i 和S j。(5)t=S i+S j(mod 256)。(6)输出密钥字k=S t。虽然RC4 要求主密钥K 至少为40位，但为了保证安全强度，目前至少要达到128位。第2章 信息保密技术2.4.2 分组密码设明文消息被划分成若干固定长度的组m=(m1，m2，mn)，其中mi=0 或1，i=1，2,，n，每一组的长度为n，各组分别在密钥k=(k1，k2，kt

41、)的作用下变换成长度为r 的密文分组c=(c1，c2，cr)。分组密码的模型如图2-4-3 所示。第2章 信息保密技术图 2-4-3 分组密码的模型第2章 信息保密技术分组密码的本质就是由密钥k=(k1，k2，kt)控制的从明文空间M(长为n的比特串的集合)到密文空间C(长为r 的比特串的集合)的一个一对一映射。为了保证密码算法的安全强度，加密变换的构造应遵循下列几个原则:(1)分组长度足够大。当分组长度n较小时，容易受到暴力穷举攻击，因此要有足够大的分组长度n来保证足够大的明文空间，避免给攻击者提供太多的明文统计特征信息。第2章 信息保密技术(2)密钥量空间足够大，以抵抗攻击者通过穷举密钥破

42、译密文或者获得密钥信息。(3)加密变换足够复杂，以加强分组密码算法自身的安全性，使攻击者无法利用简单的数学关系找到破译缺口。(4)加密和解密运算简单，易于实现。分组加密算法将信息分成固定长度的二进制位串进行变换。为便于软、硬件的实现，一般应选取加法、乘法、异或和移位等简单的运算，以避免使用逐比特的转换。第2章 信息保密技术(5)加密和解密的逻辑结构最好一致。如果加密、解密过程的算法逻辑部件一致，那么加密、解密可以由同一部件实现，区别在于所使用的密钥不同，以简化密码系统整体结构的复杂性。古典密码中最基本的变换是代替和移位，其目的是产生尽可能混乱的密文。分组密码同样离不开这两种最基本的变换，代替变

43、换就是经过复杂的变换关系将输入位进行转换，记为S，称为S 盒;移位变换就是将输入位的排列位置进行变换，记为P，称为P 盒，如图2-4-4 所示。第2章 信息保密技术分组密码由多重S 盒和P 盒组合而成，如图2-4-5 所示。S盒的直接作用是将输入位进行某种变换，以起到混乱的作用;P 盒的直接作用就是移动输入位的排列位置关系，以起到扩散的作用。分组密码算法就是采用“混乱与扩散”两个主要思想进行设计的，这是Shannon为了有效抵抗攻击者对密码体制的统计分析提出的基本设计思想，也可以认为是分组密码算法设计的基本原理。第2章 信息保密技术图 2-4-4 两种基本变换第2章 信息保密技术图 2-4-5

44、 S 盒和P 盒所组成的网络结构 第2章 信息保密技术(1)代替。代替指将明文位用某种变换关系变换成新的位，以使所产生的密文是一堆杂乱无章的乱码，这种变换与明文和密钥密切相关，要求尽可能地使密文与明文和密钥之间的关系十分复杂，不便破译者从中发现规律和依赖关系，从而加强隐蔽性。在分组密码算法中采用复杂的非线性代替变换就可达到比较好的混乱效果。第2章 信息保密技术(2)移位。移位指让明文中的每一位(包括密钥的每一位)直接或间接影响输出密文中的许多位，即将每一比特明文(或密钥)的影响尽可能迅速地作用到较多的输出密文位中去，以便达到隐蔽明文的统计特性。这种效果也称为“雪崩效应”，也就是说，输入即使只有

45、很小的变化，也会导致输出位发生巨大变化。分组密码算法设计中的移位操作就是为了达到扩散的目的。第2章 信息保密技术(3)乘积变换。在分组密码算法设计中，为了增强算法的复杂度，常用的方法是采用乘积变换的思想，即加密算法不仅是简单的一次或两次基本的S 盒和P 盒变换，而是通过两次或两次以上盒和盒的反复应用，也就是迭代的思想，克服单一密码变换的弱点，构成更强的加密结果，以强化其复杂程度。后面介绍的一些分组密码算法，无一例外地都采用了这种乘积密码的思想。第2章 信息保密技术2.4.3 数据加密标准DES 20世纪60年代末，IBM 公司开始研制计算机密码算法，在1971年结束时提出了一种称为Luciff

46、er 的密码算法，它是当时最好的算法，也是最初的数据加密算法。1973年美国国家标准局(NBS，现在的美国国家标准技术研究所，NIST)征求国家密码标准方案，IBM 就提交了这个算法。1977年7月15日，该算法被正式采纳作为美国联邦信息处理标准生效，成为事实上的国际商用数据加密标准被使用，即数据加密标准(Data Encryption Standard，DES)。当时规定其有效期为5年，后经几次授权续用，真正有效期限长达20年。第2章 信息保密技术在这20年中，DES 算法在数据加密领域发挥了不可替代的作用。进入20世纪90年代以后，由于DES 密钥长度偏短等缺陷，不断受到诸如差分密码分析(

47、由以色列密码专家Shamir提出)和线性密码分析(由日本密码学家Matsui 等人提出)等各种攻击威胁，使其安全性受到严重的挑战，而且不断传出被破解的消息。鉴于这种情况，美国国家保密局经多年授权评估后认为，DES 算法已没有安全性可言。于是NIST 决定在1998年12月以后不再使用DES 来保护官方机密，只推荐作为一般商业使用。1999年又颁布新标准，并规定DES 只能用于遗留密码系统，但可以使用加密的3DES 加密算法。第2章 信息保密技术但不管怎样，DES 的出现推动了分组密码理论的研究，起到了促进分组密码发展的重要作用，而且它的设计思想对掌握分组密码的基本理论和工程应用有着重要的参考价

48、值。第2章 信息保密技术1.DES 加密算法流程DES 算法的加密过程如图2-4-6 所示。1)初始置换IP如图2-4-7 所示，初始置换方法是将64位明文的位置顺序打乱，表中的数字代表64位明文的输入顺序号，表中的位置代表置换后的输出顺序，表中的位置顺序是先按行后按列进行排序。第2章 信息保密技术图 2-4-6 DES 算法的加密过程第2章 信息保密技术例如:表中第一行第一列的数字为58，表示将原来排在第58位的比特位排在第位;第一行第二列的数字为50，表示将原来排在第50位的比特位排在第2位，依次类推。不妨设输入位序为m1m2m64，初始置换后变为m1m2 m64=m58m50m7。初始置

49、换表中的位序特征:64 位输入按8行8列进行排列，最右边一列按2、4、6、8和1、3、5、7的次序进行排列，往左边各列的位序号依次紧邻其右边一列各序号加8。第2章 信息保密技术图 2-4-7 初始置换IP第2章 信息保密技术2)乘积变换(16 轮迭代)乘积变换部分要进行16轮迭代，如图2-4-8 所示。将初始置换得到的64位结果分为两半，记为L0和R0，各32位。设初始密钥为64位，经密钥扩展算法产生16个48位的子密钥，记为K1，K2，K16，每轮迭代的逻辑关系为其中1i16，函数是每轮变换的核心变换。第2章 信息保密技术图 2-4-8 DES 算法的乘积变换第2章 信息保密技术3)逆初始置

50、换IP-1逆初始置换IP-1与初始置换正好相反，如图2-4-9 所示。例如，处在第1位的比特位置换后排在第58位，处在第2位的比特位置换后排在第50位。逆初始置换后变为m1m2 m64=m40m8m25。逆初始置换表中的位序特征:64 位输入依然按8行8列进行排列，18 按列从下往上进行排列，然后是916 排在右边一列，依次进行排4列，然后从33开始排在第一列的左边，从41开始排在第二列的左边，交叉进行。第2章 信息保密技术图 2-4-9 逆初始置换IP-1第2章 信息保密技术2.乘积变换中的f 变换乘积变换的核心是f 变换，它是非线性的，是每轮实现混乱的最关键的模块，输入32位，经过扩展置换