帖子详情

常用加解密算法总结

jin.th 发布于2018-11-07 11:38 [评论区] [我要回复] [下载md文件] [下载pdf文件]

***数年前的培训资料***

# 引言
  数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常称为“密文”，使其只能在输入相应的密钥之后才能显示出本来内容，通过这样的途径来达到保护数据不被非法人窃取、阅读的目的。 该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。
  在项目中，我们常用的加密算法主要有DES算法、DES的加强版3DES算法、RSA算法、银联规范中POS终端MAC的算法以及RC4算法。

# DES算法
## DES算法简单介绍
  先来简单了解下DES算法，DES算法是一种最通用的对称密钥算法，属于分组密码算法。主要用于民用敏感信息的加密。
**对称密钥算法：**
  对称密钥算法被称为传统密码算法，它的对称性体现在加密密钥和解密密钥具有很强的联系性，一般解密密钥都可以从加密密钥推算出来，反之亦然，而大部分情况则是加密密钥和解密密钥所用同一密钥，因此，对称算法中的加密密钥和解密密钥都需要保密。
  对称密钥算法可以分为分组密码算法和流密码算法。
**分组密码算法：**
  分组密码将明文分割成若干个定长的数据块（称为一个分组），每次对一个分组进行处理。

## DES算法剖析
### DES算法的加解密过程
  DES的加密过程由四部分完成，分别为：初始置换函数IP、子密钥Ki及获取、密码函数F、末置换函数IP-1。
  DES的分组长度是64位（比特）。初始置换函数IP接受长度为64位的明文输入，末置换函数IP-1输出64位的密文。在子密钥的获取过程中，通过密钥置换PC-1获取K1~K16共16个子密钥，这16个子密钥分别顺序应用于密码函数的16次完全相同的迭代运算中。如下图所示
![image](/upload/BBS/3803fd32-2d69-43b2-a363-ff30e695df23.jpg)
  DES的解密算法与加密算法完全相同，只需要将密钥的应用次序与加密时相反应用即可。即解密过程是初始置换函数IP接受长度为64比特的密文输入，将16个子密钥按照K16到K1的顺序应用与函数F的16轮迭代运算中，然后将迭代的结果经由末置换函数IP-1得到64位的明文输出。

### DES的算法过程
  DES主要采用置换和移位运算来实现加解密，接下来深入剖析DES每个部分运算的实现过程。
**（1）	初始置换函数IP**
  64位的明文分组x首先经过一个初始置换函数IP进行置换运算，产生一个64位的输出0x0，该输出被分成两个分别为32位的左半部分L0和右半部分R0，用于F函数的16轮迭代运算的首次迭代的初始输入。
  初始置换函数IP实际上就是一张8x8(8行8列)的迭代表，如表1所示。明文分组中的64位按照表中的规定重新进行排序，其排列顺序为从左到右，从上到下。按表I所示，明文中的第58位被放置在0x0的第1位，第50位防止在第2位，依次类推。
![image](/upload/BBS/644e977c-8333-4ed7-8818-709e21db98fd.jpg)

**（2）	获取子密钥Ki**
  子密钥的获取主要通过置换和移位运算来实现。
  DES加密算法的密钥长度为56位，由用户提供，是DES算法的输入之一。但用户输入的密钥是64位的，按8行8列从左到右从上到下地排列，其中，每行的第8位用于奇偶校验。在DES加密算法中，子密钥获取过程中，DES经过一系列的置换和移位运算，得到K1到K16共16个子密钥，每个子密钥长48位。其实现过程如下：
  首先将输入的64位密钥去掉最后一列的8个校验位，然后用密钥置换函数PC-1对剩下的56位密钥进行置换，如表2所示。
  由表2可知，用户输入的64位密钥中，第8、16、24、32、40、48、56、64共8个校验位被去掉。剩余的56位按表2所示排放：第57位放在第1位，第49位放在第2位，依次类推。
![image](/upload/BBS/65f5bb91-5d32-4144-94aa-39f80de86d09.jpg)

经过PC-1置换后，将其置换的输出再分为前28位C0和后28位D0和两部分，上一轮置换得到的输出的两部分经过循环左移1位或2位后，每轮按表3进行移位，然后将两部分合并成56位，之后经过压缩置换PC-2后得到当前这轮置换的48位子密钥。压缩置换PC-2如表4所示。
![image](/upload/BBS/6ca4d4e2-32e8-4682-a5f9-4adc0693edde.jpg)

PC-2置换为压缩置换，即置换后的输出数据的位数要比置换前输入的位数要少，即某些位的数据在置换的过程中被去掉了。由表4可知，在压缩置换过程中，原来的7行8列共58位数据被压缩成8行6列的48位数据。在压缩置换过程中，第9、18、22、25、35、38、43、54共8位数据被丢掉。
  同时，将上一轮移位后得到的两部分再按表3进行移位，作为下一个子密钥产生的一PC-2置换的输入。依次经过16次循环左移和16次置换得到16个子密钥。其产生过程如图1-1-2所示。
![image](/upload/BBS/bfe797fc-e774-478e-950b-cd0531277148.jpg)

**（3）	密码函数F**
  密码函数F接收两个输入：32位的数据和48位的子密钥。函数F的运算过程为：
  1）先将数据的右半部分磁通过扩展置换E从32位扩展为48位。之所以称为扩展置换。是因为置换后的数据比置换前的数据的位数要多。扩展置换(E)通过将原32位数据中的某些位重复出现达到扩展的目的。其置换函数如表5。扩展置换也称位选择函数，俗称E盒。
由表5可以看出，扩展置换(E)通过将第32、1、4、5、8、9、12、13、16、17、20、21、24、25、28、29共19位分别放置在两个位置，从而将32位的数据扩展为48位。
![image](/upload/BBS/1a3a3997-7b1b-4879-b9b5-9d4d4c785a83.jpg)

2）接着将扩展置换后的48位输出E(Ri)与压缩置换后的48位密钥Ki作异或运算。

3）将异或运算得到的48位结果数据分成8个6位的块，将每一块通过对应的一个S盒产生一个4位的输出。每个S盒实际上是一张4(0～3)行16(0～15)列的置换表，注意，s盒的行列编号都是从0开始的。显然，需要8个s盒，每个S盒如表6所示。
![image](/upload/BBS/97f561fd-b83e-4610-b5aa-fd9dcb1374eb.jpg)
![image](/upload/BBS/68c774c9-d5cf-45dd-b024-8f6fd006c33c.jpg)
  S盒接收6位的输出，经过置换输出4位的数据，其具体置换过程为：将6位输人中的第1位和第6位取出来形成一个2位的二进制数X(从0-3)，该数得出S盒的行数，然后将6位输入的中问4位构成另一个二进制数Y(从0-15)．该数为s盒的列数，然后查出s的x行Y列所对应的整数，将该整数转换为一个4位的二进制数，即为S盒的输出。
  例如，假设输入数据中的第一个6位数字块为010111，则需要通过查S1盒。先取出010111中的第1位和第6位，组成二进制数01，则行数X=1，然后取出中间的4位1011，则得列数为Y=11，在s1盒中，第1行第11列的整数为11(表6中深色背景处)，转换为二进制为1011，则输出1011，即用4位的1011代替6位的010111。

4）将3）中8个6位数据的置换结果连在一起，形成一个32位的输出，输出结果再通过一个P盒置换产生一个32位的输出。P盒置换如表7所示。
![image](/upload/BBS/1e357e3b-01cf-49d2-9a29-af7bd73ba5bc.jpg)

5）P盒置换的结果与左半部分进行异或运算，然后将左右两半部分交换。之后进入下一轮迭代。在完成完全相同的16轮运算后，将得到的两部分数据合在一起，再经过一个末置换函数IP-1即可得到64位的密文。

**（4）	末置换函数**
末置换函数IP-1是初始置换IP的逆运算，如表8所示。
![image](/upload/BBS/c94e33ad-70bb-433e-9d7e-12a7e213454d.jpg)

# 3DES算法
## 3DES算法简单介绍
  3DES（或称为Triple DES）是三重数据加密算法（TDEA，Triple Data Encryption Algorithm）块密码的通称。它相当于是对每个数据块应用三次DES加密算法。由于计算机运算能力的增强，原版DES密码的密钥长度变得容易被暴力破解；3DES即是设计用来提供一种相对简单的方法，即通过增加DES的密钥长度来避免类似的攻击，而不是设计一种全新的块密码算法。

## 3DES加解密过程
  其具体实现如下：设Ek()和Dk()代表DES算法的加密和解密过程，K代表DES算法使用的密钥，P代表明文，C代表密文，这样：
```
　　3DES加密过程为：C=Ek3(Dk2(Ek1(P))) 
　　3DES解密过程为：P=Dk1(EK2(Dk3(C))) 
```

# 银联规范中POS终端MAC的算法
POS终端采用ECB的加密方式，简述如下：
1）将欲发送给POS中心的消息中，从消息类型（MTI）到63域之间的部分构成MAC ELEMEMENT BLOCK （MAB）。
2）对MAB，按每8个字节做异或（不管信息中的字符格式），如果最后不满8个字节，则添加“0x00” \x80\x00\x00\x00\x00\x00\x00\x00

示例：
```
MAB = M1 M2 M3 M4
其中：	
M1 = MS11 MS12 MS13 MS14 MS15 MS16 MS17 MS18
M2 = MS21 MS22 MS23 MS24 MS25 MS26 MS27 MS28
M3 = MS31 MS32 MS33 MS34 MS35 MS36 MS37 MS38
M4 = MS41 MS42 MS43 MS44 MS45 MS46 MS47 MS48

按如下规则进行异或运算：
		 MS11 MS12 MS13 MS14 MS15 MS16 MS17 MS18
XOR）	MS21 MS22 MS23 MS24 MS25 MS26 MS27 MS28
---------------------------------------------------
TEMP BLOCK1 =	TM11 TM12 TM13 TM14 TM15 TM16 TM17 TM18

然后，进行下一步的运算：
		 TM11 TM12 TM13 TM14 TM15 TM16 TM17 TM18
XOR）	MS31 MS32 MS33 MS34 MS35 MS36 MS37 MS38
---------------------------------------------------
TEMP BLOCK2 =	TM21 TM22 TM23 TM24 TM25 TM26 TM27 TM28

再进行下一步的运算：
		 TM21 TM22 TM23 TM24 TM25 TM26 TM27 TM28
XOR）	MS41 MS42 MS43 MS44 MS45 MS46 MS47 MS48
---------------------------------------------------
RESULT BLOCK =	TM31 TM32 TM33 TM34 TM35 TM36 TM37 TM38

3）将异或运算后的最后8个字节（RESULT BLOCK）转换成16个HEXDECIMAL：
RESULT BLOCK = TM31 TM32 TM33 TM34 TM35 TM36 TM37 TM38
= TM311 TM312 TM321 TM322 TM331 TM332 TM341 TM342 ||
TM351 TM352 TM361 TM362 TM371 TM372 TM381 TM382

4）取前8 个字节用MAK加密：
ENC BLOCK1 = eMAK（TM311 TM312 TM321 TM322 TM331 TM332 TM341 TM342）
= EN11 EN12 EN13 EN14 EN15 EN16 EN17 EN18

5）将加密后的结果与后8 个字节异或：
		EN11  EN12  EN13  EN14  EN15  EN16  EN17  EN18
XOR）   TM351 TM352 TM361 TM362 TM371 TM372 TM381 TM382
------------------------------------------------------------
TEMP BLOCK=	TE11  TE12  TE13  TE14  TE15  TE16  TE17  TE18

6）用异或的结果TEMP BLOCK 再进行一次单倍长密钥算法运算。
ENC BLOCK2 = eMAK（TE11 TE12 TE13 TE14 TE15 TE16 TE17 TE18）
= EN21 EN22 EN23 EN24 EN25 EN26 EN27 EN28

7）将运算后的结果（ENC BLOCK2）转换成16 个HEXDECIMAL：
ENC BLOCK2 = EN21 EN22 EN23 EN24 EN25 EN26 EN27 EN28
= EM211 EM212 EM221 EM222 EM231 EM232 EM241 EM242 ||
EM251 EM252 EM261 EM262 EM271 EM272 EM281 EM282
示例：
ENC RESULT= %H84, %H56, %HB1, %HCD, %H5A, %H3F, %H84, %H84
转换成16个HEXDECIMAL: 	“8456B1CD5A3F8484”
8）取前8个字节作为MAC值。
取 ”8456B1CD” 为MAC值。
```

# RC4算法
## RC4算法简单介绍
  RC4加密算法是大名鼎鼎的RSA三人组中的头号人物Ron Rivest在1987年设计的密钥长度可变的流加密算法簇。之所以称其为簇，是由于其核心部分的S-box长度可为任意，但一般为256字节。该算法的速度可以达到DES加密的10倍左右。

## RC4算法原理
  RC4算法非常简单，易于描述：用从1到256个字节(8到2048位)的可变长度密钥初始化一个256个字节的状态矢量S，S的元素记为S[0]，S[1]，⋯ ，S[255]，从始至终置换后的S包含从0到255的所有8比特数。对于加密和解密，字节K由S中256个元素按一定方式选出一个元素而生成。每生成一个K的值，S中的元素就被重新置换一次。

**1 初始化S**
开始时，S中元素的值被置为按升序从0到255，即s[0]=0，S[1]=1，⋯ ，S[255]=255．同时建立一个临时矢量T。如果密钥K的长度为256字节，则将K赋给T。否则，若密钥长度为keylen字节，则将K的值赋给T的前keylen个元素，并循环重复用K的值赋给T剩下的元素，直到T的所有元素都被赋值。这些预操作可概括如下：
```C
/*初始化*/
for i=0 to 255 do
S[i]=i；
T[i]=K[i mod keylen]
```

然后用T产生S的初始置换。从S[0]到S[255]，对每个S[i]，根据由T[i]确定的方案，将S[i]置换为S中的另一字节：
```C
/*S的初始序列*/
j=0
for i=O to 255 do
j=(j+s[i]+T[i])mod 256
swap(s[i]，s[j])；
```
因为对S的操作仅是交换，所以惟一的改变就是置换．S仍然包含所有值为0到255的元素。

**2 密钥流的生成**
矢量S一旦完成初始化，输人密钥就不再被使用．密钥流的生成是从s[0]到S[255]，对每个S[i]，根据当前S的值，将S[i]与S中的另一字节置换．当S[255]完成置换后，操作继续重复，从S[0]开始：
```C
/*密钥流的产生*/
i，j=0
while(true)
i=(i+1)mod 256
j=(j+S[i])mod 256
swap(sEi]，s[j])
t=(sEi]+s[j])mod 256；
k=S[t]
```
加密中，将k的值与下一明文字节异或；解密中，将k的值与下一密文字节异或。

## RC4加密方案
  本文以RC4算法为核心加密算法提出三种加密方案，其中方案一与方案二类似。方案一与方案二要求发送方与接收方持有相同的原始密钥。方案三不要求发送送与接收方使用相同的原始密钥，但发送方必须将本次加密密钥传送给接收方。

### 方案一
![image](/upload/BBS/afa1244d-92eb-4908-aef2-d4da818f2abd.jpg)

### 方案二
![image](/upload/BBS/0886cfe8-c88d-45d0-9373-7d24de24d22a.jpg)

方案一与方案二流程基本一致，只是方案二没有对文件内容摘要（可使用数字签名时所使用的文件内容摘要）进行加密。以方案二为例，发送方与接收方共享同一个密钥，该种方案与ＷＥＰ加密协议类似，具体流程为：
**发送方：**
  发送方首先将所持有的密钥，即本文中的原始密码（160位）与文件内容摘要（160位）进行连接，然后用SHA-1安全散列函数对连接的结果进行计算得到本次加密文件所使用的密钥（160位）。然后将本次加密所使用的密钥传给RC4算法，用RC4算法产生的密钥流与原始明文按字节进行异或，即可得到文件的加密密文。最后将文件的加密密文与文件内容摘要连接，发送给接收方。
**接收方：**
  接收方收到密文之后，首先将密文拆分成文件加密密文和文件内容摘要，然后将接收方自己所持有的原始密码与文件内容摘要连接并用SHA-1安全散列函数进行计算，得到本次解密所使用的解密密钥。将解密密钥传输给RC4算法，用RC4算法产生的密钥流与文件的密文按字节进行异或，即可解密文件得到原始明文。

### 方案三
![image](/upload/BBS/27d8e18c-119e-493d-a790-9bd96aaeca7d.jpg)

方案三与方案一、方案二的最大区别是：方案一、二的发送方与接收方所持有的原始密码必须相同，否则无法解密。方案三发送方与接收方所持有的原始密码可以相同也可以不同，但是发送方必须将本次加密时所使用的密钥发送给接收方，而且只有接收方能将得到的密钥密文解密，其他人均不可。方案三具体流程：
**发送方：**
  发送方首先将所持有的密钥，即本文中的原始密码（160位）与文件内容摘要（160位）进行连接，然后用SHA-1安全散列函数对连接的结果进行计算得到本次加密文件所使用的密钥（160位）。然后将密钥传给RC4算法，同时用接收方的公钥对本次使用的密钥进行加密得到密钥密文。用RC4算法产生的密钥流与原始明文按字节进行异或，即可得到文件的加密密文。最后将文件的加密密文与密钥密文连接，发送给接收方。
**接收方：**
  接收方接收到密文，首先将密文拆分成文件加密密文和密钥密文。然后接收方用自己的私钥将密钥密文进行解密得到解密密码。将解密密码传给RC4算法，用RC4算法产生的密钥流与文件的密文按字节进行异或，即可解密文件得到原始明文。

## RC4算法安全性
  RC4是对称密钥加密算法。由于RC4算法加密是采用的xor，所以，一旦子密钥序列出现了重复，密文就有可能被破解。那么，RC4算法生成的子密钥序列是否会出现重复呢？由于存在部分弱密钥，使得子密钥序列在不到100万字节内就发生了完全的重复，如果是部分重复，则可能在不到10万字节内就能发生重复，因此，推荐在使用RC4算法时，必须对加密密钥进行测试，判断其是否为弱密钥。根据目前的分析结果，没有任何的分析对于密钥长度达到128位的RC4有效，所以，RC4是目前最安全的加密算法之一。

# RSA算法
  RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和Len Adleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

## RSA简单介绍
  RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。 
  在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。 
  RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

## RSA加密原理
  RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。 
  RSA的缺点主要有：A）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B）分组长度太大，为保证安全性，n 至少也要 600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction）协议中要求CA采用2048bits长的密钥，其他实体使用1024比特的密钥。C)RSA密钥长度随着保密级别提高，增加很快。下表列出了对同一安全级别所对应的密钥长度。
![image](/upload/BBS/c2dce38e-da9c-43cd-a78c-b601854c4366.jpg)

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
RSA的算法涉及三个参数，n、e1、e2。
其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
e1和e2是一对相关的值，e1可以任意取，但要求e1与`(p-1）*(q-1）`互质；再选择e2，要求
`（e2*e1）mod（（p-1）*（q-1））=  1　　`
（n，e1）,(n，e2）就是密钥对。其中 (n，e1）为公钥，(n，e2）为私钥。 
RSA加解密的算法完全相同，设A为明文，B为密文，则：
```
A=B^e1 mod n；B=A^e2 mod n 
```
e1和e2可以互换使用，即： 
```
A=B^e2 mod n；B=A^e1 mod n
```

**RSA公钥私钥产生**
随意选择两个大的素数p和q，p不等于q，计算N=pq。
选择一个整数e与(p-1)(q-1)互质，并且e小于`(p-1)(q-1)`
用以下这个公式计算d：`(d * e) ≡ 1 (mod ((p-1)(q-1)) )`，这个式子的意思是`(d * e)-1=k(p-1)(q-1)`,k是正整数。
将p和q的记录销毁。
(N,e)是公钥，(N,d)是私钥。(N,d)是秘密的。公钥可以公开给任何你信任的事物。

**加解密数据**
X = (Y ^ N) % e
Y = (X ^ N) % d

**RSA例子**
1.选择两个素数，p=17,q=23
2.计算`N=pq=17*23=391`
3.计算`欧拉函数φ(N)=(p-1)(q-1)=16*22=352`
4.选择e，必须与352互质，且小于352。一般现在RSA密钥的e都选择3或者65537，这里我们选择3
4.计算d，`de-1`必须为352的整数倍，并且d小于352，选择d=235,因为`235*3-1=352*2`
5.最终公钥`{E=3,N=391}`,私钥`{D=235,N=391}`
6.用公钥对明文66加密：66³ mod 391=111
7.用私钥对密文111解密：111^235 mod 391=66;

## RSA算法安全性
  以上面的例子来说，公钥`{E=3,N=391}`是公开的，因此很容易从N计算出`N=391=17*23`,那么p和q就知道了，欧拉函数φ(N)也知道了，就很容以计算出私钥D。但是实际情况呢？现在使用的RSA至少是1024bit，也就是N的值非常大，就很难计算出N是由哪两个质数相乘得到的。
  RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。

### Miller-Rabin随机性素数测试算法
**费尔马小定理**
> 如果p是一个素数,且0<a<p,则a^(p-1)%p=1.

**Miller-Rabin测试**
> 不断选取不超过p-1的数b，s次，计算是否每次都满足b^(p-1)%p=1.

### 伪代码，算法复杂度：
```
Function Miller-Rabin(n:longint):boolean
begin
for i := 1 to s do
begin 
a := random(n-2) + 2;
If modular_exp(a, n-1, n) <> 1 then return flase;
End;
return true;
end
复杂度： 多少？？ 想想
```

评论列表

回帖