最近一次更新：2024/10/1
非对称密码学
非对称密码学应用两个密钥、公钥 Pub 和私钥 Pri 。对数据应用公钥或私钥的过程是单向的，即计算上不可能通过 Pub(x) 或 Pri(x) 来反解 x。想要通过这两者获得 x，只能应用另一把钥匙，即 Pri(Pub(x)) = x = Pub(Pri(x))。
顾名思义，公钥是公开的、私钥是保密的。利用这一点和上述数学性质，可以实现加密送信和数字签名。
A 要给 B 加密送信，只需要对明文 x 应用 B 的公钥，得到 y=Pub_B(x)，即加密。B 拿到加密后的信息 y，应用自己的私钥，就可以获得明文：Pri_B(y) = Pri_B(Pub_B(x)) = x。窃听者无法通过信道上传输的 y 来反推 x。
A 要数字签名一个消息，只需要对明文 x 应用自己的私钥，得到 y=Pri_A(x)。A 要公布消息本身 x 和签名 y，利益相关者可以对 y 应用 A 的公钥，验证 Pub_A(y) == x，从而得知 x 是 A 授权发布的。其它人若想伪装成 A 发布消息 x’，就必须同时公布 A 对消息的数字签名 Pri_A(x’)，但其它人无从得知 A 的私钥，所以不可能计算出数字签名 Pri_A(x’)。
【2024年10月1日更新】
具体到 RSA 算法，它的形式是公钥为（n, e），私钥为 d，使得 m^{ed} = m (mod n) [条件1] 对于小于 n 的 m 恒成立。Pub(x) = x^{e} mod n, Pri(x) = x^{d} mod n。
n, e, d 三个数字的生成较为复杂。首先秘密选定两个大质数 p,q，计算 n = pq。然后，通过某个算法构造 e, d 使得 ed = 1 mod ( (p-1)(q-1) ) [条件2]
Q: 为何条件2能够保证条件1？参考如下证明
A: 中国剩余定理表明，要证明 m^{ed} 和 m 在模 n 同余，只需证明它们模 p, 模 q 都同余。下面证明它们模 p 同余。费马小定理表明，当 a 不是质数 p 的倍数，a^{p-1} = 1 mod p。若 m 是 p 的倍数，m^{ed} = 0 mod p, m = 0 mod p。若 m 不是 p 的倍数，m^{ed} = m^{k(p-1) + 1} = m^{p-1}^k * m = 1*m = m mod p。
Q: 如何构造 e, d 满足条件2？
A: 首先选择 e 使得 e 与 phi(n)=(p-1)(q-1) 互质，常用 e = 2^16 + 1 = 65537 以便加速 Pub(x) 的计算。然后，使用扩展欧几里得算法求模逆元，将 e, phi(n) 作为输入，得到 a*e + b*phi(n) = gcd(e, phi(n)) = 1，把 a 作为 d 即可（若 a 为负，加上 phi(n) 的整数倍）
CA、Certificate 和 Chain of Trust
利用数字签名系统，认证权威（CA，Certificate Authority）可以给其他实体颁发数字证书（Certificate）。流程如下：
其它实体把自己的信息和公钥打包（记为 x）交给 CA ，CA 验证并信任实体后，对包裹进行数字签名（使用 CA 的 Private Key），得到一个“证书”，证书中包含 CA 对 x 的数字签名 sig=Pri_CA(x)，并把证书回复给实体。之后公众找到实体通信，实体会出示证书，公众会使用 CA 的公钥验证证书中的数字签名：Pub_CA(sig) = Pub_CA(Pri_CA(x)) = x。如果公众信任CA，那么就可以认定 x 中包含的公钥与 x 中指示的实体信息是对应的。
在上一个例子中，如果获得证书的实体利用自己的私钥进行数字签名、给自己信任的实体颁发证书的话，就形成了一个信任的链条（Chain of Trust），从根 CA 指向实体指向更多实体。这个链条中间的每一个实体的公钥都被上一级 CA 颁发的证书所认证，而它又通过自己的私钥给下一级 CA 颁发证书。
实际使用中，信任链通常只有三层：根 CA、中间 CA 和最终实体。通常规定最终实体无权颁发证书。以 TLS 证书为例，在浏览器中查看网站的 TLS 证书（详细信息->层级结构），就可以看到三个层级：根 CA、中间 CA 和网站本身。
浏览器的逻辑：为什么要信任服务器的公钥？因为服务器呈递了中间 CA 签名的证书，证明中间 CA 信任服务器的公钥。为什么要信任中间 CA 的公钥？因为中间 CA 呈递了根 CA 签名的证书，证明根 CA 信任中间 CA 的公钥。我作为浏览器通过查询一个事先确定受信任的根 CA 列表来信任根 CA，根 CA 信任中间 CA，中间 CA 信任服务器，因此我信任服务器（的公钥，并用它加密后续与服务器的通信）。
TLS 证书和 HTTPS 协议
TLS 证书中包含了诸多信息，包括服务器的信息（网站的域名、网站所有者是谁、服务器的公钥）、证书颁发者的信息（颁发者是谁、证书有效期），和颁发者对上述信息的数字签名。然而，最重要的信息是域名和服务器公钥的对应关系：它能够防御域名劫持攻击。
即使攻击者制作了一个假冒的网站并劫持了域名，使得用户在浏览器中输入正确的域名来到了假冒的网站，假冒网站也无法呈递正确的TLS证书：要么试图自制证书，使用自己的服务器的公钥，但没有任何受信任的CA会对这个（公钥，域名）对签名；要么呈递真实网站的TLS证书，但针对这个证书里的公钥，攻击者没有对应的私钥，无法继续进行HTTPS协议（见下一段）。
HTTPS 协议围绕服务器返回的 TLS 证书展开。浏览器信任证书后，就会使用证书中包含的服务器公钥来加密一个预设密码，将密文发给服务器，服务器利用自己的私钥解密。这样，浏览器和服务器就同步了一个只有二者知道的预设密码，二者能够生成同一个对称密钥。之后，浏览器和服务器之间的 HTTP 通信都使用对称密钥加密，传输的是密文（HTTP传输的是明文），有效防止窃听和篡改。
Leave a Reply