阅读 2457

RSA初探,聊聊怎么破解HTTPS

这篇文章跟大家讨论一个比较有意思的问题:怎么破解https?大家都知道,现在几乎整个互联网都采用了https,不是https的网站某些浏览器还会给出警告。面试中也经常问到https,本文会深入https原理,一直讲到https破解思路。

HTTPS

要想破解https,必须先知道https原理,下面我们先来讲讲https原理。

公私钥

https的公私钥经常在面试中出现,各种面经也会给出答案:https有两个秘钥,公钥和私钥,网站自己持有私钥,用户持有公钥,网站用自己的私钥加密数据发给用户,用户用公钥解密数据。用户要发信息就反过来,用户用公钥加密数据,网站用私钥解密数据。这种加密和解密使用不同秘钥的加密算法叫做非对称加密。这个流程有点绕,下面举例来说明下,假设网站A启用了https,小明要来访问这个网站了(以下例子仅为讲解公私钥用途,并非https真实流程,真实流程是后面“HTTPS握手流程”一节):

  1. 网站A启用https,自然有一对秘钥,私钥和公钥,私钥他自己藏起来了,公钥任何访问用户都可以拿到
  2. 小明访问网站A,拿到了A的公钥
  3. 小明要给网站A发消息就用公钥给信息加密,然后发给网站A
  4. 网站A拿到密文后,用自己的私钥解密得到消息内容
  5. 网站A要给小明回信,用自己的私钥加密信息,发送给小明
  6. 小明拿到密文后,用自己手上的公钥解密信息

通过上面的流程我们可以看出,由于公钥是公开的,所以网站私钥加密的信息其实所有用户都可以解开。在这一个阶段,保护的其实是用户发给服务器的数据,因为用户加密的数据必须要服务器的私钥才能解开。这里大家想一个有意思的问题:既然所有用户都能拿到公钥,那是不是小明加密的信息,小红也能解开呢,因为小红也有公钥啊?如果小红也能解开,那小红只要截获了小明的流量,不就知道内容了吗?这个问题简化一下就是,公钥加密的信息用同一个公钥能解开吗?答案是不能!要知道这个原因必须要知道RSA算法,我们后面会讲,先一步步来。

数字证书

前面小明访问网站A的流程是有隐患,可以被攻击的。假设小红是个中间人黑客,现在想攻击小明,她偷偷在小明电脑上做了手脚,将网站A的公钥换成了自己的:

  1. 小明访问网站A,网站A给小明发送公钥,但是这一步被小红攻击了
  2. 小红劫持了小明的流量,将网站A发过来的公钥替换成了自己的公钥
  3. 小明拿到了错误的公钥,用这个公钥加密自己的信息,这个信息可能包含他的用户名,密码等敏感信息
  4. 小明将加密信息发送给网站A,这个流量被小红截获
  5. 因为密文是用小红的公钥加密的,小红用对应的私钥解密,得到小明的密码,攻击完成

可以看到仅仅是公私钥还是不能应对中间人的流量劫持,传输过程中信息被截获仍然会被破解。这个攻击能成功的关键点就是小明拿到了错误的公钥,所以需要一种机制来保证小明拿到正确的网站A公钥,这个机制就是数字证书。数字证书说开了很简单,他里面核心东西就一个,就是网站A的公钥。网站A将自己的公钥放到数字证书里面发送给小明,小明一看,这个公钥是证书认证的,可信,就用这个了。即使小红替换了公钥,因为小红的公钥没有证书认证,所以小明也可以识别出这个假冒货。

那数字证书的安全性又是怎么保证的呢,小红再伪造一个数字证书不就行了吗?这就要说到CA(CertificateAuthority)了,CA是颁发数字证书的机构,CA有自己的公私钥。CA用自己的私钥加密一个信息,这个信息就是网站A的公钥,然后发送给用户,用户拿到这个信息用CA的公钥解密,就拿到了正确的网站A的公钥了。所以,数字证书其实就是CA私钥加密过的网站公钥。小红没有CA的私钥,她就伪造不出来网站的数字证书了,也就没法替换小明拿到的公钥了。所以,数字证书其实保证了网站公钥的正确性,CA保证了数字证书的安全性

既然CA保证了数字证书的安全性,那谁来保证CA的安全性呢?假设有个东西X保证了CA的安全性,那谁来保证X的安全性呢?感觉这个信任链条可以无穷尽呢。。。现实中,CA的安全级别非常高,他的安全不仅仅有技术手段,还有法律,物理措施等。反过来说,回到本文的主题,破解https,到这里我们其实有了第一个思路:黑掉CA!你就可以将它名下所有证书的公钥都替换成自己的,解密使用他证书的所有网站。

评论区有朋友提到,Charles可以解密https,这个原理不就跟小红攻击小明的原理一样嘛。Charles解密https的前提是你要安装他的证书,安装了他的证书,你其实就相当于信任了Charles这个假的CA。攻击流程将前面的小红换成Charles就行了。

会话秘钥

公私钥的加密解密确实很安全,但是他的速度很慢,如果每条信息都这么操作,会影响整个交流效率,所以当我们跟https建立连接后,通过公私钥交换的信息其实只有一个:会话秘钥。会话秘钥不是非对称加密,而是对称加密。对称加密在某些影视作品中很常见:某主人公得到一个藏宝图,苦于藏宝图是密码写的,看不懂,百般无奈下,想起祖传的某某书籍,拿到一对照,那本书刚好可以解密藏宝图密码。那这本书其实就是密码本,二战中很多信息加密就用的密码本的方式,通过截获密码本获取对方军事情报的事情也不少。加密解密都用密码本,其实就是用了同一个秘钥,这就是对称加密。用计算机领域的话来说,这个密码本不就是一个hash函数嘛,这个函数将一个字符映射成另外一个字符。举个例子,我们加密的hash函数就是将字符后移三位,a -> d, b -> e 这种,那"hello"就变成了:

h -> k

e -> h

l -> o

l -> o

o -> r

"hello"就变成了"khoor",那攻击者只要知道了你这个算法,再反算回来,前移三位就解密了。所以对称加密相对来说并不安全,但是,如果我能保证他的密码本(也就是秘钥)是安全的,对称加密也可以是安全的。那对称加密的秘钥怎么保证安全呢?用公私钥再加一次密啊!所以https连接后,公私钥交换的信息只有一个,那就是对称加密秘钥,也就是会话秘钥。对称加密的算法就是一个hash函数,加密解密相对更快,这种设计是从效率的角度考虑的。

数字签名

数字签名其实很简单,是用来保障信息的完整性和正确性的:

  1. 小明先将明文信息用摘要算法生成一个摘要,这个算法类似于MD5,SHA-1,SHA-2,就是一个不能反解的hash函数
  2. 小明用公钥对这个摘要进行加密
  3. 小明将这个签名附加在内容后面一起发给服务端
  4. 服务端接收到签名后,用私钥解密出摘要
  5. 服务端对内容进行同样的摘要算法,得出摘要
  6. 服务端算出的摘要如果跟签名里面的一样,则内容完整,没有被篡改

HTTPS握手流程

前面几个知识点其实已经把https的关键点都讲了,下面我们来总结下https握手流程:

  1. 小明向网站A发起请求
  2. 网站A将CA数字证书返回给客户端,证书里面有网站A的公钥
  3. 小明通过自己电脑内置的CA公钥解密证书,拿到网站A的公钥(CA公钥内置在浏览器中)
  4. 小明生成随机的对称秘钥,也就是会话秘钥。会话秘钥一定要客户端生成,因为前面说了,这里公私钥只能保证客户端发给网站信息的安全,公钥加密的信息只有私钥才能解开,私钥网站藏起来了,所以其他人拿到信息也解不开。但是如果网站生成会话秘钥,用他的私钥加密,那所有人都有公钥,所有人都能解开了。
  5. 小明将会话秘钥通过网站A的公钥加密,发送给网站A
  6. 接下来网站A和小明使用会话秘钥进行HTTP通信

RSA算法

前面我们提到过公钥加密的信息用同一个公钥也解不开,只能用私钥解密,这其实就是非对称加密的核心机密,下面我们来讲讲这个机密是怎么做到的,这其实就是RSA算法。RSA算法计算流程如下:

  1. 随机选取两个质数p和q
  2. 计算 n = pq
  3. 计算 φ(n) = (p-1)(q-1)
  4. 找一个与φ(n)互质的小奇数e,互质是指两个数的公约数只有1
  5. 对模φ(n),计算e的乘法逆元d,即找到一个d,使下列等式成立:(e*d) mod φ(n) = 1
  6. 得到公钥:(e, n),私钥: (d, n)
  7. 加密过程:c = (m^e) mod n, (c为加密后的密文,m为原文)
  8. 解密过程:m = (c^d) mod n

第七步说明下,m的e次方,m就是我们发送的原文,可以是文本,json,图片,虽然形式多样,但是在计算机里面都是二进制01,所以可以转换成数字求次方。下面我们找两个数来试一下这个算法:

  1. 随便选两个质数23和61
  2. 计算 n = 23 * 61 = 1403
  3. 计算 φ(n) = (23-1) * (61-1) = 22 * 60 = 1320
  4. 找一个与φ(n)互质的小奇数e,我们选7
  5. 计算乘法逆元d,我这里算好的是 d =943。对乘法逆元感兴趣的朋友可以网上搜搜怎么算,因为不是本文主题,我就不展开了。
  6. 得到公钥(7, 1403),私钥(943, 1403)
  7. 我们用公钥随便加密一个5试试,加密 c = (m^e) mod n = (5^7) % 1403 = 78125 % 1403 = 960
  8. 私钥解密: m = (c^d) mod n = (960^943) % 1403 = 5,(960^943)这个数字超级大,一般计算器算不出来,JS计算更不行,我是用这个网站算的:defuse.ca/big-number-…
  9. 再试试私钥加密:c = (m^d) mod n = (5^943) % 1403 = 283
  10. 公钥解密: m = (c^e) mod n = (283 ^ 7) % 1403 = 5

知道了算法,我们就可以来解答前面的那个问题了,为什么公钥自己加密的数据自己还解不出来?注意看加密算法(m^e) mod n这是个模运算啊,模运算是不能反解的。比如5对4取模,5%4=1,但是反过来,知道x%4=1,求x。这个x可以有无限个,5,9,13,17。。。所以即使你有公钥(e,n),和密文c,你也不知道(m^e)到底取哪个值,是反解不出来的,这就是非对称加密的核心机密,私钥加密同理,自己加密的自己也反解不出来。

RSA破解思路

所谓破解RSA,其实就是通过公开的信息推测出他藏起来的信息,具体来说就是已知公钥(e, n)求私钥(d,n),也就是求d。要求d,其实就是反解(e*d) mod φ(n) = 1,要反解这个式子,就必须知道φ(n),因为φ(n) = (p-1)(q-1),所以必须知道p和q。我们知道n=pq,而且n是已知的,所以还是有可能知道p和q的。所以破解RSA其实就是一句话:n是已知的,将n拆成两个质数之积就行了。说起来简单,做起来非常难!因为实际使用时,n非常大,现在好多地方用的n都是2048 bits甚至4096 bits,这个数字转换成十进制也有几百位上千位长,做个对比,JS整数最多支持53 bits。。。所以现实中有两条路来破解RSA:

  1. 找出一个算法,能够高效的将大数n拆分成两个质数。可惜目前数学界也还没找到这个算法。
  2. 没有好办法就用笨办法,穷举,从2开始遍历p, q,直到他们的乘积为n为止。据说有人花了5个月时间算出了一个512 bits的n,然后人家早就换了秘钥,RSA还升级到了1024 bits...

总结

  1. HTTPS其实就是HTTP+RSA+数字证书+会话秘钥
  2. RSA实现了非对称加密,可以让公钥任意分发,私钥即使丢失了,也可以迅速换一对公私钥。解决了对称加密密码本的漏洞。
  3. 数字证书保证了分发的公钥不能被篡改。
  4. CA保证了数字证书的安全性。
  5. CA的安全性由谁保证是个玄学
  6. 会话秘钥是对称加密,目的是为了加快加密解密速度
  7. RSA算法精髓:
    1. 加密使用模运算,完全不能反解
    2. n取一个超大数,超出了数学界理论极限和计算机的工业极限
  8. 破解HTTPS三条路:
    1. 黑掉CA,将它名下证书的公钥都换成你的,方法勿论。。。
    2. 数学之神附体,找到高效大数分解算法,分分钟算出p,q
    3. 图灵附体,研发出超快的量子计算机,秒秒钟算出p,q
  9. 自己网站没开https的赶紧回去开,记得找个靠谱的CA买证书。

文章的最后,感谢你花费宝贵的时间阅读本文,如果本文给了你一点点帮助或者启发,请不要吝啬你的赞和GitHub小星星,你的支持是作者持续创作的动力。

作者博文GitHub项目地址: github.com/dennis-jian…

作者掘金文章汇总:juejin.im/post/5e3ffc…


关注下面的标签,发现更多相似文章
评论