第3章 密码技术概述

复习与回顾信息安全涉及范畴、安全属性需求以及信息安全保障体系结构动态和可适应的信息安全防御模型风险评估、等级保护、安全测评的内容与方法2024/3/202第3章密码技术概述2024/3/203学习目标数据保密通信模型及基本术语对称密码体制及其分类与工作原理公钥密码体制及其工作原理数字签名技术及其特性消息完整性保护及认证如何定义和衡量密码体制的安全性本章介绍密码技术的基本概念、分类、实现和应用原理。内容包括：2024/3/2043.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/205什么是密码术？Cryptography?3.1密码术及发展2024/3/2063.1密码术及发展保密性要求即使非授权者获取了数据副本，他也无法从副本中获得有用的信息。

2024/3/2073.1密码术及发展古典密码北宋曾公亮、丁度等编撰《武经总要》“字验”；公元前405年，斯巴达将领来山得使用了原始的错乱密码；公元前一世纪，古罗马皇帝凯撒曾使用有序单表代替密码；古典密码使用的基本方法置换加密法：将字母的顺序重新排列。替换加密法：将一组字母用其它字母或符号代替。古典密码原理简单，容易遭受统计分析攻击。2024/3/2083.1密码术及发展现代密码1863年普鲁士人卡西斯基著《密码和破译技术》,

1883年法国人克尔克霍夫所著《军事密码学》；20世纪初，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场；第二次世界大战德国的Enigma转轮密码机，堪称机械式古典密码的巅峰之作。1949年美国人香农(C.Shannon)发表论文《保密系统的通信理论》标志现代密码学的诞生。2024/3/2093.1密码术及发展密码学已经发展成一门跨学科的学问，它以信息理论为基础，同时使用大量数学和其它领域的工具，而计算机技术和计算理论又支撑和推动了现代密码学的应用和发展。密码学包括密码编码学和密码分析学两大分支。密码编码学研究如何对信息进行加解密。密码分析学研究如何在不知道密钥的情况对密码进行破译。2024/3/20103.1密码术及发展现代密码学发展过程中的重大事件1976年，美国政府颁布数据加密标准（DES）。1976年，Diffie和Hellman发表论文《密码学的新动向》，开创了公钥密码的新思想。1978年，Rivest，Shamir和Adleman实现了RSA公钥密码体制。1969年，哥伦比亚大学的StephenWiesner首次提出“共轭编码”概念。1984年Bennett和Brassard在此思想启发下，提出量子理论BB84协议。2024/3/20113.1密码术及发展现代密码学发展过程中的重大事件1985年，Miller和Koblitz首次将有限域上的椭圆曲线用到了公钥密码系统中。1989年，Mathews,Wheeler,Pecora和Carroll等人首次把混沌理论使用到序列密码及保密通信理论。2001年，NIST发布高级加密标准AES，替代DES作为商用密码标准。2024/3/20123.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/20133.2数据保密通信模型如何在开放网络中保密传输数据？SecretTransmission?2024/3/20143.2数据保密通信模型2024/3/20153.2数据保密通信模型保密通信系统相关术语明文(Plaintext)：需要安全保护的原始信息/数据，常记为m。所有明文构成明文空间，常记为M。密文(Ciphertext)：原始数据经加密变换得到的数据，常记为c。所有密文构成密文空间，常记为C。加密(Encryption)：c＝Ek1(m)解密(Decryption)：m＝Dk2(c)。密钥(Key)：用于加解密的秘密信息。所有密钥构成密钥空间，常记为K。公众信道：数据公开传递的信道，也称公共信道。秘密信道：代指安全信道，用于传递密钥。2024/3/20163.2数据保密通信模型密码体制(CipherSystem)对于m∈M，k1,k2∈K，有

，五元组（M,C,K,E,D）称为一个密码体制，其中E和D代表具体的密码算法——具体的变换过程或数学方法。可以看出，加密可以看做是将密钥与明文混合变换的过程，而解密是从密文中剥离密钥的过程，因此也称脱密过程。Kerchhoff假设一个密码体制，对于所有密钥，加密和解密算法迅速有效；密码体制的安全性不应该依赖于算法的保密，而仅依赖密钥的保密。2024/3/20173.2数据保密通信模型密码技术、密码体制与密码算法密码技术是利用密码体制实现信息安全保护的技术；密码体制是使用特定密码算法实现信息安全保护的具体方法；密码算法是使用密钥实现数据加解密变换的数学处理过程密码体制分类（根据密钥情况分类）对称密钥密码体制：加密与解密使用相同密钥(单钥)公钥密码体制：加密与解密使用不同密钥(双钥)2024/3/20183.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/20193.3对称密码体制如何使用相同的密钥加/解密数据？SymmetricCryptography?2024/3/20203.3对称密码体制对称密码体制加密密钥与解密密钥存在明显的依赖关系，由其中一个可以很容易推导出另一个。实践中，对称密码体制多使用同一个密钥加密和解密，称为加解密双方共享密钥。对称密码体制也称为单钥密码体制。2024/3/20213.3对称密码体制对称密码体制2024/3/20223.3对称密码体制对称密码体制分类分组密码(Blockcipher)先将明文划分成若干等长的块——分组，如每个分组长64比特、128比特，然后再分别对每个分组进行加密，得到等长的密文分组；解密过程也类似。有些密码体制解密算法与加密算法完全一样，如DES。序列密码(Sequentialcipher)是把明文以位或字节为单位进行加密，一般是与密钥（由密钥种子产生的任意长度的字节流）进行混合（如异或）获得密文序列。也称流密码(Streamcipher)。2024/3/20233.3对称密码体制分组密码设计的两个思想扩散（Diffusion）：即将明文及密钥的影响尽可能迅速地散布到较多的输出密文中，典型操作就是“置换”（Permutation）（如重排字符顺序）。混淆（Confusion）：目的在于使作用于明文的密钥和密文之间的关系复杂化，使得明文和密文、密文和密钥之间的统计相关性极小化，从而使统计分析攻击不能奏效。混淆通常采用“代换”（Substitution）操作。2024/3/20243.3对称密码体制Feistel网络结构分组密码一般采用多次相同的迭代操作（轮操作），实现明文与密钥充分地混淆和扩散。许多分组密码体制采用了Feistel网络结构。Feistel结构保证了无论轮函数F是一个如何复杂的变换过程，都不影响加密与解密过程的一致性，实现加密过程的可逆性。F具有良好的非线性性，增加密码分析的难度。分组密码通过多轮处理增加了混淆效果，每一轮使用不同的轮密钥（由初始密钥扩展得到）。2024/3/2025Feistel网络结构3.3对称密码体制2024/3/20263.3对称密码体制序列密码(流密码)将明文流和密钥流混合(一般为简单的按字节或比特位异或)产生密文流。流密码使用一个“种子密钥”产生密钥流(理论上可以无限长度)，通信双方共享这个“种子密钥”，按相同方式产生密钥流。2024/3/20273.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/20283.4公钥密码体制如何方便地管理和使用密钥？AsymmetricCryptography?2024/3/20293.4公钥密码体制公钥密码体制有两个完全不同的密钥，而且其中一个可以公开（常用于加密），另一个需要保密（常用于解密）。因此，也称为双钥密码体制。公钥密码就是一种陷门单向函数f。即：对f定义域中的任意x都易于计算f(x)，而对f值域中几乎所有的y，即使f为已知时要计算f-1(y)在计算上也是不可行的。当给定某些辅助信息（陷门）时则易于计算f-1(y)。此时称f是一个陷门单向函数，辅助信息（陷门信息）作为秘密密钥。2024/3/20303.4公钥密码体制公钥加密体制2024/3/20313.4公钥密码体制公钥密码体制一般要借助某个特殊的数学问题，如数论中的大数分解、离散对数等数学难解问题，构造单向函数，因此，这类密码的安全强度取决于它所依据的问题的计算复杂度。目前的公钥密码体制主要有两类：基于大整数因子分解问题的公钥密码体制，如RSA体制基于离散对数问题的公钥密码体制，如ElGmal密码体制、椭圆曲线密码体制。2024/3/20323.4公钥密码体制一个公钥密码体制是一个七元组(M,C,SK,PK,Gen,Enc,Dec)，其中明文空间M(Message消息，或Plaintext)，需要加密的消息表示为m，m∈M。密文空间C(Ciphertext)，明文m经过加密变换为密文c，c∈C。私钥空间SK(SecretKey)与公钥空间PK(PublicKey)。2024/3/20333.4公钥密码体制一个公钥密码体制是一个七元组(M,C,SK,PK,Gen,Enc,Dec)，其中密钥生成算法Gen(KeyGenerationAlgorithm)，从私钥空间中随机选取一个私钥kpri(PrivateKey)，kpri∈SK，算法Gen输出私钥kpri和对应的公钥kpub(PubklicKey)，kpub∈PK。加密算法Enc(EncryptionAlgorithm)，给定明文m，m∈M，输出密文c，c=Enc(m,

kpub)，c∈C。解密算法Dec(DecryptionAlgorithm)，给定密文c，c∈C，输出明文m，m=Dec(c,kpri)，m∈M。2024/3/20343.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/20353.5数字签名如何在电子世界中实现签名？Digital

Signature?2024/3/20363.5数字签名一个假想的例子：路人甲要通过网络传输一份文档给路人乙，乙接收到这份文档，乙能确认这份文档的真实性吗（确实来自于甲，而不是其他人冒充甲发送的）？乙能确定这份文档的正确性码（在传输过程中没有被篡改）？甲如果否认曾经发送过该文档（实际上确实是甲发送的）怎么办？2024/3/20373.5数字签名数字签名必须使用某些对于签名者来讲具有唯一性的信息，以防止签名和伪造和否认。数字签名的生成与验证都必须是相对容易的，而且在出现纠纷时可以通过可信的第三方TTP仲裁。公钥密码技术为数字签名提供了理论依据：公钥密码体制中的私钥是私有的、保密的，其他人无法获得，可以作为持有者的唯一性信息，作为持有者身份的唯一性表示。2024/3/20383.5数字签名数字签名机制使用公钥密码技术，使得消息接收者相信接收的消息来自声称的消息发送者（消息主体的识别与鉴别），并信任该消息（消息被正确地传递，没有被篡改——完整性保护），同时消息签名者不能否认签发了该消息（不可否认性保护）。2024/3/20393.5数字签名数字签名机制2024/3/20403.5数字签名一个数字签名体制是一个七元组(M,S,SK,PK,Gen,Sig,Ver)，其中明文空间M(Message消息，或Plantext)，对应需要签名的消息表示为m，m∈M。密文空间S(Signature)，明文m经过密码变换输出密文s，s∈S。私钥空间SK(SecretKey)，所有可能的私钥构成。公钥空间PK(PublicKey)，所有可能的公钥构成。2024/3/20413.5数字签名一个数字签名体制是一个七元组(M,S,SK,PK,Gen,Sig,Ver)，其中密钥生成算法Gen(KeyGenerationAlgorithm)，从可能的私钥空间中随机选取一个私钥kpri(PrivateKey)，kpri∈SK，算法Gen输出私钥kpri和对应的公钥kpub(PublicKey)，kpub∈PK。签名算法Sig(SigningAlgorithm)，给定明文m，m∈M，输出签名s，s=Sig(m,kpri)，

s∈S。验证算法Ver(VerifyingAlgorithm)，给定签名s，s∈S，验证签名v=Ver(s,kpuk)，输出正确或错误的结果，v∈{True,False}。2024/3/20423.5数字签名数字签名机制的工作过程2024/3/20433.5数字签名密码学哈希(Hash)函数：密码学哈希函数将任意长度输入转换为特定长度输出，典型的算法如MD5、SHA、SHA-256等。一个密码学哈希函数H应具备以下特性单向性：给定一个输入m，容易计算哈希值h=H(m)；但反过来，给定一个哈希值h，计算原像m是困难的。抗碰撞性：已知一个哈希值h=H(m)，找出另一个m’，使得H(m’)等于h是困难的；同时任意找到两个值c1、c2，使得这两个数的哈希值相同，即H(c1)=H(c2)，是困难的。2024/3/20443.5数字签名数字签名可以实现3个安全属性鉴别性：实体和消息的真实性认证完整性不可否认性2024/3/20453.5数字签名数字签名与消息加密组合方案2024/3/20463.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/20473.6消息完整性保护如何保护通信数据的完整性？Digital

Signature?2024/3/20483.6消息完整性保护消息完整性的含义影响消息完整性的因素偶发因素人为破坏（恶意攻击）消息完整性保护循环冗余校验码(CRC:CyclicRedundancyCheck)?数字签名?消息认证码(MAC:MessageAuthenticationCode)2024/3/20493.6消息完整性保护消息认证码MAC——带密码的摘要2024/3/20503.6消息完整性保护IETFRFC2104HMAC:Keyed-HashingforMessageAuthentication带密钥的哈希函数消息认证：一种MAC构造标准HMAC＝H((KXORopad)||H((KXORipad)||m)消息认证码的安全问题MAC的计算可以直接使用对称密码算法或公钥密码算法，MAC的安全性完全依赖于所采用密码算法的安全性。HMAC通信双方需要事先共享密钥K或口令，HMAC的安全性依赖于Hash函数的安全性。2024/3/20513.6消息完整性保护一个基于HMAC的应用实例，使用HMAC完成一个典型的“质询/响应（Challenge/Response）”身份认证过程：客户端向服务器发出认证请求，如一个登录请求（假设是浏览器的GET请求）。服务器返回一个质询(Challenge)，一般为一个随机值，并在会话中记录这个随机值。客户端将该随机值作为输入字符串，与用户口令一起进行HMAC运算，然后提交计算结果给服务器——响应(Response)。服务器读取用户数据库中的用户口令，并使用步骤2中发送的随机值做与客户端一样的HMAC运算，然后与用户返回的响应比较，如果结果一致则验证了用户是合法的。2024/3/20523.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/20533.7认证如何验证主体的身份或消息地真实性？Digital

Signature?2024/3/20543.7认证认证的含义认证也称鉴别(Authentication)，是证明某种真实性、合法性、有效性或正确性的过程。也就是验证者(Verifier，一般为接收者)对认证者(Authenticator，也称证明者、示证者，一般为发送方)声称的某种真实性、合法性、有效性或正确性的确认方法和过程。认证的对象包括两类实体身份的真实性消息的真实性2024/3/20553.7认证实体身份真实性认证实体包括人和设备，即回答“是某人吗？”、“是某台设备吗？”、“是某个软件吗？”。对实体认证的目的往往是为了决定将什么样的特权(Privilege)授权(Authorizing)给该实体。消息真实性认证消息自身（来源、内容）的认证，即回答“这个消息真实吗？”、“这个消息正确吗？”，确认这个消息是合法用户生成的且在传递过程中没有被篡改。消息的顺序性和时间性认证。2024/3/20563.7认证认证机制与技术认证机制知道的东西：口令、密钥拥有的东西：生物特征、令牌认证技术数字签名消息认证码认证与完整性保护使用许多共同的技术和方法，但安全目标不一样。2024/3/20573.7认证零知识证明：一种有趣的“魔咒”认证方法洞穴问题：如图有一个洞穴，在洞穴深处C点与D点间有一道门，设P知道打开该门的咒语，其他人不知道咒语无法打开此门。那么现在P如何向验证者V证明他知道咒语但又不告诉V咒语是什么呢？2024/3/20583.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析目录2024/3/20593.8计算复杂理论如何定义一个密码系统是安全的？Digital

Signature?2024/3/20603.8计算复杂理论1.安全的定义只有相对的安全，没有绝对的安全。安全的意义在于保护信息安全所需的代价与信息本身价值的对比，因此信息安全保护是一种效能的折衷。安全的三个层次理论安全性（也称无条件安全）：如果具有无限计算资源的密码分析者也无法破译一个密码系统则称该密码系统是理论安全的。2024/3/20613.8计算复杂理论1.安全的定义安全的三个层次可证明安全性：如果从理论上可以证明破译一个密码系统的代价/困难性不低于求解某个已知的数学难题，则称该密码系统是可证安全的。计算安全性：如果使用已知的最好算法和利用现有的（或密码系统生命周期内）最大的计算资源仍然不可能在合理的时间完成破译一个密码系统，则称该密码系统是计算安全的。注：可证明安全性与计算安全性也称为实际安全性。2024/3/20623.8计算复杂理论2.安全的度量密码分析所需的计算量是密码体制安全性的衡量指标。计算复杂度理论用n表示问题的大小或系统输入的长度，则运算所需的时间T和存储所需的空间S都是n的函数，记为T(n)和S(n)，称为时间复杂度和空间复杂度。

时间复杂度与空间复杂度可以互相转化，即可以“空间”换“时间”。2024/3/20633.8计算复杂理论2.安全的度量计算复杂度理论如果T(n)＝O(nc

)，且c>0，则称该算法的运算时间是多项式阶的。一般认为多项式阶时间复杂度是计算上可行的。如果T(n)＝O(n

p(n))，p(n)是关于n的一个多项式，则称该算法运算时间是指数阶的。一般认为指数阶时间复杂度是计算上不可行的。如果破译一个密码体制所需的时间是指数阶的，则该密码体制在计算上是安全的，因而也是实际安全的。2024/3/20643.8计算复杂理论3.计算理论确定性算法与非确定性算法确定性算法的每一步操作结果都是确定的，计算时间也是确定的。非确定性算法的某些步骤操作结果是不确定的，在所有使算法成功操作的序列中，运行时间最短的序列所需时间就是该非确定性算法的计算时间。用确定算法可以在多项式时间内求解的问题称为P问题。多项式时间内可用非确定性算法求解的问题称为NP问题。P＝NP？或者P≠NP？2024/3/20653.8计算复杂理论3.计算理论如果一个问题X可以在多项式时间内用确定性算法转化为问题Y，而Y的解可以在多项式时间内用确定性算法转化为X的解，则称问题X可以规约化为问题Y。因此，如果某类NP问题中任何一个问题可以规约为问题Y，而且Y本身就是NP问题，则称Y是一个NP完全问题，记为NPC。如果能够找到一个计算序列作为解密算法，那么密码分析者在不知道计算序列的情况下求解问题（称为客观求解）在计算上是不可行的。因此，可以基于NP问题构造密码体制。2024/3/2066目录3.1密码术及发展3.2数据保密通信模型3.3对称密码体制3.4公钥密码体制3.5数字签名3.6消息完整性保护3.7认证3.8计算复杂理论3.9密码分析2024/3/20673.9密码分析如何攻击密码系统？