山东轻工业学院 信息安全与保密课件.ppt
密密 码码 学学经典经典密码密码一、经典密码经典密码 虽然用近代密码学的观点来看，许多虽然用近代密码学的观点来看，许多经典密码是很不安全的，或者说是极易破经典密码是很不安全的，或者说是极易破译的。译的。但是我们不能忘记经典密码在历史但是我们不能忘记经典密码在历史上发挥的巨大作用上发挥的巨大作用。另外，另外，编制经典密码的基本方法对于编制经典密码的基本方法对于编制近代密码仍然有效。编制近代密码仍然有效。一、经典密码经典密码经典密码编码方法：经典密码编码方法：l置换，代换，代数置换，代换，代数1、置换密码、置换密码把明文中的字母重新排列，字母本身不变，把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置但其位置改变了，这样编成的密码称为置换密码。换密码。(1)最最简简单单的的置置换换密密码码是是把把明明文文中中的的字字母母顺顺序序倒倒过过来来，然后截成固定长度的字母组作为密文。然后截成固定长度的字母组作为密文。明文：明晨明晨5点点发动反攻。反攻。MING CHEN WU DIAN FA DONG FAN GONG密文：GNOGN AFGNO DAFNA IDUWN EHCGN IM一、经典密码经典密码例如：例如：明文：明文：MING CHEN WU DIAN FA DONG FAN GONGMING CHEN WU DIAN FA DONG FAN GONG矩阵：矩阵：MINGCH MINGCH 选出顺序：选出顺序：按列按列按列按列 ENWUDIENWUDI ANFADO ANFADO 改变矩阵大小和取出序列改变矩阵大小和取出序列 NGFANG 可得到不同的密码可得到不同的密码 ONGONG密文：密文：MEANO INNGN NWFFG GUAAC DDNHI OGMEANO INNGN NWFFG GUAAC DDNHI OG(2)把明文按某一顺序排成一个矩阵，把明文按某一顺序排成一个矩阵，然后然后按另一顺序选出矩阵中的字母以形成密文，按另一顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。最后截成固定长度的字母组作为密文。一、经典密码经典密码理论上：理论上：、置换密码的加密钥是置换矩阵置换密码的加密钥是置换矩阵 p，解密钥是置换矩阵解密钥是置换矩阵 p-1。、置换密码经不起已知明文攻击。置换密码经不起已知明文攻击。1 2 3 n1 2 3 n a a1 1 a a2 2 a a3 3 a an nP=P=一、经典密码经典密码2、代换密码、代换密码 首首先先构构造造一一个个或或多多个个密密文文字字母母表表，然然后后用用密密文文字字母母表表中中的的字字母母或或字字母母组组来来代代换换明明文文字字母母或或字字母母组组，各各字字母母或或字字母母组组的的相相对对位位置置不不变变，但但其其本本身身改改变变了了。这这样样编编成成的的密密码码称称为为代代换换密密码。码。单表代换密码单表代换密码 多表代换密码多表代换密码一、经典密码经典密码单表代换密码单表代换密码 只只使使用用一一个个密密文文字字母母表表，并并且且用用密密文文字字母母表表中中的的一一个字母来代换明文字母表中的一个字母。个字母来代换明文字母表中的一个字母。明文字母表：明文字母表：A a a0 0,a,a1 1,.,a,.,an-1n-1 密文字母表：密文字母表：B B b b0 0,b,b1 1,.,b,.,bn-1n-1 定义一个由定义一个由A A到到 B B的映射：的映射：f:ABf:AB f(f(a ai i)=b)=bi i 设明文：设明文：M=M=（m m0 0,m,m1 1,.,m,.,mn-1n-1 ）,则密文：则密文：C=(f(mC=(f(m0 0),f(m),f(m1 1),.,f(m),.,f(mn-1n-1)。简单代换密码的密钥就是简单代换密码的密钥就是映射函数映射函数f f或或密文字母表密文字母表 B。一、经典密码经典密码单表代换密码单表代换密码、加法密码加法密码A A和和B B是有是有 n个字母的字母表。个字母的字母表。定义一个由定义一个由A A到到B B的映射：的映射：f:ABf:AB f(af(ai i)=b)=bi i=a aj j j=i+k mod nj=i+k mod n加法密码是用明文字母在字母表中后面第加法密码是用明文字母在字母表中后面第 k k个字母来代换。个字母来代换。K=3 K=3 时是著名的凯撒密码。时是著名的凯撒密码。一、经典密码经典密码单表代换密码单表代换密码、乘法密码乘法密码A A和和B B是有是有n个字母的字母表。个字母的字母表。定义一个由定义一个由A A到到B B的映射：的映射：f:ABf:AB f(af(ai i)=b)=bi i=a aj j j=j=ikik mod n mod n 其中，其中，(n,k)=1n,k)=1。注意：注意：只有只有(n,k)=1n,k)=1，才能正确解密。才能正确解密。一、经典密码经典密码单表代换密码单表代换密码密钥词组代换密码：密钥词组代换密码：随机选一个词语，去掉其中的重复字母，随机选一个词语，去掉其中的重复字母，写到矩阵的第一行，从明文字母表中去掉这第写到矩阵的第一行，从明文字母表中去掉这第一行的字母，其余字母顺序写入矩阵。然后按一行的字母，其余字母顺序写入矩阵。然后按列取出字母构成密文字母表。列取出字母构成密文字母表。一、经典密码经典密码举例：举例：密钥：密钥：HONG YE 矩阵：矩阵：HONGYE 选出顺序：选出顺序：按列按列 ABCDFI JKLMPQ 改变密钥、矩阵大小改变密钥、矩阵大小 RSTUVW 和取出序列，得到不同的和取出序列，得到不同的 XZ 密文字母表。密文字母表。密文字母表密文字母表:B=HAJRXOBKSZNCLTGDMUYFPVEIQW 一、经典密码经典密码、多表代换密码多表代换密码单表代换密码的安全性不高，一个原因是单表代换密码的安全性不高，一个原因是一个明文字母只由一个密文字母代换。一个明文字母只由一个密文字母代换。构造多个密文字母表，构造多个密文字母表，在密钥的控制下用相应密文字母表中的一个字在密钥的控制下用相应密文字母表中的一个字母来代换明文字母表中的一个字母。母来代换明文字母表中的一个字母。一个明文一个明文字母有多种代换。字母有多种代换。Vigenere密码：密码：著名的多表代换密码著名的多表代换密码一、经典密码经典密码 明明明明 文文文文 字字字字 母母母母 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 ZA 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 A 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 ZA 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 ZB 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 AB 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 AC C D E F G H I J K L M N O P Q R S T U V W X Y Z A BC C D E F G H I J K L M N O P Q R S T U V W X Y Z A BH H I J K L M N O P Q R S T U V W X Y Z A B C D E F GH H I J K L M N O P Q R S T U V W X Y Z A B C D E F GX X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Y Y Z Z A A B B C C D D E E F F G G H H I I J J K K L L M M N N O O P P Q Q R R S S T T U U V V W W X X Z Z 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 Z 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 Vigenre方阵方阵密密密密钥钥钥钥字字字字母母母母一、经典密码经典密码 Vigenre密密码码的的代代换换规规则则是是用用明明文文字字母母在在Vigenre方方阵阵中中的的列列和和密密钥钥字字母母在在Vigenre方方阵阵中中的的行行的的交交点点处处的的字字母母来来代代换换该该明明文文字字母母。例例如如，设设明明文文字字母母为为P，密密钥钥字字母母为为Y，则则用用字字母母N来来代代换换明明文文字字母母P。明文明文明文明文：MING CHEN WU DIAN FA DONG FAN GONGMING CHEN WU DIAN FA DONG FAN GONG密钥密钥密钥密钥：XING CHUI PING YE KUO YUE YONG DA XING CHUI PING YE KUO YUE YONG DA JIANG LIU JIANG LIU密文密文密文密文：JQAME OYVLC QOYRP URMHK DOAMR NPJQAME OYVLC QOYRP URMHK DOAMR NP 解密就是利用解密就是利用Vigenre方阵进行反代换。方阵进行反代换。Ci=Mi+Ki mod n Mi=Ci+Ki mod n一、经典密码经典密码3、代数密码、代数密码：Vernam密码密码 明文、密文、密钥都表示为二进制位：明文、密文、密钥都表示为二进制位：M=m1,m2,mn K=k1,k2,kn C=c1,c2,cn 加密加密：c1=mi ki ,i=1,2,n 解密解密：m1=ci ki ,i=1,2,n因为加解密算法是模因为加解密算法是模2加，所以称为代数密码。加，所以称为代数密码。对合运算对合运算：f=f-1，模模 2加运算是对合运算。加运算是对合运算。密码算法是对和运算，则加密算法解密算法，密码算法是对和运算，则加密算法解密算法，工程实现工作量减半。工程实现工作量减半。Vernam密码经不起已知明文攻击。密码经不起已知明文攻击。一、经典密码经典密码一种极端情况：一种极端情况：一次一密一次一密 密钥是随机序列。密钥是随机序列。密钥至少和明文一样长。密钥至少和明文一样长。一个密钥只用一次。一个密钥只用一次。一次一密是绝对不可破译的，但它是不一次一密是绝对不可破译的，但它是不实用的。实用的。一次一密给密码设计指出一个方向，人一次一密给密码设计指出一个方向，人们用序列密码逼近一次一密。们用序列密码逼近一次一密。一、经典密码经典密码二、经典密码的穷举分析二、经典密码的穷举分析1 1、单表代换密码分析、单表代换密码分析加法密码加法密码因为因为f(af(ai i)=b)=bi i=a aj j j=i+k j=i+k mod nmod n所以所以k=1,2k=1,2，.,n-1,.,n-1,共共n-1n-1种可能，种可能，密钥空密钥空间太小。以英文为例，只有间太小。以英文为例，只有2525种密钥。种密钥。经不起穷举攻击。经不起穷举攻击。二、经典密码的穷举分析二、经典密码的穷举分析1 1、单表代换密码分析、单表代换密码分析乘法密码乘法密码因为因为f(af(ai i)=b)=bi i=a aj j j=j=ikik mod nmod n，且（且（k,nk,n）=1=1。密钥空间更小。密钥空间更小。对于英文字母表，对于英文字母表，n=26n=26，k=1,3,5,7,9,11,15,17,19,21,23,25k=1,3,5,7,9,11,15,17,19,21,23,25 取掉取掉1 1，共，共1111种，种，比加法密码更弱。比加法密码更弱。经不起穷举攻击。经不起穷举攻击。二、经典密码的穷举分析二、经典密码的穷举分析1 1、单表代换密码分析、单表代换密码分析密钥词语代换密码密钥词语代换密码因为因为密钥词语的选取是随机的，所以密文字母密钥词语的选取是随机的，所以密文字母表完全可能穷尽明文字母表的全排列。表完全可能穷尽明文字母表的全排列。以英文字母表为例，以英文字母表为例，n=26n=26，所以共有所以共有2626！种可！种可能的密文字母表。能的密文字母表。2626！44 10102626用计算机也不可能穷举攻击。用计算机也不可能穷举攻击。注意：注意：穷举不是攻击穷举不是攻击密钥词语代换密码的唯一密钥词语代换密码的唯一方法。方法。三、经典密码的统计分析三、经典密码的统计分析2 2、密钥词组单表代换密码的统计分析、密钥词组单表代换密码的统计分析 任何自然语言都有自己的统计规律。任何自然语言都有自己的统计规律。如果如果密文中保留了明文的统计特征，就可用密文中保留了明文的统计特征，就可用统计方法攻击密码。统计方法攻击密码。由于单表代换密码只使用一个密文字母表，由于单表代换密码只使用一个密文字母表，一个明文字母一个明文字母固定的固定的用一个密文字母来代换，用一个密文字母来代换，所以所以密文的统计规律与明文相同密文的统计规律与明文相同。因此，单表代换密码可用统计分因此，单表代换密码可用统计分析攻破。析攻破。三、经典密码的统计分析三、经典密码的统计分析英语的统计规律英语的统计规律 每个单字母出现的频率稳定。每个单字母出现的频率稳定。最高频率字母最高频率字母 E E 次高频率字母次高频率字母 T A O I N S H RT A O I N S H R 中高频率字母中高频率字母 D LD L 低频率字母低频率字母 C U M W F G Y P BC U M W F G Y P B 最低频率字母最低频率字母 V K J X Q ZV K J X Q Z 三、经典密码的统计分析三、经典密码的统计分析英语的统计规律英语的统计规律 频率最高的双字母组：频率最高的双字母组：TH HE IN ER AN RE ED ONTH HE IN ER AN RE ED ON ES ST EN AT TO NT HA NDES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ETOU EA NG AS OR TI IS ET IT AR TE SE HI OFIT AR TE SE HI OF 三、经典密码的统计分析三、经典密码的统计分析英语的统计规律英语的统计规律 频率最高的三字母组：频率最高的三字母组：THE ING AND HER ERE ENT THA WASTHE ING AND HER ERE ENT THA WAS ETH FOR DHT HAT SHE ION HIS ERSETH FOR DHT HAT SHE ION HIS ERS VER VER 其中其中THETHE的频率是的频率是INGING的的3 3倍！倍！三、经典密码的统计分析三、经典密码的统计分析英语的统计规律英语的统计规律 英文单词以英文单词以E E，S S，D D，T T为结尾的超过一半。为结尾的超过一半。英文单词以英文单词以T T，A A，S S，W W为起始字母的约占一为起始字母的约占一半。半。还有其它统计规律还有其它统计规律！三、经典密码的统计分析三、经典密码的统计分析 经得起统计分析是对近代经得起统计分析是对近代密码的基本要求！密码的基本要求！
