ITPub博客

首页 > IT基础架构 > 网络安全 > DES和其他块密码系统为什么能够工作(ZT)

DES和其他块密码系统为什么能够工作(ZT)

原创 网络安全 作者:cklea 时间:2008-01-11 10:07:19 0 删除 编辑
. DES和其他块密码系统为什么能够工作
. 差异和线性密码分析
. 块密码系统:IDEA
. 流密码系统:RC4
. 公开密钥算法:
- Merkle-Hellman Knapsack算法
- RSA[@more@]1. 块密码系统

1.1 Feistel网络

很多的块密码系统都是用Feistel网络的形势。它的结构如下所示:

L_i-1 R_i-1
| |
| /|
/ f ---- K_i
/ |
/ |
/ |
/ |
/ |
/ |
/ XOR
/ |
| |
| |
L_i R_i

在F网络中输入被切分成为左块和右块,第i次的输出这样计算

L_i = R_i-1
R_i = L_i-1 XOR f(R_i-1,K_i)
F网络的一个好的性质是函数f可以任意的复杂,而且输入可以通过下面得到恢复:

R_i-1 = L_i
L_i-1 = R_i XOR f(L_i, K_i)

因此,即使f不是可逆转的,算法本身也是可逆转的,也就是允许解密。

F网络是DES,Lucipher,FEAL,Khutu,LOKI,GOST,Blowfish和其他块加密算法的一轮。
从下面的图你可以看出F网络是DES的一部分。


L_i-1 R_i-1 Key
| / | / | |
| / | Key shift shift Key
| L_i | | |
| | 压缩排列
| 扩展排列 |
| | |
| | |
| XOR-------------------/
| |
| |
| |
| S-Box置换
| |
| |
| |
| P-Box置换
| |
| |
| |
--------------- XOR
|
|
R_i

1.2 安全和块密码系统的设计目标

怎么设计f才能够使得密码是安全的呢?

混淆,漫射,雪崩效应是块密码设计的密码。混淆是指让输出和输出之间缺少联系。
这点可以通过置换得到。漫射是指在输出里面避免输入之间的联系。这点可以通过
排列得到。一个好的块密码系统应该拥有雪崩效应,也就是输出的一个bit可以很快
影响到所有的输出。

理想的64bit块的块密码系统应该是一个和密钥相关的64bit->64bit的随机映射。不
幸的是这样的话我们就需要一个2^64*2^56=2^120大小的表(如果我们使用56bit密钥
的话)。

因为这样的话,我们需要的存储太多了,于是我们使用伪随机映射来近似理想函数。
一个不停的在小块上进行置换并且在块之间进行排列的算法被称为置换-排列网络。
这样的算法是乘积密码系统的一个例子,因为它通过迭代生成混淆和漫射。一个拥有
多轮,并且每轮的结构都相同的密码系统叫做迭代密码系统。DES就是一个例子,他
是迭代块密码系统,置换-排列密码系统,也是乘积密码系统。

1.3 DES安全

DES的设计目标就是上面所述的目标。它的设计也是为防止差异密码分析。

1.3.1 E-Box和P-Box

DES的E-box的输入是32bits,输出是48bits。输出的48bits是由输入的32bits通过
某些位重复组成的。特别的,对每个4bits块,第一个和第四个重复一次,而其他两
bits不重复。因此E-box产生雪崩效应,这是因为从S-Box在R轮输出的4bits会在R+1
轮成为6个S-boxs的输入。而E-box也启动密钥的48bits在XOR操作中的使用。

...32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
| | | | | | | | | | | | | | | | |
1 48|2 3 4 5|7 6|8 9 10 11|13 12|14 15 16 17|19 18|20 21 22 23|25

DES的P-box是一个直接的32-bit的排列(每个输入bit仅仅使用一次)

1.3.2 S-box

这里有8个S-box,每个S-box的输入是6bit,输出是4bit。S-box的一些安全特性是:

. 输入中有1bit的差异至少影响输出的2bit。
. 可以防止差异分析

1.3.3 DES的弱点

. 某些密钥是不安全的。在DES的密钥空间中,64个是不好的选择。幸运的是,64
个显然太少了,程序可以检查你的密码是不是这64个之列从而提醒你不要使用他们。

- 弱密钥:这里有4个弱密钥:0x00000000000000,0x0000000FFFFFFF,
0xFFFFFFF0000000,0xFFFFFFFFFFFFFF。当你使用这些密钥时,每一轮的子密钥
都是一样的。这就是的密钥分析变的简单很多。它也使得E_k(X)=D_k(X),这是
因为DES的加密算法和解密算法是一样的,只是使用的子密钥是完全相反的顺序

- 半弱密钥:有12个。当你使用这些密钥的时候,在16轮种,你实际上只有两个
不同的子密钥。这是的密码分析变得简单很多。

- 可能的弱密钥:有48个。当你使用这些密钥的时候,这里只有4个不同的子密钥
每个子密钥使用了4次。同样,这也是的分析变得简单了许多。

. S-box 5是统计强偏。如输入是a0,a1,a2,a3,a4,a5,输出是b0,b1,b2,b3,那么
在64个可能的输入中,有12个都有a1=b0+b1+b2+b3。理想的应该有32个,而线
性分析正好可以利用这点。

1.3.4 实际应用中的DES。

DES经常在实际应用中被使用。

. 银行
- 银行机器
- 银行间的传输
. ISDN
. Kerbeios
. Unix passwd身份识别
. 加密邮件

DES并不是很多新的系统的选择,这是因为56bit的密钥太小了。虽然如此,3-DES
在依然是用DES的同时保证了更大的安全性。它的基本思想是使用不同的密钥加密
多次。在3-DES中

C = E_k1(D_k2(E_k3(P)))
P = D_k3(E_k2(D_k1(C)))

注意到你不能够简单C = E_k1(E_k2(P))而得到更好的安全性。如果算法是一个
群,那么这个和C = E_k3(P)的效果是完全一样的。如果算法不是一个群,那么
存在一种办法可以让你通过2^(n+1)次测试就能够得到密钥,而并不是你想象中
的2^(2n),这里的n是密钥的长度。而DES不是一个群。

1.4 差别分析

定义dV = V1 XOR V2以及dY = Y1 XOR Y2。

E-box

/
V Key_i
/
/
XOR
|
|
X
|
S-box
|
|
Y
|

上图展示的是DES的一轮的一部分。差别分析的基本思想是对任意给定的dV,
并不是所有的dY都是等可能的。如果一个密码分析人员可以使得某人对一对
明文进行加密,而明文的差别是dV,那么它可以得到对应的一对密文,计算
dY,然后使用dV和dY以及V来得到更多的关于Key_i的信息。当然,在你的数据
变得有统计价值之前,你需要很多对这样的信息。

这个主意对每轮作一次。在密码系统中轮数越多,这种办法就越难。

差分分析使得14轮的DES分析确实比BF分析容易很多,但是对16轮的DES越效果很小。
这是因为DES的设计者知道很多差别分析的办法,然后设计了S-box来抵御他。


1.5 线性分析

线性分析允许攻击者获得一个位的关于密钥的信息,前提是他知道明文和对应的
秘文。它的想法是 明文中某些位的异或和密文中某些位的异或的异或给出了一些
关于密钥中的某些位的异或的信息。这种分析在S-box的线性近似中出现某些偏倚
的时候工作,比如S-box 5就是DES中最偏得S-box了。

E-box


i_26

key_i的bit 26
/
/
/
XOR
|
| | | a26 | |
| | | | | |
s-box 5
| | | |
b17 b19
b18 b20

上图显示了s-box 5的操作过程。如果我们使用线性分析,直到一些关于i_26的信息,
以及b17,b18,b19,b20,那么我们就能够知道这一轮中key_i的bit 26的一些信息了。
(1) i_26 XOR key_i's bit 26 = a_26
(2) a_26 = b_17 XOR b_18 XOR b_19 XOR b_20,仅仅在64中可能中的12种出现。

线性分析是对DES的最成功的攻击,但是他并不比BF好多少。

1.6 IDEA

IDEA是另外一个块密码系统。它对64bit的块进行操作,并且使用128bit的密钥,
IDEA是一个乘积密码系统。它生成3个代数群:

. 加法(提供漫射特性)
. 乘法(提供混淆特性)
. XOR

IDEA也有一些弱密码,但是他们并不像DES的那些弱密码一样。如果你在IDEA中使用
弱密码,那么攻击者就可以选择明文来获取你的密码)。我们有2^32个弱密码,但是
因为IDEA的密码比DES的密码多得多,所以随机选择一个密码时选到一个若密码的概
率比DES要小。

1.7 块密码系统的加密速度

一些块密码系统的加密速度(33MHz的486SX上)

算法 速度KB/sec 算法 速度KB/sec
Blowfish(12轮) 182 MDC(使用MD4) 186
Blowfish(16轮) 135 MDC(使用MD5) 135
Blowfish(20轮) 110 MDC(使用SHA) 23
DES 35 NewDES 233
FEAL-8 300 REDOC II 1
FEAL-16 161 REDOC III 78
FEAL-32 91 RC5-32/8 127
GOST 53 RC5-32/12 86
IDEA 70 RC5-32/16 65
Khutu(16轮) 221 RC5-32/20 52
Khutu(24轮) 153 SAFER(6轮) 81
Khutu(32轮) 115 SAFER(8轮) 61
Luby-Rackoff(MD4) 47 SAFER(10轮) 49
Luby-Rackoff(MD5) 34 SAFER(12轮) 41
Luby-Rackoff(SHA) 11 3-way 25
Lucifer 52 Triple-DES 12

2. 流密码系统
2.1 流密码系统 vs 块密码系统

块密码系统在明文的一块一块进行操作,对每个输入产生一个输出块。流密码系统
则不一样,他每次加密或者解密一个bit。流密码系统在欧洲更流行一些,而在美国
块密码则要更流行一些。

一个流密码系统使用一个函数使用密钥作为输入然后产生一系列的伪随机的bits。
每个bit都和明文中的一个bit进行异或,产生密文的一个bit。

2.2 RC4

RC4是一个一次生成一个byte的流密码系统。密钥被用来生成一个含有256个元素的表
So,S1,S2,...,S255,他们是0到255这些数的一个排列。一旦这个表被初始化完成之
后,下面的RC4伪代码就可以一次生成一个byte了。

i = j = 0;
while(generating) {
i = (i+1) mod 256
j = (j+S_i) mod 256
swap S_i and S_j
t = (S_i + S_j) mod 256
output = S_t
}


RC4被Lotus Notes,Oracle SQL以及一些其他产品使用。

3. 公开密钥算法

公开密钥算法是基于单向的活页窗函数的。就像前面提到的那样,一个单向函数
在一个方向上很容易的,但是相反方向却是很难的。使用活页窗的单项函数在一个
方向是很容易的,在另外一个方向上如果你不使用一个密码就是很难的。如果你
直到密码,那么另外一个方向也是很容易的。

公开密钥算法使用两个密码:私有密钥和公开密钥。Alice生成一个密钥对,然后
它公开他的公开密钥并且保留对应的私有密钥。为了给ALice发送一个消息,Bob
可以使用Alice的公开密钥进行加密,然后Alice可以使用它自己的私有密钥进行
解密。和对称加密体系不同的是,两个使用公开密钥体系的人不必要交换密码。
我们要做的只是在公开密钥目录里面找到Alice的公开密钥就ok了。而至于怎么实现
一个安全的公开密钥分发系统则是另外一个问题了。

使用公开密钥对消息进行加密可以认为是单向函数的一个方向。而对应的私有密钥
就是一个活页窗,他使得函数的另外一个方向上的计算变得简单。

3.1 Merkle-Hellman Knapsack算法

MHK是一个公开密钥算法,他的安全性由背包问题的NP-完全性得到保证。算法的设计
者认为要解密用户加密的信息,攻击者需要解决背包问题。但是不幸的是这里有些
错误:背包问题确实是NP完全的,但是问题的实例或许可以不需要解决这个NP完全的
问题就得到解答。

背包问题指的是:给定一个向量M和一个数值S,计算一个bool向量B,使得M和B
的点乘等于S。

怎么把这个变成一个公开密钥算法呢?加密的时候,我们首先把输入划分成为长度
伪||M||的比特块。然后计算C_i = Sum_i B_i * M_i,这里的B_i是明文。得到的串
C_i就是密文。而M就是公开密钥。

对应的私有密钥是另外一个向量M'。M'有下面的性质:(1)M'是一个快速增加的向量
(2) Sum_i B_i * M_i' = S,也就是说M'也可以用来从S中解出B。

下面几点事实时的这个算法是一个可行的公开密钥算法:(1) 从M'计算出B只需要
多项式时间,(2) 容易把一个快速增加的背包序列转换成为一个普通的背包序列。
(2)使得你可以从你选定的私有密钥快速的计算出你的公开密钥。但是不幸的是,
用户从私有密钥计算出公开密钥的算法可能也能够让对手可以容易从公开密钥计算出
私有密钥来,那么加密信息就可以被很容易的解密了。这就是算法的弱点。

美国的MHK算法的专利在1997年八月19日过期。


3.2 RSA

MH算法是基于背包问题的,而RSA的安全性则是基于大数的分解的。

为了计算公开-私有密码对:

1. 随机选择两个大的素数p和q
2. 计算n=pq
3. 选择和(p-1)(q-1)互素的数e,注意e不一定需要是一个随机的数
4. 计算d = e^-1 mod (p-1)(q-1)

公开密钥是 (e,n),私有密钥是(d,n)

加密的时候: c = m^e mod n
解密的时候: m = c^d mod n

我们需要证明E_d(E_e(m)) = m

E_d(E_e(m)) = (m^e)^d
= m^(ed)
= m^(k(p-1)(q-1)+1)
= m*m^(k(p-1)(q-1))
= m*(m^((p-1)(q-1)))^k
= m*1^k
= m (mod n)

上面证明中的一个关键步骤是m^((p-1)(q-1)) = 1 (mod n),这点通过下一章的群伦
的讨论来说明。

总的说来,如果因式分解容易,那么RSA就很容易破解。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7196059/viewspace-997048/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 最短的小说全集
请登录后发表评论 登录
全部评论
  • 博文量
    49
  • 访问量
    191881