des算法原理

2012-02-11 12:57:31来源: 互联网
   

DES算法全称为Data Encryption Standard,即数据加密算法,它是IBM公司于1975年研究成功并公开发表的。DES算法的入口参数有三个:Key、Data、Mode。其中Key为8个字节共64位,是DES算法的工作密钥;Data也为8个字节64位,是要被加密或被解密的数据;Mode为DES的工作方式,有两种:加密或解密。 


    DES算法把64位的明文输入块变为64位的密文输出块,它所使用的密钥也是64位,其算法主要分为两步: 
1 初始置换 
    其功能是把输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分各长3 2位,其置换规则为将输入的第58位换到第一位,第50位换到第2位……依此类推,最后一位是原来的第7位。L0、R0则是换位输出后的两部分,L0是输出的左32位,R0是右32位,例:设置换前的输入值为D1D2D3……D64,则经过初始置换后的结果为:L0=D58D50……D8;R0=D57D49……D7。 
2 逆置换 
    经过16次迭代运算后,得到L16、R16,将此作为输入,进行逆置换,逆置换正好是初始置换的逆运算,由此即得到密文输出。 

RSA算法简介 
    这种算法1978年就出现了,它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。算法的名字以发明者的名字命名:Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。 

    RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数( 大于 100个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 

    密钥对的产生。选择两个大素数,p 和q 。计算: 

n = p * q 

然后随机选择加密密钥e,要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后,利用Euclid 算法计算解密密钥d, 满足 

e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) 

其中n和d也要互质。数e和n是公钥,d是私钥。两个素数p和q不再需要,应该丢弃,不要让任何人知道。 



加密信息 m(二进制表示)时,首先把m分成等长数据块 m1 ,m2,..., mi ,块长s,其中 2^s <= n, s 尽可能的大。对应的密文是: 

ci = mi^e ( mod n ) ( a ) 

解密时作如下计算: 

mi = ci^d ( mod n ) ( b ) 

RSA 可用于数字签名,方案是用 ( a ) 式签名, ( b )式验证。具体操作时考虑到安全性和 m信息量较大等因素,一般是先作 HASH 运算。 



RSA 的安全性。 

    RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理论上的证明,因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法,那它肯定可以修改成为大数分解算法。目前, RSA的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。现在,人们已能分解140多个十进制位的大素数。因此,模数n必须选大一些,因具体适用情况而定。 



RSA的速度。 

    由于进行的都是大数计算,使得RSA最快的情况也比DES慢上100倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 



RSA的选择密文攻击。 

    RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind),让拥有私钥的实体签署。然后,经过计算就可得到它所想要的信息。实际上,攻击利用的都是同一个弱点,即存在这样一个事实:乘幂保留了输入的乘法结构: 

( XM )^d = X^d *M^d mod n 

    前面已经提到,这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题,主要措施有两条:一条是采用好的公钥协议,保证工作过程中实体不对其他实体任意产生的信息解密,不对自己一无所知的信息签名;另一条是决不对陌生人送来的随机文档签名,签名时首先使用One-Way Hash Function对文档作HASH处理,或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。 



RSA的公共模数攻击。 

    若系统中共有一个模数,只是不同的人拥有不同的e和d,系统将是危险的。最普遍的情况是同一信息用不同的公钥加密,这些公钥共模而且互质,那末该信息无需私钥就可得到恢复。设P为信息明文,两个加密密钥为e1和e2,公共模数是n,则: 

C1 = P^e1 mod n 

C2 = P^e2 mod n 

密码分析者知道n、e1、e2、C1和C2,就能得到P。 

因为e1和e2互质,故用Euclidean算法能找到r和s,满足: 

r * e1 + s * e2 = 1 

假设r为负数,需再用Euclidean算法计算C1^(-1),则 

( C1^(-1) )^(-r) * C2^s = P mod n 



    另外,还有其它几种利用公共模数攻击的方法。总之,如果知道给定模数的一对e和d,一是有利于攻击者分解模数,一是有利于攻击者计算出其它成对的e’和d’,而无需分解模数。解决办法只有一个,那就是不要共享模数n。 



    RSA的小指数攻击。 有一种提高RSA速度的建议是使公钥e取较小的值,这样会使加密变得易于实现,速度有所提高。但这样作是不安全的,对付办法就是e和d都取较大的值。 



    RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。 RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何,而且密码学界多数人士倾向于因子分解不是NPC问题。RSA的缺点主要有:A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。B)分组长度太大,为保证安全性,n 至少也要 600 bits以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。目前,SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥,其他实体使用1024比特的密钥

DES算法原理:

处理密钥:
    从用户处获得64位密钥.(每第8位为校验位,为使密钥有正确的奇偶校验,每个密钥要有奇数个"1"位.(本文如未特指,均指二进制位)
具体过程:
    对密钥实施变换,使得变换以后的密钥的各个位与原密钥位对应关系如下表所示:(表一为忽略校验位以后情况).
57 49 41 33 25 17 9 1 58 50 42 34 26 18
10 2 59 51 43 35 27 19 11 3 60 52 44 36
63 55 47 39 31 23 15 7 62 54 49 38 30 22
14 6 61 53 45 37 29 21 13 5 28 20 12 4

把变换后的密钥等分成两部分,前28位记为C[0],后28位记为D[0].
计算子密钥(共16个), 从i=1开始。
分别对C[i-1],D[i-1]作循环左移来生成C[i],D[i].(共16次)。
每次循环左移位数如下表所示:

轮 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
位数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

串联C[i],D[i],得到一个56位数,然后对此数
作如下变换以产生48位子密钥K[i]。
变换过程如下:

14 17 11 24 1 5 3 28 15 6 21 10
23 19 12 4 26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40 51 45 33 48
44 49 39 56 34 53 46 42 50 36 29 32

1.2.3.3 按以上方法计算出16个子密钥。
对64位数据块的处理:

把数据分成64位的数据块,不够64位的以适当的方式填补。
对数据块作变换。

58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

将变换后的数据块等分成前后两部分,前32位记为L[0],后32位记为R[0]。
用16个子密钥对数据加密。
根据下面的扩冲函数E,扩展32位的成48位

32 1 2 3 4 5 4 5 6 7 8 9
8 9 10 11 12 13 12 13 14 15 16 17
16 17 18 19 20 21 20 21 22 23 24 25
24 25 26 27 28 29 28 29 30 31 32 1

用E{R[i-1]}与K[i]作异或运算。
把所得的48位数分成8个6位数。1-6位为B[1],7-12位为B[2],... 43-48位为B[8]。
用S密箱里的值替换B[j]。从j=1开始。S密箱里的值为4位数,共8个S密箱.
取出B[j]的第1和第6位串联起来成一个2位数,记为m.m即是S密箱里用来替换B[j]的数所在的列数。
取出B[j]的第2至第5位串联起来成一个4位数,记为n。n即是S密箱里用来替换B[j]的数所在的行数。
用S密箱里的值S[j][ m][ n]替换B[j]。8个S密箱如下所示:
S-BOXE:S1
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 14 0 4 15
0001 1 4 15 1 12
0010 2 13 7 14 8
0011 3 1 4 8 2
0100 4 2 14 13 4
0101 5 15 2 6 9
0110 6 11 13 2 1
0111 7 8 1 11 7
1000 8 3 10 15 5
1001 9 10 6 12 11
1010 10 6 12 9 3
1011 11 12 11 7 14
1100 12 5 9 3 10
1101 13 9 5 10 0
1110 14 0 3 5 6
1111 15 7 8 0 13
S-BOXE:S2
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 15 3 0 13
0001 1 1 13 14 8
0010 2 8 4 7 10
0011 3 14 7 11 1
0100 4 6 15 10 3
0101 5 11 2 4 15
0110 6 3 8 13 4
0111 7 4 14 1 2
1000 8 9 12 5 11
1001 9 7 0 8 6
1010 10 2 1 12 7
1011 11 13 10 6 12
1100 12 12 6 9 0
1101 13 0 9 3 5
1110 14 5 11 2 14
1111 15 10 5 15 9
S-BOXE:S3
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 10 13 13 1
0001 1 0 7 6 10
0010 2 9 0 4 13
0011 3 14 9 9 0
0100 4 6 3 8 6
0101 5 3 4 15 9
0110 6 15 6 3 8
0111 7 5 10 0 7
1000 8 1 2 11 4
1001 9 13 8 1 15
1010 10 12 5 2 14
1011 11 7 14 12 3
1100 12 11 12 5 11
1101 13 4 11 10 5
1110 14 2 15 14 2
1111 15 8 1 7 12
S-BOXE:S4
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 7 13 10 3
0001 1 13 8 6 15
0010 2 14 11 9 0
0011 3 3 5 0 6
0100 4 0 6 12 10
0101 5 6 15 11 1
0110 6 9 0 7 13
0111 7 10 3 13 8
1000 8 1 4 15 9
1001 9 2 7 1 4
1010 10 8 2 3 5
1011 11 5 12 14 11
1100 12 11 1 5 12
1101 13 12 10 2 7
1110 14 4 14 8 2
1111 15 15 9 4 14
S-BOXE:S5
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 2 14 4 11
0001 1 12 11 2 8
0010 2 4 2 1 12
0011 3 1 12 11 7
0100 4 7 4 10 1
0101 5 10 7 13 14
0110 6 11 13 7 2
0111 7 6 1 8 13
1000 8 8 5 15 6
1001 9 5 0 9 15
1010 10 3 15 12 0
1011 11 15 10 5 9
1100 12 13 3 6 10
1101 13 0 9 3 4
1110 14 14 8 0 5
1111 15 9 6 14 3
S-BOXE:S6
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 12 10 9 4
0001 1 1 15 14 3
0010 2 10 4 15 2
0011 3 15 2 5 12
0100 4 9 7 2 9
0101 5 2 12 8 5
0110 6 6 9 12 15
0111 7 8 5 3 10
1000 8 0 6 7 11
1001 9 13 1 0 14
1010 10 3 13 4 1
1011 11 4 14 10 7
1100 12 14 0 1 6
1101 13 7 11 13 0
1110 14 5 3 11 8
1111 15 11 8 6 13
S-BOXE:S7
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 4 13 1 6
0001 1 11 0 4 11
0010 2 2 11 11 13
0011 3 14 7 13 8
0100 4 15 4 12 1
0101 5 0 9 3 4
0110 6 8 1 7 10
0111 7 13 10 14 7
1000 8 3 14 10 9
1001 9 12 3 15 5
1010 10 9 5 6 0
1011 11 7 12 8 15
1100 12 5 2 0 14
1101 13 10 15 5 2
1110 14 6 8 9 3
1111 15 1 6 2 12
S-BOXE:S8
Binary d1d6 =>; 00 01 10 11
\/ d2..d5 \/ Dec 0 1 2 3
0000 0 13 1 7 2
0001 1 2 15 11 1
0010 2 8 13 4 14
0011 3 4 8 1 7
0100 4 6 10 9 4
0101 5 15 3 12 10
0110 6 11 7 14 8
0111 7 1 4 2 13
1000 8 10 12 0 15
1001 9 9 5 6 12
1010 10 3 6 10 9
1011 11 14 11 13 0
1100 12 5 0 15 3
1101 13 0 14 3 5
1110 14 12 9 5 6
1111 15 7 2 8 11




返回第一步直至8个数据块都被替换。
把B[1]至B[8]顺序串联起来得到一个32位数。对这个数做如下变换:

bit goes to bit bit goes to bit
16 1 2 17
7 2 8 18
20 3 24 19
21 4 14 20
29 5 32 21
12 6 27 22
28 7 3 23
17 8 9 24
1 9 19 25
15 10 13 26
23 11 30 27
26 12 6 28
5 13 22 29
18 14 11 30
31 15 4 31
10 16 25 32

把得到的结果与L[i-1]作异或运算。把计算结果賦给R[i]。
把R[i-1]的值賦给L[i]。
从a循环执行,直到K[16]也被用到。
把R[16]和L[16] 顺序串联起来得到一个64位数。对这个数实施II变换的逆变换。
以上就是DES算法如何加密一段64位数据块。解密时用同样的过程,只需把16个子密钥的顺续颠倒过来,应用的顺序为K[16],K[15],K[14],...K[1]。

关键字:des

编辑:北极风 引用地址:http://www.eeworld.com.cn/FPGA/2012/0211/article_2865.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
des

小广播

独家专题更多

富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
带你走进LED王国——Microchip LED应用专题
带你走进LED王国——Microchip LED应用专题
 

夏宇闻老师专栏

你问我答FPGA设计

北京航空航天大学教授,国内最早从事复杂数字逻辑和嵌入式系统设计的专家。

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved