计算机网络——网络安全
本章中我们将着重考察网络上运行的各式各样的程序如何保护自己的安全。 和任何成熟的密码学文章一样，我们使用Alice和Bob来表示两个希望进行安全通信的个体，用Trudy（来自Intruder，即入侵者）来表示试图迫害他们的人。
什么是网络安全
安全通信（Secure communication）具有以下特性：
- 机密性（Confidentiality）：仅有发送方和接收方可以理解传输报文的内容，这要求报文在一定程度上进行加密（encrypted）。
- 报文完整性（Message integrity）：接收方可以验证报文在传输过程中未受改变。
- 端点鉴别（End-point authentication）：发送方和接收方都可以确认通信过程中所涉及的另一方的身份。
- 运行安全性（Operational security）：保护网络系统在运行时的安全，反制对机构网络的攻击。
相对地，入侵者总是可以执行以下行为：
- 窃听：监听并记录任何信道上传输的任何报文，包括控制和数据报文；
- 修改、插入或删除任何报文或报文的任何内容。
这些行为让入侵者有能力窃听通信内容，包括口令和数据，假冒另一个实体，劫持会话或是系统过载以拒绝合法请求（称为拒绝服务攻击，DoS）。
密码学是网络安全的基石。
有关信息安全的术语翻译标准，参见(GB/T 25069-2022 信息安全技术 术语)[https://openstd.samr.gov.cn/bzgk/gb/newGbInfo?hcno=56123482721B1AC3CEDCD3B5C022CAD8]。
密码学概观
和基于语言学的传统密码学不同，现代密码学（Cryptography）基于近三十年来统计学、信息论、离散数学和抽象代数等的广泛发展。 尽管密码学通常只是有关数据的加密与解密，其与检验报文完整性、端点鉴别和不可否认性紧密相关。
我们称报文的最初形式为明文（plaintext，cleartext）。 发送方（Alice）使用加密算法（Encryption algorithm）加密其报文，然后产生密文（Ciphertext）。 该密文原则上对任何入侵者都是难以理解的（数学上讲，即对入侵者不存在计算明文的多项式算法）。
作为加密算法的输入，Alice通常需要提供一个密钥（Key），记为$K_A$。 我们用$m$来表示明文，而$K_A(m)$表示加密后的密文。 如何使用密钥进行加密则取决于语境中的加密算法。
接收方（Bob）也必须为解密算法（Decryption algorithm）提供一个密钥作为输入，记为$K_B$。 我们希望解密得出的内容和明文相同，即$m = K_B(K_A(m))$。
如果接收方和发送方的密钥相同，那么这种加密系统称为对称密钥系统（Symmetric key system）。 如果发送方使用一个密钥进行加密，接收方使用另一个密钥进行解密，那么这种加密系统就是非对称的。 在这种情况下，加密的密钥通常是公开的，称为公钥（Public key），而解密的密钥是保密的，称为私钥（Private key）。 这种加密系统也称公开密钥系统（Public key system）。
值得注意的是，公用的加密技术都是已知的，人人都可以使用。 这是因为密码学的知名原理：柯克霍夫原则（Kerckhoffs’s principle），即密码系统应该就算被所有人知道系统的运作步骤，仍然是安全的。 换句话说，即使密码系统的任何细节已为人悉知，只要密匙未泄漏，它也应是安全的，系统的安全应当依靠密钥的保密性，而非算法的保密性。 当然，对于军用算法，即使密码系统也是不公开的。
这里需要注意区分密钥（key）、口令（password）和密码。 密钥是加密或解密算法的输入，而口令通常是鉴别用户的身份所用。 日常生活中广泛接触的银行卡密码、计算机登录密码或电子邮箱的密码实际上都是口令。 有些加密系统会使用用户的口令来生成密钥，这种加密方法称为基于口令的加密（Password based encryption），在RFC 8018中就描述了这些方法。 密码则是一个口语上的说法，尽管密码学以其命名，它并不具有严格的定义。
攻击者模型
入侵者希望攻击密码系统，以获得任何密文对应的明文甚至密钥。 我们在考虑侵入者对密码系统的攻击能力时，对其能力作以下分类：
- 唯密文攻击（ciphertext-only attack）：攻击者只能够获得密文，不知道任何有关明文的信息。
- 唯密文攻击的一个特殊的子类型为暴力攻击，即穷举所有可能的密钥。如果攻击者具有无限的资源，那么只有具有信息论安全性（Information-theoretic security）的加密方法可以抵抗穷举攻击。目前最知名的信息论安全算法为一次一密加密（One-time pad）
- 已知明文攻击（known-plaintext attack）：攻击者可以获得至少一部分明文，并且知道它们对应的密文。古典密码很难对抗这种攻击。
- 选择明文攻击（chosen-plaintext attack）：攻击者可以获得任何自选明文的密文。
- 选择密文攻击（chosen-ciphertext attack）：攻击者可以获得任何自选密文的明文。这种情况下，攻击者更关心密钥而非明文。
研究在不知道通常解密所需的秘密信息（即密钥）的情况下对信息进行解密的学问称为密码分析（Cryptanalysis）。 从经典的频率分析，到纯数学的大数分解，再到基于额外信息的侧信道攻击，甚至使用强迫（Rubber-hose cryptanalysis，指用橡胶软管鞭打脚心）或隐秘手段（Black-bag cryptanalysis，指窃贼用来携带作案工具的黑色皮包），都可以看作密码分析的一部分。
对称密码系统
没有一篇介绍密码学的文章不是从凯撒密码开始的。
凯撒密码即位移密码，这种密码把每个字母依次用字母表后的几个字母替代。
假设我们取后三个字符，那么a变成d，z变成c。
在这种密码中，密钥就是后移字母的个数，此处为3。
显然，这种密码非常容易攻破，因为密钥的有效值最多只有25个。
凯撒密码的一种改进是单码代替密码（Monoalphabetic cipher）。 这种密码建立一个从字母表到字母表的双射作为密码。 加密时使用映射把原文的每个字符替代成密文，解密时使用逆映射即可。 这种密码的密钥就是这个双射，其有$26! \approx 10^{26}$种可能。
虽然这种方法足以对抗现代个人计算机的穷举攻击，但简单的统计分析就可以使其败下阵来。
以英语为例，大量语料表明，英语中字母e和t的出现频率最高。
如果能够获得足量的密文，那么使用概率分析就可以查出这个双射，因此这种密码难以对抗唯密文攻击。
显然，这种密码也不能对抗已知明文攻击，只要能够确定几个字母的对应关系，穷举所需的时间就能大大减小。
针对这种缺点，人们发明了多码代替密码（Polyalphabetic cipher）。 这种密码轮流使用多个单码代替密码来进行加密。 我们设两个不同的单码代替密码$C_1$、$C_2$，那么轮流使用$C_1, C_2, C_1, C_2, \dots$就形成了一个多码代替密码。 这种密码的密钥包括每个单码代替密码的映射表和使用这些密码的次序。
块密码
对称加密技术按照处理数据的单位可以分为两类：块密码（Block cipher）和流密码（Stream cipher）。 不正式地说，块密码把数据分成固定大小的块，然后对每一块进行加密； 而流密码则对数据的每一比特进行加密，这通常是通过按位异或做到的。 流密码主要用于各种无线数据的加密，本节中我们将主要考虑块密码，这是PGP（应用层加密）、SSL（连接层加密）和IPsec（网络层加密）的主要形式。
块密码首先把输入数据分成固定大小的块，然后使用一个双射将明文块转化成密文块。 实现这种映射的最简单形式就是构造一个数组，然后直接用明文块作为下标进行索引。 然而，当块增大时，这个数组就会以指数速度膨胀，因此即使对比较小的块（比如64比特），这种表也是不现实的。
取而代之的是，块密码通常使用函数模拟这张表。 常见的情况是首先先把较大的块分成几个较小的块，然后为这几个块依次选用不同的映射表进行加密，最后还要使用一个置乱函数打乱这些块之间的顺序。 如果将64比特分为八个八比特大小的分块，那么所有表加起来只需要$8 \times 2^8 = 2048$个表项，远远小于$2^{64}$个。 这种同时使用代替和置乱的密码系统称为代换-置换网络（Substitution-Permutation Network，SPN）
现有的比较流行的块密码，如高级加密标准（Advanced Encryption Standard，AES）和数据加密标准（Data Encryption Standard，DES），就使用SPN的变种。 这种密码系统使用密钥来决定代替表和置换函数。 AES的分块长达128比特，而其密钥长为128、192或256比特。
密码块链接
使用分块进行加密会导致一个微妙的问题。
当密钥相同时，同一位置上的相同内容会导致相同的输出。
考虑常见的HTTP报文，其第一块几乎总是含有GET ... HTTP/1.1，因此总是会产生相同的输出。
如果攻击者发现密文中反复出现相同的内容，那么他也许可以猜测出明文，甚至可能解密整个报文。
为此，我们尝试在加密过程中引入一些随机性。 我们为每个明文块$m(i)$生成一个等长的随机数$r(i)$，然后先计算两个数的按位异或，再进行加密，得出$c(i) = K_s(m(i) \oplus r(i))$。 之后，我们同时发送$c(i)$和$r(i)$。 接收方需要解密时，计算 \(K_s(c(i)) \oplus r(i) = K_s(K_s(m(i) \oplus r(i))) \oplus r(i) = m(i) \oplus r(i) \oplus r(i) = m(i)\) 即可取回明文。
这个方法固然可以避免密文的重复，但是也会导致对带宽的需求翻倍，因为还要发送额外的随机数。 为此，块密码通常使用一种称为密码块链接（Cipher Block Chaining，CBC）的技术。 这种技术的基本思想就是只随机第一个数，然后用两边协商的相同方式计算后续的随机数。
首先，在加密报文（或数据流）之前，发送方生成一个随机的比特串（记为$c(0)$），称为初始向量（Initialization Vector，IV），然后明文发送给接收方。 然后，对第一个块，发送方计算$c(1) = K_s(m(1) \oplus c(0))$，这个结果既是马上发送的密文，又是下一个使用的随机数。 此后，对每一个块，都使用$c(i) = K_s(m(i) \oplus c(i-1))$计算密文，然后发送密文。
接收方则总是使用和上文所述相同的方式得出明文。 接收方总是已经接收了$c(i-1)$，因此总是可以利用它进行解密。
使用这种加密的后果是两方必须使用一种方式协商IV，我们在之后的协议中都能见到解决这个问题的方案。
公开密钥系统
对称密钥系统面对的最困难的问题往往不在于系统本身，而在于如何让两方之间协商密钥。 公开密钥系统解决了这个问题。
公开密钥系统使用一个公开的公钥进行加密，但使用一个只有接收方知道的私钥进行解密。 我们记公钥为$K_B^+$，私钥为$K_B^-$。 公钥系统保证$K_B^-(K_B^+(m)) = m$，值得注意的是，交换公钥和私钥也能得到相同的结果，即$K_B^+(K_B^-(m)) = m$。
公开密钥系统的一大弱点在于任何人都可以使用公钥进行加密并得到密文，因此任何人都可以非常容易地进行选择密文攻击。 此外，和对称密钥系统不同，在对称密钥系统中，如果接收方收到了可以解密的报文，那么它可以确信这是由发送发而非侵入者发送的。 相对地，在公钥系统中，任何人都可以向接收方发送可以解密的报文，因此我们需要使用额外的数字签名算法来保证报文是由正确的发送方发送的。
公开密钥系统基于一类称为单向函数（One-way function）的特殊数学问题。 简单地讲，单向函数就是容易计算其函数值，但已知函数值难以计算其逆的函数。 尽管数学上尚未证明单向函数的存在（存在单向函数蕴含$NP \neq P$），但现有的公钥系统运行良好。 现有的最常用的单向函数候选为：大整数的乘法（容易计算）与分解（难以计算）与有限群上的指数（容易计算）和对数（难以计算）。 前者就是RSA算法，而后者如果运行在整数同余群上就是ElGamal算法，如果运行在椭圆曲线群上就是椭圆曲线加密（Elliptic Curve Cryptography，ECC）。 这三者都是常见的公钥加密算法。
Diffie-Hellman密钥交换算法
在研究更一般的公钥算法之前，首先让我们看看在不使用公钥的情况下如何进行密钥交换。 和ElGamal公钥加密类似，Diffie-Hellman也使用同余乘法群上的运算进行加密，这个加密实际上非常简单。
Diffie-Hellman算法通过在不安全的信道上进行以下通信来交换密钥：
- 首先，Alice和Bob协商选择一个模数$p$，然后选择一个同余群$\mathbb{Z}_p$的生成元$g$。通常$p$是一个质数，这样同余群的性质更好。$g$称为这个群的原根（Primitive root）。$p,g$都是周知的，通常从标准中选择一对。
- Alice选择一个随机整数$1 < a < n$，计算$g^a$，然后发送给Bob，其中$n$为群$\mathbb{Z}_p$的阶（即$g$的阶）。
- Bob选择一个随机整数$1 < b < n$，计算$g^b$，然后发送给Alice。
- 密钥为$\left( g^a \right)^b \equiv \left( g^b \right)^a \pmod{p}$。
任何人都可以从通信中得到$p, g, g^a, g^b$，但是却难以计算$g^{ab}$。 这是因为要计算后者需要求出同余意义下的$a = \log_g g^a$或$b = \log_g g^b$，这个问题称为离散对数问题。 而正如上文所述，离散对数问题是单向函数候选之一。
如果把群从整数同余群迁移到椭圆曲线群，那么得到的这种算法称为椭圆曲线Diffie-Hellman密钥交换算法（Elliptic Curve Diffie–Hellman key exchange, ECDH）。
RSA
RSA算法常年作为公开密钥系统的代名词，由其创始人Ron Rivest、Adi Shamir和Leonard Adleman的首字母命名。 椭圆曲线加密的性能好于RSA算法，因此其正在慢慢取代RSA算法。 但是RSA的性能已经足够好，且如同我们之后将要看到的，公钥加密算法仅在握手时使用，因此对性能并不非常敏感，所以仍有大量的网页使用RSA加密。
RSA算法基于欧拉定理，即以下著名公式： \(\gcd(a,n) = 1 \implies a^{\varphi(n)} \equiv 1 \pmod{n}\)
RSA使用以下方法生成公钥和私钥：
- 选择两个不同的大素数$p,q$。这两个素数越大，加解密所需时间就越长，但也越安全。
- 计算$n = p \times q, \varphi(n) = (p-1) \times (q-1)$。
- 任选一个数$e < n$，满足$\gcd(e,n) = 1$，即两数互素。
- 选择一个数$d$，满足$e \times d \equiv 1 \pmod{\varphi(n)}$。
- 现在，公钥为$(n,e)$，私钥为$(n,d)$。
然后使用以下算法进行加密和解密：
- 假设Alice要发送一组比特，可表示为数$m$，我们通过分块保证$m < n$，那么她计算$c = m^e \pmod{n}$作为密文。
- 现在Bob需要解密，则他计算$m = c^d \pmod{n}$。
现在我们来考虑这个算法的原理。 我们首先证明解密算法的正确性： 首先我们假设$m$与$n$互素，那么有 \(\begin{aligned} c^d &\equiv m^{ed} &\pmod{n} \\ &\equiv m^{k \varphi(n) + 1} &\pmod{n} \\ &\equiv m &\pmod{n} \end{aligned}\) 如果两者不互素，那么不能使用欧拉定理证明这个结论。 但是由于$n$只有四个因子$1,p,q,n$，因此要么有$m \equiv 0 \pmod{p}$，要么有$m \equiv 0 \pmod{q}$。 我们设$m \equiv 0 \pmod{p}$，那么我们有 \(c^d \equiv 0 \equiv m \pmod{p}\)； 同时，又因为$m < n$，因此$m,q$一定互素，所以有 \(c^d \equiv m^{k \varphi(n) + 1} \equiv m^{k(p-1)\varphi(q) + 1} \equiv m \pmod{q}\)。 根据中国剩余定理，这说明$c^d \equiv m \pmod{n}$。 使用费马小定理也可以证明这个结论。
现在让我们来看看为什么加密是有效的，即为什么不能只用公钥进行解密。 首先，攻击者显然无法在只知道密文而不知道私钥的情形下进行解密，因为对不同的$d$，$c^d$对$n$的模很大概率是不同的。 我们假设攻击者知道公钥$(n,e)$，然后希望计算私钥$(n,d)$。 这相当于求解方程$ed= k \varphi(n) + 1$。 如果$\varphi(n)$已知，那么这相当于求解一个常见的丢番图方程，是相当容易的，但如果不知道其值，那么求解是不可能的。 但问题就在于求解$\varphi(n)$。 我们已经知道$\varphi(n) = (p-1)(q-1)$，那么“只”需要求出$n$的两个质因数即可。 不幸的是，目前还没有在电子计算机上求解因式分解的多项式算法，因此这个解密是困难的。 如果不使用因数分解，则直接求解$\varphi(n)$的典型时间复杂度为$\mathcal{O}(n)$。 考虑到$p,q$的数量级通常为$2^{1024}$，这种求解也是不可能的。
会话密钥
需要注意的是，使用RSA会频繁遇到大数的指数运算，而这种运算的速度是相当慢的。 为此，通常RSA会和对称加密联合使用。
具体而言，发送方Alice提前选择一个用于对称加密的密钥，称为会话密钥（Session key），然后使用公钥加密把这个密钥发送给Bob。 Bob使用自己的私钥解密，然后就能得到会话密钥，此后就使用会话密钥进行对称加密。
这样，我们就既解决了RSA速度较慢的问题，又解决了协商密钥的问题。
如果一个加密通信过程在私钥泄露后仍能保证会话密钥不泄露，那么这种过程就是前向安全（Forward secure）的。 前向安全意味着过去的通信不会受到将来私钥泄露的威胁。 由于RSA算法并不具有前向安全性，现在流行的许多加密通信协议实际上使用Diffie-Hellman密钥交换算法的一种改进（临时DH，D-H Ephemeral）交换会话密钥。