4、DES和RSA简介

DES是分组加密算法,速度快,使用单一密钥,加密解密都使用同一个密钥,一般用于大量数据加密,目前处于半淘汰状态。
RSA算法是流式加密算法,速度慢,但是使用成对的密钥,加密解密使用不同的密钥,有利于保密和身份认定,一般用于加密DES类算法的密钥。

对称加解密算法
通信双方通信前共同拟定一个密钥,不对第三方公开。 消息发送前都通过该密钥加密,到达后也通过该密钥解密。 不具有个体原子性,一个密钥被共享,泄露机率加大。

公私钥加解密举例
设若甲有一份需保密的数字商业合同发给乙签署。经过如下步骤: 1. 甲用乙的公钥对合同加密。 2. 密文从甲发送到乙。 3. 乙收到密文,并用自己的私钥对其解密。 4. 解密正确,经阅读,乙用自己的私钥对合同进行签署。 5. 乙用甲的公钥对已经签署的合同进行加密。 6. 乙将密文发给甲。 7. 甲用自己的私钥将已签署合同解密。 8. 解密正确,确认签署。

从以上步骤,我们知道: 1. 用公钥加密的密文能且只能用与其唯一配对的私钥才能解开。 2. 如果某份密文被解开,那么肯定是密文的目标信息主体解开的。 3. 私钥因其唯一标识所有者的属性,被用于数字签名,具有法律效力。

DES 是一种单一密钥加解密算法。通信主体之间只有一个密钥,该密钥不对第三方公开。 RSA 则是公钥/私钥系统。该系统比 DES 系统更原子化,具有普遍应用意义。

1、DES 加解密算法

DES (Data Encryption Standard),是IBM在上个世纪70年代开发的单密钥对称加解密算法。该算法利用一个56+8奇偶校验位(第8, 16, 24, 32, 40, 48, 56, 64位)=64位的密钥对以64位为单位的块数据进行加解密。

有明文M(64位) = 0123456789ABCDEF,即 M(64位) = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

L(32位) = 0000 0001 0010 0011 0100 0101 0110 0111
R(32位) = 1000 1001 1010 1011 1100 1101 1110 1111

有密钥K(64位) = 133457799BBCDFF1,即 K(64位) = 0001001 0011010 0101011 0111100 1001101 1011110 1101111 1111000 (奇校验)其中红色标注为奇偶校验位,即实际密钥为56位。

第一步:生成16个子钥(48位)

对K使用PC-1(8×7),详见:http://zh.wikipedia.org/wiki/DES%E8%A1%A5%E5%85%85%E6%9D%90%E6%96%99
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 46 38 30 22  
14 6 61 53 45 37 29  
21 13 5 28 20 12 4
主要输入的64位数据中只用到了56位,剩余的8位可以用于奇偶校验。

从而,由K(64位) = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
得到K+(56位) = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111,进而
C0(28位) = 1111000 0110011 0010101 0101111
D0(28位) = 0101010 1011001 1001111 0001111
C1和D1分别为C0和D0左移1位。… C3和D3分别为C2和D2左移2位 …

从而得到C1D1 ~ C16D16:
C1 = 1110000110011001010101011111 D1 = 1010101011001100111100011110
C2 = 1100001100110010101010111111 D2 = 0101010110011001111000111101
… …
C16 = 1111000011001100101010101111 D16 = 0101010101100110011110001111

Kn(48位) = PC-2( CnDn(56位) ),该置换从56位的密钥调度状态中取出48位的子密钥。最终得到所有16个子钥,每个48位:

K1 = 000110 110000 001011 101111 111111 000111 000001 110010 
K2 = 011110 011010 111011 011001 110110 111100 100111 100101 
… …
K16 = 110010 110011 110110 001011 000011 100001 011111 110101

第二步:用子钥对64位数据加密

对明文M使用IP(8×8)
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

由于M(64位) =0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111,对M运用IP,故有 IP(64位) = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

IP(64位) = L0(32位) + R0(32位)故
L0 (32位) = 1100 1100 0000 0000 1100 1100 1111 1111
R0 (32位) = 1111 0000 1010 1010 1111 0000 1010 1010

从L0和R0开始,循环16次,得出L1R1到L16R16,依据递推公式:

Ln = R(n-1)

Rn = L(n-1) + f (R(n-1),Kn)

其中除了Kn为48位,其他变量及函数均为32位。其中+号表示异或XOR运算,函数f 从一个32位的数据块R(n-1)和一个48位子钥Kn得到一个新的32位数据块。
到此为止,我们得到了16对32位的数据块,即 L1R1, L2R2, L3R3, …, L16R16。最后一对L16R16就是我们需要的。

继续对R16L16(64位)运用一次重排列: IP-1(8×8)。即在
L16(32位) = 0100 0011 0100 0010 0011 0010 0011 0100
R16(32位) = 0000 1010 0100 1100 1101 1001 1001 0101
R16L16(64位) = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100时,对R16L16运用IP-1,得 IP-1(64位) = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101 = 85E813540F0AB405

从而,经过以上步骤,最终从明文 M = 0123456789ABCDEF 得到密文 C = IP-1 = 85E813540F0AB405,以上为加密过程,要解密,依次反向计算即可。

多层 DES

DES 算法可能是运用最广的对称加解密算法,但由于密钥长度较短,导致安全性不高。故在安全性占首要地位的应用场合如金融业等,采用多个不同密钥(K1, K2, K3)的多层DES加解密。这些多层DES系统被广泛应用,由此衍生出Triple DES, G-DES, DES-X, LOKI89和ICE等对称加解密系统。

2、RSA 加解密算法

与DES不同,RSA算法中,每个通信主体都有两个钥匙,一个公钥一个私钥。一般应用过程为:

4、DES和RSA简介

RSA 具体算法:公私钥生成

1)随机选定两个大素数p、q,计算公钥和私钥的公共模数 n = pq
2)计算模数n的欧拉函数 φ(n) ,这里φ(n)=(p-1)(q-1)
3)选定一个正整数e , 使1 < e < φ(n) , 且e与φ(n)互质。
4)计算d, 满足 de ≡ 1(mod φ(n))。de被n除的余数为1,或者说de减去1,可以被n整除。

n与e决定公钥, n与d决定私钥。在已知n和e的情况下,由于n非常大求解φ(n)是不可行的,这样别保证了d的安全性。

RSA 具体算法:加解密
该过程为小张给小李发消息,公钥为小李的公钥(n ,e), 私钥为小李的私钥(n ,d).
小张欲给小李发一个消息M, 他先把M转换为一个大数m < n, 然后用小李的公钥(n ,e)把m加密为另一个大数: c = me mod n
小李收到小张发来的大数c, 着手解密. 通过自己的私钥(n ,d), 得到原来的大数m: m = cd mod n
再把m转换为M, 小李即得到小张的原始消息.

这个过程之所以能通过,具体的证明过程要用到欧拉定理,详细知识请参考这里

选取的素数p和q要足够大,从而乘积n足够大,在事先不知道p和q的情况下分解n是计算上不可行的。由于进行的都是大数计算,使得RSA最快的情况也比DES慢上倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。

上一篇:【BZOJ4372】烁烁的游戏 动态树分治+线段树


下一篇:让Ajax更简单