信息安全原理与应用-密码学基础.ppt

1,信息安全原理与应用第二章密码学基础本章由王昭主写,2,内容提要,基本概念和术语密码学的历史古典密码,3,基本概念,密码学(Cryptology)：是研究信息系统安全保密的科学。密码编码学(Cryptography)：主要研究对信息进行编码，实现对信息的隐蔽。密码分析学(Cryptanalytics)：主要研究加密消息的破译或消息的伪造。,4,基本术语,消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。对明文进行加密操作的人员称作加密员或密码员(Cryptographer)。密码算法(CryptographyAlgorithm):是用于加密和解密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm)。所传送消息的预定对象称为接收者(Receiver)。接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm)。,5,凯撒密表,公元前54年，古罗马长官凯撒明文字母abcdefghijklmnopqrstuvwxyz密文字母DEFGHIJKLMNOPQRSTUVWXYZABC有一个拉丁文句子omniagalliaestdivisainpartestres(高卢全境分为三个部分）RPQLDJDOOLDHVWGLYLVDLQSDUWHVWUHV把明文的拉丁字母逐个代之以相应的希腊字母,6,加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey)。,7,密码学的目的：A和B两个人在不安全的信道上进行通信，而攻击者O不能理解他们通信的内容。,加密通信的模型,8,密码体制,密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）（4）任意kK，有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x)=x，这里xP。,9,密码算法分类-i,按照保密的内容分:受限制的（restricted）算法：算法的保密性基于保持算法的秘密。基于密钥（key-based）的算法：算法的保密性基于对密钥的保密。,10,密码算法分类-ii,基于密钥的算法，按照密钥的特点分类：对称密码算法（symmetriccipher)：又称传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。非对称密钥算法（asymmetriccipher）:加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-keycipher）。公开密钥算法用一个密钥进行加密,而用另一个进行解密.其中的加密密钥可以公开，又称公开密钥（publickey)，简称公钥。解密密钥必须保密，又称私人密钥（privatekey）私钥，简称私钥。,11,密码算法分类-iii,按照明文的处理方法：分组密码（blockcipher）:将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher）:又称序列密码。序列密码每次加密一位或一字节的明文，也可以称为流密码。序列密码是手工和机械密码时代的主流,12,密码算法分类-iv,对称密钥密码又可分为：分组密码每次对一块数据加密多数网络加密应用DES、IDEA、RC6、Rijndael流密码每次对一位或一字节加密手机One-timepadding、Vigenre、Vernam,13,密码算法分类-v,公开密钥密码：大部分是分组密码，只有概率密码体制属于流密码每次对一块数据加密数字签名,身份鉴别RSA、ECC、ElGamal加密解密速度慢,14,Kerckhoff原则,1883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全的基础上。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码和现代密码的分界线。,15,密码分析,假设破译者O是在已知密码体制的前提下来破译正在使用的密钥，这个假设称为Kerckhoff原则。最常见的破解类型如下：唯密文攻击：O具有密文串y。已知明文攻击:O具有明文串x和相应的密文y。选择明文攻击：O可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。选择密文攻击：O可暂时接近密码机，可选择密文串y，并构造出相应的明文x。这一切的目的在于破译出密钥或密文,16,内容提要,基本概念和术语密码学的历史古典密码,17,密码学的起源和发展-i,三个阶段：1949年之前密码学是一门艺术19491975年密码学成为科学1976年以后密码学的新方向公钥密码学,18,密码学的起源和发展-ii,1949年之前:古典密码（classicalcryptography)密码学还不是科学，而是艺术出现一些密码算法和加密设备密码算法的基本手段代替&置换（substitution&permutation）出现，针对的是字符简单的密码分析手段出现,19,密码学的起源和发展-iii,19491975年:计算机使得基于复杂计算的密码成为可能1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的TheCodebreakers1971-73年IBMWatson实验室的HorstFeistel等的几篇技术报告数据的安全基于密钥而不是算法的保密,20,密码学的起源和发展-iv,1976年以后:1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不对称密钥密码1977年Rivest，Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！,21,密码学的起源和发展-v,1976年以后:对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现“过渡性”的“postDES”算法，如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现2001年Rijndael成为DES的替代者,22,内容提要,基本概念和术语密码学的历史古典密码,23,密码算法的安全性,无条件安全（Unconditionallysecure）无论破译者有多少密文，他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性。One-timepad计算上安全（Computationallysecure）破译的代价超出信息本身的价值。破译的时间超出了信息的有效期。,24,古典密码,基于字符的密码代替密码（substitutioncipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。（代替规则、密文所用字符、明文中被代替的基本单位）置换密码（permutationcipher），又称换位密码（transpositioncipher）：明文的字母保持相同，但顺序被打乱了。,古典密码,代替密码置换密码,25,26,代替密码,简单代替密码（simplesubstitutioncipher），又称单字母密码（monoalphabeticcipher）：明文的一个字符用相应的一个密文字符代替，而且密文所用的字符与一般的明文所用字符属同一语言系统。多字母密码（ployalphabeticcipher）：明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。,27,单字母密码,单表代换密码移位（shift）密码、乘数（multiplicative）密码仿射（affine)密码、多项式（Polynomial）密码密钥短语（KeyWord）密码多表代换密码维吉尼亚（Vigenere）密码博福特（Beaufort）密码滚动密钥（running-key）密码弗纳姆（Vernam）密码转轮密码机（rotormachine）,28,多字母代换密码,可以用矩阵变换方便地描述多字母代换密码，有时又称起为矩阵变换密码。HillcipherPlayfaircipher,29,模运算-i,定义集合为Zq为小于q的所有非负整数集合：Zq=0，1，2，,q-1，该集合也可看作模q的余数集合。在该集合上可以进行算术运算，就是所谓的模运算。定义加法和乘法运算如下:加法:(amodq)+(bmodq)modq=(a+b)modq减法：(amodq)-(bmodq)modq=(a-b)modq乘法:(amodq)(bmodq)modq=(ab)modq模运算有下述性质：（1）若q|(a-b)，则ab(modq)（2）(amodq)=(bmodq)意味abmodq（3）对称性，abmodq等价于bamodq（4）传递性，若abmodq且bcmodq，则acmodq,30,模运算-ii,类似普通的加法，在模运算中的每个数也存在加法逆元，或者称为相反数。一个数x的加法逆元y是满足x+y0modq的数。对每一个，存在z，使得w+z0modq。在通常的乘法中，每个数存在乘法逆元，或称为倒数。在模q的运算中，一个数x的乘法逆元y是满足xy1modq的数。但是并不是所有的数在模q下都存在乘法逆元。如果(ab)modq=(ac)modq，bcmodq，如果a与q互素。如果q是一个素数，对每一个,都存在z，使得wz1modq，z称作w的乘法逆元w-1。,31,模运算-iii,模26的最小非负完全剩余系，即模26的余数集合为0,1,2,25。可以把字母表与模26的余数集合等同，26个英文字母与模26余数集合0,.,25建立一一对应，在此基础上对字符进行运算。,32,单字母密码,单表代换密码移位（shift）密码乘数（multiplicative)密码仿射（affine)密码密钥短语（KeyWord）密码任意的单表代替密码,33,移位密码算法,设P=C=K=Z26，对kK,定义ek(x)=x+k(mod26)=yC同时dk(y)=y-k(mod26)当k=3时，为Caesar密码abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC例子:cipher=FLSKHU实际算法为：有同时有，d3(y)=y-3(mod26),34,移位密码分析,给定加密的消息:PHHWPHDIWHUWKHWRJDSDUWB由于（1）加解密算法已知（2）可能尝试的密钥只有25个（不包括0）通过强力攻击得到明文：meetmeafterthetogaparty.移位密码很容易受到唯密文攻击。,35,单字母密码,单表代换密码移位（shift）密码乘数（multiplicative)密码仿射（affine)密码密钥短语（KeyWord)密码任意的单表代替密码,36,乘数密码算法,加密函数取形式为e(x)=ax(mod26)，aZ26要求唯一解的充要条件是gcd(a,26)=1该算法描述为：设P=C=Z26，K=aZ26|gcd(a,26)=1,对k=aK,定义ek(x)=ax(mod26)和dk(y)=a-1(y)(mod26)x,yZ26例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR明文密文cipher=SUFLKX,37,乘数密码分析,对于乘数密码，当且仅当a与26互素时，加密变换才是一一映射的，因此a的选择有11种：a=3,5,7,9,11,15,17,19,21,23,25可能尝试的密钥只有1个,38,单字母密码,单表代换密码移位（shift）密码乘数（multiplicative)密码仿射（affine)密码密钥短语（KeyWord)密码任意的单表代替密码,39,仿射密码算法-i,加密函数取形式为e(x)=ax+b(mod26),a,bZ26要求唯一解的充要条件是gcd(a,26)=1该算法描述为：设P=C=Z26K=(a,b)Z26Z26|gcd(a,26)=1,对k=(a,b)K，定义ek(x)=ax+b(mod26)和dk(y)=a-1(y-b)(mod26)x,yZ26q=26时，可能的密钥是2612-1=311个,40,单字母密码,单表代换密码移位（shift）密码乘数（multiplicative)密码仿射（affine)密码密钥短语（KeyWord)密码任意的单表代替密码,41,密钥短语密码,以西文单词为密钥的换字表例如：取university为密钥，首先找出其中发生重复的字母，去掉重复字母i，成为universty.其次，字母一共10个，从第11个字母开始，用universty按顺序进行代替配置。然后把其余17个字母按自然顺序接在后面。以university为密钥的换字表明文字母abcdefghijklmnopqrstuvwxyz密文字母JKLMOPQWXZUNIVERSTYABCDFGH,42,非自然续序配置的换字表,明文字母与代替他的密文字母豪无关联那么整个换字表就是他的密钥明文字母abcdefghijklmnopqrstuvwxyz密文字母IGVRFHPJYBNKAXLTSMCWDUEOZQ,43,单字母密码,单表代换密码移位（shift）密码乘数（multiplicative)密码仿射（affine)密码密钥短语（KeyWord)密码任意的单表代替密码,44,任意的单表代替密码算法,设P=C=Z26，K是由26个符号0，1，.，5的所有可能置换组成。任意K，定义e(x)=(x)=y且d(y)=-1(y)=x,-1是的逆置换。注：1*.置换的表示：2*密钥空间K很大，|k|=26!41026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。3*移位密码、乘数密码、仿射密码算法都是替换密码的特例,0123.2324250123.232425,),(,45,单表替换密码的破译,语言的统计特性：语言的频率特征连接特征重复特征,46,频率特征,在各种语言中，各个字母的使用次数是不一样的，有的偏高，有的偏低，这种现象叫偏用现象。对英文的任何一篇文章，一个字母在该文章中出现的次数称作这个字母（在这篇文章中）的频数。一个字母的频数除以文章的字母总数，就得到字母的使用频率。,47,英文字母的普遍使用频率,美国密码学家W.F.Friedman在调查了大量英文资料后,得出英文字母的普遍使用规律.,48,英文单字母使用频率分类,49,特殊的特征,开头结尾特征:有些文章的开头和结尾受到固定格式的限制有时文章中间的某些特定部位，某些字母也会出现较高的使用频率。,50,频度最高的前30个双字母,51,频度最高的前20个三字母,52,其它频率特征,the的使用频率最高，是ING的三倍，若把the去掉，t在第II类中排在最后，h会降为第III类，th和he也不是常出现的字母组了一半的单词以esdt结尾一半的单词以tasw开头Y的使用频率90%都集中在单词的结尾,53,连接特征,后连接：qu前连接：x的前面总是i，e很少是o和a间断连接：在e和e之间，r的出现频率最高,54,重复特征,两个字符以上的字符串重复出现的现象，叫做语言的重复特征。thtiontious,例子-密文,QRLLIQQPFVICXPFMTPZWRFNFOTFLPYWIGQPQHICQRGIVAKZWIQIBORGZWPFMQPFZWIOGVIGFCHIVYIGQIJIGCFLILCGIBRXHIZWOVQOBCFCXKQPQPFZRPZPOFXRLNZWICAPXPZKCZXICQZZOGICVZWIXCFMRCMIOBZWIOGPMPFCXZISZPQJIGKVIQPGCAXIARZFOZIQQIFZPCX,55,确定字母的相对频率,I可能相当于明文中的e,56,双字母频率,57,最常见的双字母组合ZW，Z猜测其为T，W对应为HWIHEPFIN,进一步分析-1,ZWIQI与these相似，QSTPZW与with类似，TWIQQIFZPCX与essential相似，CA，XLCFCXKQPQ与analysis类似，KYCAPXPZK与ability类似，AB,58,进一步分析-2,ZWPFM与things类似，MGXCFMRCMI与language类似，RUVICXPFM与dealing类似，VDQRLLIQQ与success类似，LCGICV与read类似，GR,59,进一步分析-3,LCGIBRX与careful类似，BFHICQRGIV与measured类似，HMHIZWOVQ与methods类似，OOJIGK猜测为veryYIGQIJIGCFLI猜测为perseveranceRFNFOTF猜测为unknown，把ZISZ猜测为text,60,密钥,61,完整明文,Successindealingwithunknownciphersismeasuredbythesefourthingsintheordernamed：perseverance，carefulmethodsofanalysis，intuition，luck.Theabilityatleasttoreadthelanguageoftheoriginaltextisverydesirablebutnotessential.,62,63,对抗频率分析的办法,多名或同音代替密码多表代替密码多字母代替密码,64,多名代替密码,与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。例如，A可能对应于5、13、25B可能对应于7、9、31、42,65,多表代替密码,多表代替密码：是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。非周期多表代替密码：代换表是非周期的无限序列一次一密密码（one-timepadding)：对每个明文每次采用不同的代换表。周期多表代替密码：代换表个数有限，重复使用。,66,多表代替密码,多表代替密码维吉尼亚（Vigenere)密码滚动密钥（running-key）密码弗纳姆（Vernam）密码转轮密码机（rotormachine）,67,Vigenrecipher(1858),是一种多表移位代替密码设d为一固定的正整数，d个移位代换表=（1，2,d)由密钥序列K（k1,k2,kd)给定，第i+td个明文字母由表i决定，即密钥ki决定ek(xi+td)=(xi+td+ki)modq=ydk(yi+td)=(xi+td-ki)modq=x例子：q=26,x=polyalphabeticcipher,K=RADIO,68,Vigenrecipher-破译,密钥空间大小为26m，m=5，265=1.1107依然保留了字符频率某些统计信息分析的第一步是确定密钥字的长度d，确定d的方法最常用的有两种Kasiski测试法1863年，普鲁士军官Kasiski提出的一种重码分析法重合指数法（indexofcoincidence),69,Kasiski测试法,重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大偶然重复和真重复他们之间的距离的因数可能就是密钥长度。Kasiski实验：对一份用周期性多表密码加密的密文，确定其中所有的重复出现的字母串，计算他们之间的距离，并对这些距离进行因子分解，出现频率较高的因子很可能是密钥的长度。,70,重合指数,设y是一个长度为n密文，即y=y=y1y2y3ym，其中yi是密文字母，同样来求从中抽到两个相同字母的概率是多少？为此，设NA为字母A在这份密文中的频数，设NB为字母B在这份密文中的频数，依此类推。从n个密文字母中抽取两个字母的方式有Cn2=n(n-1)/2，而其中NA个A组成一对A的方式有CNA2=NA(NA-1)/2，于是从y中抽到两个字母都为A的概率为NA(NA-1)/n(n-1)，因此，从y中抽到两个相同字母的概率为这个数据称为这份密文的重合指数。记为IC,71,一个判断准则,根据概率论中的大数定律，如果y是用单表加密的，那么当n较大时，IC很可能接近于0.0687,72,多表代替密码,多表代替密码维吉尼亚（Vigenere)密码滚动密钥（running-key）密码弗纳姆（Vernam）密码转轮密码机（rotormachine）,73,滚动密钥密码,对于周期代换密码，当密钥的长度d和明文一样长时，就成为滚动密钥密码。Vigenre本人建议密钥与明文一样长,74,多表代替密码,多表代替密码维吉尼亚（Vigenere)密码滚动密钥（running-key）密码弗纳姆（Vernam）密码转轮密码机（rotormachine）,75,Vernam密码,1918年，GillbertVernam建议密钥与明文一样长并且没有统计关系的密钥内容，他采用的是二进制数据:加密：Ci=PiKi解密Pi=CiKi核心：构造和消息一样长的随机密钥,76,多表代替密码,多表代替密码维吉尼亚（Vigenere)密码滚动密钥（running-key）密码弗纳姆（Vernam）密码转轮密码机（rotormachine）,77,转轮密码机,三个转轮的代替表数量262626=17576,78,对抗频率分析的办法,多名或同音代替密码多表代替密码多字母代替密码Playfair密码Hill密码,79,多字母代替密码-Playfair,Playfair:将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。55变换矩阵:I与J视为同一字符CIPHERABDFGKLMN(cipher)OQSTUVWXYZ加密规则:按成对字母加密相同对中的字母加分隔符(如x)balloonbalxloon同行取右边:heEC同列取下边:dmMT其他取交叉:ktMQODTR,80,Playfair密码分析,Playfair有2626=676种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息,81,多字母代替密码,多字母代替密码Playfair密码Hill密码,82,Hill密码（1929）,基于矩阵的线性变换:假设K是一个m*m矩阵，在Z26上可逆，即存在K-1使得：KK-1=I（在Z26上），对每一个kK，定义ek(x)=xK(mod26)和dk(y)=yK-1(mod26)明文与密文都是m元的向量（x1,x2,xm），（y1,y2,ym）,83,Hill密码分析,完全隐藏了字符（对）的频率信息采用唯密文攻击希尔密码是很难攻破的.线性变换的安全性很脆弱，易被已知明文攻击击破。,古典密码,代替密码置换密码,84,85,置换密码,在换位密码中，明文的字母保持相同，但顺序被打乱了。一种换位密码把明文按行写入,按列读出密钥包含3方面信息:行宽、列高、读出顺序完全保留字符的统计信息使用多轮加密可提高安全性,86,古典密码小结,模运算：加法、减法、乘法性质：对称、传递、交换、结合、分配加法逆元、乘法逆元对称密码的两个基本运算代替和置换（Substitution&permutation）密码分析与Kerckhoff原则多轮加密数据安全基于算法的保密,87,古典密码小结,88,参考文献,王昭，袁春编著，信息安全原理与应用，电子工业出版社，北京，2010，1WilliamStallings,Cryptographyandnetworksecurity:principlesandpractice,SecondEdition.BruceShneier,Appliedcryptography:protocols,algorithms,andsourcecodeinC,SecondEdition.ThomasH.Barr,InvitationtoCryptology,PrenticeHall,2002李克洪主编，实用密码学与计算机安全，东北大学出版社，1997，10王育民刘建伟编著，通信网的安全-理论与技术，2000，5,89,Q&A?,