第三章 古典密码1

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,密码学的起源和发展,三个阶段：,1949,年之前,密码学是一门艺术,1949,1975,年,密码学成为科学,1976,年以后,密码学的新方向,公钥密码学,第三章 古典密码,密码学的起源,隐写,术,(,steganography,):,通过隐藏消息的,存在,来保护消息,.,隐形墨水,字符格式的变化,图象图像,(,象形文字的修改,)Modified Hieroglyphics,c.1900 B.C.,密码学的第一个例子是对标准书写符号的修改,例如,:,古埃及法老坟墓上的文字,思想,:,代替,(substitution),example-i,Spartan,Scytale,c.500 B.C.,斯巴达人用于加解密的一种军事设备,发送者把一条羊皮螺旋形地缠在一个圆柱形棒上,思想：置换,（,permutation),example-ii,Polybius,Checkerboard,205123 B.C.,明文,:POLYBIUS,密文,:3534315412244543,1,2,3,4,5,1,A,B,C,D,E,2,F,G,H,IJ,K,3,L,M,N,O,P,4,Q,R,S,T,U,5,V,W,X,Y,Z,example-iii,Caesar Cipher,c.50 B.C.,A B C D E F G X Y Z,D E F G H I J A B C,明文,:Caesar cipher is a shift substitution,密文,:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQ,example-,iV,Nomenclator,代码本,c.1400,字母、符号、单词、短语 代码,代码 字母、符号、单词、短语,应用：,World War II,Example-V,Example Cont,网格加密法：中国,例：密文：,王先生：,来信收悉，你的盛情难以报答。我已在昨天抵,达广州。秋雨连绵，每天需备伞一把。大约本月,中旬即可返回，再谈。,弟：李明,2001,年,11,月,7,日,网格加密法：中国,例：密文：,王先生：,来信收悉，你的盛情难以报答。我已在昨天抵,达广州。秋雨连绵，每天需备伞一把。大约本月,中旬即可返回，再谈。,弟：李明,2001,年,11,月,7,日,明文：情报在雨伞把中。,兽栏,法：,明文：,System,密文：,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:,:.,：,：,：,：,.,密文字母表：,1949,年之前,:,古典密码（,classical cryptography),密码学还不是科学,而是艺术,出现一些密码算法和加密设备,密码算法的基本手段,(substitution&permutation),出现,，针对的是字符,简单的密码分析手段出现,密码学的起源和发展,-ii,1949,1975,年,:,计算机使得基于复杂计算的密码成为可能,1949,年,Shannon,的,“,The Communication Theory of Secret Systems,”,1967,年,David Kahn,的,The,Codebreakers,1971-73,年,IBM Watson,实验室,的,Horst,Feistel,等的几篇技术报告,Smith,J.L.,The Design of Lucifer,A Cryptographic Device for Data Communication,1971,Smith,J.L.,An,Expremental,Application of,Cryptogrphy,to a remotely Accessed Data System,Aug.1972,Feistel,H.,Cryptography,and Computer Privacy,May 1973,数据的安全基于密钥而不是算法的保密,密码学的起源和发展,-iii,1976,年以后,:,1976,年,Diffie,&,Hellman,的,“,New Directions in Cryptography,”,提出了不对称密钥密码,1977年,Rivest,Shamir,&,Adleman,提出了,RSA,公钥算法,90,年代逐步出现椭圆曲线等其他公钥算法,公钥密码使得发送端和接收端无密钥传输的保密通信成为可能,！,密码学的起源和发展,-iv,1976,年以后,:,对称密钥密码算法进一步发展,1977年,DES,正式成为标准,80年代出现,“,过渡性,”,的,“,post DES,”,算法,如,IDEA,RCx,CAST,等,90,年代对称密钥密码进一步成熟,Rijndael,RC6,MARS,Twofish,Serpent,等出现,2001年,Rijndael,成为,DES,的替代者,密码学的起源和发展,-v,HILL,2,密码的加密与解密,明文分组,(,两个一组,),，,按组转换成密文,同一字母在不同组中所对应密码不同,假设要加密的明文是由,26,个字母所构成,将每个明文字母与,0 25,的一个数字建立,1,1,对应关系，称为明文字母的,表值,字母,A B C D E F G H I J K L M,表值,1 2 3 4 5 6 7 8 9 10 11 12 13,字母,N O P Q R S T U V W X Y Z,表值,14 15 16 17 18 19 20 21 22 23 24 25 0,将明文字母依次按每两个字母一组查出其表,值，得到一组二维向量,通过加密矩阵得到,，,而,查向量,i,的字母表值，即得到密文,利用加密矩阵的逆矩阵，由密文得到明文,选择一个加密矩阵,A ,二阶正整数值的矩阵,.,例如,关于模运算（,mon26,）,模,m,等价,设,a,b,为两个整数,若,称,a,模,m,等价于,b,，,记作,剩余集,称,为模,m,的剩余集,运算律,设,a,b,为两个整数，,模,m,倒数,设,，,若存在,使得,，称,a,有模,m,倒数,记作,命 题,整数,a,有模,m,倒数的充要条件为,a,与,m,无公共素因子,模,26,倒数表,25,17,5,11,23,7,19,3,15,21,9,1,25,23,21,19,17,15,11,9,7,5,3,1,a,1,(mod26),a,怎样求模,m,倒数,即解,方程,定义,Euler,函数：,设,m,为一自然数，,Z,m,中与,m,互素的数的个数称为,m,的,Euler,函数，记为,(,m,),Euler,定理,对任意整数,k,m,若,k,m,互素，则,故所求,x,为,矩阵模,m,可逆,设,为,n,阶方阵，,若存在,使得,，称,B,为,A,的模,m,逆矩,阵，记作,命 题,矩阵,A,模,m,可逆,|,A,|,与,m,无公共素,因子,模,m,逆矩阵,例 子,一个简单实例,明 文,：,Our marshal was shot,分 组,：,ou,rm,ar,sh,al,wa,ss,ho,tt,补充哑字母,对应向量,加 密,：,左乘加密矩阵,直接结果,密文向量,密 文,ek,rm,kb ix,yj,yc,ee,ls,hh,解 密,只要将解密矩阵,左乘密文向量即可求得明文向,量，从而查出明文,结 论,使用,Hill,密码时的加密矩阵应该模,26,可逆,使用,Mathematica,In1:=,a=,1,2,0,3;,MatrixForm,a,Out1/MatrixForm=,In2:=,deta,=Mod,Det,a,26,Out2=,3,In3:=,inva,=Inversea;,MatrixForm,inva,Out3/MatrixForm=,In4:=,adja,=,deta,inva,Out4/MatrixForm=,In5:,=,ideta,=9,Out5=,9,In6:=,inva1=Mod,ideta,adja,26;MatrixForminva1,Out6/MatrixForm=,In7:,=b=5,18,11,9,25,25,5,12,8,11,13,2,24,10,3,5,19,8;,c=Modinva1.b,26;,MatrixForm,c,Out7/MatrixForm=,HILL,2,密码的破译,关键是求得加密矩阵的逆,解密矩阵,只要分析出两个明文向量（线性无关）与,相应的密文向量,若有,甲方截获了一段密文：,OJWPISWAZUXAU,一个破译例子,UISEABA,UCRS,IPLBHAAMMLPJJOTENH,经分析这段密文是用,HILL,2,密码编译的，且,这段,密文的字母,UCRS,依次代表了字母,TACO,，,若,明文字母的表值如前，试破译这密文的内容？,关 系,其中,其中,计算,A,1,(mod26),破 译,密文向量,明文向量,明文：,Clinton is going to visit a country in Middle East,假设破译者,Oscar,是在已知密码体制的前提下来破译,Bob,使用的密钥。这个假设称为,Kerckhoff,原则。最常见的破解类型如下：,1.,唯密文攻击：,Oscar,具有密文串,y.,2.,已知明文攻击,:Oscar,具有明文串,x,和相应的密文,y.,3.,选择明文攻击：,Oscar,可获得对加密机的暂时访问，因此他能选择明文串,x,并构造出相应的密文串,y,。,4.,选择密文攻击,:Oscar,可暂时接近密码机,可选择密文串,y,，,并构造出相应的明文,x.,这一切的目的在于破译出密钥或密文,密码分析,密码破译的原则,:,遵循观察与经验,方法,:,采用归纳与演绎,步骤,:,分析、假设、推测和证实,三大要素：,语言的频率特征：,e,连接特征,:q u,I e x,重复特征,:,th,tion,tious,密码破译,密码分析（,Cryptanalysis of Caesar ciphers,）,Caesar Cipher:,只有,26,种可能（,only have 26 possible ciphers,）,A maps to A,B,.Z,可以简单的实验每个密钥（穷密钥搜索）,给定一些密文，实验每个密钥。,LIZHZLVKWRUHSODFHOHWWHUV Original,ciphertext,KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3*plaintext HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 GDUCUGQFRMPCNJYACJCRRCPQ try shift of 5.MJAIAMWLXSVITPEGIPIXXIVW try shift of 25,eg,.break,ciphertext,GCUA VQ DTGCM,语言冗余度与密码分析,人类语言是有冗余度的,字母使用的频率是不相同的,在英语中，,e,的使用率是最高的,其次，,T,R,N,I,O,A,S,其它字母使用的较低,英语字母使用频率,字母频率在密码分析中的应用,计算密文中字母出现的频率,与已知字母分布比较,单码替换不改变相对字母出现的频率,阿拉伯科学家提出此方法,英语字母中常见的组合,打乱的密码代换,不仅仅是简单的移位变换,每个字母可以避免随意变换到其它不重复的字母,每个字母变换到不同的字母,密钥长度是,26,个字母,eg,.,Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZ,Cipher:DKVQFIBJWPESCXHTMYAUOLRGZN,Plaintext:IFWEWISHTOREPLACELETTERS,Ciphertext,:WIRFR