保障与安全密码学.ppt

2009-3-17,网络工程专业06级,1,第三章 密码学（2）,2009-3-17,网络工程专业06级,2,传统密码技术,一、数据表示方法数据的表示有多种形式，使用最多的是文字，还有图形、声音、图像等。这些信息在计算机系统中都是以某种编码的方式来存储的。传统加密方法的主要应用对象是对文字信息进行加密解密。古典加密技术两个基本组成部分：代替与变换 二、代替密码代替密码（Substitution Cipher）在代替密码中,用一组密文字母来代替一组明文字母以隐藏明文,但保持明文字母的位置不变。,2009-3-17,网络工程专业06级,3,传统密码技术,代替密码就是将明文字母表P中的每个字母用密文字母表C中的相应字母来代替这一类密码，包括移位密码、替换密码、仿射密码、乘数密码、多项式代替密码、密钥短语密码等。接收者对密文进行逆替换就恢复出明文来。在经典密码学中，有四种类型的代替密码。简单代替密码（Simple Substitution Cipher)Caesar 多名码代替密码 多字母代替密码 多表代替密码Vigenre。,2009-3-17,网络工程专业06级,4,传统密码技术,1单表代替密码 单表代替密码的一种典型方法是凯撒（Caesar）密码，又叫循环移位密码。它的加密方法就是把明文中所有字母都用它右边的第k个字母代替，并认为Z后边又是A。这种映射关系表示为如下函数：F(a)=(a+k)mod n其中：a表示明文字母；n为字符集中字母个数；k为密钥。,2009-3-17,网络工程专业06级,5,传统密码技术,映射表中，明文字母中在字母表中的相应位置数为如A=0，B=1，具体形式如下：设k3；对于明文PCOMPUTE SYSTEMS则f（C）=（2+3）mod 26=5=Ff（O）=（14+3）mod 26=17=Rf（M）=（12+3）mod 26=15=Pf（S）=（18+3）mod 26=21=V所以，密文C=Ek（P）=FRPSXRWHUVBVWHPV。,2009-3-17,网络工程专业06级,6,恺撒密码的特点,单字母密码（简单替换技术）简单，便于记忆令26个字母分别对应于025，a=0，b=1y=24，z=25。缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构。已知加密与解密算法C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)25个可能的密钥k,适用Brute-Force Cryptanalysis明文所用的语言是已知的，且其意义易于识别,2009-3-17,网络工程专业06级,7,Caesar Cipher,Caesar 密码的数学表示 设：A the value 0,B 1,C 2,.Y 24,Z 25;加密算法：Ek:i-i+k(mod 26)解密算法：Dk:i-i-k(mod 26),2009-3-17,网络工程专业06级,8,例1:plain:meet me after the toga partycipher:PHHW PH DIWHU WKH WRJD SDUWB1oggv og chvgt vjg vqic rctva2nffu nf bgufs uif uphb qbsuz3meet me after the toga party4ldds ld zesdq sgd snfz ozqsx56789qiix qi ejxiv xli xske tevxcBrute-force cryptanalysis is easily performed:simply try all the 25possible keys.作业1：用C编制上述程序,2009-3-17,网络工程专业06级,9,2多表代替密码,多表代替密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布，每个映射是简单代替密码中的一对一映射。维吉尼亚Vigenere 密码和博福特Beaufort 密码均是多表代替密码的例子。多表代替密码有多个单字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母等，所有密钥使用完后密钥又再循环使用。密钥k可以通过周期性地延长反复进行以至无穷。,2009-3-17,网络工程专业06级,10,Vigenere Cipher Table,The table lists the keycharacters ontop and theplaintextcharacters onthe side,2009-3-17,网络工程专业06级,11,这种加密的加密表是以字母表移位为基础把26个英文字母进行循环移位，排列在一起，形成2626的方阵。该方阵被称为维吉尼亚表。采用的算法为f（a）=（a+Bi）mod n（i=（1，2，n）即一个明文字母可表示为多个密文字母。：例如：明文为System，密钥为dog，加密过程如下：明文：S y s t e m密钥：d o g d o g密文：V my s在这个例子中，每三个字母中的第一、第二、第三个字母分别移动（mod 26）3个，14个和6个位置。,2009-3-17,网络工程专业06级,12,第四章 传统密码学,设密钥k=k1k2kn，明文M=m1m2mn，加密变换Ek(M)=c1c2cn。其中ci(mi+ki)mod 26，i=1,2n。优点：能抵抗简单的字母频率分析攻击。多表密码加密算法结果将使得对单表置换用的简单频率分析方法失效。,2009-3-17,网络工程专业06级,13,例 设密钥k=cipher，明文消息appliedcryptosystem，试用维吉尼亚密码对其进行加密，然后再进行解密。解：由密钥k=cipher，得n=6，密钥对应的数字序列为(2，8，15，7，4，17)。然后将明文按每6个字母进行分组，并转换这些明文字母为相应的数字，再用模26加上对应密钥数字，其加密过程如下表 解密使用相同的密钥，但用模26的减法代替模26加法,2009-3-17,网络工程专业06级,14,密钥为cipher的维吉尼亚密码加密过程 密文为：cxesmvfkgftkqanzxvo。作业2：用C编制上述程序,2009-3-17,网络工程专业06级,15,2009-3-17,网络工程专业06级,16,Operation,A keyword is selected and it is repeatedly written above the plaintextEXAMPLE:using the keyword“hold”,KEY,plaintext,Ciphertext,2009-3-17,网络工程专业06级,17,Select Vigenere from the Ciphers Menu,2009-3-17,网络工程专业06级,18,传统密码技术,3多名码代替密码（Homophonic Substitution）：它与简单代替密码相似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。例如，A可能对应于5、13、25 B可能对应于7、9、31、42当对字母的赋值个数与字母出现频率成比例时，安全性将有所提高。这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。1401年Duchy Mantua公司就开始使用多名码代替密码，比简单代替密码难破译，但仍不能掩盖明文语言的所有统计特性，用已知明文攻击，较容易破解，但用唯密文攻击要困难一些。,2009-3-17,网络工程专业06级,19,第四章 传统密码学,多字母或多码代替密码 不同于前面介绍的代替密码都是每次加密一个明文字母，多字母代替密码将明文字符划分为长度相同的消息单元，称为明文组，对字符块成组进行代替，这样一来使密码分析更加困难。多字母代替的优点是容易将字母的自然频度隐蔽或均匀化，从而有利于抗击统计分析。Playfair密码，Hill密码都是这一类型的密码,4 多字母代替密码-Playfair（英国一战期间曾用）,2009-3-17,网络工程专业06级,20,第四章 传统密码学,密钥由25个英文字母（J与I相同）组成的5阶方阵。每一对明文字母 m1和m2，都根据下面的6条规则进行加密。（1）明文字母 m1和m2同行。密文是其右边字母。（2）明文字母 m1和m2同列。密文是其下边字母。（3）明文字母 m1和m2不同行、不同列。密文是长方形的另两个顶点。（4）明文字母 m1和m2相同。在m1和m2之间加一个无效字母。（5）明文有奇数个字母，末尾加一个无效字母。（6）I、J看成是相同字母。,4 多字母或多码代替密码-Playfair（英国一战期间曾用）,2009-3-17,网络工程专业06级,21,4 多字母代替密码-Playfair,Playfair:将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。密钥是55变换矩阵:I与J视为同一字符C I P H ER A B D FG K L M NO Q S T UV W X Y Z加密规则:按成对字母加密 相同对中的字母加分隔符(如x)balloon ba lx lo on 同行取右边:he EC 同列取下边:dm MT 其他取交叉:kt MQ OD TR,2009-3-17,网络工程专业06级,22,Playfair举例,以前面的55变换矩阵(cipher)为例 C I P H ER A B D FG K L M NO Q S T UV W X Y Z(1)balloon ba lx lo on(2)book bo ok(3)fill fi lx lx,db sp gs ug,rs qg,ae sp sp,2009-3-17,网络工程专业06级,23,Playfair密码分析,Playfair有2626=676种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息,2009-3-17,网络工程专业06级,24,5.仿射密码（affine cipher）体制,仿射密码是代替密码的一个特例。在仿射密码中：加密函数形式为 要求唯一解的充要条件是gcd(a,26)=1 该体制描述为：设P=C=Z/(26)对 定义 ek(x)=ax+b(mod 26)和dk(y)=a-1(y-b)(mod 26),2009-3-17,网络工程专业06级,25,与26互素的数为1，3，5，7，9，11，15，17，19，21，23，25（12个）因此，模为26的仿射密码的密钥空间为1226=312在Z/(26)的情形下，与26互素的数的元的乘法逆为1-1=13-1=9(39=27=26+1)5-1=21(521=105=264+1)7-1=15(715=105=264+1)11-1=19(1119=209=268+1)17-1=23(1723=391=2615+1)25-1=25（625=2525=2624+1）,2009-3-17,网络工程专业06级,26,例子 设k（7，3），注意到7-1(mod 26)=15,加密函数是ek(x)=7x+3,相应的解密函数是dk(y)=15(y-3)=15y-19,易见 dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod 26)若加密明文：hot，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：作业3:编程实现上述加解密过程。,2009-3-17,网络工程专业06级,27,6 Hill密码（1929）,Hill cipher was developed by the mathematician Lester Hill in 1929.基于矩阵的线性变换:K是一个mm矩阵,在Z/(26)上可逆,即存在K-1使得:KK-1=I(在Z/(26)对每一个k K,定义ek(x)=xK(mod 26)和 dk(y)=yK-1(mod 26)注：明文与密文都是 m元的向量（x1,x2,xm);(y1,y2,ym)，,2009-3-17,网络工程专业06级,28,定理 设K=(k i,j)为一个定义在zn上的mm矩阵。若K在zn上可逆，则有K-1=(detK)-1 k*，这里k*为K矩阵的伴随矩阵。推论 设矩阵为一个定义在zn上的矩阵。,2009-3-17,网络工程专业06级,29,Hill密码的例子-i,例子：当 m=2时，明文元素x=(x1,x2),密文元素y=(y1,y2)K=若对明文july加密，它分成2个元素（j,u),(l,y),分别对应于（9,20）,（11,24）,有（9,20）(mod 26)=(9960,72140）(mod 26)=（3,4）且（11,24）(12172,88168)（11,22）于是对 july加密的结果为DELW。,(y1,y2)=(x1,x2),K,2009-3-17,网络工程专业06级,30,这是因为=mod26=,Detk=53mod26=11-1=1,2009-3-17,网络工程专业06级,31,Hill密码的例子-ii,为了解密，计算 且 因此，得到了正确的明文“july”,2009-3-17,网络工程专业06级,32,Hill密码分析,完全隐藏了字符(对)的频率信息线性变换的安全性很脆弱，易被已知明文攻击击破。对于一个m m的hill密码，假定有m个明文-密文对，明文和密文的长度都是m.可以把明文和密文对记为：Pj=(p1j,p2j,.pmj)和Cj=(C1j,C2j,Cmj),对任意,1j m 定义m m的方阵X=（Pij)Y=(Cij),得到Y=XK，K=X-1Y例子：friday PQCFKU(5 17)K=(15 16)(8 3)K=(2 5)(0 24)K=(10 20),2009-3-17,网络工程专业06级,33,这个结果可对第三个明文对进行验证,2009-3-17,网络工程专业06级,34,练习假设明文worker利用n=2的Hill密码加密，得到密文qihryb，求密钥K。解：将明文、密文划分为三组：明文（w,o）、（r,k）、（e,r）（22,14）、(17,10)、(4,17)密文（q,i）、（h,r）、（y,b）（16,8）、(7,17)、(24,1)作业4 通过编程求出密钥,对Hill密码的已知明文分析,2009-3-17,网络工程专业06级,35,练习假设明文worker利用n=2的Hill密码加密，得到密文qihryb，求密钥K。解：利用前两个明文密文对，构造矩阵方程：计算明文方阵行列式，由于（18,26）1，即该矩阵没有逆元，于是考虑第二、第三组明文密文对，得到矩阵方程：,对Hill密码的已知明文分析,2009-3-17,网络工程专业06级,36,249mod26=15，15-1=7显然，通过对比第一个明文密文对很容易验证该密钥。如果密码分析者不知道加密分组长度l的值，那么可以通过逐一尝试不同的l值来得到密钥。Hill密码体制的重要性在于它无可辩驳地表明数学方法在密码学中的地位是不容置疑的。,对Hill密码的已知明文分析,2009-3-17,网络工程专业06级,37,显然，通过对比第一个明文密文对很容易验证该密钥。如果密码分析者不知道加密分组长度l的值，那么可以通过逐一尝试不同的l值来得到密钥。Hill密码体制的重要性在于它无可辩驳地表明数学方法在密码学中的地位是不容置疑的。,对Hill密码的已知明文分析,2009-3-17,网络工程专业06级,38,Hill Process,Each character is assigned a numerical value a=0,b=1,.,z=25for m=3 the transformation of p1p2p3 to c1c2c3 is given by 3 equations:,c1=(k11p1+k12p2+k13p3)mod 26 c2=(k21p1+k22p2+k23p3)mod 26c3=(k31p1+k32p2+k33p3)mod 26,2009-3-17,网络工程专业06级,39,Hill Matrix,The Hill cipher is really a matrix multiplication systemThe enciphering key is an n x n matrix,MThe deciphering key is M-1For example,if n=3 one possible key is:,Encrypt n o w,13 14 22,2009-3-17,网络工程专业06级,40,First,enter the group size which is the same as the matrix size,2009-3-17,网络工程专业06级,41,转轮机,上个世纪20年代，出现了转轮密码，而由德国发明家亚瑟谢尔比乌斯发明的Enigma 密码机最为著名。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路（在下图中显示了6条），把键盘的信号对应到显示器不同的小灯上去。在图中可以看到，如果按下a键，那么灯B就会亮，这意味着a被加密成了B。同样地我们看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于是如果我们在键盘上依次键入cafe（咖啡），显示器上就会依次显示DBCE，这是最简单的加密方法之一简单代替密码。,2009-3-17,网络工程专业06级,42,转轮机,2009-3-17,网络工程专业06级,43,转轮机,不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。右图表示了连续键入3个b的情况。,2009-3-17,网络工程专业06级,44,转轮机,当第一次键入b时，信号通过转子中的连线，灯A亮起来，放开键后，转子转动一格，各字母所对应的密码就改变了；第二次键入b时，它所对应的字母就变成了C；同样地，第三次键入b时，灯E闪亮。为使机器更安全，可以把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。,2009-3-17,网络工程专业06级,45,转轮机,德国人为了战时使用，大大加强了其基本设计，军用的Enigma由3个转轮，从5个转轮中选取。转轮机中还有一块稍微改名明文序列的插板，有一个反射器导致每个转轮对每一个明文字母操作两次，结构如图所示。,2009-3-17,网络工程专业06级,46,转轮机,于是转子自身的初始方向，转子之间的相互位置，以及连接板连线的状况就组成了所有可能的密钥：三个转子不同的方向组成了26*26*26=17576种不同可能性；三个转子间不同的相对位置为6种可能性；连接板上两两交换6对字母的可能性数目非常巨大，有种；于是一共有，大约为，即一亿亿种可能性。但如此复杂的密码机在第二次世界大战中被破解了，首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。,2009-3-17,网络工程专业06级,47,一次一密乱码本,如上所述的所有密码算法均被破解，那么是否存在无法破解的理想加密方案呢？香农证明了一种密码属于这种情况，它就是一次一密乱码本（one-time pad）。一般说来，一次一密乱码本就是一个大的不重复的真随机密钥字母集，发送者用乱码本中的每一个密钥准确地加密一个明文字符，加密是明文字符和密钥字符进行模26加法。比如：明文：onetimepad密钥：TBFRGFARFM密文：IPKLPSFHGQ因为：O+Tmod26=I，N+Bmod26=P，E+Fmod26=K，如果窃听者不能得到用来加密的一次一密乱码本，这个方案就是完全保密的。给出的密文消息相当于同样长度的任何可能的明文消息。,2009-3-17,网络工程专业06级,48,代替密码的特点,单字母代替密码（Monoalphabetic Cipher)：明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。多码代替密码：没有隐藏明文中不同字母的统计特性，但安全性有所提高。多字母代替密码：字符块被成组加密，有利于抗击统计分析。多表代替密码：有多个映射表，可隐藏单字母出现的频率分布。,2009-3-17,网络工程专业06级,49,传统密码技术,三、换位密码 置换密码(Permutation Cipher)又称换位密码（Transposition Cipher)，加密过程中明文的字母保持相同，但顺序被打乱了。由于密文字符与明文字符相同，密文中字母的出现频率与明文中字母的出现频率相同，密码分析者可以很容易地由此进行判别。虽然许多现代密码也使用换位但由于它对存储要求很大，有时还要求消息为某个特定的长度，因而比较少用。,2009-3-17,网络工程专业06级,50,传统密码技术,换位密码是采用移位法进行加密的。它把明文中的字母重新排列，本身不变，但位置变了。如：把明文中的字母的顺序倒过来写，然后以固定长度的字母组发送或记录。明文：computer systems密文：sm etsy sretupmoc,2009-3-17,网络工程专业06级,51,传统密码技术,密文则以下面的形式读出：WOFHOHURIKACOSXTAMBXYNTOX 这里的密钥是数字5。,（l）列换位法将明文字符分割成为五个一列的分组并按一组后面跟着另一组的形式排好。如明文是：WHAT YOU CAN FROM THIS BOOK分组排列为：,2009-3-17,网络工程专业06级,52,传统密码技术,（2）矩阵换位法 这种加密是把明文中的字母按给定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵的字母来产生密文。如将明文ENGINEERING按行排在3*4矩阵中，如下所示：,给定一个置换：,2009-3-17,网络工程专业06级,53,传统密码技术,现在根据给定的置换，按第2列，第4列，第1列，第3列的次序排列，就得得到密文：NIEGERNEN IG在这个加密方案中，密钥就是矩阵的行数m和列数n，即m*n3*4，以及给定的置换矩阵。也就是：k=（m*n，f）,2009-3-17,网络工程专业06级,54,传统密码技术,其解密过程是将密文根据3*4矩阵，按行、列的顺序写出，再根据给定置换产生新的矩阵，恢复明文为：ENGINEERING,2009-3-17,网络工程专业06级,55,数据加密,对加密算法要求要达到以下几点：（1）必须提供高度的安全性；（2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又便于理解和掌握；（3）安全性应不依赖于算法的保密，其加密的安全性仅以加密密钥的保密为基础；（4）必须适用于不同的用户和不同的场合；（5）实现算法的电子器件必须很经济、运行有效；（6）必须能够验证，允许出口。,2009-3-17,网络工程专业06级,56,古典密码小结,Substitution&permutation密码分析多轮加密数据安全基于算法的保密,2009-3-17,网络工程专业06级,57,参考资料,Ron Rivest,Computer and Network Security Lecture series http:/段素娟 王文钦等 计算机安全与保密技术Menezes,Van Oorschot,Vanstone,Handbook of Applied CryptographyWilliam Stallings Cryptography and Network Security,2009-3-17,网络工程专业06级,58,作业5 设有如下密文串：JBCRCLQRWCRVNBJENBWRWN依次实验所有可能的解密密钥d0,d25可以得出有意义的明文。求出相应的密钥及明文串。（编程实现）,