拾石录
安全算法
- 安全和算法
- 加密的基础知识
- 哈希函数
- 共享密钥加密
- 公开密钥加密
- 混合加密
- 迪菲-赫尔曼密钥交换
- 消息认证码
- 数字签名
- 数字证书
安全和算法
通过互联网交换数据时，数据要经过各种各样的网络和设备才能传到对方那里。数据在传输过程中有可能会经过某些恶意用户的设备，从而导致内容被盗取。因此，要想安全地使用互联网，安全技术是不可或缺的。
传输数据时的四个问题
- 窃听：A 向 B 发送的消息可能会在传输途中被 X 偷看。
- 假冒：A 以为向 B 发送了消息，然而 B 有可能是 X 冒充的；反过来，B 以为从 A 那里收到了消息，然而 A 也有可能是 X 冒充的。
- 篡改：即便 B 确实收到了 A 发送的消息，但也有可能该消息的内容在途中就被 X 更改了。
- 事后否认：B 从 A 那里收到了消息，但作为消息发送者的 A 可能在事后声称「这不是我发送的消息」。
解决这些问题的安全技术
| 问题 | 解决方法 |
|---|---|
| 窃听 | 加密 |
| 假冒 | 消息认证码 或 数字签名 |
| 篡改 | 消息认证码 或 数字签名 |
| 事后否认 | 数字签名 |
「数字签名」技术存在「无法确认公开密钥的制作者」这一问题，要想解决这个问题，可以使用「数字证书」技术。
加密的基础知识
假设 A 想通过互联网向 B 发送消息，如果直接发送数据的话，数据可能会被第三者恶意窃听。因此，我们需要给想要保密的数据加密。加密后的数据被称为「密文」。
B 收到密文后，需要解除加密才能得到原本的数据。把密文恢复为原本数据的操作就叫作「解密」。
计算机会用由 0 和 1 这两个数字表示的二进制来管理所有数据。对计算机来说，数据就是一串有意义的数字罗列。密文也是数字罗列，只不过它是计算机无法理解的无规律的数字罗列。也就是说，加密就是数据经过某种运算后，变成计算机无法理解的数的过程。
在加密运算上会用到「密钥」。所以加密就是用密钥对数据进行数值运算，把数据变成第三者无法理解的形式的过程。反过来，解密就是通过密钥进行数值计算，把密文恢复成原本数据的过程。
哈希函数
哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景。为了便于理解，我们可以把哈希函数想象成搅拌机。
"abc" --Hash--> 7f0579bc2d
输出的无规律数值就是「哈希值」。哈希值虽然是数字，但多用十六进制来表示。
哈希函数的特征：
- 输出的哈希值数据长度不变。即使输入了相当大的数据，输出的哈希值的长度也保持不变。不管输入的数据多小，哈希值的长度仍然相同。
- 如果输入的数据相同，那么输出的哈希值也必定相同。
- 即使输入的数据相似，但哪怕只有一个字符不同，输出的哈希值也会截然不同。
- 即使输入的两个数据完全不同，输出的哈希值也有可能一样。这种情况叫作「哈希冲突」。
- 无法根据哈希值推算出原值。把哈希函数应用于密码等安全方面时，这是一个重要的条件。
共享密钥加密
共享密钥加密也叫「对称加密」，加密和解密都使用同一个密钥。
假设 A 用共享密钥加密对消息进行加密，并通过安全的方法将密钥发送给了 B：
- A 使用密钥对消息进行加密，得到密文
- A 把密文发送给 B
- B 收到后对密文进行解密，得到原本的数据
共享密钥加密中，加密和解密使用的是同一个密钥，所以一旦密钥泄露，密文就会被破解。常用的共享密钥加密算法有 AES、DES、3DES 等。
公开密钥加密
公开密钥加密（也叫「非对称加密」）在加密和解密时使用的是不同的密钥。其中一个密钥叫「公开密钥」（任何人都可以知道），另一个叫「私有密钥」（只有自己知道）。
- 用公开密钥加密的数据，只能用对应的私有密钥来解密
- 用私有密钥加密的数据，只能用对应的公开密钥来解密
假设 A 持有公开密钥和私有密钥，想接收 B 发来的消息：
- A 将公开密钥发送给 B
- B 使用 A 的公开密钥对消息进行加密，得到密文
- B 把密文发送给 A
- A 收到后使用自己的私有密钥进行解密，得到原本的数据
就算公开密钥被第三者知道了也没关系，因为只有持有私有密钥的 A 才能解密。代表性的公开密钥加密算法是 RSA。
补充：公开密钥加密存在两个问题。一是处理速度慢，比共享密钥加密要慢很多。二是无法确认公开密钥的制作者到底是谁，公开密钥有可能是由某个冒充 A 的人生成的。
混合加密
共享密钥加密处理速度快但存在密钥交换的问题，公开密钥加密安全性高但速度慢。混合加密将两者结合起来：
- 先用公开密钥加密来安全地交换共享密钥加密中要使用的密钥
- 交换完密钥后，再用共享密钥加密来进行消息的加密和解密
这样既能保证密钥交换的安全性，又能利用共享密钥加密的速度优势。实际上，互联网通信中广泛使用的 SSL/TLS 协议就采用了混合加密的方式。
迪菲-赫尔曼密钥交换
迪菲-赫尔曼（Diffie-Hellman）密钥交换是一种在双方之间安全地交换密钥的算法。它可以在不安全的通信线路上安全地交换密钥。
其思路是：每个人都有各自的私有密钥，并通过某种计算生成一个可以公开的数值。双方交换各自公开的数值后，再用自己的私有密钥和对方的公开数值进行计算，就能生成相同的密钥。而第三者即使知道了双方公开的数值，也无法算出这个密钥。
A 的私有密钥 × B 的公开数值 ＝ B 的私有密钥 × A 的公开数值 ＝ 共享密钥
这个算法的安全性基于「离散对数问题」——即使知道公开数值，也很难反向推算出私有密钥。
消息认证码
消息认证码（MAC，Message Authentication Code）可以实现「认证」和「检测篡改」这两个功能。
假设 A 要向 B 发送商品编号 abc：
- A 使用共享密钥加密对消息进行加密，得到密文
- A 使用密文和密钥生成一个值，这个值就是 MAC
- A 将 MAC 和密文一起发送给 B
- B 也使用收到的密文和密钥来生成 MAC，经过对比，如果一致就确认密文未被篡改
如果 X 在通信过程中对密文进行了篡改，B 使用被篡改的密文计算 MAC，得到的值和收到的 MAC 不一致，B 就能意识到密文被篡改了。
计算 MAC 的算法有 HMAC、OMAC、CMAC 等，目前 HMAC 的应用最为广泛。
解说：加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密。如果原本的消息就是商品编号等无法被人们直接理解的内容，那么解密后接收者便很难判断它是否被篡改。由于密码本身无法告诉人们消息是否被篡改，所以就需要使用消息认证码来检测。
缺点：使用 MAC 时，生成的一方和检测的一方持有同样的密钥，所以不能确定 MAC 由哪方生成。也就是说，我们无法证明原本的消息是 A 生成的还是 B 生成的，因此不能预防「事后否认」。这个问题可以用数字签名来解决。
数字签名
数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。由于在消息认证码中使用的是共享密钥加密，持有密钥的收信人也有可能是消息的发送者，无法预防事后否认。而数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了。
数字签名的生成与验证
数字签名的生成使用的是公开密钥加密，但密钥的使用方式恰好相反：
- 在公开密钥加密中，加密用公开密钥 P，解密用私有密钥 S
- 在数字签名中，加密用私有密钥 S，解密用公开密钥 P
流程如下：
- A 准备好需要发送的消息、私有密钥和公开密钥
- A 将公开密钥发送给 B
- A 使用私有密钥加密消息，加密后的消息就是数字签名
- A 将消息和签名都发送给 B
- B 使用公开密钥对签名进行解密
- B 对解密后的消息进行确认，看它是否和收到的消息一致
解说：生成的是「只能由持有私有密钥的 A 来加密，但只要有公开密钥，谁都可以进行解密的密文」。这个密文作为密码似乎没有任何意义，但是换一个角度来看就会发现，它可以保证这个密文的制作者只能是持有私有密钥的 A。
能够用 A 的公开密钥解密的密文，必定是由 A 生成的。因此，我们可以利用这个结论来确认消息的发送者是否为 A，消息是否被人篡改。由于 B 只有公开密钥，无法生成 A 的签名，所以也预防了「事后否认」这一问题的发生。
为了节约运算时间，实际上不会对消息直接进行加密，而是先求得消息的哈希值，再对哈希值进行加密，然后将其作为签名来使用。
缺陷：虽然 B 会相信消息的发送者就是 A，但实际上也有可能是 X 冒充了 A。其根本原因在于使用公开密钥加密无法确定公开密钥的制作者是谁，公开密钥有可能是由某个冒充 A 的人生成的。使用「数字证书」就能解决这个问题。
数字证书
「公开密钥加密」和「数字签名」无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。如果使用数字证书，就能保证公开密钥的正确性。
数字证书的流程：
- A 持有公开密钥和私有密钥，想要将公开密钥发送给 B
- A 向认证中心（CA，Certificate Authority）提出申请
- 认证中心使用自己的私有密钥对 A 的公开密钥进行签名，生成数字证书
- A 将数字证书发送给 B
- B 使用认证中心的公开密钥对证书进行验证，确认 A 的公开密钥确实来自认证中心
只要 B 信任认证中心，就可以信任证书中包含的公开密钥。认证中心是第三方机构，其公开密钥通常预先安装在操作系统或浏览器中。
这样一来，通过数字证书，我们就能确认公开密钥的制作者，解决数字签名中「无法确认公开密钥制作者」的问题，从而实现完整的认证、防篡改和防否认功能。