1、1网络信息安全理论基础 2第2章 网络信息安全理论基础 本章主要内容：本章主要内容：2.1 前言前言 2.2 密码学的基本概念密码学的基本概念 2.3 密码系统模型和密码体制密码系统模型和密码体制2.4 密密码分析码分析2.5 古典密码古典密码 32.1 前言l 基础数论在密码学中的作用基础数论在密码学中的作用 基础数论作为一门古老的数学学科，在整个数学学科中占有非常重要的位置。数论中许多基本内容，如同余理论、中国剩余定理（CRT）、高次剩余理论等，在新型密码体制、密钥分配与管理、数字签名、身份认证等方面有直接的应用。l 现代密码与近代数学形影不离现代密码与近代数学形影不离 近代数学在现代密码
2、研究中比比皆是：群论，有限域上椭圆曲线理论，多项式理论与迹函数理论，陷门单向函数 等。42.2 密码学的基本概念密码学的基本概念 密码学密码学(Cryptology)：研究信息系统安全保密的科学。它：研究信息系统安全保密的科学。它 包含两个分支。包含两个分支。密码编码学密码编码学(Cryptography)(Cryptography)，对信息进行编码实现隐，对信息进行编码实现隐蔽信息的一门学问蔽信息的一门学问密码分析学密码分析学(Cryptanalytics)(Cryptanalytics)，研究分析破译密码的，研究分析破译密码的学问。学问。5 2.2 密码学的基本概念密码学的基本概念 明文明
3、文(消息)(Plaintext)：被隐蔽消息。密文密文(Ciphertext)或密报密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密加密(Encryption)：将明文变换为密文的过程。解密解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员加密员或密码员密码员(Cryptographer)：对明文进行加密操作的人员。6 2.2 密码学的基本概念密码学的基本概念 加密算法加密算法(Encryption algorithm)：密码员对明文进行加密时所采用的一组规则。接收者接收者(Receiver)：传送消息的预定对象。解密算法解密算法：接收者对密文进行
4、解密时所采用的一组规则。密钥密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥加密密钥和解密密钥解密密钥。截收者截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。72.2 密码学的基本概念密码学的基本概念 密码分析密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击被动攻击(Passive attack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击主动攻击(Active attack)
5、：非法入侵者非法入侵者(Tamper)、攻击者攻击者(Attcker)或黑客黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。82.3 密码系统模型和密码体制密码系统模型和密码体制l Shannon的保密系统模型的保密系统模型9 2.3 密码系统模型和密码体制密码系统模型和密码体制l 现代密码系统模型现代密码系统模型信 源MM加密器 cm1kE非法接入者密码分析员（窃听者）搭线信道（主动攻击）搭线信道（被动攻击）解密器接收者 mc2kD密钥源密钥源1K K2K Kmmmc c1k2k信道密钥信道102.3 密码系统模型和密码体制密码系
6、统模型和密码体制l 密码体制密码体制(Cryptosystem)六元组六元组(MM,C C,K K1,K K2,E E,DD)u明文空间明文空间:M M，m M M 称为明文称为明文(plaintext)u密文空间密文空间:C C，c C C 称为密文称为密文(ciphertext)u加密密钥空间加密密钥空间:K K1，k1 K K1 称为加密密钥称为加密密钥(encryption key)u解密密钥空间解密密钥空间:K K2 k2 K K2 称为解密密钥称为解密密钥(decryption key)密钥密钥(key):k=(k1,k2)11l 密码体制密码体制(Cryptosystem)六元组
7、六元组(MM,C C,K K1,K K2,E E,DD)u加密变换簇加密变换簇:E E1111 ,:)kkkEE(encryption map,function,algorithm加密变换（映射、函数、算法）KEKEMCMCu解密变换簇解密变换簇:DD2222 ,:)kkkDD(decryption map,function,algorithm解密变换（映射、函数、算法）KDKDCMCM 2.3 密码系统模型和密码体制密码系统模型和密码体制12l 密码体制密码体制(Cryptosystem)u加密变换与解密变换的关系加密变换与解密变换的关系.)(,),(1212212121的左逆变换称为有：满
8、足kkkkkkEDmmEDmDEkkk MM DDE EK KK K )(1mEckmcDk)(2 )(1mEckmMMC CcmcDk)(2 2.3 密码系统模型和密码体制密码系统模型和密码体制13 保密系统应当满足的要求保密系统应当满足的要求u 系统即使达不到理论上是不可破的，即系统即使达不到理论上是不可破的，即prm=m=0，也应当为实际上不可破的。就是说，从截获的密文或也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。上是不可行的。u 系统的保密性不依赖于对加密体制或算法的保密，而系统
9、的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的依赖于密钥。这是著名的Kerckhoff原则。原则。u 加密和解密算法适用于所有密钥空间中的元素。加密和解密算法适用于所有密钥空间中的元素。u 系统便于实现和使用。系统便于实现和使用。14认证与认证系统认证与认证系统认证系统认证系统(Authentication system)防止消息被窜改、删除、重放和伪造的一种有效方法防止消息被窜改、删除、重放和伪造的一种有效方法,使发送的消息具有被验证的能力，使接收者或第三者能够使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作认识别和确认消息
10、的真伪。实现这类功能的密码系统称作认证系统证系统保密性保密性 保密性是使截获者在不知密钥条件下不能解读密文的内保密性是使截获者在不知密钥条件下不能解读密文的内容。容。认证性认证性 使任何不知密钥的人不能构造一个密报，使意定的接使任何不知密钥的人不能构造一个密报，使意定的接收者解密成一个可理解的消息收者解密成一个可理解的消息(合法的消息消息)。15安全认证系统应满足下述条件安全认证系统应满足下述条件意定的接收者能够检验和证实消息的合法性和真实意定的接收者能够检验和证实消息的合法性和真实性。性。消息的发送者对所发送的消息不能抵赖。消息的发送者对所发送的消息不能抵赖。除了合法消息发送者外，其它人不能
11、伪造合法的消除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文息。而且在已知合法密文c和相应消息和相应消息m下，要确定下，要确定加密密钥或系统地伪造合法密文在计算上是不可行加密密钥或系统地伪造合法密文在计算上是不可行的。的。必要时可由第三者作出仲裁。必要时可由第三者作出仲裁。16l 密码体制系统的分类密码体制系统的分类u对称密码体制对称密码体制(symmetric cryptosystem)k=k1=k2 或或 k1 k2 单钥、私钥单钥、私钥(one-key,private key)密码体制密码体制加密器 cmkE解密器 mckD密钥产生器mckk密钥信道明文密文解读后明文密
12、钥产生器 2.3 密码系统模型和密码体制密码系统模型和密码体制17u单钥体制单钥体制(One-key system)(One-key system)：加密密钥和解密密钥相同加密密钥和解密密钥相同，即能简单的由加（解）密密即能简单的由加（解）密密钥求得解（加）密密钥。钥求得解（加）密密钥。注意：一个保密系统的加密密钥和解密密钥相同，或注意：一个保密系统的加密密钥和解密密钥相同，或者虽然不同，但由其中的任意一个很容易的求得另外一者虽然不同，但由其中的任意一个很容易的求得另外一个，即使用的是对称密钥密码体制，那么某个实体有能个，即使用的是对称密钥密码体制，那么某个实体有能力加密，也就有能力解密。力加
13、密，也就有能力解密。18l 密码体制系统的分类密码体制系统的分类u对称密码体制对称密码体制(symmetric cryptosystem)p分组密码分组密码(block cipher)将明文消息分为包含若干个符号的组，在选定密钥后使用将明文消息分为包含若干个符号的组，在选定密钥后使用固定的加密变换对明文分组逐组地进行加密。固定的加密变换对明文分组逐组地进行加密。例如，例如，DES(1977),AES(2001)p流密码流密码(stream cipher)明文：明文：m=m1m2m3.密钥：密钥：k=k1k2k3.加密：加密：c1=Ek1(m1),c2=Ek2(m2),c3=Ek3(m3),.密
14、文：密文：c=c1c2c3.例如，例如，GSM移动台（手机）到基站移动台（手机）到基站BS之间无线传输之间无线传输 中使中使用的加密算法用的加密算法A5/1是一种流密码是一种流密码 2.3 密码系统模型和密码体制密码系统模型和密码体制19u非对称密码体制非对称密码体制(asymmetric cryptosystem)双钥、公钥双钥、公钥(two-key,public key)密码体制密码体制 k1 k2 或或 k1不能不能k2 公钥公钥:k1=pk；私钥私钥:k2=skBpkEBskDmc明文密文用户A用户Bm搭线信道,.h m查找B的公开密钥Bpk使用自己的秘密密钥Bsk 2.3 密码系统模
15、型和密码体制密码系统模型和密码体制20u双钥体制双钥体制(Two key system)(Two key system)：加密密钥和解密密钥不同。加密密钥和解密密钥不同。一个保密系统把加密和解密分开，加密和解密分别用两一个保密系统把加密和解密分开，加密和解密分别用两 个不同的密钥实现，并且由加密密钥推导出解密密钥是计算个不同的密钥实现，并且由加密密钥推导出解密密钥是计算是不可行的，则该系统使用的是非对称密钥密码体制（公钥是不可行的，则该系统使用的是非对称密钥密码体制（公钥密码体制）如：密码体制）如：RSARSA、EIGaMalEIGaMal、椭圆曲线密码体制等是非对、椭圆曲线密码体制等是非对称
16、密码体制的典型代表。称密码体制的典型代表。使用公钥密码体制的每个用户都有一对选定的密钥，其使用公钥密码体制的每个用户都有一对选定的密钥，其中一个是可以公开的，称为公钥，另外一个是用户自己中一个是可以公开的，称为公钥，另外一个是用户自己秘密保存。秘密保存。思考：用于加密的还是解密的秘钥保存？212.3 密码系统模型和密码体制密码系统模型和密码体制l 密码系统的设计原则密码系统的设计原则 设计加密函数与解密函数的学科称为密码编码学设计加密函数与解密函数的学科称为密码编码学 (Cryptography)、密码学或保密学。、密码学或保密学。u具有某种安全性具有某种安全性p理论上不可破理论上不可破p实际
17、上不可破实际上不可破 uKerckhoff假设：系统的保密性不依赖于对加密体制或假设：系统的保密性不依赖于对加密体制或加（解）密算法的保密，而仅依赖于密钥的保密。加（解）密算法的保密，而仅依赖于密钥的保密。u加密和解密算法适用于密钥空间的全部元素加密和解密算法适用于密钥空间的全部元素u系统便于实现和使用方便系统便于实现和使用方便22 2.3 密码系统模型和密码体制密码系统模型和密码体制l 密码学发展简史密码学发展简史u密码学发展史简图密码学发展史简图远古远古1949年年1976年年1977年年1949年年现代密码现代密码古典密码古典密码1976年年私钥密码私钥密码公钥密码公钥密码1977年年
18、商用密码商用密码23l 密码学发展简史密码学发展简史u古典密码时期古典密码时期(1949)p特定应用领域：军事、政治、外交特定应用领域：军事、政治、外交 p神秘性神秘性 p艺术性艺术性u现代密码学现代密码学(1949)：密码技术成为一门学科密码技术成为一门学科 著名论文著名论文:Communication theory of secrecy systems,Bell Syst.Tech.J.,Volume 28,656-715,1949.仙农仙农(C.D.Shannon:1916-2001)2.3 密码系统模型和密码体制密码系统模型和密码体制24l 密码学发展简史密码学发展简史u公钥密码学公钥
19、密码学(1976)p计算机网络环境中的应用pW.Diffie和M.E.Hellman提出公钥密码的思想(1976)p著名论文：W.Diffie and M.E.Hellman,New direction in cryptography,IEEE Tran.On Information Theory,IT-22,(6),644-654,1976.u密码学的商业应用密码学的商业应用(1977)p1977：美国国家标准局(National Bureau of Standards)颁布数据加密标准DES(Data Encryption Standard)p1994：美国政府颁布数字签名标准DSS(Da
20、ta Signature Standard)p2001：美国政府颁布高级加密标准AES(Advanced Encryption Standard)2.3 密码系统模型和密码体制密码系统模型和密码体制252.4 密码分析密码分析 截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。262.4 密码分析密码分析 密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别 密
21、码设计是利用数学来构造密码 密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力，有时还靠点运气。27l 利用密文推断出明文或解密密钥的学科称为密码分析学利用密文推断出明文或解密密钥的学科称为密码分析学 (Cryptanalysis)分析分析(analysis)=破译破译(break)=攻击攻击(attacks)l 攻击方式攻击方式u主动攻击主动攻击(active attack)窜改通信中的数据流，或在通信中产生虚假数据流窜改通信中的数据流，或在通信中产生虚假数据流u被动攻击被动攻击(passive attack)窃听或监视通信过程，从中获得信息窃听或监视
22、通信过程，从中获得信息2.4 密码分析密码分析28l 攻击方法攻击方法 2.4 密码分析密码分析能能量量分分析析时时序序分分析析物物理理破破译译法法统统计计分分析析法法确确定定性性分分析析法法数数学学分分析析法法穷穷举举破破译译法法传传统统破破译译法法攻攻击击方方法法 29u穷举破译法穷举破译法(exhaustive attack method)p方法：对截获的密文依次用各种可能的密钥试译，直到获得有意义的明文；或者利用对手已注入密钥的加密机（比如缴获得到），对所有可能的明文依次加密直到得出与截获的密文一致的密文。p对策：将密钥空间和明文空间设计得足够大。u确定性分析法确定性分析法p方法：利用
23、密文或者明文密文对等已知量以数学关系式表示出所求未知量（如密钥等），然后计算出未知量。p对策：设计具有坚实数学基础和足够复杂的加密函数u统计分析法统计分析法p方法：密码破译者对截获的密文进行统计分析，找出其统计规律或特征，并与明文空间的统计特征进行对照比较，从中提取出密文与明文间的对应关系，最终确定密钥或明文。p对策：扰乱密文的语言统计规律 攻击方法攻击方法30u物理破译方法物理破译方法(Kocher,1996)利用加密执行时的物理现象来确定密钥的密码分析方利用加密执行时的物理现象来确定密钥的密码分析方法，也被称为法，也被称为“边信道攻击边信道攻击”（side-channel attack）。
24、）。所利用的物理现象有密码算法执行器件（加密芯片）所利用的物理现象有密码算法执行器件（加密芯片）的功耗，各算法步执行时间度量，甚至主机执行加密的功耗，各算法步执行时间度量，甚至主机执行加密任务时主板上电容器发出的声音等等。任务时主板上电容器发出的声音等等。攻击方法攻击方法31l 攻击类型攻击类型u唯密文攻击唯密文攻击(ciphertext-only attack)密码分析者仅知道有限数量用同一个密钥加密的密文密码分析者仅知道有限数量用同一个密钥加密的密文u已知明文攻击已知明文攻击(known plaintext attack)密码分析者除了拥有有限数量的密文外，还有数量限密码分析者除了拥有有限
25、数量的密文外，还有数量限定的一些已知定的一些已知“明文明文密文密文”对对u选择明文攻击选择明文攻击(chosen plaintext attack)密码分析者除了拥有有限数量的密文外，还有机会使密码分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的加密机，通过自由选择明文来获用注入了未知密钥的加密机，通过自由选择明文来获取所希望的取所希望的“明文明文密文密文”对对 u选择密文攻击选择密文攻击(chosen ciphertext attack)密码分析者除了拥有有限数量的密文外，还有机会使密码分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的解密机，通过自由选择密文来获用注入
26、了未知密钥的解密机，通过自由选择密文来获取所希望的取所希望的“密文密文明文明文”对对32无条件安全和计算安全无条件安全和计算安全 无条件安全无条件安全 如果算法产生的密文不能给出唯一决定相应明文的足够信息，无论截获多少密文，花费所少时间都不能解密密文。Shannon指出，仅当密钥至少和明文一样长时达到无条件安全（即一次一密）计算安全计算安全 破译密文的代价超过被加密信息的价值 破译密文所花时间超过信息的有效期331）代替）代替密码密码（替换密码）（替换密码）可分为单表可分为单表密码密码、多表密码、多表密码单表单表密码密码：将明文中的字母或符号用另一种字母或符号来代替，将明文中的字母或符号用另一
27、种字母或符号来代替，这种代替是一一对应的。这种代替是一一对应的。明文与密文之间只有一种对应关系。明文与密文之间只有一种对应关系。多表密码：多表密码：代替不是一一对应的。代替不是一一对应的。代替规律不同，密码体制也不同。代替规律不同，密码体制也不同。代替规律相同，明密文间字母对应关系不同，代替规律相同，明密文间字母对应关系不同，代替出的密码也不同。代替出的密码也不同。e.g.同余密码（加同余、乘同余、线性同余）同余密码（加同余、乘同余、线性同余）随机替代、密钥词组、多表组合随机替代、密钥词组、多表组合2.4 古古典密码典密码34*一般单码替换密码一般单码替换密码 简单的方法给出密钥简单的方法给出
28、密钥 写出密钥（删除重复字母）写出密钥（删除重复字母）在其下面依次写出剩余字母在其下面依次写出剩余字母 （以横、纵行）（以横、纵行）按列读取字母得到密文。按列读取字母得到密文。2.4 古古典密码典密码35 一般单码替换密码举例一般单码替换密码举例 给定密钥字给定密钥字STARWARSSTARWARS 去掉重复字母得到去掉重复字母得到STARWSTARW 填写剩余字母：填写剩余字母：STARWSTARWBCDEFBCDEFGHIJKGHIJKLMNOPLMNOPQUVXYQUVXYZ Z 按列读取字母得到密文按列读取字母得到密文 Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZP
29、lain:ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher:SBGLQZTCHMUADINVREJOXWFKPYCipher:SBGLQZTCHMUADINVREJOXWFKPY 可以用这个密钥加密、解密可以用这个密钥加密、解密 例如例如Plaintext:I KNOW ONLY THAT I KNOW NOTHINGPlaintext:I KNOW ONLY THAT I KNOW NOTHING Ciphertext:H UINF NIAP OCSO H UINF INOCHIT Ciphertext:H UINF NIAP OCSO H UINF INOCHIT36 一
30、般单码替换密码的密码分析一般单码替换密码的密码分析 根据频率统计进行分析根据频率统计进行分析 确定每个字母被映射到什么字母确定每个字母被映射到什么字母 如果知道单词之间的间隙知道如果知道单词之间的间隙知道,则破译会很容则破译会很容易易.单个字母出现的可能是单个字母出现的可能是A A或或I I 一般来说一般来说3 3个字母出现的可能是个字母出现的可能是THETHE或或ANDAND 还可以用其他通常出现的双字母或三字母组合还可以用其他通常出现的双字母或三字母组合)还可以应用其它很少应用的字母还可以应用其它很少应用的字母37同余密码同余密码 (1)加同余码：加同余码：一种移位密码，如一种移位密码，如
31、凯撤凯撤(Cacsar)密码密码：以查码：以查码表方式进行一对一替换。表方式进行一对一替换。收发双方采用同一码表。收发双方采用同一码表。凯撤凯撤密码加密变换：密码加密变换：C=P+3(mod 26)凯撤凯撤密码解密变换：密码解密变换：P=C-3(mod 26)密钥：密钥：338 若明文若明文m=Casear cipher is a shift substitution 则密文则密文C=E(m)=FDVHDU FLSHU LV D VKLIW VXEVWLWXWLRQ明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC39凯撤凯
32、撤密码扩展：密码扩展：C=P+n(mod 26)P=C-n(mod 26)密钥：密钥：n密码分析密码分析（）加解密算法已知（）加解密算法已知（）可能尝试的密钥只有（）可能尝试的密钥只有6 6个个通过强力攻击得到明文通过强力攻击得到明文40(2)乘同余码：乘同余码：移位或等间隔抽取码，明密文之间没有一一对移位或等间隔抽取码，明密文之间没有一一对应关系。（容易产生多义性）。应关系。（容易产生多义性）。变换按照同余乘法进行：变换按照同余乘法进行：加密变换：加密变换：C=P k(mod 26)解密变换：解密变换：P=C k(mod 26)密钥：密钥：k 41 (3)线性同余：线性同余：加同余与乘同余密
33、码的结合。加同余与乘同余密码的结合。正常字母顺序替换，解码容易正常字母顺序替换，解码容易42随机替换密码随机替换密码 随机改变字母替换顺序，改变单一字母组合，随机改变字母替换顺序，改变单一字母组合，增加字符或者专用符号替换，从而增加了密钥增加字符或者专用符号替换，从而增加了密钥数量，使密码破译困难，但用户自己记忆也困难。数量，使密码破译困难，但用户自己记忆也困难。通常以码表查阅实现。通常以码表查阅实现。密钥词组密码密钥词组密码 解决密钥记忆困难问题，任选一词组作为密钥。解决密钥记忆困难问题，任选一词组作为密钥。加解密均也采用查表方式。加解密均也采用查表方式。上述密码均是字母、符号的排列和组合，
34、用计算上述密码均是字母、符号的排列和组合，用计算机可以对上述密码进行破译。机可以对上述密码进行破译。43多表密码多表密码 利用多码表组合形成的加解密机制，打乱明文利用多码表组合形成的加解密机制，打乱明文统计规律，提高保密强度统计规律，提高保密强度。多表代换密码是以一多表代换密码是以一系列系列(两个以上两个以上)代换表依次对明文消息的字母进代换表依次对明文消息的字母进行代换的加密方法行代换的加密方法 e.g.维吉尼亚密码、博福特密码等维吉尼亚密码、博福特密码等441 1维吉尼亚密码维吉尼亚密码一种以移位代换为基础的周期代换密码，为一种以移位代换为基础的周期代换密码，为18581858年法国年法国
35、密码学家维吉尼亚提出。密码学家维吉尼亚提出。首先构造一个维吉尼亚方阵：首先构造一个维吉尼亚方阵：它的基本阵列是它的基本阵列是2626行行2626列的方阵列的方阵.方阵的第一行是按正方阵的第一行是按正常顺序排列的字母表常顺序排列的字母表,第二行是第一行左移循环第二行是第一行左移循环1 1位得到位得到的的,依此类推依此类推,得到其余各行得到其余各行.然后在基本方阵的最上方然后在基本方阵的最上方附加一行附加一行,最左侧附加一列最左侧附加一列,分别依序写上分别依序写上a a到到z 26z 26个字个字母母,表的第一行与与附加列上的的字母表的第一行与与附加列上的的字母a a相对应相对应,表的第表的第二行
36、与附加列上的字母二行与附加列上的字母b b相对应相对应.最后一行与附加列上最后一行与附加列上的字母的字母z z相对应相对应.如果把上面的附加行看作是明文序列，如果把上面的附加行看作是明文序列，则下面的则下面的2626行就分别构成了左移行就分别构成了左移0 0位，位，1 1位，位，2 2位位，2525位的位的2626个单表代换加同余密码的密文序列。加密时，按个单表代换加同余密码的密文序列。加密时，按照密钥字的指示，决定采用哪一个单表。照密钥字的指示，决定采用哪一个单表。45ABCDEFGHIJ.YZAABCDEFGHIJ.YZBBCDEFGHIJK.ZACCDEFGHIJKL.ABDDEFGHI
37、JKLM.BCEEFGHIJKLMNCDFFGHIJKLMNODEGGHIJKLMNOPEFHHIJKLMNOPQFGZZABCDEFGHI.XY46维吉尼亚密码维吉尼亚密码密钥字 encryptionencryptione明 文：publickeydistribution密 文：thdcgrdmmqmfvrgqnbwbr由于密钥字比明文短，所以要重复书写密钥字，由于密钥字比明文短，所以要重复书写密钥字，以得与明文等长的密钥序列。以得与明文等长的密钥序列。47Vigenre cipher-破译依然保留了字符频率某些统计信息重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个
38、相同的子串对应的密文相同的可能性很大。482）置换密码）置换密码 也称换位密码或转置密码也称换位密码或转置密码。加密方式与密文形式不同于代替密码体制。加密方式与密文形式不同于代替密码体制。不改变组成明文消息的符号本身，只对符号进不改变组成明文消息的符号本身，只对符号进行重新排列。行重新排列。可以分类为：可以分类为：倒序密码：颠倒明文书写顺序。倒序密码：颠倒明文书写顺序。栅栏密码：明文交替书写排列。栅栏密码：明文交替书写排列。行列转置：明文行列转置书写。行列转置：明文行列转置书写。49变换密码的关键思想变换密码的关键思想按一定规则写出明文，按另一规则读出密文。按一定规则写出明文，按另一规则读出密
39、文。密钥：用于读密文的方法和写明文的方法密钥：用于读密文的方法和写明文的方法50例、行变换密码例、行变换密码-（Row transposition Row transposition ciphers ciphers）按行写出字母按行写出字母以密钥给出的顺序按行读出密文以密钥给出的顺序按行读出密文（总是有一个密钥对）（总是有一个密钥对）51行变换密码行变换密码(续续1)1)Plain:THESIMPLESTPOSSIBLETRANSPOSITIONSXXKey(R):2 5 4 1 3Key(W):4 1 5 3 2T H E S I S T I E HM P L E S E M S L PT
40、P O S S S T S O P I B L E T E I T L BR A N S P S R P N AO S I T I T O I I SO N S X X X O X S N Cipher:STIEH EMSLP STSOP EITLB SRPNA TOIIS XOXSN523）代码密码）代码密码 可以对明文字母、符号、词组和短语等进行替可以对明文字母、符号、词组和短语等进行替换，甚至对明文句子进行替换换，甚至对明文句子进行替换。不考虑明文的结构，代码替换可以是等长的，不考虑明文的结构，代码替换可以是等长的，也可以是不等长的。也可以是不等长的。短码替换使明文长度缩短，实现明文压缩
41、。短码替换使明文长度缩短，实现明文压缩。长码替换使明文长度增长，实现明文扩展。长码替换使明文长度增长，实现明文扩展。e.g.以各种编码实现替换：以各种编码实现替换：二进制码、八或二进制码、八或16进制码、五中出二码、进制码、五中出二码、格雷码等。格雷码等。53一次一密密码一次一密密码l 一次一密密码，由AT&T公司的Gilbert Vernam在1917年提出。发方和收方各保存一份一次一密乱码本，它是一个大的不重复的真随机密钥字母集。发方用乱码本中的某一页密钥加密明文。加密方法：明文字符和乱码本密钥字符的模26加法。l 每个密钥仅对一个消息使用一次。发方对所发的消息加密，然后销毁乱码本中用过的
42、一页。收方有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符，然后销毁乱码本中用过的一页。54l 语言的统计规律性语言的统计规律性uC.E.Shannon 1949年第一次透彻地阐明了密码分析的真谛，指出密码能够被破译的最根本原因是于明文空间非均匀的统计特性u英文字母频率表英文字母频率表 初等密码分析实例初等密码分析实例字母字母概率概率字母字母概率概率字母字母概率概率字母字母概率概率ABCDEFG0.081670.014920.027820.042530.127020.022280.02015HIJKLMN0.060940.069660.001530.0080.0400.02
43、40.067OPQRSTU0.0750.0190.0010.0600.0630.0910.028VWXYZ0.0100.0230.0010.0200.00155l 单表代换密码分析单表代换密码分析 给定密文：给定密文：EJM H AFJPD PBKRNM QJ AN ONPSMN BQO AFJPD NIW QRG GSOQ AN FHMWN NIJSWR QJ YNQNM OQHQBOQB PHF HIH FXOBOQRN AFJPD FNIWQR JE YNO GHX AN QRN ORJMQNOQJIN u首先求出密文字母的频度分布表首先求出密文字母的频度分布表 密文字母密文字母 ABC
44、D EFGH I J K L M N O P Q RST UVWX YZ 频频 数数 6 5 0 3 2 8 37 510 1 0 6 17 10 6 14 73 0 0 0 4 2 2 0u先猜测先猜测Ek:eN,，再利用英文高频度的双字母知识，比，再利用英文高频度的双字母知识，比对密文中出现的双字母（词）及次高频度字母集对密文中出现的双字母（词）及次高频度字母集t,a,o,i,n,s,h,r，猜测，猜测Ek:tQ,oJ,得到部分试译结果：得到部分试译结果：EoM H bFoPD PBKReM to be OePSMe BtO bFoPD FeIWtR G GSOt be FHMWe eIo
45、SWR to YeteM OtHtBOtBPHF HIHFXOBO tRe bFoPD FeIWtR oE YeO GHX be tRe ORoMteOt oIe56u利用三字母组合和元音辅音拼写知识，猜测单词利用三字母组合和元音辅音拼写知识，猜测单词tRe为为the，即，即 Ek:hR.u在余下的次高频度字母集在余下的次高频度字母集a,i,n,s,r中选择适当的辅音字中选择适当的辅音字母作为密文母作为密文O的原像的原像,即即Ek:sO.u利用构词分析从利用构词分析从shoMtest猜测猜测Ek:rM,从从oIe猜测猜测Ek:nI.试译：试译：Eor H bFoPD PBKher to be
46、sePSre Bts bFoPD FenWth G GSst be FHrWe enoSWh to Yeter stHtBstBPHF HnHFXsBs the bFoPD FenWth oE Yes GHX be the shortest one u对余下的次高频度字母集对余下的次高频度字母集a,i,猜测猜测 Ek:aH.试译：试译：Eor a bFoPD PBKher to be sePSre Bts bFoPD FenWth G GSst be FarWe enoSWh to Yeter statBstBPaF anaFXsBs the bFoPD FenWth oE Yes GaX b
47、e the shortest one 单表代换密码分析单表代换密码分析(2)57u对余下的中高频度字母对余下的中高频度字母F,其原像应当是辅音其原像应当是辅音,故在中频故在中频度字母集度字母集d,l中猜测中猜测Ek:lF.利用构词分析从利用构词分析从lenWth猜猜测测Ek:gW.试译：试译：Eor a bloPD PBKher to be sePSre Bts bloPD length G GSst be large enoSgh to Yeter statBstBPal analXsBs the bloPD length oE Yes GaX be the shortest one 单表代
48、换密码分析单表代换密码分析(3)u再猜测余下的映射再猜测余下的映射 Ek:fE,cP,kD,mG,uS,iB,pK,dY,yX.最后得明文：最后得明文：for a block cipher to be secure its block length m must be large enough to deter statistical analysis the block length of des may be the shortest one 58u破译的代换表为：破译的代换表为：单表代换密码分析单表代换密码分析(4):A A A A abcdefghijklmnopqrstuvwxyzH
49、APYNEWRBDFGIJKMOQSXu由于密文中未出现由于密文中未出现C、L、T、U、V、Z，所以代换表，所以代换表尚不完整。如果有更多的密文供分析使用，就很有可能尚不完整。如果有更多的密文供分析使用，就很有可能得到正确的代换表：得到正确的代换表：:A A A A abcdefghijklmnopqrstuvwxyzHAPYNEWRBCDFGIJKLMOQSTUVXZ59l 对密码分析有用的英文统计特性对密码分析有用的英文统计特性u冠词冠词the对统计特性影响极大，它使对统计特性影响极大，它使t、h、th、he和和the在单、双和三字母统计中都为高频度元素。在单、双和三字母统计中都为高频度元素。u英文中大约有一半的字以英文中大约有一半的字以e、s、d和和t作为字的结尾作为字的结尾字母。字母。u英文中大约有一半的字以英文中大约有一半的字以t、a、s或或w作为字的开头作为字的开头字母。字母。初等密码分析实例初等密码分析实例
