---密码学基础(古典密码-素材).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,网络与信息安全,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,古典密码算法,2015-6-9,1,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语密码,仿,射密码,攻击方法,小结,2,当今的信息网络蕴含了,表现,为信息形式的多种巨大,利益,政治的、军事的、经济的、商业的,通过网络非法获取和利用信息可能,随时发生,互联网的开放性是根源,网络安全已成为网络设计、建设和维护的重要内容,密码学,/,密码算法成为保护网络信息的,利器,以数学为工具，将信息明文变换为密文,成为保护信息的核心屏障,网络与密码算法,3,密码学的目的,合法通信双方,Alice,和,Bob,在不安全的信道上进行,安全,通信，而破译者,Oscar,不能理解他们通信的内容,“,安全,”指,机密性、完整性、鉴别、不可抵赖,简单加密系统模型,简单加密系统模型,密码系统,4,密码系统,包含带参数,K,的变换,E,K,(,),、带参数,K,的逆变换,D,K,(,),、信息传送信道、密钥传送信道,变换,E,K,得将明文消息,P,变换为密文,C,，这个过程称为加密,E,为加密算法，,K,为密钥。,E,不同或,K,不同，密文,C,就不同,典型的密码系统,密码系统,小游戏,角色,1,如何给你的朋友发一封由你自己加密的电子邮件？,角色,2,如何解密你朋友给你发来的加密邮件？,5,对密码算法的基本要求,加密能力强,当密文或明文密文对被截获时，破解密钥或明文在计算上是不可行的,安全性不依赖于密码算法本身的保密，而依赖于密钥,易于实现，使用方便,对密码算法的基本要求,6,古典密码（,Classical Cryptography,）,密码算法针对的基本操作对象是字符,/,字母,方法,字符,代换,（,Substitution,）或字符,置换,（,Permutation,）,1949,年之前,此类密码学还不是科学，而是艺术,产生了一些密码算法和加密设备,也出现简单的密码分析手段,古典密码,7,古典密码分类,代换,Substitution,置换,Transposition,单表代换,Monoalphabetic,多表代换,Polyalphabetic,单字符,单表代换,多字符,单表代换,移位密码,单表密码,短语单表密码,Playfair,密码,Beaufort,密码,Vigenre,密码,行变换密码,栅格密码,Hill,密码,仿射密码,Autokey,密码,转子机,凯撒密码,一次性密码,8,代换与置换,代换,密码算法,（,Substitution Cipher,）,将明文中的每一个字符均被替换成另一个字符（密文字符）。接收者对密文做反向替换就可以恢复出明文,置换,密码算法,（,Permutation Cipher,）,又称换位密码算法（,Transposition Cipher,）：改变明文中各个字母的位置次序，但明文字母（的出现及出现次数）保持不变,9,代替密码,单表密码算法,（,Monoalphabetic Cipher),密码表仅,1,个,固定,任何明文加密、密文解密均使用同一个密码表加密,明文中相同的字母必然被加密成相同的密文字母,10,代替密码,多表密码算法,（,Polyalphabetic Cipher),密码表,多个,不固定,一条明文加密和解密同时使用多个密码表,明文中两个相同的字母可能被加密成不同的密文字母,11,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语密码,仿射密码,攻击方法,小结,12,凯撒密码,恺撒密码,（,Caesar Cipher,）,Julius Caesar,发明，是已知最早的代换密码,明文字母用,其后的第三个,字母代替，作为其密文字母，即，将明文字母表,循环左移三位,作为密码表,13,两个字母表,明文字母表,P,p,0,p,1,p,25,密文字母表,C,C,0,C,1,C,25,基本型凯撒密码等于如下变换,明文字母表,密文字母表,明文表和密文表共同构成,密钥,加密,解密,凯撒密码,14,让每个字母对应一个数值,则,基本型凯撒,密码可以表示为,加密：,C,i,=E(p,i,)=(p,i,+3)mod 26,解密：,p,i,=D(C,i,)=(C,i,3,)mod 26,密钥数量：,1,凯撒密码,15,凯撒密码,凯撒密码,实例,明文：,meet me after the party,密文：,PHHW PH DIWHU WKH SDUWB,16,凯撒密码,特点,极为简单,密钥数为,1,，极其脆弱,17,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语密码,仿射密码,攻击方法,小结,18,移位,密码,（,Shift Cipher,）,明文字母用,其后的第,k,个,字母代替，作为其密文字母，即，将明文字母表,循环左移,k,位,作为密码表,明文字母用,任一个,密文字母代替，即，,明文字母表的任一个,排列,均构成一个对应的密码表,加密：,C,i,=E(p,i,)=(p,i,+k)mod 26,解密：,p,i,=D(C,i,)=(C,i,k)mod 26,移位密码,19,移位密码,移位密码,20,例如，,k=5,明文字母表：,密文字母表：,密钥,数量,：,25,明文,密文,移位密码,21,特点,非常简单,密钥数为,25,，仍非常脆弱,移位密码,22,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语密码,仿射密码,攻击方法,小结,23,单表,密码（,Monoalphabetic Cipher,）,明文字母用,任一个,密文字母代替，即，,明文字母表的任一个,全,排列,均构成一个对应的密码表,加密：,C,i,=E(p,i,)=(p,i,+k,i,)mod 26,解密：,p,i,=D(C,i,)=(C,i,k,i,)mod 26,当,p,i,p,j,有,C,i,C,j,k,i,k,j,=0,1,2,25,例,：,明文,字母表,：,密文,字母表,：,k,i,:,13 17 21 24,单表密码,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,N,S,X,C,H,M,R,W,B,G,L,Q,V,A,F,K,P,U,Z,E,J,O,T,Y,D,I,24,密钥,数量,：,26,!,=403,291,461,126,605,635,584,000,000,410,26,=400,亿亿亿,特点,密钥数极大，安全性好,密钥无规律，使用不便,单表密码,25,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语,密码,仿射密码,攻击方法,小结,26,短语密码,短语,密码,（,Keyword Cipher,）,是,单表,密码的一种实用形式,引入一个,关键词,（短语）来构造明文字母表的一个,排列,，从而构成对应的密码表,密码表构造方法,1,指定一个关键词（词组、句子,）,去除关键词中的重复字母和空格，前置于密码表,将剩余的字母依次按序后置于密码表,密钥,数量：,26!,（,410,26,=400,亿亿亿,）,27,实例,关键词：,GUANG ZHOU BAI YUN SHAN,去重前置：,GUANZHOBIYS,剩余后置：,TVWXCDEFJKLMPQR,明文字母表,：,密文字母表,：,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,G,U,A,N,Z,H,O,B,I,Y,S,T,V,W,X,C,D,E,F,J,K,L,M,P,Q,R,短语密码,28,短语,密码,密码表构造方法,2,指定一个关键词，去重复、空格，按行排阵,将剩余的字母依次继续,按行排,阵,阵的各列构成密码表,例：,关键词,=,COLLEGE,阵：,明文字母表,密文,字母表,短语密码,29,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语密码,仿射密码,攻击方法,小结,30,仿射密码,仿射密码,（,Affine Cipher,）,用仿射变换构造密码表（,密码,表便于记忆）,密码表,两个,字母表,明文字母表,P,p,0,p,1,p,n-1,密文字母表,C,C,0,C,1,C,n-1,引入,两个,参数,、,，使明文字母,P,用字母,aP+b,代替，作为其密文字母,加密：,C,i,=E(p,i,)=(,p,i,+,)mod n,解密：,p,i,=D(C,i,)=,1,(C,i,)mod n,31,仿射密码,实例,取,参数,=5,=8,明文,=AFFINECIPHER,密文,=IHHWVCSWFRCP,明文,A,F,F,I,N,E,C,I,P,H,E,R,p,i,0,5,5,8,13,4,2,8,15,7,4,17,(5p,i,+8),8,33,33,48,73,28,18,48,83,43,28,93,(5p,i,+8)mod 26,8,7,7,22,21,2,18,22,5,17,2,15,C,i,I,H,H,W,V,C,S,W,F,R,C,P,32,仿射密码,提示,仿射加密函数,要求,和,n,互素,，,即,gcd(,n)=1,，否则，,(,p,i,+,)mod,n,就,不是一个单射,函数,当,=1,、,=,3,时,，仿,射密码就是著名的,凯撒,密码,在解密时,，,需求解,在有限域,Z,n,上,的,乘法,逆元,1,Z,n,，这,可由扩展欧几里得算法,求解,Z,26,上所有与,26,互素的元素,的乘法,逆元：,33,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语密码,仿射密码,攻击方法,小结,34,对,单表代换,密码的攻击,两种典型的攻击,直接攻击文本,方法,频度分析,直接攻击密钥,方法,暴力破解（穷举破解）,两种攻击,联合使用,或,单独使用,可一举破解单表代换密码,35,直接攻击文本,频度分析,9,世纪阿尔,-,金迪,:,关于破译加密信息的手稿,西文语言的独到特征,文章中字母的出现频度有统计规律：元音字母频度高,对,单表代换,密码的攻击,36,频度分析的步骤,统计密码字母的频度,排序,按照已知频度分布替换密文字母,对,单表代换,密码的攻击,37,密文,频度分析,h:,可能是,e,a,i,o,尝试,h,e,d,a,l,i,r,o,结果,密文,:,明文,:,频度分析,攻击,：实例,38,直接攻击,密钥,暴力破解,前提,已知采用的是,代换,密码,暴力破解的要点,尝试所有可能的密码表,（,移位,密码：最多仅需尝试,25,次）,暴力破解的步骤,选择一个密码表,作逆代换,检查,逆,代换后的文本是否有意义，有则结束，否则换另一个密码表，进入步骤,2,对,单表代换,密码的攻击,39,实例,密文,明文,对,单表代换,密码的攻击,40,本质,选取字母表的一个,全排列,作为对称,密钥,密钥数量,26!,（,410,26,）,单表代换,密码,：小结,41,提 纲,概述,单表代换算法,单符号代换算法,凯撒密码,移位密码,单表密码,短语密码,仿射密码,攻击方法,小结,42,特征,代换固定,明文字符的代换字符固定,位置相同,密文字符与明文字符的位置相同,优点,简单,得到密文所需的计算量小,缺点,继承,密文继承了明文的统计特性（频率,）,跟随,明文字符的跟随关系反映在密文中,单字符,代换算法：小结,43,存在多种不同的破解途径,攻击密文,频度分析,攻击密钥,穷举密钥,改进思路：多角度同时抵御,针对,频度分析,使频度呈现,“,均匀分布,”,针对穷举密钥,增大密钥空间,如何做到？,代换密码算法：如何改进？,44,如何解密用短语代换密码的密文？,如何代换密码加密中文？,对于本次给出的四种代换密码，指出它们是沿着什么思路改进的？,进阶问题,45,生成,26,个字母表的一个全排列，画出计算机程序的流程图。,生成短语代换密码的一个密码表，画出计算机程序的流程图。,画出用短语代换密码加密明文和解密密文的计算机程序流程图。,选取一个代换密码，利用邮件、微博或微信与你的朋友进行一次秘密通信。,请一位第三方同学尝试破解密文，根据破解结果评价你选取的代换密码。,调换角色，重做。,课后作业,46,单字母密码,单表代换密码,移位（,shift,）密码、乘数（,multiplicative),密码,仿射（,affine),密码、多项式（,Polynomial),密码,密钥短语（,Key Word),密码,多表代换密码,维吉尼亚（,Vigenere),密码,博福特（,Beaufort,）密码,滚动密钥,(running-key),密码,弗纳姆,(Vernam),密码,转子机,(rotor machine),47,