一文弄懂HTTPS（I）：密码学基础
大家一定在浏览器地址栏的前面见到过一把小锁。
这把小锁代表着我们与服务器之间的通信是安全的。而安全背后的保障就是HTTPS(HyperText Transfer Protocol Secure)。本系列文章将会从密码学背景开始，尝试去弄懂HTTPS背后的原理。（其实发现一篇文章的写太长了，才分P的，www）
¶为什么HTTPS保证了数据安全？
提到HTTPS之前，不得不说HTTP。大家都知道HTTP是明文传输的协议，在传输过程中，其中任何节点都可能窃听或者篡改原文而不被察觉。当不用HTTPS之前，有很多人的网站被运营商插进广告也是因为这个原因。
那么为什么HTTPS能够防止中间人窃听和篡改？一个肯定不会错的答案是，HTTPS在数据传输过程中对数据进行加密。加密后的数据（称为密文）只能由通信双方解密。
那么接下来问题可能接踵而至？如，为什么只能由双方解密？为什么中间人就解密不了呢?
当然，答案隐藏在加密算法本身——对称加密以及非对称加密。
¶加密算法
（以下部分内容可能比较数学化一点）。。 所谓加密算法，目的就是使得密文像垃圾数据一样。当数据到达之后，通信另外一方能够通过某种方式把这堆垃圾数据还原成原文。首先，我们先介绍对称加密。（这是一个很有历史的算法哦）
¶对称加密
如果需要保密，信中便用暗号，也即是改变字母顺序，使局外人无法组成一个单词。如果想要读懂和理解它们的意思，得用第4个字母置换第一个字母，即以D代A，余此类推。 苏维托尼乌斯, 罗马十二帝王传
远在两千多年以前，凯撒就已经使用了加密算法加密重要文件。这种加密方法叫凯撒密码，用数学公式定义如下
$$ E_n(x) = (x + n) \mod 26 \\ D_n(x) = (x - n) \mod 26 $$
其中$E_n$为加密方法，$D_n$为解密方法。
可以看见，要是安全通信成立，通信双方就$n$建立公式。双方同时使用$n$进行加密以及解密。符合双方用同一密钥加解密的算法称为对称加密。
当然现代对称加密方法肯定不会像凯撒密码那么简单，有兴趣可以参见对称加密算法或者密码学专业书籍。
对称加密具有运算快的特点，但是有一个严重的问题使得对称加密几乎无法单独使用：“双方如何通过不安全信道共享同一个密钥”。
¶非对称加密
天才总是那么牛逼。他们从数论中找到了一种方法，使得一方可以在不泄露密钥的情况下，让通信对方用一把公开的密钥实现单向的安全通信。这种方法的出现可以很好的解决上一个问题。
非对称加密的步骤是
- Bob持有一把公钥一把私钥。其中公钥是公开的，任何人都可以使用，私钥是保密的，绝对不能泄露；
- Alice想联系Bob，便使用Bob的公钥加密信息，然后通过不安全信道传递给Bob；
- Bob收到密文后，使用自己的私钥解密信息。
当然，光看上面的描述会感觉，这是什么和什么啊？为什么怎么做有效呢？我们用一个著名的非对称加密算法RSA作为例子。
¶RSA算法
RSA算法的名字以MIT的美国科学家Ron Rivest、Adi Shamir与Leonard Adleman的姓氏首字母构成。英国数学家Clifford Cocks也独立发现了这一算法。
首先，通信一方如Bob可以生成一个公钥$(n, e)$，其中$n = pq$，$p$，$q$分别是一个非常大的质数。$e$与$(p-1)(q-1)$互质。然后据此可以产生一把私钥$d$，是$e$关于$(p-1)(q-1)$的模反元素。模反元素就是说$de \equiv 1 \mod (p-1)(q-1)$。现在所有加解密要素都齐全了，Bob可以随意将公钥$(n, e)$散播出去。
¶加密过程
如果Alice要发送一份秘密的文件给Bob，首先Alice可以取得Bob散播的公钥$(n, e)$（公开的，怎么传都没关系）。然后设原文为$m, m < n$，如果原文$m > n$应该采取划分的方法产生若干满足小于条件的整数，为了简单起见，这里还是令$m$为处理后的原文。
加密过程很简单。。。Alice只需要进行下面的变换： $$ c \equiv m^e \mod n $$
然后把$c$传给Bob即可。
¶解密过程
Bob接到密文之后，进行下面的变换就可以解密： $$ m \equiv c^d \mod n $$
那么为什么呢？下面都是数学原理，如果不感兴趣的话可以跳过:
首先我们知道$c \equiv m^e \mod n$，则 $$ c^d \equiv m^{de} = m^{1 + k(p-1)(q-1)} \mod n $$
其中$k$为任意整数，等号的变换是因为$de \equiv 1 \mod (p-1)(q-1)$。 据费马小定理：
费马小定理： 如果$a$不是$p$的倍数，则$a^{p-1} \equiv 1 \mod p$。
$$ c \equiv m \cdot (m^{p-1})^{k(q-1)} = m \cdot 1 \mod p \\ c \equiv m \cdot (m^{q-1})^{k(p-1)} = m \cdot 1 \mod q $$
又因为$gcd(p, q) = 1$，由中国剩余定理有：
$$ c^d \equiv m \mod pq $$
因此，可以使用上面提到的解密算法解密。
¶安全保证
为什么说RSA能够保证传输安全呢？注意到解密需要私钥$d$。求$d$最简单的方法是已知$p, q$用定义式去求。已知公钥$n, e$，其中$n = pq$。那么要求$p, q$，攻击者需要对$n$做分解。这个在多项式时间不能解决。
当然，随着计算力的发展，较低数位的RSA已经被证实可以破解。因此，实用的RSA的话$n$至少要在2048位。
¶数字签名
非对称加密除了用来加密信息，反向利用也可以用来验证一个信息是否由指定实体发送。比如Bob用自己的私钥加密一段信息，然后将这段信息和密文发送给Alice，Alice如果可以使用Bob的公钥把密文还原成信息原文比对，就可以确定这段信息由Bob发送。这个会在下一篇文章介绍。
¶非对称加密的劣势
非对称加密对于对称加密的劣势在于加解密的速度较慢。因此，在实际使用的时候，我们总是配合非对称加密与对称加密使用。非对称加密可以用来交换对称加密使用的密钥。
¶密钥交换
现在我们来看一看如何安全地共享同一把密钥，典型的协议是Diffie-Hellman密钥交换协议。过程如下。
- Alice与Bob同意使用一个质数$p$以及一个$p$的原根$a$；
- Alice选择一个随机数$k_1$，然后把$a^{k_1} \mod p$发送给Bob；
- Bob选择一个随机数$k_2$，然后把$a^{k_2} \mod p$发送给Alice；
- Alice计算$(a^{k_2})^{k_1} \mod p$；
- Bob计算$(a^{k_1})^{k_2} \mod p$;
因为$(a^{k_1})^{k_2} \mod p = (a^{k_2})^{k_1} \mod p$，可以作为对称加密密钥。
¶中间人攻击
但是上述交换协议有一个非常大的弱点。假设有一个中间人Eve在窃听Alice与Bob之间的通信，他可以与双方分别进行一次D-H密钥交换，从而获取整条信道的信息。Alice与Bob不会察觉到中间人的存在。
上述问题的核心在于确定一个实体的公钥是否是可信的公钥。因此，HTTPS建立了所谓了公开密钥认证体系。这一个我们下一篇文章再谈（太长了。。。）
¶总结
这一篇文章严格上没有介绍HTTPS，但是了解了这些基础知识。下面真正见到HTTPS时就会有种的熟悉感。接下来一篇文章大概会介绍HTTPS的客户端与服务器的通信流程。我们下期再见。。。