信息安全技术：第2章 信息保密技术

第二章信息保密技术第二章信息保密技术2.1概述2.2古典密码2.3分组加密技术2.4公钥加密技术密码学密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。变明文为密文，称为加密变换；变密文为明文，称为解密变换。密码学是研究如何隐密地传递信息的学科。在现代特别指对信息以及其传输的数学性研究，常被认为是数学和计算机科学的分支，和信息论也密切相关。著名的密码学者RonRivest解释道：“密码学是关于如何在敌人存在的环境中通讯”。从工程学的角度来看，这相当于密码学与纯数学的异同。密码学是信息安全等相关议题（如认证、访问控制等）的核心。密码学的首要目的是隐藏信息的涵义，而不是隐藏信息的存在。密码学也促进了计算机科学的发展，特别是在计算机与网络安全方面，如访问控制与信息的机密性。密码学已被应用在日常生活的各个方面，这包括自动柜员机的芯片卡、计算机使用者存取密码、电子商务等等。密码技术的发展历史密码技术几乎与文字的历史一样长。古典密码：远古——1949年近代密码：1949——1976年现代密码：1976——至今2.1概述密码学的发展第一个阶段:1949年以前古典加密计算机技术出现以前密码学作为一种技艺,而不是一门科学第二个阶段:1949年到1976年标志:Shannon发表”CommunicationTheoryofSecrecySystem”密码学进入了科学的轨道主要技术:单密钥的对称密钥加密算法第三个阶段:1976年以后标志:Diffie,Hellman发表”NewDircetionsinCryptography”一种新的密码体制:公开密钥体制第一台计算机克劳德香农Rivest、Shamir和AdlemanDiffie和Hellman密码学的发展历史密码体制的基本类型可以分为四种：错乱：按照规定的图形和线路，改变明文字母或数码等的位置成为密文；代替：用一个或多个代替表将明文字母或数码等代替为密文；密本：用预先编定的字母或数字密码组，代替一定的词组单词等变明文为密文；加乱：用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。以上四种密码体制，既可单独使用，也可混合使用，以编制出各种复杂度很高的实用密码。密码学的基本概念密码学（cryptology）作为数学的一个分支，是密码编码学和密码分析学的统称。使消息保密的技术和科学叫做密码编码学（cryptography）。破译密文的科学和技术就是密码分析学（cryptanalysis）。密码学的基本目的是面对攻击者Oscar，在被称为Alice和Bob的通信双方之间应用不安全的信道进行通信时，保证通信安全。明文密文明文AliceBobOscar密码学的基本概念密码体制的定义密码体制：密码体制的构成包括以下要素：M：明文消息空间，表示所有可能的明文组成的有限集。C：密文消息空间，表示所有可能的密文组成的有限集。K：密钥空间，表示所有可能的密钥组成的有限集。E：加密算法集合。D：解密算法集合。密码学的基本概念明文密文明文AliceBob加密密匙解密密匙保密通信的一般机制密码学的基本概念密码体制的分类

对称密匙密码系统SymmetricKeyCryptosystem

加密密钥=解密密钥

非对称密匙密码系统AsymmetricKeyCryptosystem

加密密钥≠解密密钥

钥匙是保密的

加密密钥为公钥（PublicKey）解密密钥为私钥（PrivateKey）密码学的基本概念密码学的基本概念密码学的基本概念在计算机出现以前，密码学的算法主要是通过字符之间代替或易位实现的，这些密码体制被称为古典密码。其中包括：易位密码、代替密码（单表代替密码、多表代替密码等）。这些密码算法大都十分简单，现在已经很少在实际应用中使用了。这一时期密码学还没有成为一门真正的科学，而是一门艺术。密码学专家常常是凭自己的直觉和信念来进行密码设计，而对密码的分析也多基于密码分析者（即破译者）的直觉和经验来进行的。2.2古典密码2.2古典密码移位密码代换密码置换密码古典密码代换密码单表代换密码移位密码(凯撒密码)替换密码仿射密码多表代换密码Vigenère(维吉尼亚）密码置换密码古典密码学主要有两大基本方法

（1）代替密码：就是将明文的字符替换为密文中的另一种的字符，接收者只要对密文做反向替换就可以恢复出明文。

（2）置换密码（又称易位密码）：明文的字母保持相同，但顺序被打乱了。最早的古典密码–

凯撒密码20attackdefense凯撒密码原理–

简单的移位替换当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。偏移量=[1,25]21移位密码的加密对象为英文字母，移位密码采用对明文消息的每一个英文字母向前推移固定位的方式实现加密。换句话说，移位密码实现了26个英文字母的循环移位。移位密码中，当取密钥k=3时，得到的移位密码称为凯撒密码，因为该密码体制首先被JuliusCaesar所使用。移位密码挑战实践-恺撒密码破译某人递给你的字条上写着以下密文：密文：yqqfyqmrfqdftqbmdfk明文=? 字母表：(密码本）密文：ABCDEFGHIJKLMNOPQRSTUVWXYZ明文：MNOPQRSTUVWXYZABCDEFGHIJKL解密过程：pi=Di（Ci）=Ci-12加密算法：C=E（p）=（p+12）mod（26）解密算法：P=D（C）=（C-12）mod（26）meetmeaftertheparty凯撒密码的破解分析暴力破解25种可能性24DecryptionCandidateplaintext0exxegoexsrgi1dwwdfndwrqfh2cvvcemcvqpeg3buubdlbupodf4attackatonce5zsszbjzsnmbd6yrryaiyrmlac...23haahjrhavujl24gzzgiqgzutik25fyyfhpfytshj凯撒密码的改进加入密钥有意改变字母的排列顺序，可增大密钥空间keyphases=Thequickbrownfoxjumpsoverthelazydog.key=thequickbrownfxjmpsvlazydg密钥空间26!=4X102625ABCDEFGHIJKLMqwertyuiopasdNOPQRSTUVWXYZfghjklzxcvbnm假设明文为：securityktexloznsecurity加密：解密：代换密码(替换密码)仿射密码加密函数为：当＝1时，为移位密码仿射函数是双射当且仅当gcd(a,26)=1时同余方程对每个y有唯一的解仿射密码系统

设，且对定义且因为满足，gcd(a,26)=1的只有12种候选，对参数没有要求。所以仿射密码有种可能的密钥。攻击！频率统计分析32频率统计分析破解密码实例密文:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ统计字母的频率3302468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ频率密文字母频率频率统计分析破解密码实例(2)猜测PZ可能是e和t；统计字母的相对频率-双字母猜测ZW可能是th，因此ZWP可能是the经过反复猜测、分析和处理，明文：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow34古典密码代换密码单表代换密码移位密码(凯撒密码)替换密码仿射密码多表代换密码Vigenère(维吉尼亚）密码置换密码Vigenère密码Vigenère密码是由法国密码学家BlaisedeVigenère于1858年提出的，它是一种以移位代换（当然也可以用一般的字母代换表）为基础的周期代换密码。设m是某固定的正整数，定义，对一个密钥，定义：且所有的运算都在中。[例]利用Vigenère密码，使用密钥word加密信息computer。 明文：computer

密钥：wordword

密文：ycdsqhvu38VigenèreCipher:Unbreakable?CharlesBabbage,1791-1871(查理斯.巴贝奇)In1846,BabbagebreakedVigenèrecipher

PartofBabbage'sdifferenceengine/wiki/Charles_Babbage39多表替换加密经典方法:

Vigenère(维基尼亚)cipherPlaintext:ATTACKATDAWNKey:LEMONLEMONLECiphertext:LXFOPVEFRNHRKi=11,4,12,14,13,11,4,12,14,13…1467,1508,155340如果我们知道key的长度…Ifthelengthofthekeywordis5,thenweknowthatthe1st,6th,11th,…lettersareencodedbythesamerowinthePolyalphabeticsubstitution,Thisequalsamono-alphabeticcipher.Plaintext:ATTACKATDAWNONEATTACK……Key:LEMONLEMONLEMONLEMON……Ciphertext:LXFOPVEFRNHR...LXFOP……41Findrepeatedsequences,spacesintheciphertext那我们如何知道key的长度呢？42频率统计分析:

Vigenère(维基尼亚)cipher置换密码：保持明文字符未改变，通过重排而更改位置，又称换位密码（TranspositionCipher）。置换密码置换密码举例

例：栅栏式密码 美国南北战争时期（1861-1865年），军队中曾经使用过的“栅栏”式密码（railfencecipher)。（1）原理 明文：sendhelp

加密过程：snhledep

密文：snhledep（2）算法描述 将明文写成双轨的形式，然后按行的顺序书写得到密文。置换密码举例例：矩阵置换：以矩阵形式排列明文，逐行写入，逐列读出。密钥指出各列读出的顺序如:明文abcdefghijklmnopqrstuvwxyzab密钥为:4312567

abcdefghijklmnopqrstuvwxyzabdkrycjqxahovbipwelszfmtagnub加密棒Phaistos圆盘ENIGMA密码机中国的经典密码–

藏头诗47战争中的密码49第一次世界大战:美国为什么参战?OnthefirstofFebruary,weintendtobeginunrestrictedsubmarinewarfare.Inspiteofthis,itisourintentiontoendeavortokeeptheUnitedStatesofAmericaneutral.Intheeventofthisnotsucceeding,weproposeanallianceonthefollowingbasiswithMexico:Thatweshallmakewartogetherandmakepeacetogether.Weshallgivegenerousfinancialsupport,andanunderstandingonourpartthatMexicoistoreconquerthelostterritoryinNewMexico,Texas,andArizona.Thedetailsofsettlementarelefttoyou.YouareinstructedtoinformthePresident[ofMexico]oftheaboveinthegreatestconfidenceassoonasitiscertainthattherewillbeanoutbreakofwarwiththeUnitedStatesandsuggestthatthePresident,onhisowninitiative,inviteJapantoimmediateadherencewiththisplan;atthesametime,offertomediatebetweenJapanandourselves…..解密的密码电报促使美国参战1917年2月24日，美国驻英大使佩奇收到破获的齐默曼电报，电报称如果墨西哥对美国宣战，德国将协助把美国西南部还给墨西哥，加上在之前德国使用无限制潜艇战，使美国多只船只被击沉，于是美国以此为根据，在该年4月6日向德国宣战。5051一战中的德国密码：

ADFGVXCIPHERS第一步:替换ADFGVX密码是德军在第一次世界大战中使用的栏块密码。事实上，它是早先一种密码ADFGX的增补版。1918年3月FritzNebel上校发明了这种密码，并提倡使用。52一战中的德国密码：

ADFGVXCIPHERS(2)Codes&CodebreakersInWorldWarI/ttcode_04.html#m1第二步骤:移位53WorldWarII:ENIGMA谢尔比乌斯ArthurScherbius1919年发明ENIGMA,装备德国海军54Attachement55二次世界大战中的Enigma“闪电战”的提出者，德国装甲部队之父，纳粹德国的海因茨·古德里安(HeinzGuderian)将军在指挥车上。在照片的左下方我们可以看见一台ENIGMA。56Enigma密码机是如何工作的?如果转子不转，则只是一个单表替换A-B-AC-D-F-CE-E57多表替换：当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在示意图中就是转动1/6圈，而在实际中转动1/26圈）。有26个替换表的Vigenere加密Enigma工作原理58Enigma工作原理转子转动一圈重复的问题：增加多个转子ENIGMA里有三个转子不重复的方向个数达到26*26*26=17576个。有17576个替换表的Vigenere59反射器：加密与解密过程相同反射器和转子一样，把某一个字母连在另一个字母上，但是它并不转动。反射器可以使译码的过程和编码的过程完全一样。发射器从不把输入映射成自身60Plugboard（连接板）从26个字母中取出6对，交换，比如

A/J,S/O,T/D,B/W,K/F,U/YSelect12lettersfrom26:26!/(12!*14!)Swap12letters:(12!/(6!*6!))*6!/2

26!12!-----------*--------=26!/(14!*6!*2)14!*12!6!*2=3.21E1261Enigma密码机的强度分析Orientationofrotors：26*26*26=17576Orderofrotors:3!连接板上两两交换6对字母的可能性数:3.21E12Total:17576*6*3.21E12≈

3.38E17，亿亿Enigma仍然是一个多表替换，表的个数

3.38E17Enigma曾在13年时间里（1926-1939）被认为坚不可摧62Codebook–

密码本63Enigma的密钥管理算法公开，密钥保密连接板交换6对字符，如：A/L,P/R,T/D,B/W,K/F,O/Y转子的顺序，比如：2,3,1转子的初始方向，如：Q-C-W每月发送当月每天的密钥每条密文使用不同的密钥每条电文的开头是加密的临时密钥，由三个字母重复两次加密而成,称为indicatorSender：使用当天的密钥加密一个Indicator，如输入PGHPGH，输出KIVBJE；把KIVBJE写在报文的开头，然后调整转子的初始方向位PGH，然后加密报文Receiver:用当天的密钥解密报文开头的6字符，得到PGHPGH；开头，然后调整转子的初始方向位PGH，然后解密报文64CrackingtheEnigma一战时英国密码破译工作：齐默曼电报一战后的德国、法国、英国、波兰恐怖笼罩之下的波兰德国人汉斯-提罗·施密特的情报Enigma，codebook算法公开，密钥保密最大的弱点不在于Enigma本身，而在如何使用每条报文开头重复的密钥：PGHPGHKIVBJE汉斯-提罗·施密特Hans-ThiloSchmidt65Enigma的破译：波兰人的工作可证明对于任何的连线变化都不影响循环圈的个数和每个循环圈上字母的个数；尝试所有3个rotors的初始位置，可以得到所有密钥的”fingerprint”，即循环圈的个数、每个循环圈上字母的个数:需要操作的次数：26*26*26＝17576考虑3个转子交换顺序3!，用6台Enigma协作运算建立这样一个档案（bookoffingerprints）用了一年时间66从Poland到British1938年,德国人提升了密码强度Enigma密码机另外增加了2个转子:5*4*3=60连接板交换6对字符提升至10对字符波兰人没有足够经费造出足够多的Enigma密码机德国人汉斯-提罗·施密特停止提供情报和密码本1939年4月,德国撕毁与波兰签订的和平协定，波兰处于战争乌云阴影之中。1939年7月,波兰人将破译成果展示给英法同行1939年9月,希特勒下令闪电战入侵波兰，逃亡67ContributionsbyAlanTuringAlanTuring(1912-1954)1931年进入剑桥大学，提出图灵机模型1933年受聘于GCCS，1939进入BletchleyPark波兰的方法依赖密钥的重复，如果德军改变密钥规则怎么办？图灵的方法在候选单词的明文和密文之间找到字母循环圈的指纹68bombe:MultiplesetsofenigmaworkinparallelSelect3from5rotors6060Parallel12lettersinthecircle12enigmainacircle60*12Givencribs，thekey

couldbefoundinweeks,laterinhours.uk/69Enigma相关的几个人谢尔比乌斯ArthurScherbiusScherbiusdidn’tseethesuccessofEnigma,ashewaskilledinahorsecarriageaccidentin1929.(51yearsold)Rejewski(马里安·雷杰夫斯基)1939逃亡法国，1940年逃亡英国，1946返波兰，退休前做accountant,对Enigma相关工作保密，1980去世(74岁)2000年7月17日，波兰政府向雷杰夫斯基、罗佐基和佐加尔斯基追授波兰最高勋章。2000年9月英国将一台从德国潜艇上缴获的ENIGMA机赠送给波兰，表示对波兰在破译ENIGMA密码中作出贡献的感谢。AlanTuringHomosexualitycriminalprosecutionin1952Diedin1954,aged41.第二次世界大战后期的德国密码1942年德国突然更换了新式恩尼格码密码机盟军始终无法破解70“NCZWVUSXPNYMINHZXMQXSFWXWLKJAHSHNMCOCCAKUQPMKCSMHKSEINJUSBLKIOSXCKUBHMLLXCSJUSRRDVKOHULXWCCBGVLIYXEOAHXRHKKFVDREWEZLXOBAFGYUJQUKGRTVUKAMEURBVEKSUHHVOYHABCJWMAKLFKLMYFVNRIZRVVRTKOFDANJMOLBGFFLEOPRGTFLVRHOWOPBEKVWMUQFMPWPARMFHAGKXIIBG”2006年终遭业余爱好者破解StefanKrah是一名德国出生的小提琴手，他的业余爱好是钻研密码和开源软件M4项目-计算机破解德国二战后期密码“遭深水炸弹攻击后紧急下潜，与敌接触的最后方位为：0830hAJ9863；（方向）220度，（速度）8节；（我）正在尾随（敌人）；（压力读数）14兆巴；（风向）北-北-偏东；（兵力）4；能见度10”71多字母代换密码——Hill密码特点每次对个字母进行代换，这样做的优点是容易将字母的自然频度隐蔽或均匀化而有利于抗统计分析。算法

设m是某个固定的正整数，，又设

；对任意，定义，则其中，所有的运算都是在中进行。注1：m＝1时，系统退化为单字母仿射代换密码，可见Hill密码是仿射密码体制的推广。注2：如果m＝2，可以将明文写为密文写为.是的线性组合.若取简记为其中为密钥.2.4分组密码2.4.1DES算法2.4.2分组密码的安全性及工作模式基本概念分组密码是指将处理的明文按照固定长度进行分组，加解密的处理在固定长度密钥的控制下，以一个分组为单位独立进行，得出一个固定长度的对应于明文分组的结果。属于对称密码体制的范畴。1)明文分组（固定长度）。2）密钥分组（固定长度）。3）以组为单位独立进行运算，得到密文（长度固定）。在分组密码中用代替、置换实现扩散和混淆功能。混淆：指加密算法的密文与明文及密钥关系十分复杂，无法从数学上描述，或从统计上去分析。扩散：明文（密钥）中的任一位，对全体密文位有影响。经此扩散作用，可以隐藏明文的统计特性，增加密码的安全。基本概念DES算法DES算法的产生发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功。基础：1967年美国HorstFeistel提出的理论。产生：美国国家标准局（NBS)1973年5月到1974年8月发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于1977年7月15日生效。DES加密算法的背景美国国家安全局（NSA,NationalSecurityAgency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位。1979年，美国银行协会批准使用DES。1980年，DES成为美国标准化协会(ANSI)标准。1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。DES算法的描述为二进制编码数据设计的，可以对计算机数据进行密码保护的数学运算。DES使用56位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。在每轮编码时，一个48位的“每轮”密钥值由56位的“种子”密钥得出来。DES算法的参数有三个：Key、Data和Mode。Key为8个字节共64位，是DES算法的工作密钥；Data也为8个字节64位，是要被加密或被解密的数据；Mode为DES的工作方式，有两种：加密或解密。64位明文变换到64位密文；64位密钥，实际可用长度56位。DES算法DES算法初始换位的功能：64位数据块按位重新组合，把输出分为L0、R0两部分，每部分各长32位。其置换规则见下表：58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆置换正好是初始置的逆运算。DES算法DES算法描述（续）逆置换正好是初始置的逆运算。【例】第1位经过初始置换后，处于第40位，而通过逆置换，又将第40位换回到第1位，其逆置换规则如下表所示：

408481656246432397471555236331

386461454226230375451353216129

364441252206028353431151195927

34242105018582633141949175725

在变换中用到的S1,S2...S8为选择函数，俗称为S-盒，是DES算法的核心。其功能是把6bit数据变为4bit数据。

S1:

1441312151183106125907

0157414213110612119538

4114813621115129731050

1512824917511314100613

在S1中，共有4行数据，命名为0，1、2、3行；每行有16列，命名为0、1、2、3，......，14、15列。

现设输入为：D＝D1D2D3D4D5D6

令：列＝D2D3D4D5

行＝D1D6

然后在S1表中查得对应的数，以4位二进制表示，此即为选择函数S1的输出。

101100102

0123456789101112131415014413121511831061259071015741421311061211953824114813621115129731050315128249175113141006130010输出4位使用选择函数S1的例子输入6位S1费斯妥函数（F函数）1.扩张—用扩张置换将32位的半块扩展到48位，其输出包括8个6位的块，每块包含4位对应的输入位，加上两个邻接的块中紧邻的位。2.与密钥混合—用异或操作将扩张的结果和一个子密钥进行混合。16个48位的子密钥（是利用密钥调度从主密钥生成的），每个用于一个回次的F变换。3.S盒—在与子密钥混合之后，块被分成8个6位的块，然后使用“S盒”，或称“置换盒”进行处理。8个S盒的每一个都使用以查找表方式提供的非线性的变换将它的6个输入位变成4个输出位。S盒提供了DES的核心安全性—如果没有S盒，密码会是线性的，很容易破解。4.置换—最后，S盒的32个输出位利用固定的置换，“P置换”进行重组。这个设计是为了将每个S盒的4位输出在下一回次的扩张后，使用4个不同的S盒进行处理。S盒，P置换和E扩张DES的两个主要弱点：密钥容量：56位不太可能提供足够的安全性。S盒：可能隐含有陷井(Hiddentrapdoors)。DES的半公开性：S盒的设计原理至今未公布。DES算法DES的破译DES的实际密钥长度为56-bit，就目前计算机的计算能力而言，DES不能抵抗对密钥的穷举搜索攻击。1997年1月28日，RSA数据安全公司在RSA安全年会上悬赏10000美金破解DES，克罗拉多州的程序员Verser在Inrernet上数万名志愿者的协作下用96天的时间找到了密钥长度为40-bit和48-bit的DES密钥。1998年7月电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56-bit的DES。1999年1月电子边境基金会（EFF）通过互联网上的10万台计算机合作，仅用22小时15分就破解了56-bit的ＤES。不过这些破译的前提是，破译者能识别出破译的结果确实是明文，也即破译的结果必须容易辩认。如果明文加密之前经过压缩等处理，辩认工作就比较困难。DES算法DES的导入被认为是密码学的学术研究的催化剂，尤其是对块密码的密码分析DES可以被称为对加密算法的非军用研究和发展的开始。1970年代除了为军队或情报组织工作的以外，只有很少的密码学者，对密码学的学术研究也很少。现在则有许多活跃的学术性的密码学者，善于密码学方面编程的数学家，以及商业信息安全公司和顾问。一整代的密码学者都拼命分析（或者说，破解）DES算法。用密码学家布鲁斯·施奈尔的话说：“DES在促进密码学界的发展上做的比其它的一切都多。现在有一种算法供学者们分析了。”在1970和1980年代，密码学中关于DES的公开文献所占的比例令人大吃一惊，而且DES是用来对每一种对称密钥算法进行比较的标准对象。国际数据加密算法（IDEA）IDEA（InternationalDataEncryptionStandard）由瑞士联邦理工学院的XuejiaLai和JamesMassey于1990年提出，分组长度为64-bit，密钥长度为128-bit。能抵抗差分密码分析，目前还没有发现明显的安全漏洞，应用十分广泛。著名的电子邮件安全软件PGP就采用了IDEA进行数据加密。IDEA的混淆特性IDEA的混淆特性是经由混合下述三种操作而成的：以比特为单位的异或运算定义在模（mod65536）的模加法运算，其操作数都可以表示成16位整数定义在模＋1（mod65537）的模乘法运算。IDEA的混淆特性（续）在IDEA的设计中，使用了这三种操作混合组合来打乱数据。攻击者无法用化简的方式来分析密文与明文及密钥之间的关系。IDEA的扩散特性IDEA的扩散特性是建立在乘法/加法（MA）的基本结构上。该结构一共有4个16位的输入，两个16位的输出。其中的两个输入来源于明文，另两个输入是子密钥，源于128位加密密钥。Lai经过分析验证，数据经过8轮的MA处理，可以得到完整的扩散特性。MA基本结构F1F2⊙⊙G1G2Z5Z6子密钥（16位）明文输入（16位）明文输入（16位）子密钥（16位）输出（16位）输出（16位）（i）（i）＋＋IDEA算法描述IDEA是由8轮相似的运算和随后的一个输出变换组成64位的明文分组在每一轮中都是被分成4份，每份从16位为一单元来处理每一轮中6个子密钥×8＋输出变换4个子密钥＝52个子密钥每一轮的运算又分成两部分：第一部分即变换运算。利用加法及乘法运算将4份16位的子明文分组与4个子密钥混合，产生4份16位的输出。这4份输出又两两配对，以逻辑异或将数据混合，产生两份16位的输出。这两份输出，连同另外的两个子密钥成为第二部分的输入。第二部分即用以产生扩散特性的MA运算。MA运算生成两份16位输出。MA的输出再与变换运算的输出以异或作用生成4份16位的最后结果。这4份结果即成为下一轮运算的原始输入。

IDEA的设计理念IDEA的设计主要考虑是针对16位为单位的处理器。因此无论明文、密钥都是分成16位为一个单元进行处理。IDEA使用了三种简单的基本操作，因此在执行时可以达到非常快的操作。在33MHz386机器上运行，加密速度可以达到880kb/s。经过特殊设计的VLSI芯片，更可以达到55Mb/s的速度。IDEA采用三种非常简单的基本操作，混合运算，以达到混淆目的。而相对地，DES采用经过特殊设计的S-盒，而对这些S-盒的分析又不对外公开。相较之下，IDEA的安全性评估，较易被大家接受。IDEA的整体设计非常规律。MA运算器及变换运算器重复使用在系统上。因此非常适合VLSI实现。AES算法

1997年4月15日，美国国家标准技术研究所（NIST）发起征集AES（AdvancedEncryptionStandard)的活动，目的是为响应公众日益增长的替换DES的要求，确定21世纪的数据加密标准。1997年9月12日正式公布了通告。通告要求AES比3DES快而且安全，分组长度为128-bit，密钥长度为128、192及256-bit。

AES算法NIST原名为NBS（国家标准局），是美国商业部下属的一个机构，1988年改为现名。著名的DES加密算法即是由它们颁布的。1998年8月20日公布了符合基本要求的15个算法。1999年3月从中选出了5个。2000年4月对5个算法进行了讨论。2000年10月，NIST公布了最终的获胜者是Rijndael算法。AES算法能有效地抵抗差分分析与线性攻击。但加密、解密过程不完全对称，使用了不同的代码和S-盒，所以实现起来占用资源相对多一些。AES算法-Rijndael算法数据块长度和密钥长度可以是128比特、192比特和256比特，其原型是Square算法。设计策略——宽轨迹策略（WideTrailStrategy）。宽轨迹策略针对差分分析和线性分析提出，其最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼进的偏差的界。AES算法-Rijndael算法（续）Rijndael采用的是代替/置换网络。每一轮由以下三层组成：线性混和层——确保多轮之上的高度扩散；非线性层——由16个S－盒并置而成，起到混淆的作用；密钥加层——子密钥简单地异或到中间状态上。S－盒选取的是有限域GF（28）中的乘法逆运算，它的差分均匀性和线性偏差都达到了最佳。密码的分析方法解密与密码分析解密是加密的逆过程，是指掌握密钥和密码算法的合法人员从密文恢复出明文的过程。密码分析则是指非法人员对密码的破译，而且破译以后不会告诉对方。

共同点

“解密（脱密）”和“密码分析（密码破译）”都是设法将密文还原成明文。

不同点二者的前提是不同的，“解密（脱密）”掌握了密钥和密码体制，而密码分析（破译）则没有掌握密钥和密码体制分组密码的分析方法(续）根据攻击者掌握的信息，可将分组密码的攻击分为以下几类：唯密文攻击：攻击者除了所截获的密文外，没有其他可利用的信息。已知明文攻击：攻击者仅知道当前密钥下的一些明密文对。选择明文攻击：攻击者能获得当前密钥下的一些特定的明文所对应的密文。选择密文攻击：攻击者能获得当前密钥下的一些特定的密文所对应的明文。分组密码的分析方法(续）一种攻击的复杂度可以分为两部分：数据复杂度和处理复杂度。数据复杂度是实施该攻击所需输入的数据量。处理复杂度是处理这些数据所需的计算量。

对某一攻击通常是以这两个方面的某一方面为主要因素，来刻画攻击复杂度。

【例如】穷举攻击的复杂度实际就是考虑处理复杂度；差分密码分析其复杂度主要是由该攻击所需的明密文对的数量来确定。几种常见的攻击方法1.强力攻击强力攻击可用于任何分组密码，且攻击的复杂度只依赖于分组长度和密钥长度，严格地讲攻击所需的时间复杂度依赖于分组密码的工作效率（包括加解密速度、密钥扩散速度以及存储空间等）。强力攻击常见的有：穷举密钥搜索攻击、字典攻击、查表攻击和时间-存储权衡攻击等。几种常见的攻击方法（续）2.差分密码分析基本思想通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特密码分析者可随机选择具有固定差分的一对明文（只要求它们符合特定差分条件），然后使用输出密文中的差分，按照不同的概率分配给不同的的密钥。随着分析的密文对越来越多，其中最可能的一个密钥就显现出来了。这就是正确的密钥。几种常见的攻击方法（续）3.线性密码分析本质：一种已知明文攻击方法。基本思想：通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统。公钥加密技术基本概念RSA公钥密钥算法ElGamal算法椭圆曲线算法基本概念1976年，W.Diffie和M.E.Hellman发表了“密码学的新方向（NewDirectionsinCryptography)”一文，提出了公钥密码学（Public-keycryptography）的思想，在公钥密码体制（Public-keycryptosystem）中加密密钥和解密密钥是不同的，加密密钥可以公开传播而不会危及密码体制的安全性。通信的一方利用某种数学方法可以产生一个密钥对，一个称为公钥（Public-key)，另外一个称为私钥（Private-key)。该密钥对中的公钥与私钥是不同的，但又是相互对应的，并且由公钥不能推导出对应的私钥。选择某种算法（可以公开）能做到：用公钥加密的数据只有使用与该公钥配对的私钥才能解密。基本概念（续）公钥加密算法的核心——单向陷门函数，即从一个方向求值是容易的。但其逆向计算却很困难，从而在实际上成为不可行。定义1.设是一个函数，如果对任意给定的,计算,使得是容易计算的，但对于任意给定的，计算，使得是难解的，即求的逆函数是难解的，则称是一个单向函数。基本概念（续）定义2.设是一个函数，是与有关的一个参数。对于任意给定的，计算，使得

是容易的。如果当不知参数时，计算的逆函数是难解的，但当知道参数时，计算函数的逆函数是容易的，则称是一个单向陷门函数，参数称为陷门。2.3.2RSA公钥密码算法RSA是Rivet，Shamir和Adleman于1978年在美国麻省理工学院研制出来的，它是一种比较典型的公开密钥加密算法。基础

大数分解和素性检测——将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。

RSA公钥算法特点：思想最简单；分析最透彻；应用最广泛；易于理解和实现；经受住了密码分析，具有一定的可信度。RSA公钥密码算法为了获得最大程度的安全性，选取的p和q的长度应差不多，都应位长度在100位以上的十进制数字。RSA算法的描述独立选取两个大素数p

和q

；计算：随机选取一个满足且的整数e，则e在模下的逆元为：

n和e为公钥，d为私钥。

注：p和q不再需要时，可以销毁，但一定不能泄露。举例取两个质数p=11，q=13，p和q的乘积为n=p×q=143，算出另一个数d=(p-1)×(q-1)=120；再选取一个与d=120互质的数，例如e=7，则公开密钥=（n，e）=（143，7）。对于这个e值，可以算出其逆：a=103。因为e×a=7×103=721，满足e×amodd=1；即721mod120=1成立。则秘密密钥=（n，a）=（143，103）。

设张小姐需要发送机密信息（明文）m=85给李先生，她已经从公开媒体得到了李先生的公开密钥（n，e）=（143，7），于是她算出加密值：c=memodn=857mod143=123并发送给李先生。李先生在收到密文c=123后，利用只有他自己知道的秘密密钥计算：m=camodn=123103mod143=85，所以，李先生可以得到张小姐发给他的真正的信息m=85，实现了解密。加密变换：将信息划分成数值小于n的一系列数据分组。对每个明文分组m进行如下的加密变换得到密文c：解密变换：RSA算法的描述

例

选取p=5，q=11，则有：n=55且明文分组应取1到54的整数。

选取加密指数e=7，则e满足

且与互素，故解密指数为d=23。

假如有一个消息m=53197，分组可得：，，。

分组加密得到：密文的解密为：最后恢复出明文RSA算法的安全性缺点：密钥产生和加/解密过程都很复杂，系统运行速度比较慢。攻击方法具体实现：算法安全的现状RSA算法安全性更危险的安全威胁来自于大数分解算法的改进和新算法的不断提出。破解RSA-129采用的是二次筛法；破解RSA-130使用的算法称为推广的数域筛法；尽管如此，密码专家们认为一定时期内1024到2048比特模数的RSA还是相对安全的。该算法使破解RSA-130的计算量仅比破解RSA-129多100%。除了对RSA算法本身的攻击外，RSA算法还面临着攻击者对密码协议的攻击。

利用RSA算法的某些特性和实现过程对其进行攻击。RSA算法安全性共用模数攻击前提：

RSA的实现中，多个用户选用相同的模数n，但有不同的加解密指数e和d。共用模数优点：算法运行简单。缺点：算法不安全。

低加密指数攻击较小加密指数e：

—可以加快消息加密的速度。

—太小会影响RSA系统的安全性。原理：

在多个用户采用相同的加密密钥e和不同的模数n的情况下，如果将同一个消息（或者一组线性相关的消息）分别用这些用户的公钥加密，那么利用中国剩余定理可以恢复出明文。假设取e=3，三个用户不同模数分别是n1,n2,和n3，将消息x用这三组密钥分别加密为：根据中国剩余定理，由y1,y2和y3求出：低加密指数攻击由于：因此：于是：低加密指数攻击

如何抵抗攻击？

—加密指数e必须足够大；

—对较短的消息进行独立的随机数填充；破坏明文消息的相关性，以防止低加密指数攻击。低加密指数攻击中间相遇攻击指数运算具有可乘性，这种可乘性有可能招致其他方式的攻击。如果明文m可被分解成两项之积那么：这意味着明文的分解可导致密文的分解，明文分解容易使得密文分解也容易。密文分解容易将导致中间相遇攻击。由RSA的可乘性得：前提：中间相遇攻击

1）攻击者先创建一个有序的序列：

2）搜索这个有序序列，尝试从中找到两项和满足：

3）攻击者能在步操作之内找到和，由此获得明文。中间相遇攻击中间相遇攻击

RSA算法的脆弱性p、q选择不当，则变换周期性、封闭性而泄密例：p=17，q=11，e=7，则n=187。设m=123，则

C1=1237mod187=183C2=1837mod187=72C3=727mod187=30C4=307mod187=123

明文m经过4次加密，恢复成明文。总之，RSA对用户要求太苛刻，密钥不能常更换。2ElGamal算法该体制是由ElGamal在1985年提出的，其安全性是基于有限域上计算离散对数的困难性。

ElGamal提出了加密模型和认证模型两种体制，加密模型没有被充分应用，而其认证模型是美国数字签名标准（DSS）的基础。椭圆曲线算法1985年Koblitz和Miller提出在密码学中应用椭圆曲线的思想，使其成为构造公开密钥密码系统的一个有利工具。其安全性是基于椭圆曲线上的离散对数计算的困难性。优点：椭圆曲线上离散对数的计算要比有限域上离散对数的计算更困难。与RSA相比，椭圆曲线密码体制能用较短的密钥达到较强的安