西安电子科技大学：《现代密码学》课程教学资源（PPT课件讲稿）第四章 分组密码（分组密码的分析）

四、AES 2021/2/21

2021/2/21 2 四、AES

密钥编排 ■轮密钥的比特数等于分组长度乘以轮数 加1 ■种子密钥被扩展为扩展密钥 轮密钥从扩展密钥中按顺序选取 2021/2/21

2021/2/21 3 密钥编排 ◼ 轮密钥的比特数等于分组长度乘以轮数 加1 ◼ 种子密钥被扩展为扩展密钥 ◼ 轮密钥从扩展密钥中按顺序选取

分组密码的分析 2021/2/21

2021/2/21 4 分组密码的分析

差分密码分析( Differential感 cryptanalysis) DES经历了近20年全世界性的分析和攻击,提出了 各种方法,但破译难度大都停留在25量级上。 1991年 Biham和 Shamir公开发表了差分密码分析法 才使对DES一类分组密码的分析工作向前推进了 大步。目前这一方法是攻击迭代密码体制的最佳方 法,它对多种分组密码和Hash函数都相当有效, 相继攻破了FEAL、 LOKI LUCIFER等密码 ■此法对分组密码的研究设计也起到巨大推动作用 2021/2/21 5

2021/2/21 5 差分密码分析(Differential cryptanalysis) ◼ DES经历了近20年全世界性的分析和攻击，提出了 各种方法，但破译难度大都停留在2 55量级上。 ◼ 1991年Biham和Shamir公开发表了差分密码分析法 才使对DES一类分组密码的分析工作向前推进了一 大步。目前这一方法是攻击迭代密码体制的最佳方 法，它对多种分组密码和Hash 函数都相当有效， 相继攻破了FEAL、LOKI、LUCIFER等密码。 ◼ 此法对分组密码的研究设计也起到巨大推动作用

差分密码分析 erential cryptanalysis) 以这一方法攻击DES,尚需要用247个选择明文 和247次加密运算。为什么DES在强有力的差值 密码分析攻击下仍能站住脚? 根据 Coppersmith199内部报告透露,IBM的 DES研究组早在1974年就已知道这类攻击方法, 因此,在设计S盒、P置换和迭代轮数上都做 了充分考虑,从而使DES能经受住这一有效破 译法的攻击。 2021/2/21 6

2021/2/21 6 差分密码分析(Differential cryptanalysis) ◼ 以这一方法攻击DES，尚需要用2 47个选择明文 和2 47次加密运算。为什么DES在强有力的差值 密码分析攻击下仍能站住脚? ◼ 根据Coppersmith[1992内部报告]透露，IBM的 DES研究组早在1974年就已知道这类攻击方法， 因此，在设计S盒、P-置换和迭代轮数上都做 了充分考虑，从而使DES能经受住这一有效破 译法的攻击

差分密码分析( Differential感 cryptanalysis) 差分密码分析是一种攻击迭代分组密码的选择明 文统计分析破译法。 不是直接分析密文或密钥的统计相关性,而是 分析明文差分和密文差分之间的统计相关性。 给定一个r轮迭代密码,对已知n长明文对X和X, 定义其差分为 △X=XQ(X) 其中,⑧表示n-bits组X的集合中定义的群运算, (x)为X在群中的逆元 2021/2/21

2021/2/21 7 差分密码分析(Differential cryptanalysis) ◼ 差分密码分析是一种攻击迭代分组密码的选择明 文统计分析破译法。 ◼ 它不是直接分析密文或密钥的统计相关性，而是 分析明文差分和密文差分之间的统计相关性。 ◼ 给定一个r轮迭代密码，对已知n长明文对X和X‘， 定义其差分为 X=X(X’) -1 其中，表示n-bits组X的集合中定义的群运算， (X’)-1为X’在群中的逆元

差分密码分析 erential cryptanalysis) 在密钥k作用下,各轮迭代所产生的中间密文 差分为 △Y(l)=Y(Y(a)10≤i≤r ■i=0时,Y(0=X,Y(0=X,△Y(0=△X。 i=r时,△F△Y(),是第滯加密的子密钥, Y()=f(Y(-1),0)。 由于X≠Y”,因此,△Y()≠e(单位元) 每轮迭代所用子密钥与明文统计独立,且可 认为服从均匀分布。 2021/2/21

2021/2/21 8 差分密码分析(Differential cryptanalysis) ◼ 在密钥k作用下，各轮迭代所产生的中间密文 差分为 Y(i)=Y(i)Y’(i) -1 0ir ◼ i=0时，Y(0)=X，Y’(0)=X’ ，Y(0)=X。 ◼ i=r时，Y=Y(r)，k (i)是第i轮加密的子密钥， Y(i)=f(Y(i－1), k (i))。 ◼ 由于XX’ ，因此，Y(i)e(单位元)。 ◼ 每轮迭代所用子密钥k (i)与明文统计独立，且可 认为服从均匀分布

差分密码分析 Differential cryptanalysis) Y(OFF Y(1) Y(2) Y(r-1 f Y(r) (1) k k kr Y(OEX 力叫 △X=△Y(0) △Y(1) △Y(2) △Y(r-1) △Y=△Y(r) r轮迭代分组密码的差分序列 2021/2/21

2021/2/21 9 差分密码分析(Differential cryptanalysis) r 轮迭代分组密码的差分序列 Y’(0)=X’ Y’(1) Y’(2) Y’(r－1) Y’® Y(0)=X Y(1) Y(2) Y(r－1) Y(r) f f … f k (1) k (2) k (r) f f … f X=Y(0) Y(1) Y(2) Y(r－1) Y=Y(r)

差分密码分析( Differential感 cryptanalysis) Lai等引入 Markov链描述多轮迭代分组密码的差 分序列。并定义了 Markov密码。 nLa等证明, Markov密码的差分序列△X=△Y(0), △Y(1),,△Y(r)是一齐次 Markov链,且若△X在群 的非零元素上均匀分布,则此 Markov链是平稳的。 ■不少迭代分组密码可归结为 Markov密码。如 DESLOK、FEAL和 REDOC[Lai.1992 2021/2/21

2021/2/21 10 差分密码分析(Differential cryptanalysis) ◼ Lai等引入Markov链描述多轮迭代分组密码的差 分序列。并定义了 Markov密码。 ◼ Lai等证明，Markov密码的差分序列X=Y(0)， Y(1), …, Y(r)是一齐次Markov链，且若X在群 的非零元素上均匀分布，则此Markov 链是平稳的。 ◼ 不少迭代分组密码可归结为Markov密码。如 DESLOK1、FEAL和REDOC [Lai. 1992]

差分密码分析 erential cryptanalysis) 个 Markov型密码,可以用转移概率 P(△AX(1)=a1△X=a)的所有可能转移值构成 的矩阵描述,称其为齐次 Markov链的转 移概率矩阵,以∏表示 个n-bits分组密码有1≤i,M=2-1。对 所有r,有 I=;()=P(△)=a1△X=a ∏的每一行都是一概率分布,行元素之和 为 2021/2/21

2021/2/21 11 差分密码分析(Differential cryptanalysis) ◼ 一个Markov 型密码，可以用转移概率 P(Y(1)=jX=i )的所有可能转移值构成 的矩阵描述，称其为齐次Markov 链的转 移概率矩阵，以表示。 ◼ 一个n-bits分组密码有1i, jM=2 n－1。对 所有r，有 r=[pij (r)]=[P(Y(r)=jX=i )] 的每一行都是一概率分布，行元素之和 为1