密码学原理与应用汇编

1、 内容 一、密码学概论 1. 密码体制及其分类 2. 密码学发展简史 3. 密码分析概念和原理 二、密码编码学基本原理 1. 对称密码概念与典型算法：Feistel结构、DES等 2. 公钥密码概念与典型算法：RSA等 3. 消息认证概念与典型算法：MD5等 三、密码学典型应用 1. 加密设备的部署 2. 密钥管理与密钥分配 3. 数字证书与PKI 一、密码学概论 1. 密码体制及其分类 2. 密码学发展简史 3. 密码分析概念和原理 密码体制及其分类学科内涵 学科内涵 研究如何隐秘地传递信息的学科 对信息以及其传输的数学性研究 与数学、信息论、计算机科学等紧密相关 是信息安全（认证、访问控制

2、等技术）的基础和核心 其首要目的是隐藏信息的涵义，而不是隐藏信息的存在 密码体制及其分类基本术语 密码学（Cryptology） 泛指研究保密通信的学科，包括设计和破 译两个方面 密码编码学（Cryptography） 研究如何达到信息秘密性、鉴别性等的科 学，研究编码系统 密码编码者（cryptographer） 密码分析学（Cryptanalysis） 研究如何破解密码系统，或伪造信息使密码 系统失效的科学 密码分析者（cryptanalyst） 加密和破译既相互对立又密切相关，二者的相互作用促进了密码 学的发展 密码体制及其分类密码体制 密码系统五元组（M，C，K，E，D） 明文空间 M

3、 密文空间 C 密钥空间 K 加密算法 E 解密算法 D 密码体制及其分类 明文(plaintext)原始的消息。 加密算法(encryption algorithm) 对明文进行各种代替和变换的算法， 加密算法的输入为明文和密钥，输出为密文。 密文(ciphertext) 加密后的消息。 解密算法(decryption algorithm) 加密算法的逆运算，输入密文和密 钥，输出原始明文。 密钥(secret key) 加密算法的输入，密钥独立于明文和算法，算法 根据所用的特定密钥而产生不同的输出。 密码体制及其分类三种分类(1) 明文转换为密文的运算类型 代替(Substitution)

4、 ：明文中每个元素映射成另一个元素 置换(Transposition) ：将明文元素重新排列 基本要求是不允许信息丢失（即可逆） 大多数密码体制使用多层代替和置换（即乘积密码系统） 密码体制及其分类三种分类(2) 所用的密钥数 对称密码：收发双方使用相同的密钥（又称为单钥或传统密码） 非对称密码：收发双方使用不同的密钥（又称为双钥或公钥密码） 密码体制及其分类三种分类(3) 明文处理方式 分组密码：每次处理输入的一组元素，相应地输出一组元素 流密码：连续地处理输入元素，每次输出一个元素（又称为序列密码） 密码学发展简史 密码学发展史简图 密码学发展简史 密码学发展两大阶段 古典密码阶段(194

5、9) ：特定应用领域（军事、政治、外交） 现代密码学阶段(1949)：密码技术成为一门学科 著名论文: Communication theory of secrecy systems, Bell Syst. Tech. J.,Volume 28, 656-715, 1949. 密码学发展简史古典密码 古典密码 密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段出现，针对的是字符 简单的密码分析手段出现 主要特点：数据的安全基于算法的保密 密码学发展简史古典密码 二十世纪早期密码机 密码学发展简史现代密码 现代密码发展初期（1949-1975） 计算机使得基于复杂计算的密

6、码成为可能 相关技术的发展 1949年Shannon的The Communication Theory of Secret Systems 1967年David Kahn的The Codebreakers 1971-73年IBM Watson实验室的Horst Feistel等几篇技术报告 主要特点：数据的安全基于密钥而不是算法的保密 密码学发展简史现代密码 现代密码公钥密码学（1976-） W. Diffie和E. M. Hellman提出公钥密码的思想(1976) 著名论文：W. Diffie and M. E. Hellman, New direction in cryptography

7、, IEEE Tran. On Information Theory, IT-22, (6), 644-654,1976. 1977年Rivest,Shamir & Adleman提出了RSA公钥算法 90年代逐步出现椭圆曲线等其他公钥算法 主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能 密码学发展简史现代密码 现代密码系统设计要求 系统即使达不到理论上是不可破的，也应当为实际上不可破的。就是说， 从截获的密文或某些已知的明文密文对，要决定密钥或任意明文，在计 算上是不可行的 系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥保密。 这是著名的Kerckhoff原则 加

8、密和解密算法适用于所有密钥空间中的元素 系统便于实现和使用 密码学发展简史现代密码 现代密码密码技术的商用化（1977-） 1977：美国国家标准局(现美国家标准与技术研究所NIST)颁布对称密码算 法数据加密标准DES (Data Encryption Standard) 80年代出现“过渡性”的“Post DES”算法,如 IDEA、RCx、CAST等 90年代对称密钥密码进一步成熟，Rijndael、RC6、MARS、Twofish、 Serpent等出现 2001年Rijndael成为DES的替代者 密码分析概念与原理基本概念 非授权者通过各种办法（如搭线窃听电磁信号等）来窃取机密信

9、息，称其为截收者。 截收者虽然不知道系统所用的密钥，但通过分析可能从截获的密 文推断出原来的明文或密钥，这一过程称为密码分析。 研究如何从密文推演出明文或密钥的科学称为密码分析学。 破译者使用的策略取决于加密方案的固有性质以及破译者掌握的 信息。 密码分析概念与原理主要分析方法 密码分析概念与原理主要分析方法 传统破译法穷举破译法 方法： 对截获的密文依次用各种可能的密钥试译，直到获得有意义的明文； 或者利用对手已注入密钥的加密机（比如缴获得到），对所有可能的 明文依次加密直到得出与截获的密文一致的密文。 对策：将密钥空间和明文空间设计得足够大。 密码分析概念与原理主要分析方法 传统破译法数学

10、分析法 确定性分析法 方法：利用密文和部分明文等已知量以数学关系式表示出所求未知量（如密钥等）， 然后计算出未知量。 对策：设计具有坚实数学基础和足够复杂的加密函数 统计分析法 方法：密码破译者对截获的密文进行统计分析，找出其统计规律或特征，并与明文 空间的统计特征进行对照比较，从中提取出密文与明文间的对应关系，最终确定密 钥或明文。 对策：扰乱密文的语言统计规律 密码分析概念与原理主要分析方法 边信道攻击法（side channel attack） 利用密码系统实现时泄漏的额外信息，推导密码系统各种的秘密 参数，也被称为“侧信道攻击方法”、“物理分析方法” 密码算法执行器件（加密芯片）的功耗

11、 密码算法各步骤执行的时间度量 电磁辐射 计算错误 与具体实现有关，非通用的分析方法，但更有效、更强大 密码分析概念与原理密码分析 当加密方案产生的密文满足下面条件之一或全部条件时，则称该 方案是计算安全的(computationally secure) 破解密文的代价超出被加密信息的价值 破解密文需要的时间超出信息的有用寿命 问题的关键是，我们很难定量的评估成功破译密文需要付出的努 力。但是，假设算法没有内在的数学弱点，那么就只剩下穷举攻 击方法了，我们就能够对其成本和时间做出合理的评估。 密码分析概念与原理密码分析 穷举搜索密钥需要的平均时间 穷举方法尝试所有可能的密钥直到把密文翻译成可解

12、的明文。平均而言， 一般需要尝试所有可能密钥的一半才能成功。 下面的表格给出了不同密钥长度所需的时间 二、密码编码学基本原理 1. 对称密码概念与典型算法：Feistel结构、DES等 2. 公钥密码概念与典型算法：RSA等 3. 消息认证概念与典型算法：MD5等 对称密码概念与典型算法概念 对称密码体制（Symmetric System） 传统密码算法（又称为单密钥算法） 加密密钥和解密密钥相同，或从一个易于推出另一个 能加密就能解密，加密能力和解密能力是结合在一起的，开放性差 如：DES、IDEA、RC5、AES等算法 对称密码概念与典型算法概念 对称密码体制 优点： 算法多、速度快、安全

13、性好 缺点： 密钥更换、传递和交换需要可靠信道 如有N用户，则需要C=N(N-1)/2个密钥，N很大时，秘钥管理困难 不能实现数字签名 对称密码概念与典型算法概念 对称密码体制的细分 根据明文处理方式，可以分为： 分组密码（block cipher) 将明文分成固定长度的组，用同一密钥和算法对每 一块加密，输出也是固定长度的密文。如DES、IDEA、AES等 流密码（stream cipher) 又称序列密码。流密码每次通过输出密钥流序列加 密(通常是模2加)一位或一字节的明文。如A5、E0 、RC4等 对称密码概念与典型算法分组密码典型算法 DES (Data Encryption Stan

14、dard,数据加密标准) DES也称为DEA (Data Encryption Algorithm,数据加密算法)； 1972年，IBM设计完成； 1975年，IBM发布该算法的详细内容； 1976年，美国联邦政府采用该算法，成为从二十世纪80年代到二十世纪 末事实上的对称加密标准； 采用56位密钥（64位，其中每个字节一个奇偶校验位），64位明文； 共进行16轮加密操作。 Feistel网络示意图 Feistel加密结构 输入是分组长为2w的明文和一个密钥K。将每组明文分成左 右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以 产生密文分组。其第i轮迭代的输入为前一轮输出的函数：

15、其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各 轮子密钥彼此不同而且与K也不同。 1 11, ii iiii LR RLF RK Feistel加解密过程 DES加密过程加密过程 密文（64bits） IP置换（64bits） L0(32bits)R0(32bits) L1=R0R1=L0 f(R0,k1) fki+ 16轮同样运算 L16 + R16=L15 f(R15,ki)+ IP-1置换（64bits） 明文（64bits） 对称密码概念与典型算法分组密码典型算法 IDEA(International Data Encryption Algorithm,国际数据加密算法) 1

16、990年提出，1992年确定 IDEA受专利保护 应用于PGP（Pretty Good Privacy） 分组为64位，密钥为128位，52个子密钥，每个子密钥16位 8轮输出置换，每轮使用6个子密钥 过程与DES相似，但是相对简单一些 对称密码概念与典型算法分组密码典型算法 AES(Advanced Encryption Standard,高级加密标准) 虽然到目前为止，尚没有致命的攻击能够破解DES（目前大多数的破解都是 针对DES密钥长度太短来破解） 但是已经影响到了DES密码体制的安全。 1997年4月15日，美国国家标准技术研究所（NIST）发起征集高级加密标准 （Advanced

17、Encryption Standard,AES）的活动，活动目的是确定一个非保密 的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加 密标准。 1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作 为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。 对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长 度为128比特、密钥长度为128/192/256比特。 对称密码概念与典型算法分组密码典型算法 AES(Advanced Encryption Standard,高级加密标准) 1998年8月12日，在首届AES会议上

18、指定了15个候选算法。 1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是 RC6，Rijndael，SERPENT，Twofish和MARS。 2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进 行了讨论。 2000年10月2日，NIST宣布了获胜者Rijndael算法。 2001年11月出版了最终标准FIPS PUB197。 对称密码概念与典型算法分组密码典型算法 AES的特点 非Feistel结构 采用对称和并行结构算法的实现更加灵活 适合于现代处理器，也可在智能卡上实现 AES每轮主要包括四个步骤 字节代替 移位行（置换） 混合列（有限域

19、上算术运算） 轮密钥加（与部分密钥异或） 对称密码概念与典型算法序列密码典型算法 RC4算法是由Ron Rivest于1987年为RSA公司设计的一种可变密钥长 度（1-256B）的序列密码。 广泛应用于商业密码产品中。软件实现速度快，有广泛应用，如 无线网络WEP、WAP，BT protocol encryption，Microsoft Point-to- Point Encryption，SSL (optionally)，Remote Desktop Protocol， Kerberos (optionally) 该算法的速度可以达到普通分组加密的10倍左右，且具有很高级 别的非线性。 对

20、称密码概念与典型算法 非对称密码概念与典型算法概念 非对称（公钥）密码体制 加密密钥和解密密钥不同，一个用于加密，一个用于解密，且 从一个密钥导出另一个密钥是计算上不可行的 非对称密码概念与典型算法公钥密码体制简介 1976年Diffie 和 Hellman在New Directions in Cryptography中提 出了非对称密钥密码 非对称密码概念与典型算法公钥密码体制简介 加密与解密由不同的密钥完成 加密： 解密： 知道加密算法，从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以作为加密而另一个用作解密 XEYYX KU : XEDYDXXY KUKRKR : 非对

21、称密码概念与典型算法公钥密码体制简介 保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方 不需要交换密钥就可以实现保密通信 非对称密码概念与典型算法公钥密码体制简介 签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个 用户对数据加密而使多个用户解读 非对称密码概念与典型算法公钥密码体制简介 签名保密 XDEZBA ab KRKU : XZDEB ba KRKU : 非对称密码概念与典型算法公钥密码体制简介 优点：优点： 加密能力与解密能力是分开的 可满足不相识的人之间保密通信，适合网络应用 需要保存的密钥量大大减少，N个用户只需要N个 可以实现用户身份的确认 缺点：缺点： 速度较慢

22、、密钥长(通常是1024比特以上) 非对称密码概念与典型算法RSA算法简介 Ron Rivest, Adi Shamir, Leonard Adleman于1977年发明 第一个非对称密码算法 安全性基于大数分解的难题 非对称密码概念与典型算法RSA算法简介 RSA安全性基于大数分解的难题 产生一对大素数很容易 求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难 公钥和私钥经过一对大素数运算而来，破解算法的难度等价于分解这两 个大素数的乘积 非对称密码概念与典型算法RSA算法描述 1）取两个随机大宿舍p和q (保密) 2）计算公开的模数n=p*q (公开） 3）计算秘密的欧拉函数欧

23、拉函数(n)=(p-1)(q-1) (保密) 4）随机选择整数e(0e(n)，满足e和(n)互素(公开e，加密密钥) 5）计算d，使得de1 mod (n) (保密d，解密密钥） 6）公钥为(n,e),私钥为(n,d) 7）将明文x加密得密文y，y=xe (mod n) 8）密文y解密得明文x， x=yd (mod n) 非对称密码概念与典型算法RSA算法安全性分析 密码分析者攻击RSA体制的关键点在于如何分解n 若分解成功使n=pq，则可以算出(n)(p-1)(q-1)，然后由公开的e， 解出秘密的d 非对称密码概念与典型算法RSA算法安全性分析 计算能力的不断提高和分解算法的进一步改进，原

24、来被认为是不 可能分解的大数已被成功分解 RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布 式计算历时8个月于1994年4月被成功分解 RSA-155（512比特）已于1999年8月被成功分得到了两个78位（十进制） 的素数 RSA-768（232十进制）已于2009年12月被成功分得到了两个116位（十进 制）的素数 估计在未来一段比较长的时期，密钥长度介于1024比特至2048比 特之间的RSA是安全的 对称密码与非对称密码对比 数字信封对称加密与非对称加密的结合 数字信封数字信封是一种解决两个对等实体之间通过网络发送大量数据的解决方法。 通信方A用B的公钥K2

25、加密A与B之间的共享密钥K1，并将其发送给B。 B用自己的私钥K3解密收到的消息，得到共享密钥K1。 A、B之间用对称密钥K1对收发的数据加解密。 数字信封对称加密与非对称加密的结合 数字信封的优点 由于非对称密码用于对称密码密钥的发布，较好地解决了对称密码的密 钥发布问题。 由于对称密钥相对于要发送的明文而言通常要小，因此，密钥交换过程 中的加解密过程很快。 由于使用对称密码进行实际数据的传输，因此，实际数据传输过程中的 加解密过程很快。 消息认证 消息认证是用来验证消息完整性的一种机制或服务。确保收到的 数据确实和发送时一样（未被修改、插入、删除或重放），且发 送方声称的身份是真实有效的

26、消息认证主要是为了防范（检测）主动的完整性攻击 消息认证 在网络环境中，传统的攻击类型有： 认证内容 认证消息（数据）的内容内容 认证消息（数据）的来源来源 认证消息（数据）的时效性时效性 消息认证分类 使用认证函数产生某种认证符，分为三类： 消息加密：将整个消息的密文作为认证符。 消息认证码（MAC）：消息和密钥的函数，它产生定长的值，以该值作 为认证符。 杂凑函数（Hash）：又称散列函数，将任意长的消息映射为定长的散列 值的函数，以该散列值作为认证符。 消息认证消息加密 对称加密 非对称加密 消息认证消息认证码 消息认证码Message Authentication Code(MAC)

27、利用密钥生成一个固定长度的短数据块，并将该数据附加在消息 之后。 M消息C MAC函数 K 共享的密钥MAC 消息认证码 MACC(K,M) 消息和MAC一起发送给接收方，接收方对收到的消息用相同的密 钥进行相同的运算得到新的MAC，若新MAC与收到的MAC一致，则 可确保： （1）消息未被修改 （2）消息来自真正的发送方 （3）若消息中含有序列号，则可相信消息顺序是正确的。 消息认证散列函数 单向散列函数(Hash) 又称为杂凑函数，是消息认证码的一种变形。 Hash与MAC的相同之处： 输入是可变大小的消息M，输出是固定大小的散列码。 Hash与MAC的不同之处： 散列码并不使用密钥，它仅

28、是输入消息的函数。 散列码，也称为消息摘要(Message Digest)或者散列值，是消息的一个指 纹。 消息认证散列函数 散列码的应用 用对称密码对消息及附在其后的散列码加密（冗余保护，提供认证与保 密） 用对称密码仅对散列加密，对那些不要求保密性的应用，这种方法处理 代价小（提供认证） 用发送方的私钥仅对散列加密（原理同上） 先用发送方的私钥对散列码加密，再用对称密码对消息和上述加密结果 进行加密（常用的技术，提供保密与认证） 通信双方共享公共的秘密值S（类似于密钥），A将M和S的联合体计算散 列值，并将其附在M后（提供认证） 消息认证散列函数 散列函数的要求 给定一个消息，计算其散列值

29、应该非常容易。 对给定的消息，散列值总是一致的。 给定一个散列值，找出创建该散列值的原消息是非常困难的。 任意给定两个消息，如果计算其消息摘要，两者的消息摘要必须不同。 如果两个消息产生相同的散列值，则称为冲突(Collision)。 如果散列值的长度为n，则两个消息产生同样的散列值的概率为1/2n，n 较大时，如为128位时，小概率事件难以发生。 消息认证散列函数 散列函数的雪崩效应 两个原消息之间非常小的变化，得到的消息摘要应该有很大的变化。 消息认证散列函数 散列函数的性质 散列函数可应用于任意大小的数据块； 散列函数产生定长的输出； 对任意给定的x，计算H（x）比较容易，用硬件和软件均

30、可实现； 对任意散列函数，找出满足 H（x）h 的x在计算上是不可行的，有些文 献中称之为单向性； 对任意给定的分组x，找到满足y不等于x，且H（y） H（x）的y在计算 上是不可行的，称之为抗弱冲突性； 找出任何满足H（x）H（y）的偶对（x，y）在计算上是不可行的，称 之为抗强冲突性。 消息认证MD5 1990年MIT的 Ron Rivest 提出MD4。 1992年 Ron Rivest 完成MD5 (RFC 1321)。 其发展历程为MD、MD2、MD3、MD4、MD5。 现行美国标准SHA-1以MD5的前身MD4为基础。 输入：任意长度的报文。 输入分组长度：512位。 输出：128

31、 位的消息摘要。 消息认证MD5 MD5不是足够安全的 Dobbertin在1996年找到了两个不同的512位块,它们在MD5计算下产生相 同的hash，但对一般性的一个512位分组，并不能总是找到一个产生同样 hash的另一个分组； 2004年，山东大学王小云教授针对一个X，计算MD5(X)，能够通过更改X 的某些位，得到一个Y，使得MD5(X)=MD5(Y)。 Rivest说，我们不得不做更多的重新思考了。 三、密码学典型应用 1. 加密设备的部署 2. 密钥管理与密钥分配 3. 数字证书与PKI 加密设备的部署 链路加密 很多的加密设备 较高的安全性 在每个交换节点都需要解密数据包 端到

32、端加密 源主机加密和接收端解密 静载荷加密 包头为明文 加密设备的部署 加密设备的位置 链路加密： 对于链路层加密，每条易受攻击的通信链路都在包交换器两端装备加密 设备。因此，所有通信链路的所有通信都受到保护。 尽管这在大型网络中需要很多加密设备，但它提供了较高的安全性。 缺点：消息每次进入包交换机都要被解密。 这是必要的，因为交换机必须读取包头（packet header）地址来发送包。 因此，每次交换时消息都易受攻击。如果这是一个公共包交换网络， 则 用户不可控制节点安全。 加密设备的位置 端到端加密： 对于端到端加密，加密过程在两个端系统上实现。 主机只能加密包中的用户数据部分而必须保留

33、包头为明文，使得它能被 网络读取。 因此使用端到端加密，用户数据是安全的，但是通信模式不安全，因为 包头以明文传递。 加密设备的位置 为获得更高安全性，两种形式都采用。 主机使用端到端加密密钥 加密包的用户数据部分。然后使用链路加密密钥加密整个包。 这样除了在包交换机里存储包时包头是明文外，整个包都是安全 的。 加密设备的部署 密钥管理与密钥分配 密码技术的安全性都依赖于密钥 密码学的原则：一切秘密寓于密钥之中 密钥管理：处理密钥自产生到最终销毁的整个过程中的有关问题 密钥分配 密钥分配技术是在不让其他人看到密钥的情况下将一个密钥传递 给希望交换数据的双方的方法。 密钥分配往往和身份认证联系在

34、一起。 一个密码系统的安全强度依赖于密钥分配技术。 密钥管理方法因所使用的密码体制（对称密码体制和公钥密码体 制）而异。 密钥分配 对称密钥的分配 对称加密基于共同密钥实现，如何建立安全的数据通道传输密钥成为密 钥管理的关键！ 解决：建立安全传输密钥的数据通道 非对称密钥的分配 正确地获取其他用户的公钥是密钥管理的关键！ 解决：公开密钥的集中式管理 密钥分配 分布式：网络中的主机具有相同的地位，他们之间的密钥分配取 决于他们之间的协商如基于公钥密码体制的密钥分配方法、 Diffie-Hellman密钥交换协议 集中式：一个中心服务器(密钥分配中心KDC)，团体中的任何一个 实体与中心服务器共享一个密钥。KDC接受用户的请求，为用户 提供安全的密钥分配服务 密钥分配 数字证书与PKI PKI (Public Key Infrastructure)：X.509定义PKI为：创建、管理、存 储、发布和撤消基于公钥密码系统的数字证书所需要的硬件、软 件、人和过程的集合 一种标准的密钥管理平台，它能够为所有网络应用透明地提供采 用加密和数据签名等密码服务所必须的密钥和证书管理 登记注册、管理、发布公钥证书，撤销过去签发但现已失效的密 钥证书 公钥证书Public-key certificates 公钥证书又称数字证书，可以理解为是一种数据结构 证书中