[TOC]

加密的基础知识。文章里的我是作为黑客出现的。。本文内容直接来源于《我的第一本算法书》去了些图片，做了简化。

在现代互联网社会中，加密技术是不可或缺的。那么对数据进行加密和解密时，计算机会进行哪些处理呢？这一节我们将讲解加密技术的必要性和基本原理。

直接发送

假设A想通过互联网向B发送消息。数据要经过互联网上各种各样的网络和设备才能到达B那里。如果像上图这样直接发送数据的话……

可能被窃听。udp是非面向链接的，每个ip其实都拿到了数据。tcp虽然面向链接，但如果A 链接的路由器如果是我提供的，那我当然也可以监听他的数据。

加密-防监听

解决办法是加密。加密后的数据被称为“密文”。A给数据加密，然后发送加密的数据给B, 这样即使我拿到了数据，我也不懂其含义。

同样的B其实也不懂。。。。所以A还要发个密钥给B, B用密钥解密，得到原始数据。这个过程叫解密。

加密方法1. 公开密钥加密（非对称加密，加密和解密密钥不同， AES）

公开密钥加密。AES比较流行。

公开密钥加密是加密和解密使用不同密钥的一种加密方法。由于使用的密钥不同，所以这种算法也被称为“非对称加密”。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”。

正常通信流程

1. B 生成公开密钥P和私有密钥S。因为B需要解密，所以由B生成。
2. B发送公开密钥给A。
3. A 使用 B提供的公开密钥P 加密数据。
4. A 把密文发送给B, 然后B用私有密钥S解密。得到原文。

存在中间人攻击风险

1. B 生成公开密钥PB和私有密钥SB。因为B需要解密，所以由B生成。
2. 中间人生成公开密钥PX和私有密钥SX.
3. B发送公开密钥PB给A。在这个过程中， X把PB替换成PX。A无法发现。因为公钥没有身份信息。
4. A 使用 PX 加密数据 发送给B。
5. X捕获数据，然后使用SX解密，再使用PB生成假消息，发送给B。
6. B解密得到的是X篡改过的消息。。B无法发现。

ps:

公开密钥的可靠性会出现问题，就是因为A无法判断收到的公开密钥是否来自B。要想解决这个问题，就要用到之后会讲到的“数字证书”。公开密钥加密还有一个问题，那就是加密和解密都比较耗时，所以这种方法不适用于持续发送零碎数据的情况。要想解决这个问题，就要用到“混合加密”。

要想找到实现公开密钥加密的算法并不容易。

考虑到加密所需的计算流程，算法必须满足如下条件。

① 可以使用某个数值对数据进行加密（计算）。

② 使用另一个数值对加密数据进行计算就可以让数据恢复原样。

③ 无法从一种密钥推算出另一种密钥。

稍微思考一下便知道，想要找到满足以上条件的算法难度有多大。所以，RSA等可以实现公开密钥加密的算法的提出，对当今互联网社会的安全有着重要的意义。

加密方法2：共享密钥加密(对称加密，加密和解密密钥相同，RSA)

共享密钥加密, 也叫对称加密。RSA比较流行。

加密数据的方法可以分为两种：加密和解密都使用相同密钥的“共享密钥加密”和分别使用不同密钥的“公开密钥加密”。

正常通信流程

1. A生成密钥。
2. A使用密钥加密数据生成密文。
3. A 发送密钥给B
4. A 发送密文给B
5. B使用密钥解密。得到原文。

Ps:

实现共享密钥加密的算法有凯撒密码、AES、DES、动态口令等，其中AES的应用最为广泛。

可能的问题, 如果A和B只能通过网上交互密钥的话，密钥可能被监听， 从而监听者可以解密，也就失去了加密的意义。

在第二次世界大战中，德军所用的“恩尼格玛密码机”（Enigma）使用的加密方式就是共享密钥加密。德军将一个月的密钥记录成表格进行交接，因此密钥分配并不是该密码机的弱点。然而，使用该密码机加密后的密文会周期性地出现相同的文字，英国的数学家艾伦·图灵就是利用这一点破译了密文，给盟军的胜利带来了极大的帮助。现在被普遍使用的加密算法即便连续发送相似的文字，也难以被破解。

混合加密，SSL协议

混合加密。SSL协议就应用了混合加密。

共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密。

性能问题：使用共享密钥加密数据。

安全问题，共享密钥算法中的密钥则使用公开密钥加密处理。

流程如下：

1. B准备公开密钥PB和私有密钥SB. 并发送PB给A
2. A使用PB加密 共享密钥SA, 并发送给B。B通过SB解密密文得到 共享密钥SA。
3. A 使用SA加密数据，并发送给B
4. B接受到数据后 使用SA解密，得到原文。

这个解决的性能问题。无法解决中间人攻击问题。

ps:

像这样，混合加密在安全性和处理速度上都有优势。能够为网络提供通信安全的SSL协议也应用了混合加密方法。SSL是Secure Sockets Layer（安全套接层）的简写，该协议经过版本升级后，现在已正式命名为TLS（TransportLayer Security，传输层安全）。但是，SSL这个名字在人们心中已经根深蒂固，因此该协议现在也常被称为SSL协议或者SSL / TLS协议。

消息认证码(使用共享密钥加密)-防篡改

消息认证码（英语：Message authentication code，缩写为MAC）

消息认证码可以实现“认证”和“检测篡改”这两个功能。密文的内容在传输过程中可能会被篡改，这会导致解密后的内容发生变化，从而产生误会。消息认证码就是可以预防这种情况发生的机制。

首先，我们来看看什么情况下需要使用消息认证码。

假设A在B处购买商品，需要将商品编号abc告诉B。

1. A通过安全的方法把共享密钥发送给B。

2. A加密消息。

3. A把密文发送给B

4. B收到后对密文进行解密，最终得到了原本的商品编号abc。

过程3，我可以篡改密文。这样B解密错误的密文，得到的就是错误的商品编号xyz。（假设是使用的公开密钥加密，私有密钥解密。这样谁都可以加密消息，然后只有A、B可以解密。于是我虽然不能解密，但是我可以伪造消息）。

如果使用消息认证码

1. A通过安全的方法把共享密钥发送给B。
2. A加密消息。
3. A只做用于消息认证码的密钥，安全地发送给B。
4. A 使用密文+密钥 生成mac(Message Authentication Code)
5. A把密文和mac发送给B
6. B收到后, 先用密文+密钥 生成mac, 对比接收到的mac, 如果不相同，说明消息被篡改。否则对密文进行解密，最终得到了原本的商品编号abc。

说明：

我们可以把MAC想象成是由密钥和密文组成的字符串的“哈希值”。计算MAC的算法有HMAC[插图]、OMAC[插图]、CMAC[插图]等。目前，HMAC的应用最为广泛。

这种情况下，即时我篡改密文，我也没法生成相应的mac, 因为我没有对应的密钥。

安全地发送方法可以使用 参考中的 迪菲-赫尔曼 密钥交换。

ps:

加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密相关的计算。如果原本的消息是很长的句子，那么它被篡改后意思会变得很奇怪，所以接收者有可能会发现它是被篡改过的。**但是，如果原本的消息就是商品编号等无法被人们直接理解的内容，那么解密后接收者便很难判断它是否被篡改。**由于密码本身无法告诉人们消息是否被篡改，所以就需要使用消息验证码来检测。

[TOC]

数字签名(使用公开密钥加密)-防篡改

数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。由于在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发送者，这样是无法预防事后否认行为的。而数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了。

使用流程

1. A给消息生成 数字签名，且只能由A生成。
2. A发送消息和签名 给B
3. B确认签名后，就能确认消息发送者一定是A.

签名过程-公开密钥加密

我们先来复习一下前面的知识。公开密钥加密中，加密使用的是公开密钥P，解密使用的是私有密钥[插图]。任何人都可以使用公开密钥对数据进行加密，但只有持有私有密钥的人才能解密数据。然而，数字签名却是恰恰相反的。

数字签名中A使用私钥加密，这样只有A可以生成数字签名。。

其他人使用公开密钥解密验证。

补充说明：

公开密钥加密的加密和解密都比较耗时。为了节约运算时间，实际上不会对消息直接进行加密，而是先求得消息的哈希值，再对哈希值进行加密，然后将其作为签名来使用

虽然数字签名可以实现“认证”“检测篡改”“预防事后否认”三个功能，但它也有一个缺陷。那就是，虽然使用数字签名后B会相信消息的发送者就是A，但实际上也有可能是X冒充了A。其根本原因在于使用公开密钥加密无法确定公开密钥的制作者是谁（中间人攻击）。收到的公开密钥上也没有任何制作者的信息。因此，公开密钥有可能是由某个冒充A的人生成的。使用下一节将要讲到的“数字证书”就能解决这个问题。

数字证书

“公开密钥加密”和“数字签名”无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。不过，如果使用本节讲解的数字证书，就能保证公开密钥的正确性。

使用流程：

1. A时才有PA和SA, 现在需要把PA发送给B
2. A首先想CA 申请发行证书，证明PA确实是A生成的。。这里需要用A的邮箱信息，如果是网站就是域名信息。
3. 认证中心(CA) 有其自身的公钥PC和私钥SC
4. A 将PA+包含邮箱信息的个人资料发给CA
5. CA确认资料无误，使用SC, 根据A的资料生成数字签名。
6. 认证中心将生成的数字签名和资料放入同一个文件中。 然后发送给A。这个文件就是A的数字证书。
7. A将作为公开密钥的数字证书发送给B。
8. B收到数字证书后，确认证书里的邮箱地址确实是A的地址，接着，B获取了认证中心的公开密钥。
9. B对证书内的签名进行验证，判断它是否为认证中心给出的签名。证书中的签名只能用认证中心的公开密钥PC进行验证。如果验证结果没有异常，就说明整份证书的确由认证中心发行。
10. 确认了证书是由认证中心发行的，且邮件地址就是A的之后，B从证书中取出A的公开密钥PA。这样，公开密钥便从A传到了B。

可能的问题：

1. X 为了假冒A, 也申请一个证书。但是证书里的信息不是A的。。所以仿冒失败。
2. X 为了假冒A, PC也伪造。但是实际上这里PC也是通过数字证书交互的，由他的上级认证中心签发。一级一级上去知道RCA, 注意这里RCA的公开密钥是一开始就存到电脑的，所以没有通信就没法伪造。。从而确保认证中心的PC是无法伪造的。

参考

哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景。

任意数据作为输入，经过哈希函数处理，生成固定长度的无规律数值。这个无规律数值就是“哈希值”。

哈希函数的特征：

1. 哈希值长度固定。不论输入多大/多小。
2. 输入相同，则哈希值也相同。所以如果哈希值相同，则输入也相同（并不绝对，其实有哈希冲突，一般不考虑）。
3. 即使输入差异很小，哈希值差异也会很大。 避免通过hash值逆运算求输入。
4. 可能有哈希冲突，即不同输入，可能hash值一样。概率很低。
5. 不可逆。就是不能逆运算从hash值求输入。
6. 计算容易。

哈希函数的算法中具有代表性的是MD5、SHA-1和SHA-2等。其中SHA-2是现在应用较为广泛的一个，而MD5和SHA-1存在安全隐患，不推荐使用。

不同算法的计算方式也会有所不同，比如SHA-1需要经过数百次的加法和移位运算才能生成哈希值。

虽然本节中讲过如果输入的数据相同，那么输出的哈希值也必定相同，但这是在使用同一个算法的前提下得出的结论。若使用的算法不同，那么就算输入的数据相同，得到的哈希值也是不同的。

应用示例

将用户输入的密码保存到服务器时也需要用到哈希函数。如果把密码直接保存到服务器，可能会被第三者窃听，因此需要算出密码的哈希值，并只存储哈希值。当用户输入密码时，先算出该输入密码的哈希值，再把它和服务器中的哈希值进行比对。这样一来，就算保存的哈希值暴露了，鉴于上文中提到的哈希函数的第五个特征（输入输出不可逆），第三者也无法得知原本的密码。就像这样，使用哈希函数可以更安全地实现基于密码的用户认证。

迪菲-赫尔曼 密钥交换（安全）

迪菲-赫尔曼（Diffie-Hellman）密钥交换是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。

假设：

1. P+S = PS 可合成密钥
2. 合成的密钥不能分解，譬如由PS+P 无法推出S, PS+S也无法推出P。
3. 合成的密钥可继续合成。 P+PS = PPS
4. 合成的密钥与顺序无关，只与使用了哪些密钥有关。PPS=PSP

使用流程

1. A 生成密钥P, P泄露也没事。
2. A 把 P 发送给B
3. A和B各自准备自己的私钥 SA和SB. 这个自己管理，不需要通信，所以是安全的。
4. A合成自己的密钥 P+SA = P-SA
5. B合成自己的密钥P+SB = P-SB
6. 交互密钥： A将密钥P-SA发送给B, B也将密钥P-SB发送给A。于是A有 P, SA, P-SA, P-SB, B有P, SB, P-
   SA, P-SB
7. A使用自己的私钥和对方的合成密钥 再合并为 SA+P+SB
8. B使用自己的私钥和对方的合成密钥 再合并为 SB+P+SA. 这个SA+P+SB 就可以作为密钥来加密解密时候用。

这个过程中，P, P-SA, P-SB 都可能泄露。但是泄露的这3个密钥无法生成SA+P+SB, 所以是安全的。

数学方法

接下来用公式来表示这种密钥交换法。用P、G两个整数来表示一开始生成的公开密钥P。其中P是一个非常大的素数，而G是素数P所对应的生成元（或者“原根”）中的一个。

1. 首先，由A来准备素数P和生成元G。这两个数公开也没有关系。
2. A将素数P和生成元G发送给B。
3. 接下来，A和B分别准备了各自的秘密数字X和Y。X和Y都必须小于P-2。
4. A和B分别计算“（G的秘密数字次方）mod P”。mod运算就是取余运算。“G modP”就是计算G除以P后的余数。此处的运算等同于概念意义上的“合成”。
5. A和B将自己的计算结果发送给对方。
6. A和B收到对方的计算结果后，先计算这个值的秘密数字次方，然后再mod P。最后A和B会得到相同的结果。

下面来验证这种密钥交换法的安全性。即便X窃听了整个通信过程，也无法用窃听到的数字计算出A和B共有的数字。而且，窃听者也无法计算出保密数字X和Y。因此，此处使用迪菲-赫尔曼密钥交换是安全的。

迪菲-赫尔曼密钥交换由惠特菲尔德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman）提出，两人在2015年获得了图灵奖。根据素数P、生成元G和“GX mod P”求出X的问题就是“离散对数问题”，人们至今还未找到这个问题的解法，而迪菲-赫尔曼密钥交换正是利用了这个数学难题。