经典密码学教学课件

经典密码学密码体制的理解密码体制的理解一个加密变换加密变换乃一个下列形式的一一映射：E:MK1 C 一般对于给定的kK1,把E(-,k)记为Ek;一个解密变换解密变换乃对应一个加密变换E而言，其实是一个以下形式的映射：D:CK2 M 并且适合（对于给定的kK2,也把D(-,k)记为Dk）：6密码体制的理解密码体制的理解重要原则重要原则：对任一kK1,都能找到k”K2,使得Dk”(Ek(m)=m，mM。7一般性说明一般性说明u我们常将26个英文字母(不区分大小写)与整数025依次一一对应。u记 Zq=0,1,2,q-1称之为模q剩余类环；当q为素数时，该环进一步形成为域，可改写为Fq。8一般性说明一般性说明u一般说来，一个密码体制的任一密钥控制下的加密变换都要求把明文按n（最少必要的固定数）个信息单元进行分组。照理，一个密码体制的明文空间M应该是所有可能明文的集合，但人们却习惯于把它写成前述所有n个信息单元组的集合；如此，密文空间C以及加解密变换的定义也有相应的变通。9简单密码举例简单密码举例n密码学的历史已有4000多年n古埃及人曾把象形文字写在石碑上10简单密码举例简单密码举例例例1.凯撒（Caesar)密码凯撒密码是古罗马人Julius Caesar发明的一种密码体制，它是使用最早的密码体制之一。凯撒密码用于对英文信息进行加密，它依据下列代替表（由英文字母表左环移3位得到）对信息中26个英文字母进行替换：明文字母abcdefghijklmnopqrstuvwxyz密文字母DEFGHIJKLMNOPQRSTUVWXYZABC11简单密码举例简单密码举例若明文为：Substitution cryptosystem 则相应的密文是：VXEVWLWXWLRQ FUBSWRVBVWHP在上述凯撒密码体制中，英文字母代替表即相当于密钥；若将英文字母表左环移k(0k1）称该密码为分组（块）密码。25密码体制的分类密码体制的分类序列（流）密码的特点：加解密速度快，无错误扩散；一般用于实际的安全产品。分组（块）密码的特点：适合数据库加密，组内有错误扩散；一般用于公开的理论研究。26密码体制的分类密码体制的分类v依据密钥分类依据密钥分类单钥密码单钥密码(传统密码，对称钥密码）传统密码，对称钥密码）双钥密码双钥密码(公钥密码公钥密码,非对称钥密码非对称钥密码)基于计算复杂性，人们可以设计出这样的密码体制：加密变换与相应的解密变换分别使用不同的密钥k与k”，并且kk”在计算上不可行（尽管理论上应该能够）。如此，用户选择该体制的一对加解密密钥(k,k”)后，可以将前者公开而后者私存。区别于传统上加解密密钥一致或相近而必须都保密的观念,称之为非对称(公开)钥密码体制。27密码体制的分类密码体制的分类一般说来，单钥密码体制（包括分组、序列密码）都是基于计算安全性的，而双钥密码体制是基于可证明安全性的。这两种安全性都是从计算量来考虑，但不尽相同。计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低于解已知数学难题的计算量。28密码体制的分类密码体制的分类单钥密码优点：运行速度快，具有可靠的保密强度；不足：不便密钥交换和管理。双钥密码优点：便于密钥交换和管理，还可用于消息认证（数字签名）；不足：运行速度缓慢，其安全性所 依赖的数学难题的复杂性一般都未能证明。29早期密码体制大都比较简单，其中许多经不起计算机的破译攻击。这些体制一般都是直接针对原始的信息单元（字母或符号等）设计，而并不象现代密码体制那样非常重视和体现信息的数字化与数学处理。但对早期密码体制的讨论可以说明构造和破译的基本原理和方法，对于理解、构造和分析现代复杂的实用密码体制有着起码的利益。2.代替密码代替密码30早期密码体制基本上可以按照下述分类笼统起来：n代替密码n移位密码以下我们便按照这样的分类来依次学习早期的密码体制及其破译。2.代替密码代替密码312.代替密码代替密码一个代替密码，若其任何密文可以看成是对相应明文的各组信息单元使用同一个代替表进行替换而得到，则称其为单表代替密单表代替密码码；否则，即有密文是依次对相应明文的各组信息单元使用有限个周期性重复的或无限多的固定代替表进行替换而得到，称其为多多表代替密码。表代替密码。32单表代替密码单表代替密码n每个字母可以用其它任何一个字母替换（不能重复）n每个字母可以随机的映射到其它一个n因此密钥长度是26个字母n单字母替换密码（Monoalphabetic Substitution Cipher）n例如：n明文:ABCDEFGHIJKLMNOPQRSTUVWXYZn密文:DKVQFIBJWPESCXHTMYAUOLRGZNnPlaintext:IFWEWISHTOREPLACELETTERSnCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA33单表代替密码举例单表代替密码举例n给定密钥字“STARWARS”，去掉重复字母得到“STARW”，填写剩余字母：STARWBCDEFGHIJKLMNOPQUVXYZn按列读取字母得到密文：nPlain:ABCDEFGHIJKLMNOPQRSTUVWXYZCipher:SBGLQZTCHMUADINVREJOXWFKPYn可以用这个密钥加密、解密n例如Plaintext:IKNOWONLYTHATIKNOWNOTHINGnCiphertext:HUINFNIAPOCSOHUINFINOCHIT34单表代替密码单表代替密码n需要一种简单方法指定密钥。n有多种方法，一种简单方法是写没有重复字母的“密钥字密钥字”，其它字母按顺序写在密钥字最后字母后面。n例如，给定密钥字JULIUSCAESARnPlain:ABCDEFGHIJKLMNOPQRSTUVWXYZnCipher:JULISCASRTVWXYZBDFGHKMNOPQ35单表代替密码的密码分析单表代替密码的密码分析n根据频率统计进行分析，确定每个字母被映射到什么字母，单个字母出现的可能是A或I（sinceknowsinglewordsareAorI）n一般来说个字母出现的可能是THE或AND，还可以用其他通常出现的双字母或三字母组合。n还可以应用其它很少应用的字母36单表代替密码构造方法单表代替密码构造方法u举例例例1.1.一个英文单表代替密码例例2.2.方格密码例例3.3.普莱费尔(Playfair)密码u构造方法构造单表代替密码的关键是构造一张明密代替表(可能以对应Z26的观点写成一个数学公式)。以后不加声明，总假定M=C=a,b,c,z(记为A),Z26,或它们的n-直积。37单表代替密码构造方法单表代替密码构造方法密钥字法该法形成明密代替表如下：首先依次列出密钥字中字母(去掉其中的重复)，然后依次列出字母表中其余的字母。特点：便于由记忆的密钥字构造出明密代替表；但密钥空间K由所有可能的密钥字构成，其实密钥量|K|比较小。38洗牌法该法就是将写有每个英文字母的26张纸牌打乱次序后重新排列形成明密代替表。如例1。特点：密钥空间K由26个英文字母的所有可能的全排列构成（|K|=26！），密钥的保密性较好，但不便于记忆。单表代替密码构造方法单表代替密码构造方法39仿射法该法的加密变换Ek为：Ek(m)=k1m+k2(mod 26),mZ26其中，k=(k1,k2)为密钥；为使上述加密变换是一一的（从而才有相应的解密变换），必要且只要(k1,26)=1。特点：便于用计算机实现，但密钥空间K=(k1,k2)|k1,k2Z26,(k1,26)=1，密钥量|K|=1226-1=311较小。单表代替密码构造方法单表代替密码构造方法40多项式法该法的加密变换Ek为(t为取定自然数)：Ek(m)=ktmt+kt-1mt-1+k1m+k0(mod 26),mZ26其中，k=(kt,kt-1,k1,k0)为密钥。仿射法其实是上述多项式法当t=1时的特例。有关多项式法的加密变换Ek何时是一一的以及对密钥空间K 的讨论已超出本课程的知识范围，在此不去涉及。单表代替密码构造方法单表代替密码构造方法41矩阵法该法的思想是：将明文组m=(m1m2mn)通过Z26上可逆的线性变换转换为密文组c=(c1c2cn)。如此，密钥空间K=(kij)|(kij)为Z26上n阶可逆方阵(有关讨论超出本课程的知识范围)；对于k=(kij)K，加密变换Ek为：Ek(m1m2mn)=(c1c2cn),miZ26其中，ci=ki1m1+ki2m2+kinmn(mod 26)。单表代替密码构造方法单表代替密码构造方法42（2）多表代替密码）多表代替密码多表代替密码是依次对明文的各组信息单元使用有限个周期性重复的或无限多的固定代替表进行替换来得到密文的：若是使用无限多的固定代替表（相对于明文变化是随机的），则称其为一次一密代一次一密代替密码替密码；若是使用有限个周期性重复的固定代替表，则称其为周期多表代替密码周期多表代替密码。43（2 2）多表代替密码）多表代替密码一次一密密码是在理论上唯一不可破解的密码，这种密码对于明文的特点可实现完全隐藏，但由于需要的密钥量与明文所含信息单元的个数一样大，故其难以实用。周期多表代替密码的实际情形如下：在给定的密钥(d个代替表排列T1T2Td)之下，加密明文m=m1m2m3的结果是c=T1(m1)Td(md)T1(md+1)Td(m2d)d称为该周期多表代替密码的周期。44周期多表代替密码周期多表代替密码u举例例例1.1.四表代替密码。例例2.2.维吉尼亚(Vigenere)密码。45nBlaisedeVigenre发明了多字母替换密码（polyalphabeticsubstitutioncipher）n使用多个单字母替换表n因此一个字母可以被多个字母替换。n方法：用一个密钥选择对每个字母使用哪个字母表，密钥的第I个字母表示使用第ith个字母表，依次使用每个字母表，当密钥的字母使用完后，在从头开始。Vigenre Cipher46n例：n写出明文，在明文下重复写出密钥字；n依次使用每个字母作为caesarcipher的密钥，加密对应的明文字母。nPlaintextTHISPROCESSCANALSOBEEXPRESSEDKeywordCIPHERCIPHERCIPHERCIPHERCIPHEPlaintextVPXZTIQKTZWTCVPSWFDMTETIGAHLHVigenre Example47nC-CDEFGHIJKLMNOPQRSTUVWXYZABnI-IJKLMNOPQRSTUVWXYZABCDEFGHnP-PQRSTUVWXYZABCDEFGHIJKLMNOnH-HIJKLMNOPQRSTUVWXYZABCDEFGnE-EFGHIJKLMNOPQRSTUVWXYZABCDnR-RSTUVWXYZABCDEFGHIJKLMNOPQABCDEFGHIJKLMNOPQRSTUVWXYZtomaptheaboveplaintextletters.T uses key C maps to V H uses key I maps to P I ises key P maps to X。Vigenre Example48n可以看出，越安全的密码使用起来越复杂，因此，在有些场合还可以看到单码替换密码，随着破译单码密码的技术提高，使得vigenrecipher逐渐被各国使用，1854年，首次被CharlesBabbage攻破，但没有公开。FriedrichKasiski与1863年攻破并发表了此密码的各种变形被沿用到20世纪。History of the Vigenre Cipher49周期多表代替密码周期多表代替密码例例3.3.博福特(Beaufort)密码。例例4.4.弗纳姆(Vernam)密码该密码是美国电报电话公司的G.W.Vernam在 1917年发明的。他将英文字母编成五位二元波多电码(Baudot code)，参见P.47表3.2.9。选择随机的二元密钥序列k=k1k2ki，对字母变换成二元码后的明文m=m1m2mi加密以后得到c=c1c2ci，其中ci=mi ki，i=1,2,50周期多表代替密码周期多表代替密码思考：怎样理解上述弗纳姆密码是周期多表代替密码？其实，弗纳姆密码可以看成周期d=明文长(明文所含字母数目)的多表代替密码。一般地,我们称周期d=明文所含信息单元组数目的多表代替密码为滚动密钥滚动密钥(Running-(Running-key)key)密码密码。51周期多表代替密码周期多表代替密码对于一个滚动密钥密码,其密钥序列(即依次决定d个代替表的系列对应要素，如弗纳姆密码所用的二元密钥序列)若能真正随机产生，则该种代替密码便相当于一次一密的了；一般密钥序列要由一给定主密钥作为初态的某密钥源伪随机地产生。52周期多表代替密码周期多表代替密码u构造方法照理，周期为d的多表代替密码的密钥空间应为K=T1T2Td|Ti为代替表,i=1,2,d,但在实际应用之中的密钥变化量往往较小：人们首先构造出dd个代替表T1,T2,Td，然后以T1,T2,Td取出d个的排列为密钥空间。如例1、2、3。上述在T1,T2,Td中取出d个排列起来的过程一般是借助决定d个代替表的系列对应要素进行，因此称之为构造密钥序列。53周期多表代替密码周期多表代替密码显然，周期多表代替密码的构造可以归结为：多个代替表（称为底表）的构造密钥序列的构造一个周期多表代替密码的密钥其实是上述密钥序列，底表预先定义，而在加密中每次应用哪一底表完全由该密钥序列来控制。54周期多表代替密码周期多表代替密码底表的构造一个底表一般为二维表，并且要求每个密文单元所在的行或列中出现一次且只出现一次，即该二维表应构成一个拉丁方阵。有关拉丁方阵的研究和构造可参见一些组合学书籍或刊物。55周期多表代替密码周期多表代替密码要求底表为一个拉丁方阵是必要的：因一般来说，底表的行、列分别对应明文和密钥：若横行有重码，则加密变换便不是一一的；若纵列有重码，则即使密钥序列是随机选取的，但明码中的不平衡性，也会造成密码的不平衡，从而使破译者仅从密码的统计分析即可获得明文的部分信息，这不利于保密。当然，若周期较大，则对保密性而言，底表的作用不大，其完全取决于密钥序列。56周期多表代替密码周期多表代替密码密钥序列的构造人们当然希望所产生的密钥序列具有尽可能好的随机性。一般可有下述三种构造方法：主观密钥源该种密钥源是以一本书或一个文件的选择内容作为密钥序列k1k2kd。评价评价：由于书本或文件中各信息单元出现的频率差异很大，故该种密钥源的保密性能不佳。57周期多表代替密码周期多表代替密码随机密钥源该种密钥源是以某种随机的方式产生密钥序列k1k2kd。例如，对维吉尼亚密码或博福特密码，使用者可将分别刻有26个英文字母的26个小球放在坛子里，然后用有放回地随机拣球方法产生密钥序列。评价评价：该种密钥源的保密性能最佳，但当d较大时一则难以实现，另则必须将此产生的较长密钥序列完全传送给接收方、或要由接收方妥善保管、等等，实有诸多不便。58周期多表代替密码周期多表代替密码伪随机密钥源该种密钥源是根据现代的编码方法，利用计算机硬件或软件实时地产生密钥序列k1k2kd。评价评价：该种密钥源往往以一给定的主密钥作为初态，产生一个自身呈周期性的密钥序列。但设计者可根据实际保密强度的要求，预期密钥序列的周期远远大于一般所加密明文的长度，而且还具有良好的随机性；此时可以认为伪随机密钥源在保密性能上已近似于随机密钥源了。59周期多表代替密码周期多表代替密码一个值得重视的问题是：密钥序列自身的保密性能固然重要，但若是应用不当，再好的密钥序列也可能无济于整个体制的安全。比如，密钥序列重用(这一现象称为重乱）就会给相应的周期多表代替密码体制带来危害，有关的具体情形以后会讲到。60多表代替密码的特点多表代替密码的特点q单表代替密码的特点单表代替密码的特点：具有明密异同规律，一般容易破译。q周期多表代替密码的特点周期多表代替密码的特点：在一定程度上打破了明密异同规律当周期d较小时，可确定之，并通过对密文重排，使其破译问题转化为对单表代替密码的破译对周期d较大且密钥序列是伪随机的，可达到实际保密对周期d较大且密钥序列是随机的,可达到理论保密q一次一密代替密码的特点一次一密代替密码的特点：无规律可循613.变换密码变换密码 transposition ciphersn变换密码（或置换密码）n方法：通过重新编排消息字母隐藏信息n特点：没有改变原来消息的字母集62（1）Scytale 密码密码n一种早期的希腊变换密码n一张纸条环绕在一个圆柱上n消息沿着圆柱横写n纸条上的字母看起来是一些随机字母n并不十分安全，密钥是纸条和圆柱的宽度63n以不同的行写下消息字母n按行读取消息nPlain:IAESWCNURDnCMIAIOQEEnCipher:IAESWCNURDCMIAIOQEE（2）轨道栏杆密码）轨道栏杆密码 Rail Fence cipher64n以一种形式写下消息，以另一种形式读取消息（3）几何图形密码）几何图形密码65n变换密码的关键思想n按一定规则写出明文，按另一规则读出密文。n密钥：用于读密文的方法和写明文的方法变换密码的关键思想变换密码的关键思想66（4）行变换密码）行变换密码-Row transposition ciphersngroupthemessageandshuffleletterswithineachgroupnmoreformallywritelettersacrossrowsnthenreorderthecolumnsbeforereadingofftherowsnalwayshaveanequivalentpairofkeys(ReadoffvsWriteIn)67nPlain:THESIMPLESTPOSSIBLETRANSPOSITIONSXXKey(R):25413Key(W):41532THESISTIEHMPLESEMSLPTPOSSSTSOPIBLETEITLBRANSPSRPNAOSITITOIISONSXXXOXSNnCipher:STIEHEMSLPSTSOPEITLBSRPNATOIISXOXSN行变换密码行变换密码68n可以用一个英文单词做密钥，指定以字母顺序做为读取密文（或明文）nPlain:CONVENIENTWAYTOEXPRESSTHEPERMUTATIONnKey(W):COMPUTERnKey(W):14358726nANOVINCEnEWTAOTNYnERPETSXSnHEPRTUEMnAOINZZTZnCipher:ANOVINCEEWTAOTNYERPETSXSHEPRTUEMAOINZZTZ行变换密码行变换密码69n用密钥sorcery加密下列消息:nKey(R):sorcery=6341257nlaserbeamscanbemodulatedtocarrymoreintelligencethanradiowaves=erasblecamsnabdumoleatoedctamoryrreelntliiceentghadnriaoesavw行变换密码举例行变换密码举例70n步骤:n按列写出消息n按解密密钥读取明文行变换密码解密算法行变换密码解密算法71n频率分析能够提供语言轮廓n基本思想:猜测密钥周期,再对可能的行列变换进行猜测.n利用常出现的双字母对或3字母对.Cryptanalysis of Row Transposition ciphers72密码分析举例密码分析举例 n给定密文:LDWOEHETTSHESTRHUTELOSBEDEFIEVNTn对连续周期测试,对前面一些字母重新排列.n2:LDWOEHETTSHESTRHUTELOSBEDEFIEVNT-NOn3:LDWOEHETTSHESTRHUTELOSBEDEFIEVNT-NOn4:LDWOEHETTSHESTRHUTELOSBEDEFIEVNT-NOn5:LDWOEHETTSHESTRHUTELOSBEDEFIEVNT-NOn6:LDWOEHETTSHESTRHUTELOSBEDEFIEVNT-YES!nnote第二组可能提供THESETorTTHESEn可以猜测6字密钥能够给出这种密文nkey5,6,1,4,2,3恢复明文如下:nWEHOLDTHESETRUTHSTOBESELFEVIDENTornWEHOLDTHESETRUTHSTOBESELFEVIDENT73（5）块（）块（Block）变换密码）变换密码n另一类变换密码n消息按行写，按列读出。n按列读出的顺序由密钥给出。74n为方便起见，把消息写成满矩阵形式Key(R):sorcerynsorceryKey(R):63412576341257laserbelaserbeamscanbamscanbemodulaemodulatedtocatedtocarrymorerrymoreintellIintelligencethgencethanradioanradiowaveswavesqrmatrixincompletecomplete块变换密码举例块变换密码举例75续续n由密钥给出的顺序读出密文（4,5,2,3,6,1,7)necdtmecaerauooledsammernenassodytnrvbnlcrltiqlaetrigawebaaeihor76块变换密码解密块变换密码解密 n计算密文行数n(bydividingmessagelengthbykeylength)n按列写出密文消息（密钥给出顺序）n按行读出明文消息77块变换密码分析块变换密码分析 n首先要知道是否块变换密码，通过消息长度猜测距阵大小，简单测试每个密钥，按列写出消息最一般的，利用自动工具实验所有置换，可以对一些可能单词组合形式的变换进行实验。78密码分析例子密码分析例子 n给定密文:HADVFNITHBCTSBEHTEGESRYRNAMINRIAISTTETOOETSANGLIETGTDRSCYGAITANAHFLNAUETIEMEOHUEAELYRIISn假设对行变换失败n现猜测是块变换n寻找THE，实验各种大小的密钥ntry2,usecommandb2/THE-nonematchntry3,usecommandb3/THE-nonematchntry4,usecommandb4/THE-2matches,bothrubbishntry5,usecommandb5/THE-1stmatchgivesanswer-b5/THEnTHEGREATESTDISCOVERYOFMYGENERATIONISTHATAHUMANBEINGCANALTERHISLIFEBYALTERINGHISATTITUDESAccept(y/n/q)?y79Nihilist ciphers n更复杂的变换密码（行变换和列变换同时应用）80n仅仅基于替换或置换的密码是不安全的n前面的得例子可以看到这一点n这是由于他们不能克服语言结构的特点n因此考虑连续使用几种密码克服,n注:n两个替换密码只能提高很少的复杂度n两个置换也只能提高很少的复杂度n但替换与置换连用，可以提高较高的复杂密码增加密码的安全性增加密码的安全性814.乘积密码乘积密码n是一种替换与变换合用的密码，一般情况下，手工破译是非常困难的。n一种有名的乘积密码“ADFGVXcipher”在第一次世界大战中使用。82ADFGVX 乘积密码乘积密码 n这样命名是因为变换仅依赖与ADFGVX，在WW1有德国人使用，并被英国人破译。n方法：使用一个固定的替换表，把每个明文字母映射成一个字母对(row-colindex)，在用一个带密钥的块变换把每个对分解then利用带密钥的块变换写下所有字母对，写出密文（按块密码形式）。83ADFGVX Substitution Table nADFGVXAKZWR1FD9B6CL5FQ7JPGXGEVY3ANV8ODH02XU4ISTM84ADFGVX 加密举例加密举例nPlaintext:PRODUCTCIPHERSnIntermediateText:nFGAGVDVFXADGXVnDGXFFGVGGAAGXGn带密钥的块变换矩阵：nDEUTSCHKeyn2376514SortedOrdernFGAGVDVnFXADGXVnDGXFFGVnGGAAGXGnCiphertext:DXGXFFDGGXGGVVVGVGFGCDFAAAXA851.encryptandthendecryptbyhand,thetextbelowusingablock(column)transpositionwithakeyofSNEAKY:2.thecatonlygrinnedwhenitsawaliceitlookedgoodnaturedshethoughtstillithadverylongclawsandagreatmanyteethsoshefeltthatitoughttobetreatedwithrespect练习练习86练习练习2.encryptandthendecryptbyhand,thetextbelowusingtheADFGVXcipherwithakeyofSNEAKY:toseevictoryonlywhenitiswithinthekenofthecommonherdisnottheacmeofexcellence875.密码机发展过程密码机发展过程n为了简化加密/解密过程，导致密码设备出现。nJefferson cylinder,1790s被研制成功，包含36个圆盘，每个圆盘有个随机字母表1920年还被美国军队使用。88nWheatstone disc,byWadsworthin1817,andWheatstonein1860s,comprisedtwoconcentricwheelstogenerateapolyalphabeticcipher。密码机发展过程密码机发展过程89n随着密码技术的提高，要求有更高级的密码装置，高级密码装置可以实现更复杂的密码，这些装置在二战时期广泛使用。例：theGermanEnigma,theSwedishHagelin(below)andtheJapanesePurple密码机发展过程密码机发展过程90THE END！9126、要使整个人生都过得舒适、愉快，这是不可能的，因为人类必须具备一种能应付逆境的态度。卢梭27、只有把抱怨环境的心情，化为上进的力量，才是成功的保证。罗曼罗兰28、知之者不如好之者，好之者不如乐之者。孔子29、勇猛、大胆和坚定的决心能够抵得上武器的精良。达芬奇30、意志是一个强壮的盲人，倚靠在明眼的跛子肩上。叔本华谢谢！谢谢！92