第1章 密码学概论

1.1 信息安全与密码学

1. 信息安全：防止任何对数据进行未授权访问的措施，或者防止造成信息有意无意泄露、破坏、丢失等问题的发生，让数据处于远离危险、免于威胁的状态或特性
2. 网络安全：计算机网络环境下的信息安全

1.1.1 信息安全的目标

• 本课程主要关注以密码学为基础的信息安全的5个主要方面
• CIA三元组为：机密性、完整性、可用性

1. 机密性(Confidentiality)：保证信息不泄露给非授权的用户和实体

• 加密技术

2. 完整性(Integrity)：保证信息处于保持完整或一种未受损的状态，防止任何对信息应有特性或状态的中断、窃取、篡改、伪造等

• 散列函数（Hash函数）

3. 可用性(Availability)：授权用户按需随时访问所需信息而不被非法拒绝
4. 认证性(Authentication)：确保消息的来源，可分为消息认证和实体认证

• 身份鉴别技术

5. 不可否认性(Non-Repudiation)：保障用户无法在事后否认曾经对消息的生成、签发、接收等

• 数字签名

1.1.2 攻击的主要形式和分类

针对信息安全攻击的主要形式

• 中断（拒绝服务）：对可用性的攻击
• 截取：对机密性的攻击
• 篡改：对完整性、真实性、有序性的攻击
• 伪造：对身份认证性的攻击
• 重放：重放将一个数据单元截取后进行重传，产生一个未授权的信息。在这种攻击中，攻击者记录下某次通信会话，然后在以后某个时刻，重放整个会话或其中的一部分

攻击的分类

1.2 密码学发展史

1. 传统密码学阶段(~~1949年)：是艺术，而不是科学

• 隐写术
  剃头刺字、藏头诗、暗示、隐语、隐形墨水、微缩技术

2. 现代密码学阶段(1949年~至今)

• 1949-1976：1949年Shannon发表《保密系统的信息理论》(“Communication Theory of Secrecy Systems") ，产生了信息论
• 1976-1984: Diffie和Hellman发表《密码学的新方向》，公钥密码体制思想，开创了公钥密码学的新纪元（1976年以前所有密码系统均属于对称密码学范畴）
• 1984-至今:1984年Goldwasser和Micali提出可证明安全理论

1.2.1 传统密码

1. 古代密码术（代换、换位）

• 棋盘密码（Polybius校验表）：I/J同一格
• 凯撒密码：明文中每个字母用其后的第三个字母代替
• 栅栏式密码：将明文写成铁轨的形式（即两行）
• 摩斯电码

2. 近代密码

• 单表代换密码
  仿射密码
• 多表代换密码
  Vigenere密码
  转轮密码机Enigma（恩格玛密码机）
  弗纳姆密码（Vernam）：利用电传打字机的五单位码与密钥字母进行模2相加

1.2.2 现代密码学

1. 1949-1976：1949年Shannon（1916-2001，香农）发表《保密系统的信息理论》（“Communication Theory of Secrecy Systems”），产生了信息论，标志着现代密码学的开始
2. 1975年1月15日，对计算机系统和网络进行加密的DES（Data Encryption Standard，数据加密标准）由美国国家标准局NIST颁布为国家标准—密码术历史上具有里程碑意义的事件
3. 1976年，美国斯坦福大学的Diffie和Hellman两人提出了公钥密码的新思想（密码学的新方向；New Direction in Cryptography），把密钥分为加密公钥和解密私钥，这是密码学的一场革命
4. 1977年，美国的Ronald Rivest、Adi Shamir和Len Adleman提出第一个较完善的公钥密码体制——RSA体制，这是一种建立在大数因子分解基础上的算法
5. 1997年美国国家标准和技术研究所（NIST）发起征集高级数据加密标准（AES，Advanced Encryption Standard）的活动

• 2000年10月，比利时密码学家Joan Daemen 和 Vincent Rijmen 提出的“ Rijndael 数据加密算法”被确定为AES算法，作为新一代数据加密标准

6. 公钥密码领域，椭圆曲线密码体制ECC由于其安全性高、计算速度快等优点引起了人们的普遍关注和研究，并在公钥密码技术中取得重大进展
7. 新的密码技术不断涌现

• 混沌密码、量子密码、DNA密码等。新的密码技术正在逐步地走向实用化

1.2.3 密码学的基本概念

1. 密码学（Cryptology）：是结合数学、计算机科学、电子与通讯等诸多学科于一体的交叉学科，是研究信息系统安全保密的一门科学
2. 密码编码学（Cryptography）：研究密码编制的科学
3. 密码分析学（Cryptanalysis）：研究密码破译的科学
4. 密码学的基本思想是伪装信息，使未授权者不能理解它的含义

• 明文(Plaintext,Message)：伪装前的原始数据
• 密文(Ciphertext) ：伪装后的数据
• 密钥(Key) ：参与密码变换的参数
• 加密(Encrypt) ：伪装的过程
• 加密算法：用于对数据加密的一组数学变换
• 解密(Decrypt) ：将密文恢复为明文
• 解密算法：用于解密的一组数学变换

1.2.4 密码学的主要任务

• 机密性
• 完整性
• 认证性（消息认证和实体认证）
• 不可否认性

1.2.5 现代密码学中密码算法是公开的，那如何实现保密？→ 密钥（Key）

• 使用一个密钥的加密/解密
• 使用两个密钥的加密/解密：DK2(EK1(P))=P

1.2.6 密码体制

密码体制，也称密码系统(Cryptosystem)，由五部分组成：

• 明文空间M：全体明文的集合
• 密文空间C：全体密文的集合
• 密钥空间K：全体密钥的集合。其中每一个密钥K均由加密密钥K_e和解密密钥K_d组成，即K＝< K_e, K_d >
• 加密算法E：一组由M到C的加密变换
• 解密算法D：一组由C到M的解密变换

1.2.7 密码体制的设计原则

1. 科克霍夫原则（Kerckhoffs Principle）：密码系统的安全性不应该取决于不易改变的算法，而应取决于可随时改变的密钥
2. 科克霍夫假设：密码分析者知道密码算法，唯一不知道的是密钥
   WHY？

• 维护短的密钥比维护算法更容易；共享和安全存储短的密钥比共享和安全存储百千倍的程序更容易；算法的细节更容易泄露（逆向工程）
• 一旦密钥泄露，更换密钥比更换算法更容易（定期密钥更新）
• 多用户通信时，使用相同算法但不同的密钥比分别使用不同的算法更容易

1.2.8 密码体制的分类

1. 对称密码：如果一个密码体制的K_d＝K_e，或由其中一个很容易推出另一个。如同现实生活中的保密箱机制
   根据对明文和密文的处理方式和密钥的使用不同，又可分为：

• 序列密码（流密码）
  例如：RC4、A5、SEAL等
• 分组密码
  例如： DES、3DES、AES、IDEA等

2. 公钥密码：如果在计算上K_d不能由K_e推出，这样将K_e公开也不会损害K_d的安全，于是便可将K_e公开
   例如： RSA、ECC、Rabin、Elgamal、NTRU等

1.2.9 两种密码体制的比较

1. 对称密码体制优点：

• 速度快
• 密钥较短
• 密文往往与明文长度相同

2. 对称密码体制缺点：

• 密钥分发需要安全通道
• 密钥量大，难于管理
• 难于解决不可否认问题

3. 公钥密码体制优点：

• 密钥分发相对容易
• 密钥管理简单
• 可以实现数字签名

4. 公钥密码体制缺点：

• 加解密速度慢
• 密钥较长
• 密文长度往往大于明文长度

1.2.10 对密码系统的攻击

1. 穷举攻击法（强力或蛮力（Brute force）攻击）

• 变体：字典攻击

2. 统计分析法：根据明文、密文和密钥的统计规律来破译密码的方法

• 多适用于对称密码体制

3. 数学分析攻击法：针对加解密算法的数学基础和某些密码学特性，通过数学求解的方法来破译密码

• 对适用于公钥密码体制

1.2.11 密码分析攻击分类

根据密码分析者对明文、密文等数据资源的掌握程度，可以将密码分析攻击分为以下几种（假设：攻击者知道密码算法）：

1. 惟密文攻击（Ciphertext-only attack）：被动攻击，密码分析者仅能根据截获的密文进行分析，以得出明文或密钥（破译难度最大）

• 穷举攻击和统计分析都是惟密文攻击

2. 已知明文攻击（Plaintext-known attack）：被动攻击，密码分析者除了有截获的密文外，还有一些已知的“明文—密文对”来破译密码

• 现代的密码体制（基本要求）不仅要经受得住唯密文攻击，而且要经受得住已知明文攻击

3. 选择明文攻击（Chosen-plaintext attack）：主动攻击，密码分析者除得到一些“明文—密文对”外，还可以选择被加密的明文，并获得相应的密文；密码破译者暂时控制加密机

• 自适应选择明文攻击（Adaptive-chosen-plaintext attack）

4. 选择密文攻击(Chosen-ciphertext attack) ：主动攻击，指密码分析者可以选择一些密文，并得到相应的明文；密码破译者暂时控制解密机

• 密码分析者的任务目标是推出密钥
• 这种密码分析多用于攻击公钥密码体制
• 自适应选择密文攻击（Adaptive-chosen-ciphetext attack ）

1.2.12 攻击的复杂性

衡量密码系统攻击的复杂性主要考虑三个方面：

1. 数据复杂性（Data Complexity）：密码攻击所需要输入的数据量
2. 处理复杂性（Processing Complexity）：完成攻击所需要花费的时间
3. 存储需求（Storage Requirement）：进行攻击所需要的数据存储空间大小

• 攻击的复杂性取决于以上三个因素的最小复杂度，在实际实施攻击时往往要考虑这三种复杂性的折衷，如存储需求越大，攻击可能越快

1.2.13 密码体制的安全性

一个安全的密码体制应该具有如下三条性质：

1. 从密文恢复明文应该是难的，即使分析者知道明文空间（如明文是英语）
2. 从密文计算出明文部分信息应该是难的
3. 从密文探测出简单却有用的事实应该是难的（如相同的信息被发送了两次）

1.2.14 从攻击效果看，敌手可能达到以下结果

• 完全攻破：敌手找到了相应的密钥，从而可以恢复任意密文
• 全盘推导：密码分析者找到一个算法，使得可以在不知道密钥的情况下通过替代算法恢复出任意密文
• 部分攻破：敌手没有找到相应的密钥，但对于给定的密文，敌手能够获得明文的特定信息
• 密文识别：如对于两个给定的不同明文及其中一个明文的密文，敌手能够识别出该密文对应于哪个明文，或者能够识别出给定明文的密文和随机字符串

1.2.15 评价密码体制安全性

评价密码体制安全性有不同的途径，包括：

1. 无条件安全性（理论安全性）：如果密码分析者具有无限的计算能力，密码体制也不能被攻破，那么这个密码体制就是无条件安全的
2. 计算安全性：如果攻破一个密码体制的最好算法用现在或将来可得到的资源都不能在足够长的时间内破译，该密码体制被认为是计算上安全的
3. 可证明安全性：可证明安全性只是说明密码体制的安全与一个问题是相关的，可证明安全性也有时候被称为归约安全性