第二讲信息论基础与古典加密技术

Size: px

Start display at page:

Download "第二讲信息论基础与古典加密技术"

崩濮
5 years ago
Views:

1 第四讲现代分组加密技术上海交通大学计算机系

2 内容三重 DES 3DES 国际数据加密算法 IDEA 高级数据加密标准 AES 分组密码的工作模式

3 序言 DES 的 56 比特的密钥长度太小, 注定将被取代本章将探讨当前最重要几种对称密码算法这些密码算法均具有如下特征 : 高密码强度应用广泛代表了至 DES 以来的现代对称密码技术

4 1.DES 的变形 DES 在穷举攻击下, 理论上脆弱需要寻找替代算法多次使用 DES, 且使用多个密钥设计新的密码算法最简单形式 : 双重 DES 两次进行加密, 每次使用不同的密钥加密解密 C = E K 2[ EK 1[ P]] P = D K 1[ DK 2[ C]]

5 双重 DES E [ E [ ]] [ ] 2 K P E P 1 K 3 K = 如果成立, 不管用 DES 进行了多少次加密, 效果均等同于用一个 56 bit 密钥进行一次 DES 加密

6 对双重 DES 的攻击 (1) 中间相遇攻击针对所有分组密码原理如果 : 则有 : 算法步骤 E 2[ E 1[ P]] K K = C E 1[ P] = D [ C] = K K 2 给定明文密文对 (P, C), 对 P 按照 K 1 的所有可能值 ( 2 56 个 ) 加 X 密, 所得结果按照 X 的值排序放在表 T 内再对 C 用 K 2 的所有可能值 ( 2 56 个 ) 解密每解密一次, 将结果与 T 表中的值比较如果等式成立, 则用 K 1,K 2 依次对 P 加密, 若结果为 C, 则获得正确密钥

7 对双重 DES 的攻击 (2) 中间相遇攻击的成功概率双重 DES 密文空间长度 :2 64 双重 DES 密钥长度 112, 密钥空间对固定明文 P, 运行双重 DES 得到固定密文 C 的密钥个数平均为 /2 64 =2 48 其中仅一个密钥是正确的因此对第一个(P, C) 对, 平均能找到 2 48 个密钥对 (K 1, K 2 ) 对第二个 (P, C ) 对, 用 K 1 K 2 对 P 加密, 若所得结果为 C, 则认为 (K 1, K 2 ) 对正确第二次出错的概率为 2 48 /2 64 =2-16 结论 : 使用中间相遇攻击, 在已知两组明文密文对时, 付出数量级为 2 56 的代价, 可以成功攻击密钥长度为的双重 DES (CP. DES, 攻击数量级为 2 55 攻击 ) 双重 DES 不能提高 DES 的安全性

8 三重 DES (3DES)(1) 思想 : 为了对抗中间相遇攻击, 使用三个密钥进行三次加密, 使得已知明文攻击的代价上升为数量级 ( 安全!) 广泛替代了 DES, 用于密钥管理标准 ANS X9.17 和 ISO 8732 弱点 : 密钥长度为 168 位 Tuchman 建议使用两个密钥进行三次加密 : 加密 - 解密 - 加密 (EDE) 加密与解密加密 C = E K 1[ DK 2[ EK 1[ P]]] 解密 P = D K 1[ EK 2[ DK 1[ C]]]

三重 DES(2) EDE 的目的 : 与 DES 兼容 ( 设 K 1 =K 2 即可 ) 对 3DES 的攻击目前对 3DES 没有可行攻击方法已证明穷举攻击代价为 2 112 5 10 33 数量级可以对抗差分攻击线性攻击

但是选择明文攻击, 所需明文密文对数量为 2 56 已知明文攻击 : 给定 n 个明文密文对 (P, C) ( 运算数量级约 2 56-log n, 也不实际 ) 2) 对所有可能密钥 K i = i, 计算 P i =D i [a]

9 三重 DES(2) EDE 的目的 : 与 DES 兼容 ( 设 K 1 =K 2 即可 ) 对 3DES 的攻击目前对 3DES 没有可行攻击方法已证明穷举攻击代价为数量级可以对抗差分攻击线性攻击 : 攻击代价按指数增长, 比 DES 超过倍 Merkle,Hellman 攻击 ( 不实际 ) 逐个查看可能的明文, 看哪一个明文的第一个中间值 (A) 为 0 再使用中间相遇攻击代价 :2 56 数量级但是选择明文攻击, 所需明文密文对数量为 2 56 已知明文攻击 : 给定 n 个明文密文对 (P, C) ( 运算数量级约 2 56-log n, 也不实际 ) 2) 对所有可能密钥 K i = i, 计算 P i =D i [a] 1) 随机选择 a 4) 对所有可能 K 2 =j, 计算 a 对应的第二个中间值 B j =D j [a] 5) 若 B j =B i 则认为 (K 1,K 2 )=(i, j) 3) 若 P 属于已知对, 计算 B i =D i [C], 入表并排序

10 三重 DES(3) 虽然二密钥的 3DES 可以对抗上述攻击, 但研究者仍不放心很多研究者推荐使用 3 个密钥的三重 DES C = EK 3[ DK 2[ EK 1[ P]]] 兼容性 P = D K [ E 3 K [ D 2 K [ P]]] 1 与 DES 兼容 : K 3 =K 2, 或 K 1 =K 2 三密钥的 3DES 的应用 PGP (Pretty Good Privacy ) S/MIME (Secure Multipurpose Internet Mail Extensions 多用途网际邮件扩充协议 )

11 三重 DES 的优点与缺点 NIST 在 1999 年发布新版 DES 标准 (FIPS PUB46-3), 指出 DES 只能用于遗留系统,3DES 将取代 DES 成为新标准优点密钥长度 112bit, 足够长底层算法与 DES 相同, 因此受密码分析时间远远长于其他加密算法, 对密码分析攻击有很强免疫力仅考虑安全性,3DES 会成为未来数十年加密算法的合适选择缺点 DES 的设计主要针对硬件实现, 而今在许多领域, 需要用软件方法来实现它, 在这种情况下,DES 效率相对较低分组长度 64, 似乎应该更长因此,3DES 不能成为长期使用的加密算法标准

2. IDEA 简介由瑞士的 Xuejia Lai 和 James Massey 于 1990 的 EuroCrypt 90 年公布了

为抗击差分密码攻击, 他们增强了算法的强度, 称 IPES(Improved PES) 并于 1992 年改名为

( 欧洲美国 ), 以商业目的使用 IDEA 算法必须向该公司申请许可分组大小 :64bit; 密钥长度 :128bit ; 不是

12 2. IDEA 简介由瑞士的 Xuejia Lai 和 James Massey 于 1990 的 EuroCrypt 90 年公布了 IDEA 密码算法第一版, 称为 PES (Proposed Encryption Standard) 在 EuroCrypt 91 上, 为抗击差分密码攻击, 他们增强了算法的强度, 称 IPES(Improved PES) 并于 1992 年改名为 IDEA(International Data Encryption Algorithm) IDEA 已由瑞士的 Ascom 公司注册专利 ( 欧洲美国 ), 以商业目的使用 IDEA 算法必须向该公司申请许可分组大小 :64bit; 密钥长度 :128bit ; 不是 Feistel 结构抗穷搜索攻击能力比 DES 强目前没有对 IDEA 的有效攻击 IDEA 的混淆和扩散设计原则来自三种运算, 它们易于软硬件实现 ( 加密速度快 )

13 IDEA 简介按位异或运算 ( ) 整数模 2 16 加 ( + ) 整数模乘 ( )(IDEA 的 S 盒 ) 扩散由称为 MA 结构的算法基本构件提供 F F2 Z Z6 G G2

14 IDEA 基本运算单元逐位异或, 记做例如 : = 模 2 16 的整数加, 记做例如 : = 模的整数乘, 记做定义为 : a b = ab mod ( ) 注意, 全零的分组代表 2 16 = -1( 因此 0 的乘法逆元是 0), 例 = 既 mod ( )=

15 IDEA 加密概述使用子分组 :16bit 的子分组 ; 使用简单操作 ( 易于加法移位等操作实现 ) 加密解密过程类似 ; 规则的结构 ( 便于 VLSI 实现 ) 每轮轮密钥长度为 96 bit(6 16) 64 位的明文分成 4 块 : X 1,X 2,X 3,X 4 明文经过 8 轮迭代和一个输出变换, 得到 64 位的密文 Y 1,Y 2,Y 3,Y 4 可以看作是 8.5 轮 :8 轮轮函数 +0.5 轮输出变换

16 IDEA 加密示意图 128 位密钥密钥扩展 16 Z 1 Z 52 由 128bit 密钥, 经过密钥扩展, 生成 52 个长度为 16 的子密钥

17 IDEA 轮函数 X1 X2 X3 X4 Z 1 Z 2 Z 3 Z 4 Z 5 Z 6

18 8

19 IDEA 的密钥生成由 128bit 密钥, 经过密钥扩展, 生成 52 个长度为 16 的子密钥前 8 个子密钥直接从密钥中取出 ; 对前 8 个 16 比特的子密钥进行 25bit 的循环左移, 得到下一个 8 16 比特, 该过程循环 7 次接下来的密钥就从中取出 ; 重复进行直到 52 个子密钥都产生出来轮数

的头 4 个子密钥中导出 ; 解密密钥第 1 4 个子密钥对应于 1 4 加密子密钥的乘法逆元 ;2 3

20 IDEA 解密及解密密钥生成加密解密实质相同, 算法也相同但使用不同的密钥解密密钥来自加密密钥, 以如下方法从加密子密钥 Z 1 -Z 52 中导出 : 解密循环 i 的头 4 个子密钥从加密循环 10-i 的头 4 个子密钥中导出 ; 解密密钥第 1 4 个子密钥对应于 1 4 加密子密钥的乘法逆元 ;2 3 对应 2 3 的加法逆元 ; 对前 8 个循环来说, 循环 i 的最后两个子密钥等于加密循环 9-i 的最后两个子密钥 ;

21 IDEA 的速度和密码分析软件实现比 DES 快两倍抗穷举攻击若有每秒测试十亿个密钥的芯片, 并采用十亿个芯片并行处理, 需要比宇宙年龄更长若有个上述芯片并行处理, 可在一天内找出密钥但宇宙中没有足够硅原子来制作这样的芯片目前比穷举攻击更快对 IDEA 的攻击仅对 2.5 轮以下有效 4 轮 IDEA 很快且刚好是安全的抗差分攻击 Lai 证明了 IDEA 的第四轮以后对差分免疫存在极其少的弱密钥, 但被选中的概率为 (1/2 96 ), 且很容易被修订虽然 IDEA 有坚强的理论基础高效且安全已经实用化, Bruce Schneier 认为 IDEA 是 DES 的最好替代, 但要取代一个当今正在使用的算法仍不容易

22 3. AES 1997 年 4 月 15 日美国国家标准和技术研究所 (NIST) 发起征集 AES(AES Advanced Encryption Standard) 算法的活动, 并成立了 AES 工作组目的是为了确定一个非保密的公开披露的全球免费使用的加密算法, 用于保护下一世纪政府的敏感信息 AES 的基本要求 : 比三重 DES 快至少和三重 DES 一样安全分组长度 128 比特支持密钥长度为 128/192/256 比特

23 历史 1998: 21 个候选算法中的 15 个候选算法通过第一轮评估 1999: 5 个候选算法入围 : Mars (IBM): -complex, fast, high security margin RC6 (MIT):-v. simple, v. fast, low security margin Rijndael( 比利时,Joan Daemen & Vincent Rijmen):-clean, fast, good security margin Serpent( 英, 以, 美 ): -slow, clean, v. high security margin Twofish( 美 ): -complex, v. fast, high security margin 2000: Rijndael 算法被选中其原型是 Square 算法, 可抗击差分分析和线性分析迭代分组密码, 其分组长度和密钥长度都是可变的根据 AES 的要求, 分组长度为 128bit, 密码长度为 128/192/256bit, 相应的轮数 r 为 10/12/14; 2001 年 11 月, 美国 NIST 发布标准 FIPS PUB 197

24 NIST 评估标准第一轮及第二轮安全性 : 实际安全随机性可靠性其它成本 : 无专利, 软硬件效率存储空间需求 ( 电路门数 RAM 大小 ) 算法和执行特征 : 灵活性简洁性适用性最终评估标准一般安全性 : 对抗现有攻击软件实现 : 速度跨平台能力密钥长度导致执行速度变化受限空间环境 :RAM/ROM 受限环境硬件实现 : 如硬件设备存储区域加倍将导致设备费用上升对执行的攻击 : 如计时攻击和能量分析攻击加密与解密 : 算法若不一致, 会占用存储空间, 且存在执行时间差异密钥灵活性 : 用少量资源快速改变密钥多功能性和灵活性 : 密钥长度分组长度轮数的变化 ; 特定环境下的优化指令级并行执行的潜力 : 当前和未来处理器中利用 ILP 特征的能力

25 选择 Rijndael 的原因 NIST 最终选择了 Rijndael 作为 AES 的标准, 因为全面地考虑,Rijndael 汇聚了安全, 性能好, 效率高, 易用和灵活等优点 Rijndael 使用非线性结构的 S-boxes, 表现出足够的安全余地 ; Rijndael 在无论有无反馈模式的计算环境下的硬, 软件中都能显示出其非常好的性能它的密钥安装的时间很好, 也具有很高的灵活性 ; Rijndael 的非常低的内存需求也使它很适合用于受限的环境 ; Rijndael 的操作简单, 并可抵御时间和能量攻击, 此外, 它还有许多未被特别强调的防御性能 ; Rijndael 在分组长度和密钥长度的设计上也很灵活, 算法可根据分组长度和密钥长度的不同组合提供不同的迭代次数, 虽然这些特征还需更深入地研究, 短期内不可能被利用, 但最终,Rijndael 内在的迭代结构会显示良好的潜能来防御入侵行为

26 AES 参数密钥长度分组大小迭代轮数轮密钥长度扩展密钥长度 (bit) (bit) (bit) (bit) (bit) AES AES AES

27 AES 基本运算一个被 Rijndael 处理的数据块 ( 称为状态 ) 和密钥均可用一个矩阵列图来表示每一列为一个 4 字节阵列 (1 字 =4 字节 =32 位 ) N b 代表分组长度对应的列数 (=n/32) N k 代表密钥长度对应的列数 (=k/32) 每次加密操作的迭代次数 (Nr) 分为三种以 AES-128 为例, 明文长度 n=128, 密钥长度 k=128 不是 Feistel 结构

28 密钥和扩展密钥的结构从上到下, 从左到右, 每列 8 4=32 比特输入 State 数组输出 K 0 K 4 K 8 K 12 K 1 K 5 K 9 K 13 w o w 1 w 2 w 42 w 43 K 2 K 6 K 10 K 14 K 3 K 7 K 11 K 15 密钥从上到下, 从左到右, 每列 8 4=32 比特扩展密钥扩展为 44 个字 ( 每个字为 32 比特, 4 字节 ) 每列代表一个字

29 AES 的完整结构 (AES-128)

30 AES 具体结构不是 Feistel 结构, 加密解密算法不同对于加密和解密均以轮密钥加作为开始 9 轮迭代, 每轮包括字节代换 :S 盒子 ( 代换, 之前有密钥, 属于混淆, 非线性 ) 行移位 : 简单置换 ( 属于扩散, 线性 ) 列混淆 : 利用域 GF(2 8 ) 上的算术特性 ( 属于扩散, 线性 ) 轮密钥加 : 当前分组 XOR 轮密钥 (Vernam 密码, 线性 ) 第 10 轮只包含字节代换行移位轮密钥加目的是满足算法的可逆性仅在轮密钥加阶段使用密钥每个阶段均可逆具有非常明晰的代数结构

31 AES 的一轮加密过程字节代换 8 8 行移位 8 列混淆 8 8 轮密钥加 8

32 AES的字节代换及逆变换 S盒子正向字节代换简单查表 S盒子是一个16 16矩阵包含8位值所能表达的全部256种可能的变换字节代换时对每个字节高四位作为行值低四位作为列值找到S盒子中的对应元素输出例 S {95}={2A} 正向S盒子 S-1{2A}={95} 逆向S盒子

33 AES 演示 AES 演示

34 4.1 分组密码的工作模式电码本模式 (ECB 模式 ) Electronic Codebook 工作方式 : 用相同密钥对各个明文组分别加密, 一次处理 64 位明文每个 64 位明文对应唯一密文明文长度大于 64 位 : 明文分段, 最后一段可能需要填充特征 : 相同 64 位明文对应相同 64 位密文攻击 : 若消息有固定开头交换明文组顺序, 并交换对应密文组顺序对分组的代换或重排攻击成功的原因 : 对各个分组的加密彼此独立应用 : 单个数据的安全传输

35 Electronic Codebook (ECB) 模式 ECB 加密 ECB 解密

36 4.2 分组密码的工作模式密码分组链接模式 Cipher Block Chaining (CBC) 目的 : 克服 ECB 的弱点思路 : 将消息分为很多块, 并通过加密进行链接已加密的密文分组与当前的明文分组链接在一起使用初始向量 IV C i = E K (P i C i-1 ) C 0 = IV 应用 : 对大量数据的加密和认证

37 CBC 加密解密 CBC 加密 CBC 解密

38 CBC 消息填充与优缺点消息的最后一个 Block 小于 64 比特时, 需要填充方法一 : 填充 NULL 方法二 : 写入填充个数 [b1 a2 c3]=>[b1 a2 c ] 优点每个密文分组均依据于之前的全部分组对任意一个分组的改动都会影响后继的所有密文分组需要初始向量缺点收发双方都必须知道 IV 如果攻击者获得了 IV, 可以通过预先改变 IV 中的某些位, 使得接收者的明文中部分位被取反 P 1 [i] = IV[i] D k (C 1 [i]) 解决方法 :IV 为固定值, 或者在发送消息前用 ECB 来保护 IV

39 4.3 密码反馈模式 (CFB) Cipher FeedBack 消息被看作比特流, 本质是分组加密, 可以用于实现流密码实现每次对任意比特的加密 (CFB-1, CFB-8, CFB-64, CFB-128) 明文消息与分组加密的输出进行异或, 所得结果反馈进入移位寄存器作为下一阶段的输入加密 :C i = P i A s (E K (S s (C i-1 ))), 其中 s 是流密码每次加密的长度 = P i = C i, C -1 = IV, S s 代表移位寄存器 S 移动 s 位, A s 代表取前 s 位解密 :P i =C i A s (E K (S s (C i-1 ))) 用途 : 流密码加密, 认证

40 CFB 加密 C M-1 移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位选择丢弃 s 位 64 - s 位选择丢弃 s 位 64 - s 位选择丢弃 s 位 64 - s 位

41 CFB 解密 C M-1 移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位选择丢弃 s 位 64-s 位选择丢弃 s 位 64-s 位选择丢弃 s 位 64-s 位

42 CFB 的优缺点优点非常适合数据流的加密, 是最常见的流密码模式缺点每得到 s 个输入比特, 需要暂停进行分组加密存在误差扩散 : 密文传输中某位发生错误, 会影响后继的解密

43 4.4 输出反馈模式 (OFB) Output FeedBack 与 CFB 非常相似, 消息被看作比特流与 CFB 不同, 加密函数的输出被反馈回移位寄存器作为下一次的输入 ( 而不是密文单元 ) 因为反馈值与明文消息无关, 所以反馈值都可以预先计算分组加密的输出与明文异或得到密文加密 C i = P i O i O i =A s (E K (S s (O i-1 ))) O -1 = IV 用途 : 有信道噪声环境下的流密码

44 OFB 加密 C M-1 移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位选择丢弃 s 位 64 - s 位选择丢弃 s 位 64 - s 位选择丢弃 s 位 64 - s 位

45 OFB 解密 C M-1 移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位移位寄存器 64-s 位 s 位选择丢弃 s 位 64 - s 位选择丢弃 s 位 64 - s 位选择丢弃 s 位 64 - s 位

46 OFB 优缺点优点传输过程中, 比特差错不会扩散可以预计算分组, 流加密时不需停顿缺点对抗消息流篡改攻击的能力弱于 CFB: 若对密文取反, 则解密后的明文也取反可以看作是一次一密的变形 (Vernam 密码 ) 所以绝对不能重复使用相同的密钥序列和 IV 发送方和接收方必须同步

47 4.5 计数器模式 (CRT) Counter 在 70 年代已经被提出, 直到在 ATM 和 IPSec 中应用, 才被人们广泛研究与 OFB 相似处 : 明文与分组的输出异或得到密文与 OFB 的差异 : 分组加密的输入是计数对每个明文, 必须使用不同的分组密钥和计算器值 ( 绝不重用 ) 可以并行处理加密 C i = P i O i O i = E K (Counter) 用途 : 高速网络加密

49 CTR 的优缺点优点高效缺点可以并行处理多块明文密文可以预计算 good for bursty high speed links 随机访问 : 密文的第 i 个分组可以随机访问, 不需知道前面 i-1 个密文组 (c.p. CBC) 可证安全 : 是 CPA 安全的前提 : 使用了真正的随机数生成器, 且每个计数器值绝不重用密钥计数器值绝不能重用

50 总结知识要点三重 DES 3DES, 两个密钥的 3DES, 参数国际数据加密算法 IDEA 的参数及优点高级数据加密标准 AES 的参数及优点分组密码的工作模式, 各种模式的优缺点

51 下一讲预告用对称密码实现保密性

52 谢谢!

第二讲信息论基础与古典加密技术

第二讲信息论基础与古典加密技术第三讲分组密码与数据加密标准上海交通大学计算机系内容分组密码简介 Feistel 密码简化 DES 数据加密标准 Data Encryption Standard DES 的强度差分分析和线性分析引言 -- 分组密码与流密码对称加密包括分组密码和流密码分组密码 VS. 流密码 (Stream Cipher) 分组密码信息被分块 (block) 进行加密和解密, 连续的明文元素使用相同的密钥

第二讲 信息论基础与古典加密技术

第二讲信息论基础与古典加密技术