Chapter 2 密码学基础

本书配套网站出版时间：2013年5月清华大学出版社ISBN：9787302312345第二章密码学基础目录2.1密码学的基本知识2.2对称密码体制2.3密码学的数学基础2.4公钥密码体制。全体可能出现的密文集合称为密文空间C密文未经过加密的原始信息称为明文m，明文的全体称为明文空间M明文由明文空间、密文空间、密码方案和密钥空间组成密码系统密码学的基本概念密码学的基本概念(2)加密和解密算法的操作在称为密钥（k）的元素控制下进行。密钥的全体称为密钥空间（K）密钥确切地描述了加密变换和解密变换的具体规则密码方案加密算法对明文进行加密时所使用的规则的描述Ｅ(m)解密算法对密文进行还原时所使用的规则D(c)有了密钥的概念后，加密的过程：c=EKe(m)，解密的过程:m=DKd(c)，其中m∈M，c∈C被动攻击和主动攻击密码分析者（Cryptanalyst）又称攻击者，可采用搭线窃听等方式直接获得未经加密的明文或加密后的密文，并分析得知明文。这种对密码系统的攻击手段称为被动攻击（Passiveattack），特点：不破坏原始信息攻击者还可以采用删除、更改、增添、重放、伪造等手段主动向系统注入假信息，这种对密码系统的攻击手段称为主动攻击（Activeattack）被动攻击和主动攻击形式威胁特点被动攻击窃听流量分析机密性不破坏原始信息难于发现主动攻击篡改、伪造重放、否认完整性易于探测但却难于防范拒绝服务可用性密码体制的分类1.按照密码的发展历史分类密码可分为古典密码和近现代密码2.按照需要保密的内容分类根据密码体制的密码算法是否需要保密，可分为受限制的算法和基于密钥的算法1883年Kerchoffs第一次明确提出了编码的原则，即加密算法应建立在算法的公开不影响明文和密钥的安全的基础上密码体制的分类3.根据加密和解密所使用的密钥是否相同对称密码体制公钥密码体制：也称为非对称密码体制对称密码体制对称密码体制SymmetricKeyCryptosystem加密密钥=解密密钥密钥必须保密公钥密码体制公钥密码体制PublicKeyCryptosystem加密密钥≠解密密钥•加密密钥为公钥（PublicKey），公钥无需保密•解密密钥为私钥（PrivateKey）密码体制的分类4.根据对明文的处理方式分组密码算法和流密码算法5.根据是否能进行可逆的加密变换分为单向函数密码体制和双向变换密码体制密码学的发展历程密码学的发展历程古典密码体制•近现代密码体制•Shannon的《保密通信的信息理论》•密码学的新方向Diffie和Hellman《密码学的新方向》密码分析与密码系统的安全性密码系统的安全性取决于(1)所使用的密码算法的保密强度(2)密码算法以外不安全的因素因此必须同时完善技术与管理上的要求，才能保证整个密码系统的安全密码分析研究如何分析和破解密码密码分析的方法密码分析的方法数学分析攻击（Mathe-maticalanalysisattack）统计分析攻击（Statisticalanalysisattack）穷举分析攻击（Exhaustiveattack）密码分析攻击的类型假设密码分析者已经知道加密算法，根据密码分析者对明文、密文等资源的掌握程度：1）唯密文攻击（Ciphtext-onlyattack）2）已知明文攻击（Plaintext-knownattack）3）选择明文攻击（Chosen-plaintextattack）4）选择密文攻击（Chosen—Ciphtextattack）现代加密算法的设计目标是要能抵抗住选择明文攻击密码系统安全性的层次无条件安全（UnconditionallySecure）计算上安全（ComputationallySecure）可证明安全（ProvableSecure）一般认为，密码系统只要能达到计算上安全就是安全的目录2.1密码学的基本知识2.2对称密码体制2.3密码学的数学基础2.4公钥密码体制对称密码体制对称密码体制，即加密密钥与解密密钥相同的密码体制，这种体制只要知道加（解）密算法，就可以反推解（加）密算法在1976年公钥密码算法提出以前的所有加密算法都是对称密码体制对称密码体制可分为分组密码和流密码本节将介绍的古典密码、分组密码和流密码古典密码置换（换位）是对明文中的元素进行换位排列，可以证明置换是替代的一种特殊形式置换替代是将明文中的每个元素映射为另一个元素，明文元素被其他元素所替代而形成密文替代采用的加密思想：替代和置换对于明文“dog”，使用替代技术加密：结果可能是“eph”，使用置换技术加密：结果可能是“ogd”讨论下面密码算法的加密思想Scytale密码棋盘密码123451abcde2fghijk3lmnop4qrstu5vwxyz几种典型的古典密码移位密码（又称凯撒密码）一般单表替代密码仿射密码密钥短语密码维吉尼亚（Vigenere）密码希尔（Hill）密码置换密码移位密码加密变换：Ek(m)=m+k(mod26)m∈M,k∈K解密变换：Dk(c)=c-k(mod26)c∈C,k∈K很容易利用穷举法将密文解密，最多尝试25次，就能找到密文对应的明文信息明文：youth密文：brxwk将明文每个字母前移三位移位密码加密示例密钥产生）Alice与Bob协定编码方式为明文字母后移4位，即加密密钥及解密密钥同为K=4。密钥：Alice将明文“gaulisdividedintothreepart”转为数字代码：（6，0，20，11，8，18，3，8，21，8，3，4，3，8，13，19，14，19，7，17，4，4，15，0，17，19）。使用加密函数E（m）m+k=m+4（mod26）计算得：（10，4，24，15，12，22，7，12，25，12，7，8，7，12，17，23，17，23，11，21，8，8，19，4，21，23）即密文“K，E，Y，P，M，Z，M，H，I，H，M，R，X，R，X，L，V，I，I，T，E，V，X”。加密：一般单表替代密码明文消息中的每个字母不是同时移动相同的位数，而是根据一张替代表使用随机替换一张一般单表替代密码的映射表明文abcdefghijklm密文qwertyuiopasd明文nopqrstuvwxyz密文fghjklzxcvbnmc=Ek(m)=π(m)m=Dk(c)=π-1(c)仿射密码加密变换为：c=Ek(m)=(k1m+k2)mod26相应的解密变换为：m=Dk(c)=k1-1(c-k2)mod26注意：k1必须和26互素，如果不互素，例如取k1=2，则明文m=mi和m=mi+13两个字符都将被映射成同一个密文字符仿射密码示例例：Alice欲将明文m=“affine”用仿射密码加密，传递给Bob，Bob来解读。密钥：Alice与Bob事先协定一把密钥K=(3,8)其中gcd(3,26)=1加密：E(.)m'affine'(0,5,5,8,13,4)(8,23,23,6,21,20)'IXXGVU'cE(m)3m8(mod26)解密：1D(c)3(c8)9(c8)(mod26)D(.)c'IXXGVU'(8,23,23,6,21,20)(0,5,5,8,13,4)'affine'm密钥短语密码密钥短语密码选用一个英文短语或单词作为密钥，如密钥为university时，先去掉重复字母i，成为universty明文字母abcdefghijklmnopqrstuvwxyz密钥字母universtyabcdfghjklmopqwxz总结：单表替代密码的特点以上几种密码都是单表替代密码，特点如下：这个特点使其密文中单字母出现的频率分布与明文中的相同，因此任何单表替代密码都经不起统计分析。明文和密文是一对一的映射关系。Ef(x0,x1,x2,…)=(f(x0),f(x1),f(x2),…)另外最常出现的双字母组合为：th(3.15%)，he(2.51%)，an(1.72)，in(1.69%)，er(1.54%)，re(1.48%)，es(1.45%)，on(1.45%)，ea(1.31%)，ti(1.28)，at(1.24%)，st(a.21%)，en(1.20%)，nd(1.18%)等。最常出现的三字母组合（Trigram）为：the，ing，and，her，ere，ent，tha，…。多表替代密码多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布同一个明文字母将对应不同的密文字母Ef(x0,x1,x2,…)=(f0(x0),f1(x1),f2(x2),…)维吉尼亚（Vigenere）密码维吉尼亚密码：一种典型的多表替代密码，该密码体制有一个参数n，表示采用n位长度的字符串（例如一个英文单词）作为密钥。设密钥k=k1k2…kn，明文M=m1m2…mn，则加密变换为：Ek(m1,m2,…,mn)=(m1+k1mod26,m2+k2mod26,…,mn+knmod26)维吉尼亚密码举例例2.2设明文为“killthem”密钥为“gun”，试用维吉尼亚密码对明文进行加密。加密密钥：k=gun=(6,20,13)明文对应的数字为1081111197412密钥对应的数字6201362013620相加取余变换后：16224171320106对应的密文是：hcyrnvwg因密文为：hcyrnvwg破解维吉尼亚密码密文为：hcyrnvwgcxgtuhncucvxywgrgt关键是如何确定密钥长度n希尔密码希尔密码：利用矩阵变换来对信息实现加密。数学定义：设m是一个正整数，令M=E=(Z26)m，密钥Km×m={定义在Z26上的m×m矩阵}，其中K的行列式值必须和26互素，否则不存在K的逆矩阵K-1。对任意的密钥Km×m，定义加密/解密变换为Ek(x)=Km×m·xmod26Dk(y)=K-1m×m·ymod26希尔（Hill）密码举例密钥产生：首先决定所用矩阵的大小，譬如是2×211E3