信安小白，科普一篇博文讲对称密码算法、非对称密码算法_非对称密码模型

---

系列博文

1. 信安小白，说明白渗透测试及信息安全
2. 信安小白，一篇博文讲明白暴力破解和SQL注入
3. 信安小白，一篇博文讲明白上传漏洞——获得shop靶机的Webshell
4. 信安小白，一篇博文讲明白存储型、反射型XSS漏洞
5. 信安小白，一篇博文讲明白CSRF攻击和防御
6. 信安小白，科普一篇博文讲对称密码算法、非对称密码算法
7. 信安小白，一篇博文讲明白数字签名
8. 信安小白，一篇博文讲明白数字证书和PKI(公钥基础设施)

一、密码学的发展

• 1949年之前，密码学是一门艺术。
• 1949～1975年，密码学成为科学
• 1976年以后，密码学的新方向——公钥密码学

  自从人类有了战争，就有了密码。历史上的战争，特别是两次世界大战对于保密学的理论技术的发展起了巨大的推动作用。

• 手工加密——机械加密——计算机加密
• 基于算法安全——基于密钥安全
• 贵族——平民

二、对称密码算法

2.1 数据加密的基本模型

• 明文：明明白白的文章，没有加密的原文。

  明文通过加密算法和密钥得到了密文，此密钥称为加密密钥，密文到达对方手里，通过解密密钥和解密算法对密文进行变化，还原出明文。
  加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Key).

  对称密码算法：加密算法等同于解密算法，加密密钥与解密密钥也相同。也就是说上图中间划一条线，两边对称且对应相等。

2.2 数据加密的基本术语

• 消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)，加密和解密要在密钥的控制下进行。
• 对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm).
• 接收者对密文解密所采用的一组规则称为解密算法
  (Decryption Algorithm).

注：在不同的算法中，加密算法和解密算法可能不一样，加密密钥和解密密钥也有可能不一样。

2.3 对称密码算法举例

2.3.1 置换密码

  置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。
  根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,……，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。

2.3.2 密文的得出

先读顺序为 1 的明文列，即 aba.
再读顺序为 2 的明文列，即 cnu
最后读顺序为 6 的明文列，即 ksr
因此密文就是：abacnuaiotettgfksr

2.3.3 接收端收到密文后按列写下

收到的密文：abacnuaiotettgfksr
先写下第 1 列密文 aba
再写下第 2 列密文 cnu
最后写下第 6 列密文 ksr
最后按行读出明文。

这里加密（从行读入列输出）和解密（按列读入行输出）有所不同。

提示：
  置换密码算法不太好，原因是字母在字母表的顺序是相同的容易造成，不同的密钥能用相同的字母顺序解开。

2.4 特点

  对称密码算法（symmetric cipher)：又称传统密码算法（conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法
。

• 加密速度快，便于硬件实现和大规模生产。传递信息和大量数据包能经常使用。
• 密钥分配：必须通过保密的信道
• 密钥个数：n(n-1)/2
• 无法用来签名和抗抵赖（没有第三方公证时）

2.5 对称密码体制

加密和解密使用相同的密钥
密钥必须使用秘密的信道分配

在对称密码算法中，密钥的安全传递决定了对称密码算法的安全性！

三、常见对称密码算法——DES概述

• 1973年美国国家标准局NBS（国家标准与技术研所NIST的前身）公开征求国家密码标准方案。
• 1975年IBM公司首次提出方案
• 1977年被NIST确定为联邦信息处理标准并命名为DES，曾经是对称密码体制事实上的国际标准
• 输入：64位明文分组、64位密钥（8位校验位）
• 输出：64位密文分组
• 解密算法与加密算法相同
• 交替使用S-变换和P-变换，具有Feistel结构特点

3.1 DES设计准则

1. 随机性：输出与输入之间无规律
2. 雪崩效应：1位输入的改变平均将引起输出中32位
   的变化
3. 完全性：每个输出位都是所有输入位的函数
4. 非线性性：加密函数相对于密钥都是非线性的
5. 相关免疫性：输出不会与输入位的子集相关

3.2 DES生命周期

  DES作为第一个广泛应用的加密标准，是一种最有代表性的对称分组密码算法。详细研究这一算法的基本原理对于掌握对称分组密码理论很有意义。

3.3 DES 加密过程

一轮迭代：S-盒是一个表，只供商用查询。

S－盒 置换：

子密钥生成：

3.4 DES的安全性评论

• 自从DES问世至今，对它多次的分析研究。利用穷举法搜索攻击，只能说明56位的密钥可能太少；DES的迭代次数可能太少；
• 1982年，已经有办法攻破4次迭代的DES系统了。
• 1985年，对于6次迭代的DES系统也已破译。
• 1990年，以色列学者发明并运用差分分析方法证明，通过已知明文攻击，任何少于16次迭代的DES算法都可以用比穷举法更有效的方法。
• 1998年，电子边境基金会（EFF）动用一台价值25万美元的高速电脑，在56h内利用穷尽搜索的方法破译DES。
• 1999年1月，电子边境基金会只用了22小时15分钟就将DES破解。故该算法已经是超期役的密码算法。

DES在商用应用广泛，但却能在很快的时间被破解，由于涉及商用，硬件条件不能变换太频繁，因此急需补救措施。

3.5 双密钥3DES（补救措施）

用两个密钥：用DES加密一次，用K2解密，再用K1加密。

延长密钥到64*2=128位
C=E_K1</sub>(D_K2(E_K1(P)))
P=D_K1(E_K2(D_K1(C)))

3.6 密钥 3DES（补救措施）

用三个密钥：用K1加密一次，用K2解密，再用K3加密。
延长密钥到64*3=192位
C=E_K3(D_K2(E_K1(P)))
P=D_K1(E_K2(D_K3(C)))

四、AES算法——Rijndael

• 1997年4月15日，美国ANSI发起征集AES（advanced encryption standard）的活动，并为此成立了AES工作小组。
• 1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。对AES的基本要求是： 比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。
• 1998年8月12日，在首届AES候选会议（first AES candidate conference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论。
• 1999年3月，在第2届AES候选会议（从15个候选算法中选出了5个。分别是RC6、Rijndael、SERPENT、Twofish和MARS。
• 2000年10月2日，NIST宣布Rijndael作为新的AES。经过3年多的讨论，Rijndael终于脱颖而出。
• Rijndael由比利时的Joan Daemen和Vincent Rijmen设计。算法有很好的抵抗差分密码分析及线性密码分析的能力。

4.1 AES算法

• 明文分组的长度为128位即16字节
• 密钥长度可以为16，24或者32字节(128，192，256位)
• 根据密钥的长度，算法被称为AES-128，AES-192或者AE-256
• AES加密算法涉及4种操作：字节替代、行移位、列混淆和轮密钥加。

注:
  轮密钥加操作就是将轮密钥与明文（状态）按比特异或。轮密钥通过密钥扩展得到，初始密钥与初始明文均是用户自己设置。简单来说，密钥加操作就是逐字节相加，有限域GF(2⁸)上的加法是模2加法，即异或。

轮密钥加 c语言描述（参考别的人）：

#include <iostream>
using namespace std;
 
void PrintfMatrix(unsigned char m[4][4])
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
		printf("%2x",m[i][j]);
		if(j%4==3)
			puts("");
		}
		
	}
}
 
void AddRoundKey(unsigned char state[4][4],unsigned char key[4][4])    //密钥加函数
{
	int i,j;
	for (i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			state[i][j]^=key[i][j];          //明文与密钥的异或，即密钥加
		}
	}
}
int main()
{
	unsigned char state[4][4]={
		0,4,8,12,
			1,5,9,13,
			2,6,10,14,
			3,7,11,15,
	};
	unsigned char key[4][4]={
		0,1,2,3,
			4,5,6,7,
			8,9,10,11,
			12,13,14,15,
	};
	printf("明文为:\n");PrintfMatrix(state);
	printf("密钥为:\n");PrintfMatrix(key);
	AddRoundKey(state,key);                        //在主函数中调用密钥加函数
	printf("密钥加结果:\n");PrintfMatrix(state);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

AES原理图：

4.2 对称算法发展

3DES是DES向AES过度的加密算法，现在正在使用的加密标准是AES，wifi无线路由器通讯就是采用AES算法加密的。

---

五、非对称密码算法

  上面讲了对称密码算法，对称密码算法加密和解密使用相同的密钥，但算法存在：加密方如何将密钥安全传递给解密方的问题！如果再次将密钥加密会继续产生相同的问题（继续下去，问题会圈套圈连环下去！）还有：两人共享一个密钥，信息泄露算谁的？因此科学家为解决上述问题设计了非对称密码算法。

5.1 公钥密码学

1976年以后：

• 1976年，Diffie & Hellman的“New Directions in Cryptography”提出了非对称密钥密码。
• 1977年，Rivest,Shamir & Adleman提出了RSA公钥算法。
• 90年代，逐步出现椭圆曲线等其他公钥算法。

公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！

5.2 非对称密码算法

  每个通信实体有一对密钥（公钥，私钥）。公钥公开，私钥保密

• 甲向乙发送消息，用乙的公钥加密
• 乙收到密文后，用自己的私钥解密
• 综上所述：用一个密钥加密，用另一个密钥解密。
  

核心算法：

  上述运算中，23和7作为两个密钥，公开一个，另一个作为私钥即可。例如：公钥为7，私钥为23，则即使攻击者知道7、187和密文11，但如果他不知道私钥23，那么他无论如何也算不出明文88。

5.3 RSA算法

• 1977年由美国麻省理工学院三位教授Ron Rivest、Adi Shamir和Len Adleman发明的一种基于因子分解的指数函数的单向陷门函数，于1978年正式公布。它是迄今为止理论上最为成熟完善的公钥密码体制。
• RSA是一种分组加密算法。RSA密钥一般推荐使用1024位，CA(CA认证)采用2048位长的密钥。分组长度小于1024位。
• 目前应用最广泛的公钥密码算法（最重要的算法）。
• 只在美国申请专利，且已于2000年9月到期。

5.4 RSA算法详解

  再拿上述运算举例，23和7作为两个密钥，公开一个，另一个作为私钥即可。例如：公钥为7，私钥为23，则即使攻击者知道7、187和密文11，但如果他不知道私钥23，那么他无论如何也算不出明文88。

1. 选择两个大素数P、Q(保密)
   P=11，Q=17

2. 计算 N = P x Q (可以公开)
   N = 11 x 17 = 187

3. 选择一个公钥E，并且不是P-1和Q-1的因子
   (P -1)x(Q -1) =10 x 16 = 160，选择E与(p-1)(q-1)互质，并且E小于(p-1)(q-1)，所以选择E为7，E的选择不唯一。

4. 选择一个私钥D， (D x E)mod(P - 1) x (Q x 1) = 1
   $$\begin{gathered} (D\times E)mod(P-1)\times (Q-1)=1 \\ (D\times 7)mod160=1 \\ D\times 7=K\times 160+1 \\ K=1,D=23 \end{gathered}$$
   E确定了，D也就确定了。

5. 加密：明文PT -> 密文CT
   $$CT=P{T}^{E}modN$$
   已知明文为88，那么用E加密明文，得到密文为11$$\begin{gathered} CT=P{T}^{E}modN \\ CT=88^{7}mod187 \\ CT=11 \end{gathered}$$

6. 解密：密文CT -> 明文PT
   $$PT=C{T}^{D}modN$$
   用D解密密文$$\begin{gathered} PT=C{T}^{D}modN \\ PT=11^{23}mod187 \\ PT=88 \end{gathered}$$

换个例子： 如果P=7，Q=17呢?

• N = P x Q = 7 x 17 = 119

• (P -1)x(Q -1) =6 x 16 = 96，选择E与(p-1)(q-1)互质，并且E小于(p-1)(q-1)，所以选择E = 5

• 计算私钥D，D小于(p-1)(q-1)
  $$\begin{gathered} (D\times E)mod(P-1)\times (Q-1)=1 \\ (D\times 5)mod96=1 \\ D\times 5=K\times 96+1 \\ K=4,D=77 \end{gathered}$$

• 已知明文为2，那么用D加密明文，得到密文为32 $$\begin{gathered} CT=P{T}^{E}modN \\ CT=2^{77}mod119 \\ CT=32 \end{gathered}$$

• 知道密文32，$$\begin{gathered} PT=C{T}^{D}modN \\ PT=32^{5}mod119 \\ PT=2 \end{gathered}$$

   RSA能不能被破解就是看能否从公钥计算出私钥来，由加密公式可以看出来，公钥实际上包括E和N:
$$CT=P{T}^{E}modN$$
  要想计算出D来，那么就要先计算出P和Q
$$\begin{gathered} (D\times E)mod(P-1)\times (Q-1)=1 \\ N=P\times Q \end{gathered}$$
  但P和Q是私密的，因此RSA的安全性基于 从P和Q得到N很容易，但从N分解P和Q，大数分解却很难。

5.5 破解步骤（已经知道E和N）

• 由N分解出P和Q
  $$N=P\times Q$$
• 由公式
  $$\begin{gathered} (D\times E)mod(P-1)\times (Q-1)=1 \\ D=\frac{K\times (P-1)\times (Q-1)+1}{E} \end{gathered}$$
• 当N和E都非常大的时候，计算量是非常大的
• 目前被破解的最长RSA密钥是768个二进制位
• 一般是是1024位

六、密码算法小结

---