05密码学---分组密码

1 .密码学 导论˙第 5 章 分组密码 李卫海

2 .本章目录 密码学导论 -- 中国科学技术大学 2

3 .第一节 数据加密标准 DES 密码学导论 -- 中国科学技术大学 3

4 .一、 Feistel 框架 分组密码 (Block Cipher) ： 通常以大于等于 64 位的数据块为处理单位 密文仅与算法和密钥有关，与明文数据块的位置无关 例如： DES 、 AES 等 理想分组密码： n 比特的明文分组， 加密 产生 n 比特的密文分组 2 n 个不同的明文分组， 各自 产生 2 n 个 唯一的密文分组 本质上是一个巨大的代换表 密码学导论 -- 中国科学技术大学 4

5 .一、 Feistel 框架 完美安全的分组映射： n 位的分组就有 2 n 种输入 每种输入需要 n 位“密钥”控制，共需 n×2 n 位“密钥” 例： 2 4 个明文 每个映射需用 4 比特 描述，共 2 4 个映射，密钥共需要 4×2 4 位 密码学导论 -- 中国科学技术大学 5 2 4 个密文

6 .Feistel 密码框架 很多 分组密码基于 Feistel 密码结构 通过复杂运算，达到近似的理想 采用了乘积加密器的思想， 交替 使用 代换 和置换 代换 S-box 置换 P-box S-P 网络（ Substitution-Permutation Network ） 密码学导论 -- 中国科学技术大学 6

7 .Feistel 密码框架 加密算法： 将输入等分为两段， 进行若干轮运算，每轮中 对左半段数据进行代换，依据 轮函数 F （右半段数据和子密钥） 然后置换：交换左右两段数据 解密算法： 与加密算法过程一致 子密钥使用次序相反 密码学导论 -- 中国科学技术大学 7

8 .8 Feistel 解密正确性证明 考虑第 i 轮 加密： 解密：

9 .参数： 分组长度： 长度越大，安全性越高，处理速度也越低 密钥长度： 长度越大，安全性越高，可能降低处理速度 迭代轮数： 单轮不能提供足够的安全性；轮数越多，安全性越高，处理 时间 也成倍增加 子密钥产生算法： 算法越复杂，密码分析攻击越难，会降低处理速度 轮函数： 算法越复杂，安全性越高，处理速度也降低 特点： 快速软件加 / 解密 分析简单：利于脆弱性的分析与测试 对 DES 并没有简便的分析方法 密码学导论 -- 中国科学技术大学 9

10 .讨论 对轮函数 F 的要求： 从可解密角度：没有 从安全角度：尽可能复杂 例如 扩散效应局限在两个对应比特上 轮函数 F 对扩散的效果有影响 同样，对子密钥的生成也应考虑到混淆的效果。 密码学导论 -- 中国科学技术大学 10

11 .二、数据加密标准 DES IBM 设计出 Lucifer 密码 (1971) 由 Horst Feistel 带领的团队 用 128 比特密钥加密 64 比特数据分组 Tuchman-Mayer 牵头开发商业密码 适合于单芯片实现 密钥长度 56 比特，抗密码分析能力更强 美国国家安全局介入 1973 年美国国家标准局征求国家密码标准方案， IBM 将上述方案提交，并被采用，称为数据加密标准（ DES ） 密码学导论 -- 中国科学技术大学 11

12 .安全性曾争议颇多 用 56 比特密钥加密 64 比特数据 设计标准列入机密 民间研究显示 DES 安全性很强 广泛应用在金融、遗产等领域 虽然差分攻击和线性分析攻击在理论上有效，但实现起来计算量仍很大 曾 是应用最广泛的分组密码技术 AES 正取而代之 密码学导论 -- 中国科学技术大学 12

13 .DES 的整体结构 64 比特明文分组输入 64 比特密文分组输出 64 比特密钥 实际只使用 56 位 其它用作奇偶校验等 Feistel 密码框架 16 轮操作 IP ：初始置换 IP -1 ：逆初始置换 PC1 、 PC2 ：压缩置换 IP 64 比特密文 64 比特明文 K 1 K 16 64 比特密钥 第 1 轮 第 2 轮 第 16 轮 32 比特置换 IP -1 PC1 分组左移 分组左移 分组左移 PC2 PC2 PC2 64 64 64 48 48 48 64 56 56 56 56 56 密码学导论 -- 中国科学技术大学 13

14 .初始置换 IP 与逆初始置换 IP -1 置换表中的每个元素表明了输入位在 64 位输出中的位置 两表互逆 IP 表中第 1 个是 58 ，表示明文的第 58 位被置换到第 1 位； IP -1 表中第 58 个是 1 ，表示输入的第 1 位被置换到第 58 位； 注意： IP -1 表很有规律 密码学导论 -- 中国科学技术大学 14

15 .轮结构 64 位数据分为 L 、 R 各 32 位 子密钥 K 为 48 位 轮函数： 将 32 位 R 通过 E 扩展为 48 位 与密钥 K 异或 由 8 个 S 盒子紧缩为 32 位 由置换 P 作用后输出 S 盒置换 扩展置换 E 置换 P K i R i-1 L i-1 R i L i F 32 32 32 32 32 48 48 48 密码学导论 -- 中国科学技术大学 15

16 .扩展置换 E 观察扩展置换 E 将 32 位输入分为 8 组，每组 4 位 从相邻两组的邻近位置各取 1 位 扩展置换 E 扩散作用 某一个比特，几轮操作后其影响会扩散到整个分组 64 位 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 密码学导论 -- 中国科学技术大学 16

17 .S 盒子结构 S 盒子为 4 行 16 列的矩阵，每行定义一个可逆置换 输入 6 位，输出 4 位 S 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8 48 32 4 4 4 4 4 4 4 4 6 6 6 6 6 6 6 6 密码学导论 -- 中国科学技术大学 17

18 .S 盒子 输入 6 位，输出 4 位 输入的第 1 位和第 6 位组成一个 2 位二进制数，选择行 输入的第 2 位至第 5 位组成一个 4 位二进制数，选择列 将选中的数字以二进制数输出 例： S 1 盒子输入 011001 选择行 1 （ 01 ）；选择列 12 （ 1100 ） 将选中的 9 输出 1001 。 注意： S 盒子的行、列从 0 开始计数 密码学导论 -- 中国科学技术大学 18

19 .密码学导论 -- 中国科学技术大学 19

20 .密钥的产生 输入 64 位密钥，保留 56 位 置换选择 PC1 将 64 位原始密钥置换输出 56 位 注意： 若用大写英文字母作为密钥，常用它们的 ASCII 码作为二进制密钥。这是危险的，因为它们的 ASCII 码最高位均为 0 ，而 DES 舍弃的是最低位！ 密码学导论 -- 中国科学技术大学 20

21 .56 位密钥分为两组，每轮迭代分别循环左移 1 位或 2 位，作为下一轮的密钥输入 移位产生的值经置换选择 2 ，输出 48 位作为轮函数子密钥 LS-1 PC2 K i C i-1 LS-1 28 28 48 28 28 28 28 D i-1 C i D i 密码学导论 -- 中国科学技术大学 21

22 .DES 解密 解密是加密的逆过程 对 Feistel 框架密码，采用相同算法，但是子密钥使用的次序正好相反： IP 变换抵消加密的最后一步 IP -1 ； 第一轮使用密钥 K 16 ； 第二轮使用密钥 K 15 ； …… 第十六轮使用密钥 K 1 ； IP -1 变换抵消加密的第一步 IP ； 获得解密明文。 密码学导论 -- 中国科学技术大学 22

23 .三、 DES 的安全性 密钥的长度问题 56bits 密钥有 2 56 = 72,057,584,037,927,936 ≈ 7.2 亿亿之多 蛮力搜索 ( brute force search ) 似乎很困难， 20 世纪 70 年代估计要 1000 － 2000 年 技术进步使蛮力搜索成为可能 1997 年网络合作破译耗时 96 天。 1998 年在一台专用机上 (EFF) 只要三天时间即可 1999 年在超级计算机上只要 22 小时 ! 蛮力搜索需要明文可判决 S-box 问题 其设计标准没有公开 迄今没有发现 S 盒存在致命弱点 密码学导论 -- 中国科学技术大学 23

24 .三、 DES 的安全性 密钥的长度问题 56bits 密钥有 2 56 = 72,057,584,037,927,936 ≈ 7.2 亿亿之多 蛮力搜索 ( brute force search ) 似乎很困难， 20 世纪 70 年代估计要 1000 － 2000 年 技术进步使蛮力搜索成为可能 1997 年网络合作破译耗时 96 天。 1998 年在一台专用机上 (EFF) 只要三天时间即可 1999 年在超级计算机上只要 22 小时 ! 蛮力搜索需要明文可判决 S-box 问题 其设计标准没有公开 迄今没有发现 S 盒存在致命弱点 密码学导论 -- 中国科学技术大学 23

25 .雪崩效应 Avalanche Effect 雪崩效应 ： 明文或密钥的一比特的变化，引起密文许多比特的改变 加密算法的关键性能之一 希望明文或密钥的 1 比特变化，会使半数密文比特发生变化；否则，可能存在方法减小待搜索的明文和密钥空间 DES 密码有良好的雪崩效应 如果用同样密钥加密只差一比特的两个明文： 0000000000000000......00000000 1000000000000000......00000000 2 轮迭代后密文有 21 个比特不同， 16 轮迭代后有 34 个比特不同 如果用只差一比特的两个密钥加密同样明文： 2 轮迭代后密文有 14 个比特不同， 16 轮迭代后有 35 个比特不同 密码学导论 -- 中国科学技术大学 25

26 .26

27 .计时攻击 依据加密或解密算法对于不同输入所花的时间上的细微差别，进行分析 多用于公开密钥算法 DES 能够很好地抵抗计时攻击 能量攻击 通过分析电子设备执行计算过程中的能量消耗来寻找有关密钥的信息 指令执行时（例如在智能卡中）所消耗的能量与其执行的指令和数据的存取有关 密码学导论 -- 中国科学技术大学 27

28 .能量攻击可分为简单能量分析攻击 SPA（Simple Power Analysis） 和差分能量分析攻击 DPA（Differential Power Analysis） 通过观测密码算法在执行过程（例如在智能卡中）中任何特定时间所消耗的能量来获得一些有用的信息。 执行乘法比执行加法消耗更多的能量 向存储器中写 1 比写 0 消耗更多的能量 某智能卡用 DES 算法加密时的能量追踪图 密码学导论 -- 中国科学技术大学 28

29 .DES 的密码分析 密码分析攻击问题 主要利用了加密器的一些深层结构 搜集加密信息 最终设法恢复部分或全部子密钥的位 如果必要的话对其余部分再辅以穷举搜索 这些攻击本质上是统计分析，包括 差分分析、线性分析、相关密钥攻击 DES 不能抵御差分分析、线性分析 密码学导论 -- 中国科学技术大学 29