2010-5-14 1
第四章 分组密码
一、分组密码概述
二、分组密码运行模式
三,DES
四,AES
五、分组密码的分析
2010-5-14 2
四,AES
2010-5-14 3
密钥编排
? 轮密钥的比特数等于分组长度乘以轮数
加 1
? 种子密钥被扩展为扩展密钥
? 轮密钥从扩展密钥中按顺序选取
2010-5-14 4
分组密码的分析
2010-5-14 5
差分密码分析 (Differential
cryptanalysis)
? DES经历了近 20年全世界性的分析和攻击, 提出了
各种方法, 但破译难度大都停留在 255量级上 。
? 1991年 Biham和 Shamir公开发表了差分密码分析法
才使对 DES一类分组密码的分析工作向前推进了一
大步 。 目前这一方法是攻击迭代密码体制的最佳方
法, 它对多种分组密码和 Hash 函数都相当有效,
相继攻破了 FEAL,LOKI,LUCIFER等密码 。
? 此法对分组密码的研究设计也起到巨大推动作用 。
2010-5-14 6
差分密码分析 (Differential
cryptanalysis)
? 以这一方法攻击 DES,尚需要用 247个选择明文
和 247次加密运算 。 为什么 DES在强有力的差值
密码分析攻击下仍能站住脚?
? 根据 Coppersmith[1992内部报告 ]透露, IBM的
DES研究组早在 1974年就已知道这类攻击方法,
因此, 在设计 S盒, P-置换和迭代轮数上都做
了充分考虑, 从而使 DES能经受住这一有效破
译法的攻击 。
2010-5-14 7
差分密码分析 (Differential
cryptanalysis)
? 差分密码分析是一种攻击迭代分组密码的选择明
文统计分析破译法 。
? 它不是直接分析密文或密钥的统计相关性, 而是
分析明文差分和密文差分之间的统计相关性 。
? 给定一个 r轮迭代密码, 对已知 n长明文对 X和 X‘，
定义其差分为
?X=X?(X’)-1
其中, ?表示 n-bits组 X的集合中定义的群运算,
(X’)-1为 X’在群中的逆元 。
2010-5-14 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)与明文统计独立, 且可
认为服从均匀分布 。
2010-5-14 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)
2010-5-14 10
差分密码分析 (Differential
cryptanalysis)
? Lai等引入 Markov链描述多轮迭代分组密码的差
分序列 。 并定义了 Markov密码 。
? Lai等证明, Markov密码的差分序列 ?X=?Y(0)，
?Y(1),…,?Y(r)是一齐次 Markov链, 且若 ?X在群
的非零元素上均匀分布, 则此 Markov 链是平稳的 。
? 不少迭代分组密码可归结为 Markov密码 。 如
DESLOK1,FEAL和 REDOC [Lai,1992]。
2010-5-14 11
差分密码分析 (Differential
cryptanalysis)
? 一个 Markov 型密码, 可以用转移概率
P(?Y(1)=?j??X=?i)的所有可能转移值构成
的矩阵描述, 称其为齐次 Markov 链的转
移概率矩阵, 以 ?表示 。
? 一个 n-bits分组密码有 1?i,j?M=2n－ 1。 对
所有 r,有
?r=[pij (r)]=[P(?Y(r)=?j??X=?i)]
?的每一行都是一概率分布, 行元素之和
为 1。
2010-5-14 12
差分密码分析 (Differential
cryptanalysis)
对于 Markov型密码, 当 ?X在非零元素
上为均匀分布, 则 ?Y为一平稳 Markov
链, 此时对于每个 j有
即各列元素之和亦为 1,从而可知各列
也构成一概率分布 。
p pij n n ij n
ii
nn 1
2 1
1
2 1
1
2 11
2 1
1
2 1
? ? ? ? ??
?
?
?
??
2010-5-14 13
差分密码分析 (Differential
cryptanalysis)
? 差分密码分析揭示出, 迭代密码中的一个轮迭代函数 f,若
已知三元组 { ? Y(i－ 1),Y(i),Y(i) ? Y(i)=f(Y(i－ 1),k(i)),
Y’(i)=f(Y’(i－ 1),k(i))},则不难决定该轮密钥 k(i)。
? 因此轮函数 f的密码强度不高 。 如果已知密文对, 且有办法
得到上一轮输入对的差分, 则一般可决定出上一轮的子密
钥 (或其主要部分 )。
? 在差分密码分析中, 通常选择一对具有特定差分 ?的明文,
它使最后一轮输入对的差值 ?Y(r－ 1)为特定值 ?的概率很高 。
2010-5-14 14
差分密码分析 (Differential
cryptanalysis)
? 差分密码分析的基本思想是在要攻击的迭代密码系统
中找出某高概率差分来推算密钥 。
? 一个 i轮差分是一 (?,?)对, 其中 ?是两个不同明文 X和 X’
的差分, ?是密码第 i轮输出 Y(i)和 Y’(i)之间的差分 。
? 在给定明文的差分 ?X＝ ?条件下, 第 i轮出现一对输出
的差分为 ?的条件概率称之为第 i轮差分概率, 以
P(?Y(i)=?|?X＝ ?)表示 。
? 对于 Markov密码, 第 i差分概率就是第 i阶转移概率矩
阵 ?i中的元素 (?,?)。
2010-5-14 15
r轮迭代密码的差分分析
? 寻求第 (r－ 1)轮差分 (?,?)使概率 P(?Y(r－ 1)=?|?X=?)的
值尽可能为最大 。
? 随机地选择明文 X,计算 X’使 X’与 X之差分为 ?,在密钥 k
下对 X和 X’进行加密得 Y(r)和 Y’(r),寻求能使 ?Y(r－ 1)=?
的所有可能的第 r轮密钥 K(r),并对各子密钥 ki(r)计数, 若
选定的 ?X=?,(X,X’)对在 ki(r)下产生的 (Y,Y’)满足 ?Y(r－
1)=?,就将相应 ki(r)的计数增加 1。
? 重复第 2步, 直到计数的某个或某几个子密钥 ki(r)的值,
显著大于其它子密钥的计数值, 这一子密钥或这一小的
子密钥集可作为对实际子密钥 K(r)的分析结果 。
2010-5-14 16
线性攻击
? Rueppel[1986]的流密码专著中曾提出以最接近的
线性函数逼近非线性布尔函数的概念, Matsui推
广了这一思想以最隹线性函数逼近 S盒输出的非零
线性组合 [1993],即所谓线性攻击, 这是一种已知
明文攻击法 。
? 对已知明文 x密文 y和特定密钥 k,寻求线性表示式
(a·x)?(b·y)=(d·k)
其中 (a,b,d)是攻击参数 。 对所有可能密钥, 此表
达式以概率成立 。 对给定的密码算法, 使极大化 。
2010-5-14 17
线性攻击
? 为此对每一 S盒的输入和输出之间构造统计线
性路径, 并最终扩展到整个算法 。
? 以此方法攻击 DES的情况如下：
? PA-RISC/66MHz工作站,
? 对 8轮 DES可以用 221个已知明文在 40秒钟内破译；
? 对 12轮 DES以 233个已知明文用 50小时破译；
? 对 16轮 DES以 247个已知明文攻击下较穷举法要快 。
? 如采用 12个 HP 9735/PA-RISC99MHz的工作站联合
工作, 破译 16轮 DES用了 50天 。
2010-5-14 18
第四章 单钥体制（二）
—— 分组密码
本 章 到此
结束。
谢谢大家！
2010-5-14 19
第五章 公钥密码
2010-5-14 20
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 21
数论简介
2010-5-14 22
素数和互素数
? 因子
? 整数 a,b,如果存在 m，使 a=mb，称为 b整除
a，记为 b|a，称 b是 a的因子。
? 性质
? a|1，则 a=± 1
? a|b且 b|a，则 a=b
? 对任意 b,b≠0,则 b|0
? b|g,b|h,对任意整数 m,n,有 b|(mg+nh)
(证明留给大家 )
2010-5-14 23
素数和互素数
? 素数
? 整数 p(p>1)为素数，如果 p的因子只有 ± 1,± p
? 整数分解的唯一性
任一整数 a(a>1)可唯一的分解为
其中 p1>p2>… >pt是素数,ai>0
例,91=7× 11,11011=7× 112× 13
tataa pppa ?21 21?
2010-5-14 24
素数和互素数
? 整数分解唯一性的另一表示
? P是所有素数的集合，任一 a(a>1)可表示为
? ap≥0,大多数指数项 ap为 0，任一整数可由非 0指数
列表表示。例如 11011可以表示为 {a7=1,a11=2,
a13=1}
? 两数相乘等价于对应的指数相加
? 由 a|b可得，对每一素数 p,ap ≤bp
?
?
?
Pp
a ppa
2010-5-14 25
素数和互素数
? c是 a和 b的最大公因子,c=gcd(a,b)
? c是 a的因子也是 b的因子
? a和 b的任一公因子也是 c的因子
? gcd(a,b)=1,称为 a,b互素
第四章 分组密码
一、分组密码概述
二、分组密码运行模式
三,DES
四,AES
五、分组密码的分析
2010-5-14 2
四,AES
2010-5-14 3
密钥编排
? 轮密钥的比特数等于分组长度乘以轮数
加 1
? 种子密钥被扩展为扩展密钥
? 轮密钥从扩展密钥中按顺序选取
2010-5-14 4
分组密码的分析
2010-5-14 5
差分密码分析 (Differential
cryptanalysis)
? DES经历了近 20年全世界性的分析和攻击, 提出了
各种方法, 但破译难度大都停留在 255量级上 。
? 1991年 Biham和 Shamir公开发表了差分密码分析法
才使对 DES一类分组密码的分析工作向前推进了一
大步 。 目前这一方法是攻击迭代密码体制的最佳方
法, 它对多种分组密码和 Hash 函数都相当有效,
相继攻破了 FEAL,LOKI,LUCIFER等密码 。
? 此法对分组密码的研究设计也起到巨大推动作用 。
2010-5-14 6
差分密码分析 (Differential
cryptanalysis)
? 以这一方法攻击 DES,尚需要用 247个选择明文
和 247次加密运算 。 为什么 DES在强有力的差值
密码分析攻击下仍能站住脚?
? 根据 Coppersmith[1992内部报告 ]透露, IBM的
DES研究组早在 1974年就已知道这类攻击方法,
因此, 在设计 S盒, P-置换和迭代轮数上都做
了充分考虑, 从而使 DES能经受住这一有效破
译法的攻击 。
2010-5-14 7
差分密码分析 (Differential
cryptanalysis)
? 差分密码分析是一种攻击迭代分组密码的选择明
文统计分析破译法 。
? 它不是直接分析密文或密钥的统计相关性, 而是
分析明文差分和密文差分之间的统计相关性 。
? 给定一个 r轮迭代密码, 对已知 n长明文对 X和 X‘，
定义其差分为
?X=X?(X’)-1
其中, ?表示 n-bits组 X的集合中定义的群运算,
(X’)-1为 X’在群中的逆元 。
2010-5-14 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)与明文统计独立, 且可
认为服从均匀分布 。
2010-5-14 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)
2010-5-14 10
差分密码分析 (Differential
cryptanalysis)
? Lai等引入 Markov链描述多轮迭代分组密码的差
分序列 。 并定义了 Markov密码 。
? Lai等证明, Markov密码的差分序列 ?X=?Y(0)，
?Y(1),…,?Y(r)是一齐次 Markov链, 且若 ?X在群
的非零元素上均匀分布, 则此 Markov 链是平稳的 。
? 不少迭代分组密码可归结为 Markov密码 。 如
DESLOK1,FEAL和 REDOC [Lai,1992]。
2010-5-14 11
差分密码分析 (Differential
cryptanalysis)
? 一个 Markov 型密码, 可以用转移概率
P(?Y(1)=?j??X=?i)的所有可能转移值构成
的矩阵描述, 称其为齐次 Markov 链的转
移概率矩阵, 以 ?表示 。
? 一个 n-bits分组密码有 1?i,j?M=2n－ 1。 对
所有 r,有
?r=[pij (r)]=[P(?Y(r)=?j??X=?i)]
?的每一行都是一概率分布, 行元素之和
为 1。
2010-5-14 12
差分密码分析 (Differential
cryptanalysis)
对于 Markov型密码, 当 ?X在非零元素
上为均匀分布, 则 ?Y为一平稳 Markov
链, 此时对于每个 j有
即各列元素之和亦为 1,从而可知各列
也构成一概率分布 。
p pij n n ij n
ii
nn 1
2 1
1
2 1
1
2 11
2 1
1
2 1
? ? ? ? ??
?
?
?
??
2010-5-14 13
差分密码分析 (Differential
cryptanalysis)
? 差分密码分析揭示出, 迭代密码中的一个轮迭代函数 f,若
已知三元组 { ? Y(i－ 1),Y(i),Y(i) ? Y(i)=f(Y(i－ 1),k(i)),
Y’(i)=f(Y’(i－ 1),k(i))},则不难决定该轮密钥 k(i)。
? 因此轮函数 f的密码强度不高 。 如果已知密文对, 且有办法
得到上一轮输入对的差分, 则一般可决定出上一轮的子密
钥 (或其主要部分 )。
? 在差分密码分析中, 通常选择一对具有特定差分 ?的明文,
它使最后一轮输入对的差值 ?Y(r－ 1)为特定值 ?的概率很高 。
2010-5-14 14
差分密码分析 (Differential
cryptanalysis)
? 差分密码分析的基本思想是在要攻击的迭代密码系统
中找出某高概率差分来推算密钥 。
? 一个 i轮差分是一 (?,?)对, 其中 ?是两个不同明文 X和 X’
的差分, ?是密码第 i轮输出 Y(i)和 Y’(i)之间的差分 。
? 在给定明文的差分 ?X＝ ?条件下, 第 i轮出现一对输出
的差分为 ?的条件概率称之为第 i轮差分概率, 以
P(?Y(i)=?|?X＝ ?)表示 。
? 对于 Markov密码, 第 i差分概率就是第 i阶转移概率矩
阵 ?i中的元素 (?,?)。
2010-5-14 15
r轮迭代密码的差分分析
? 寻求第 (r－ 1)轮差分 (?,?)使概率 P(?Y(r－ 1)=?|?X=?)的
值尽可能为最大 。
? 随机地选择明文 X,计算 X’使 X’与 X之差分为 ?,在密钥 k
下对 X和 X’进行加密得 Y(r)和 Y’(r),寻求能使 ?Y(r－ 1)=?
的所有可能的第 r轮密钥 K(r),并对各子密钥 ki(r)计数, 若
选定的 ?X=?,(X,X’)对在 ki(r)下产生的 (Y,Y’)满足 ?Y(r－
1)=?,就将相应 ki(r)的计数增加 1。
? 重复第 2步, 直到计数的某个或某几个子密钥 ki(r)的值,
显著大于其它子密钥的计数值, 这一子密钥或这一小的
子密钥集可作为对实际子密钥 K(r)的分析结果 。
2010-5-14 16
线性攻击
? Rueppel[1986]的流密码专著中曾提出以最接近的
线性函数逼近非线性布尔函数的概念, Matsui推
广了这一思想以最隹线性函数逼近 S盒输出的非零
线性组合 [1993],即所谓线性攻击, 这是一种已知
明文攻击法 。
? 对已知明文 x密文 y和特定密钥 k,寻求线性表示式
(a·x)?(b·y)=(d·k)
其中 (a,b,d)是攻击参数 。 对所有可能密钥, 此表
达式以概率成立 。 对给定的密码算法, 使极大化 。
2010-5-14 17
线性攻击
? 为此对每一 S盒的输入和输出之间构造统计线
性路径, 并最终扩展到整个算法 。
? 以此方法攻击 DES的情况如下：
? PA-RISC/66MHz工作站,
? 对 8轮 DES可以用 221个已知明文在 40秒钟内破译；
? 对 12轮 DES以 233个已知明文用 50小时破译；
? 对 16轮 DES以 247个已知明文攻击下较穷举法要快 。
? 如采用 12个 HP 9735/PA-RISC99MHz的工作站联合
工作, 破译 16轮 DES用了 50天 。
2010-5-14 18
第四章 单钥体制（二）
—— 分组密码
本 章 到此
结束。
谢谢大家！
2010-5-14 19
第五章 公钥密码
2010-5-14 20
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 21
数论简介
2010-5-14 22
素数和互素数
? 因子
? 整数 a,b,如果存在 m，使 a=mb，称为 b整除
a，记为 b|a，称 b是 a的因子。
? 性质
? a|1，则 a=± 1
? a|b且 b|a，则 a=b
? 对任意 b,b≠0,则 b|0
? b|g,b|h,对任意整数 m,n,有 b|(mg+nh)
(证明留给大家 )
2010-5-14 23
素数和互素数
? 素数
? 整数 p(p>1)为素数，如果 p的因子只有 ± 1,± p
? 整数分解的唯一性
任一整数 a(a>1)可唯一的分解为
其中 p1>p2>… >pt是素数,ai>0
例,91=7× 11,11011=7× 112× 13
tataa pppa ?21 21?
2010-5-14 24
素数和互素数
? 整数分解唯一性的另一表示
? P是所有素数的集合，任一 a(a>1)可表示为
? ap≥0,大多数指数项 ap为 0，任一整数可由非 0指数
列表表示。例如 11011可以表示为 {a7=1,a11=2,
a13=1}
? 两数相乘等价于对应的指数相加
? 由 a|b可得，对每一素数 p,ap ≤bp
?
?
?
Pp
a ppa
2010-5-14 25
素数和互素数
? c是 a和 b的最大公因子,c=gcd(a,b)
? c是 a的因子也是 b的因子
? a和 b的任一公因子也是 c的因子
? gcd(a,b)=1,称为 a,b互素
