二、密码学基础
初识密码
与人类共生
- 密码: 用来混淆的技术, 不同于隐藏、访问控制.
密码基本概念
- 传统加密:
- 对称加密、单钥加密.
- 代换密码、置换密码及二者组合.
- 安全性在于保持算法本身的保密性
- 不适合大规模生产, 用户无法了解算法的安全性.
- 现代加密:
- 非对称加密、公钥加密, 1976 年第一次公开发表.
- 密码算法公开，密钥保密.
- 安全性在于保持密钥的保密性.
- 适于大规模生产.
- 密码学:
- 密码编码学: 研究加密方案的学科.
- 密码分析学: 研究破译密码获得消息.
- 统称为密码学.
- 密码编码学系统的三个独立的特征:
- 转换明文为密文的运算类型:
- 置换和代换, 不允许丢失信息.
- 所用的密钥数:
- 密钥相同/不同——对称密码/非对称密码.
- 处理明文的方法:
- 分组密码/块密码: 处理分组.
- 流密码/序列密码: 连续处理元素.
- 转换明文为密文的运算类型:
- 无条件安全: 无论有多少密文, 都不足以唯一确定对应的明文.
- 计算安全:
- 破译代价超过密文的价值.
- 破译时间超过密文的生命期.
密码发展历程
- 第 1 阶段: 古典密码 (1949 年前)
- 安全基于算法的保密, 密码学不是科学而是艺术.
- 算法基本手段是代换和置换, 针对字符.
- 简单的密码分析手段.
- 第 2 阶段: 近代密码
- 计算机——复杂密码计算.
- 有线电报——现代密码编码学.
- 无线电报——现代密码分析学.
- 现代密码学的原理 (Kerchoffs):
- 加密体系安全性依赖于使用的密匙.
- 古典密码和现代密码的分界线.
- 香农发表《保密通信的信息理论》论文, 密码学成为一门科学.
- 第 3 阶段: 现代密码
- 公钥密码:
- 无密钥传输的保密通信成为可能
- 1976年, Diffie & Hellman 提出公钥密码体制.
- 1977年, Rivest & Shamir & Adleman 提出 RSA 公钥算法.
- 对称密码:
- 1977年, 美国实施公开的 DES 对称加密算法.
- 公钥密码:
古典密码
代换技术
单表代换密码:
- Casear 密码, 密钥词密码.
- 明文语法模式和结构被保留, 密穷举攻击破译.
多表代换密码:
Playfair 密码:
- 一次加密两个字母.
- 基于由密钥词构成的 5×5 字母矩阵.
- 保留了明文语言的结构.
Hill 密码:
- 加密过程: $C=KP\pmod{26}$.
解密过程: $P=K^{-1}C\pmod{26}$.
隐蔽单字母的频率特性.
Vigenere 密码:
一系列 Casear 密码.
隐藏了字母频率信息.
并非所有的明文结构都被隐藏.
Verman 密码和一次一密:
随机密钥与消息一样长且无重复.
运算基于二进制数据.
无条件安全.
局限性:
- 产生大规模随机密钥很困难.
密钥的分配和保护很困难.
置换技术
- 置换形成新的排列.
- 栅栏技术.
- 转轮机.
破译举例
- 穷举法/频率分析法.
对称密码算法
- 加密解密的密钥相同.
- 使用秘密信道分配密钥.
S-DES 算法
示例:
Feistel 密码结构
流密码:
- 每次加密数据流一位或一字节.
- Vigenere 密码和 Verman 密码.
分组密码:
- 明文组整体加密, 得到等长密文组.
- 大多数对称密码使用分组密码.
- 现行的对称分组密码基于 Feistel 分组密码结构.
Feistel 分组密码结构:
使用乘积密码的概念逼近简单代换密码, 依次使用两个或以上的基本密码.
交替使用代换和置换.
是香农提出的交替使用混淆和扩散乘积密码的实际应用.
几乎所有传统分组密码结构都和 Feistel Cipher 类似.
- 输入: 第 i 轮迭代输入来自上轮迭代输出.
- 子密钥: 由密钥 K 推导出来.
- 轮函数: 每轮迭代相同, 输入的子密钥不同.
- 代换: 数据左半部分, 轮函数 F 作用在右半部分, 与左半部分异或.
- 置换: 代换后交换数据左右两半.
影响参数: 迭代轮数, 分组和密钥长度, 子密钥产生算法, 轮函数.
混淆和扩散:
- 刻画密码系统的两个基本构件, 现代分组密码设计的里程碑.
- 挫败基于统计方法的密码分析.
- 扩散: 使明文的统计特征消散在密文中, 每个明文数字影响多个密文数字.
- 混淆: 使密文和密钥的统计关系更复杂, 挫败推导密钥的企图
DES 算法
算法结构:
- 密钥长度 56 bits, 加上奇偶校验写成 64 bits.
- 分组长度 64 bits.
- 迭代轮数 16 轮.
- 初始置换 $IP$.
- 末尾置换 $IP^{-1}$.
除初始置换和末尾置换, DES 结构与 Feistel 结构完全相同.
子密钥生成:
一轮迭代:
解密过程: 与加密过程完全相似, 将 16 次迭代的子密钥顺序倒过来.
常用对称密码
3-DES:
两个密钥 $K_1K_2$, 长度为 112 比特, 明文攻击代价为 $2^{112}$ 数量级.
Blowfish:
算法结构:
- 密钥长度 32-448 bits.
- 分组长度 64 bits.
- 迭代轮数 16 轮.
- 基本运算: 模 $2^{23}$ 加法与按位异或.
F 映射包含四个 S 盒运算, 子密钥和 S 盒由算法本身生成, 数据不可辨认, 密钥分析困难.
与古典 Feistel 结构不同, 每轮运算对左右部分同时进行, 强度增强.
密钥长度可抵抗穷举攻击, 安全性未受挑战.
RC5:
算法结构:
- 密钥长度 0-2040 bits.
- 分组长度 32/64/128 bits.
- 迭代轮数不定.
基本运算: 模 $2^{w}$ 加法, 按位异或与循环左移.
AES:
3DES 的缺点: 软件实现速度慢, 分组长度过小.
算法结构:
- 密钥长度 128 bits.
- 分组长度 128 bits.
- 迭代轮数 10 轮.
不是 Feistel 结构, 每一轮都使用代换和置换并行处理分组.
算法过程:
- 字节代换: S 盒.
- 行移位: 置换.
- 列混淆: 代换.
轮密钥加: 按位异或.
其他对称密码算法:
非对称密码算法
公钥密码原理
对称密钥密码的缺陷:
- 安全的信道分配密钥.
- 无法用于数字签名.
- 管理复杂, 密钥的数量 $O(n^2)$.
公钥密码:
- 密码学历史上唯一一次真正的革命.
- 基于数学函数而非代换和置换.
- 基于陷门单向函数的概念, 不知陷门信息下求逆困难.
- 公钥公开, 存于寄存器或文件, 加密和验证签名.
- 私钥保密, 解密和签名.
- 系统控制私钥, 通信就是安全的.
- 系统可以改变私钥, 公布相应的公钥代替.
加密原理/签名原理.
用途:
- 加密/解密.
- 数字签名.
密钥交换: 协商会话密钥, 用于对称密钥加密.
实际应用中目前局限于数字签名和密钥管理.
误解:
- 密码分析角度看, 公钥密码比传统密码更安全.
- 加密安全性依赖于密钥长度和破译所需计算量.
- 公钥密码是通用方法, 传统密码已过时.
- 公钥密码需大量计算, 仅限密钥管理和签名, 难以取代传统密码.
- 传统密码与密钥分配中心的握手很麻烦, 公钥密码实现密钥分配很简单.
- 公钥密码也需协议和中心代理, 处理过程不比传统密码简单有效.
- 密码分析角度看, 公钥密码比传统密码更安全.
RSA 算法
1978 年首次发表.
是最早满足要求、广泛接受并实现的通用公钥分组密码算法.
攻击方法:
- 蛮力攻击.
- 数学攻击: 因子分解.
- 计时攻击：记录解密消息所用的时间, 来确定私钥.
- 不仅可以攻击 RSA, 还可攻击其它公钥密码系统.
- 完全不可预知性, 仅依赖明文, 有很大的威胁.
DH 密钥交换算法
局限性: 只进行密钥交换.
有效性: 计算离散对数非常困难.
DSA 算法
- 数字签名算法, 用于数字签名标准 DSS.
- 安全性: 计算离散对数非常困难.
- 局限性:
- 只用于数字签名, 不能加密或密钥分配.
- 由 NIST 研制的, 可能有后门.
- 选择过程不公开, 提供的分析时间不充分.
- 比 RSA 慢 10－40 倍, 512 位密钥长度太小.
密钥分配
概述
加密方法:
- 链路加密.
端到端加密.
密钥分配方法:
- 将密钥发给数据交换双方, 不让别人知道.
密码系统强度与密钥分配方法有关.
三种情况
传统对称密码分配
- 人工传送: 适用于链路加密.
- 密钥分配中心: 适用于端到端加密.
- 密钥分配中心 KDC 模式:
- A 向 KDC 请求会话密钥, 消息有 A 和 B 的标识及临时交互号 N1.
- KDC 用 Ka 加密响应, A 可知一次性会话密钥 Ks, 含 N1 原始请求消息, 还有用 Kb 加密的一次性会话密钥 Ks 和 A 的标识符 IDa.
- A 存下会话密钥 Ks, 将响应后两项内容发给 B.
- 网络规模很大, 密钥分配不限定在单个 KDC 上, 使用层次式 KDC.
- 主密钥分配代价变小, 本地 KDC 出错或被攻击不会影响全局.
公钥分配
- 公开发布:
- 通信方将公钥发送给另一通讯方或广播给各方 (电子邮件 PGP 协议).
- 方法简便, 但是任何人都可以伪造.
- 公开可访问目录:
- 可信的实体或组织维护一个动态可访问的公钥目录.
- 管理员定期发布或者更新该目录.
- 通讯方可以用新密钥替代当前密钥, 也可以从安全认证通道访问目录.
- 比公开公钥要安全, 但是一旦攻击者获得目录管理员私钥, 危险很大.
- 公钥授权:
- A 发送时间戳消息给公钥管理员, 请求 B 的公钥. 管理员发送用其私钥 KR 加密的消息, A 用管理员公钥解密, 包含 B 的公钥、原始请求、原始时间戳.
- A 保存 B 公钥, 并将 A 的表示和临时交互号 N1 发给 B. B 从管理员得到 A 的公钥. 通过核对临时交互号, 确认各自身份, 安全通信机制就建立了.
- 但是只要通信, 公钥管理员就成为系统瓶颈.
- 公钥证书:
- 不通过管理员, 用证书交换密钥, 与公钥授权安全性相同.
- 证书由证书管理员产生, 发给拥有相应私钥的通讯方.
- 通信方传递证书以传递密钥信息, 可以验证证书由证书管理员发出.
利用公钥分配传统密码密钥
原因: 公钥密码速度较慢, 更适合在传统密码中实现密钥分配.
分配方法:
简单的密钥分配方法:
- A 产生公/私钥对, 将 KUa 和 A 表示发给 B.
- B 产生密钥 Ks, 用 A 公钥加密后传给 A.
- A 计算得到密钥 Ks.
- 容易受到主动攻击.
具有保密性和真实性的密钥分配方法:
可以抗击主动攻击和被动攻击.
混合方法.
