一文弄懂HTTPS(I):密码学基础

大家一定在浏览器地址栏的前面见到过一把小锁。 safe icon

这把小锁代表着我们与服务器之间的通信是安全的。而安全背后的保障就是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$进行加密以及解密。符合双方用同一密钥加解密的算法称为对称加密。

当然现代对称加密方法肯定不会像凯撒密码那么简单,有兴趣可以参见对称加密算法或者密码学专业书籍。

对称加密具有运算快的特点,但是有一个严重的问题使得对称加密几乎无法单独使用:“双方如何通过不安全信道共享同一个密钥”。

非对称加密

天才总是那么牛逼。他们从数论中找到了一种方法,使得一方可以在不泄露密钥的情况下,让通信对方用一把公开的密钥实现单向的安全通信。这种方法的出现可以很好的解决上一个问题。

非对称加密的步骤是

  1. Bob持有一把公钥一把私钥。其中公钥是公开的,任何人都可以使用,私钥是保密的,绝对不能泄露;
  2. Alice想联系Bob,便使用Bob的公钥加密信息,然后通过不安全信道传递给Bob;
  3. 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密钥交换协议。过程如下。

  1. Alice与Bob同意使用一个质数$p$以及一个$p$的原根$a$;
  2. Alice选择一个随机数$k_1$,然后把$a^{k_1} \mod p$发送给Bob;
  3. Bob选择一个随机数$k_2$,然后把$a^{k_2} \mod p$发送给Alice;
  4. Alice计算$(a^{k_2})^{k_1} \mod p$;
  5. 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的客户端与服务器的通信流程。我们下期再见。。。