密码基本概念、分类、实现和应用原理

1、学习目标数据保密通信模型及基本术语对称密码体制及其分类与工作原理公钥密码体制及其工作原理数字签名技术及其特性消息完整性保护及认证如何定义和衡量密码体制的安全性本章介绍密码基本概念、分类、实现和应用原理。23.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析目 录3什么是密码术？4Cryptography?3.1 密码术及发展保密性要求即使非授权者获取了数据副本，他也无法从副本中获得有用的信息。53.1 密码术及发展宋曾公亮、丁度等编撰武经总要“字验”公元前405年，斯巴达的将领

2、来山得使用了原始的错乱密码；公元前一世纪，古罗马皇帝凯撒曾使用有序的单表代替密码；1863年普鲁士人卡西斯基所著密码和破译技术1883年法国人克尔克霍夫所著军事密码学20世纪初，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。第二次世界大战德国的Enigma密码转轮机，堪称机械式古典密码的巅峰之作。63.1 密码术及发展1976年美国政府颁布数据加密标准（DES）。1976年Diffie和Hellman发表的文章密码学的新动向1978年R.L.Rivest，A.Shamir和L.Adleman实现了RSA公钥密码体制1969年哥伦比亚大学的Stephen Wiesn

3、er首次提出“共轭编码” 概念。1984年H. Bennett 和G. Brassard在此思想启发下，提出量子理论BB84协议1985年Miller和Koblitz首次将有限域上的椭圆曲线用到了公钥密码系统中。1989年R.Mathews, D.Wheeler, L.M.Pecora和Carroll等人首次把混沌理论使用到序列密码及保密通信理论。2001年NIST发布高级加密标准AES，替代DES作为商用密码标准。73.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析目 录8

4、9如何在开放网络中保密传输数据？Secret Transmission?103.2 数据保密通信模型对于mM，k1,k2K，有 ，五元组（M,C,K,E,D）称为一个密码体制，其中E和D代表具体的密码算法具体的变换过程或数学方法。可以看出，加密可以看做是将密钥与明文混合变换的过程，而解密是从密文中剥离密钥的过程，因此也称脱密过程。Kerchhoff假设：一个密码体制，对于所有的密钥，加密和解密算法迅速有效；密码体制的安全性不应该依赖于算法的保密，而仅依赖密钥的保密。113.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.

5、6 认证3.7 计算复杂理论3.8 密码分析目 录1213如何使用相同的密钥加/解密数据？Symmetric Cryptography?14对称密码体制3.3 对称密码体制对称密码体制分类：分组密码先将明文划分成若干等长的块分组，如每个分组长64比特、128比特，然后再分别对每个分组进行加密，得到等长的密文分组。解密过程类似，有些密码算法解密算法与加密算法完成一样，如DES。序列密码是把明文以位或字节为单位进行加密，一般是与密钥（如由密钥种子产生的任意长度的字节流）进行混合（最简单地进行异或运算）获得密文序列。153.3 对称密码体制两个思想：扩散（Diffusion）：即将明文及密钥的影响尽

6、可能迅速地散布到较多的输出密文中，典型操作就是“置换”（Permutation）（如重新排列字符）。混乱（Confusion）：目的在于使作用于明文的密钥和密文之间的关系复杂化，使得明文和密文、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。混乱通常采用“代换” （Substitution）操作。1617Feistel网络结构3.3 对称密码体制序列密码（流密码）将明文流和密钥流混合（一般为简单的按字节或比特位异或）产生密文流。流密码使用一个“种子密钥”产生密钥流（理论上可以是无限长度），通信双方共享这个“种子密钥”，按相同方式产生密钥流。183.1 密码术及发展3.2 数据保

7、密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析目 录1920如何方便地管理和使用密钥？Asymmetric Cryptography?3.4 公钥密码体制21公钥加密体制3.4 公钥密码体制公钥密码就是一种陷门单向函数f。即：（1）对f的定义域中的任意x都易于计算f(x)，而对f的值域中的几乎所有的y，即使当f为已知时要计算f-1(y)在计算上也是不可行的。（2）当给定某些辅助信息（陷门信息）时则易于计算f-1(y)。此时称f是一个陷门单向函数，辅助信息（陷门信息）作为秘密密钥。这类密码一般要借助特殊的数

8、学问题，如数论中的大数分解、离散对数等数学难解问题，构造单向函数，因此，这类密码的安全强度取决于它所依据的问题的计算复杂度。223.4 公钥密码体制一个公钥密码体制是一个七元组(M,C,SK,PK,Gen,Enc,Dec)：明文空间M（Message消息，或Plantext），需要加密的消息表示为m，mM。密文空间C（Ciphertext），明文m经过加密变换为密文c，cC。私钥空间SK（Secret Key），所有可能的私钥构成。公钥空间PK（Public Key），所有可能的公钥构成。密钥生成算法Gen（Key Generation Algorithm），从可能的私钥空间中随机选取一个私钥

9、kpri（Private Key），kpriSK，算法Gen输出私钥kpri和对应的公钥kpub（Pubklic Key），kpubPK。加密算法Enc（Encryption Algorithm），给定明文m，mM，输出密文c，c=Enc(m, kpub)，cC。解密算法Dec（Decryption Algorithm），给定密文c，cC，输出明文m，m=Dec(c, kpri)，mM。233.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析目 录2425如何在电子世界中实现签

10、名？DigitalSignature?3.5 数字签名一个假想的例子：某人甲要通过网络传输一份文档给乙，乙接收到这份文档，乙能确认这份文档的真实性吗（确实来自于甲，而不是其他人冒充甲发送的）？乙能确定这份文档的正确性码（在传输过程中没有被篡改）？甲如果否认曾经发送过该文档（实际上确实是甲发送的）怎么办？2627数字签名机制3.5 数字签名一个数字签名机制是使用一种公钥密码，使得一个消息接收者相信接收的消息来自声称的消息发送者（消息主体的识别与鉴别），并信任该消息（消息被正确地传递，没有被篡改完整性保护），同时消息签名者不能否认签发了该消息（不可否认性保护）。283.5 数字签名一个数字签名体制

11、是一个七元组(M, S, SK, PK, Gen, Sig, Ver)：明文空间M（Message消息，或Plantext），对应需要签名的消息表示为m，mM。密文空间S（Signature），明文m经过密码变换输出密文s，sS。私钥空间SK（Secret Key），所有可能的私钥构成。公钥空间PK（Public Key），所有可能的公钥构成。密钥生成算法Gen（Key Generation Algorithm），从可能的私钥空间中随机选取一个私钥kpri（Private Key），kpriSK，算法Gen输出私钥kpri和对应的公钥kpub（Pubklic Key），kpubPK。签名算法S

12、ig（Signing Algorithm），给定明文m，mM，输出签名s，s=Sig(m, kpri)， sS。加密算法Ver（Verifying Algorithm），给定签名s，sS，验证签名v=Ver(s, kpuk)，输出正确或错误的结果，vTrue,False。2930数字签名机制3.5 数字签名密码学哈希函数：密码学哈希函数将任意长度输入转换为特定长度输出，典型的算法如MD5、SHA、SHA-256等。一个密码学哈希函数H应具备以下特性：单向性：给定一个输入m，容易计算哈希值h=H(m)；但反过来，给定一个哈希值h，计算原像m是困难的。抗碰撞性：已知一个哈希值h=H(m)，找出另一

13、个m，使得H(m)等于h是困难的；同时任意找到两个值c1、c2，使得这两个数的哈希值相同，即H(c1)= H(c2)，是困难的。31带签名加密封装323.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析目 录3334如何保护通信数据的完整性？DigitalSignature?3.5 消息完整性保护循环冗余校验码（Cyclic Redundancy Check，CRC）?数字签名?353.5 消息完整性保护消息认证码（Message Authentication Code，MAC

14、）带密码的摘要363.5 消息完整性保护一个基于HMAC的应用实例，使用HMAC完成一个典型的“质询/响应”（Challenge/Response）身份认证过程：（1）客户端向服务器发出认证请求，如一个登录请求（假设是浏览器的GET请求）。（2）服务器返回一个质询（Challenge），一般为一个随机值，并在会话中记录这个随机值。（3）客户端将该随机值作为输入字符串，与用户口令一起进行HMAC运算，然后提交计算结果给服务器响应（Response）。（4）服务器读取用户数据库中的用户口令，并使用步骤2中发送的随机值做与客户端一样的HMAC运算，然后与用户返回的响应比较，如果结果一致则验证了用户是

15、合法的。373.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析目 录3839如何验证主体的身份或消息地真实性？DigitalSignature?3.6 认证认证（也称鉴别，Authentication）是证明一个对象身份的过程，换句话讲，指验证者（Verifier，一般为接收者）对认证者（Authenticator，也称证明者、示证者，又记Certifier，一般为发送方）身份的真实性的确认方法和过程。403.6 认证对消息自身的认证，即回答“这个消息真实吗？”、“这个消息正

16、确吗？”，换句话讲，确认这个消息是合法用户生成的且在传递过程中没有被篡改。41消息发送实体认证，人或设备，即回答“是某人吗？”、“是某台设备吗？”、“是某个软件吗？”。对实体认证的进一步目的，往往是为了决定将什么样的特权（Privilege）授权（Authorizing）给该身份的实体。3.6 认证零知识证明一种有趣的“魔咒”认证方法洞穴问题：如图有一个洞穴，在洞穴深处C点与D点间有一道门，设P知道打开该门的咒语，其他人不知道咒语无法打开此门。那么现在P如何向验证者V证明他知道咒语但又不告诉V咒语是什么呢？423.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制

17、3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析目 录4344如何定义一个密码系统是安全的？DigitalSignature?3.7 计算复杂理论理论安全性（也称无条件安全）：如果具有无限计算资源的密码分析者也无法破译一个密码系统（密码体制），则称该密码系统是理论安全的。可证明安全性：如果从理论上可以证明破译一个密码系统的代价（困难性）不低于求解某个已知的数学难题，则称该密码系统是可证安全的。计算安全性：如果使用已知的最好的算法和利用现有的（或密码系统生命周期内）最大的计算资源仍然不可能在合理的时间完成破译一个密码系统，则称该密码系统是计算安全的。451.

18、 安全的定义3.7 计算复杂理论运算所需的时间T和存储所需的空间S，它们都是n的函数，记为T(n)和S(n)，也称为时间复杂度和空间复杂度。如果 ，其中c0，那么称该算法运算的时间是多项式阶的。如果 ，其中p(n)是关于n的一个多项式，则称该算法运算时间是指数阶的。462. 安全的度量3.7 计算复杂理论使用确定算法可以在多项式时间内求解的问题称为P问题。在多项式时间内可以用非确定性算法求解的问题称为NP问题。如果一个问题X可以在多项式时间内用确定性算法转化为问题Y，而Y的解可以在多项式时间内用确定性算法转化为X的解，则称问题X可以规约化为问题Y。因此，如果某类NP问题中任何一个问题可以规约为

19、问题Y，而且Y本身就是NP问题，则称Y是一个NP完全问题，记为NPC。如果能够找到一个计算序列作为解密算法，那么密码分析者在不知道计算序列的情况下求解问题（称为客观求解）在计算上是不可行的。473. 计算理论目 录3.1 密码术及发展3.2 数据保密通信模型3.3 对称密码体制3.4 公钥密码体制3.5 数字签名3.5 消息完整性保护3.6 认证3.7 计算复杂理论3.8 密码分析4849如何攻击密码系统？DigitalSignature?3.8 密码分析惟密文攻击（Ciphertext only）：破译者已知的东西只有两样：加密算法、待破译的密文。已知明文攻击（Known plaintext）：破译者已知的东西包括：加密算法和经密钥加密形成的一个或多个明文-密文对，即知道一定数量的密文和对应的明文。选择明文攻击（Chosen plaintext）：破译者除了知道加密算法外，他还可以选定明文消息，并可以知道该明文对应的加密密文。例如，公钥密码体制中，攻击者可以利用公钥加密他任意选定的明文。503.8 密码分析选择密文攻击(Cho