差分密码分析和线性密码分析原理.pptx

差分密码分析和线性密码分析原理
CONTENTS
01
02
差分密码分析
线性密码分析
PART
ONE
差分密码分析
差分密码分析是迄今为止已知的攻击迭代分组密码最有效的方法之一,其基本思想是:通过分析明文对的差值对密文对的差值来影响来恢复某些密钥比特
当密码分析人员可以进行选择明文分析时,差分密码分析十分有效。
已知明文的差分密码分析也是可行的,但是要求已知明密文的量很大
差分密码分析简介
设计DES的IBM小组知道了差分分析
1974
1991
1990
……
Biham和Shamir对多种加密算法和Hash函数进行差分密码分析攻击,结果发表在[BIHA93]中
差分密码分析公开发表
最早研究是Murphy分析分组密码FEAL【MURP90】
差分密码分析的历史
6
符号定义
P 表示明文,T 表示密文
(P, P∗)表示明文对,其异或后得到特定的值:P’,使得 P’= P ⊕ P∗
(T, T∗) 表示密文对,其异或后得到特定的值T’,使得 T’= T ⊕ T∗
带撇的值总是表示差分,P’,T’, a’, A’。例如,a’= a ⊕ a∗
7
差分密码分析_DES
DES 的设计要求之一是确保尽可能的分布均匀
例如,明文或密钥的1比特变化,将导致64比特的密文中大约32比特的看起来是不可预测和随机的变化
不过对于固定的密钥,DES的差分并不呈现伪随机现象
即对于固定明文P 和P∗的异或P’
T’=T⊕T∗不是均匀分布的
8
S-Box是非差分均匀的
对于输入S盒的6比特的(x, x∗)值对,一共有多少种可能?
考虑一个S-box的差分现象:
输入值对的差分为x’= x⊕ x∗
差分值可能有多少种?
对于其4比特输出值,y=S(x), y∗= S(x∗),以及y’=y⊕ y∗=S(x)⊕ S(x∗)
输出差分值有多少种可能?
642 = 4096
26= 64
24= 16
S-Box是非差分均匀的
x
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
x⊕f’
f
e
d
c
b
a
9
8
7
6
5
4
3
2
1
0
S(x)
e
4
d
1
2
f
b
8
3
a
6
c
5
9
0
7
S(x⊕f’)
7
0
9
5
c
6
a
3
8
b
f
2
1
d
4
E
S(x) ⊕S(x⊕f’)
9
4
4
4
e
9
1
b
b
1
9
e
4
4
4
9
输入差分f’=1111
10
S1 的差分分布表
0
.
.
.
.
.
.
.
.
.
63
=26-1
出现的次数
6比特的差分输入x’有64个值:00-3F(16进制,10进制是0-63)
4比特的差分输出y’有16个值:0-F(16进制,10进制是0-15)
可以看到:第一行除第一列外全为0,因为当x’= x⊕ x∗= 0,同样的输入出现了两次,因此其输出y’=y⊕ y∗= 0
后面的行:
例如,当 x’= 01 时, 6个可能的y’中有5个值:0, 1, 2, 4, 8呈现0可能次数,就是说不出现。
A 出现的概率是12/64
9 和C 出现的概率是10/64
这就是说,S1呈现出很强的不均匀分布
这种差分不均匀性对于所有的S盒S1, S2, . . . , S8都有体现
考虑输入异或值为34时,可能的输出异或是:
其中:344有两种可能,这种输入对是成双的,即:(α, β)和(β, α)