HTTPS与P=NP问题卍解（演讲）

最近做了个技术分享公开课，把演讲的ppt和现场说过的内容原封不动的copy下来。。。

这篇文章将从HTTPS的基本原理讲起，不同的是，“这里不讲技术，只谈思想”。我不会去讲https以及RSA是怎么计算的，而是谈谈https背后的一些“自然哲学的数学原理”，这样也符合我一贯的写作风格。

HTTPS卍解

首先是https的历史背景：协议栈收敛。

很久以前流行过一个概念：OSI参考模型。这个模型定义了2点之间通讯所经过的7层协议栈，后来人们发现，7层太多了，不需要那么多层，更可气的是，不仅没用的栈有那么多层，该有的协议层偏偏没有，比如专门为安全服务的协议层（后来这一层发展成了SSL）OSI就没有。

许多年以前互联网是非常畸形的，人们喜欢在应用层使用明文传输的http，为了安全就把所有的数据加密任务放在了网络层！人们企图利用tcp/ip本身自带的加密和认证功能保障网络安全。这种做法显然是很懒的，因为这种情况下网络层到应用层之间的若干层都成了黑客可能的攻击目标。

栈顶加密

后来应用层也开始加密了，再后来人们发现一个天大的秘密，网络层根本不用加密！因为只要在协议栈的栈顶加密就足够了，栈顶向下的所有数据都处于密文状态，所以关于机密有且仅需要一层，而且这层是栈顶。

所以在这个趋势之下，网络层开始收敛，保障网络安全的责任由网络层转向了应用层。与此同时，原来的“传输层”也开始收敛。

TCP即将淘汰？

TCP协议提供了2个重要的功能分别是数据包确认机制和长连接。其中数据包确认机制保障了网络的可靠性，长连接为应用层提供了服务。但后来人们逐渐发现，网络可靠性根本不需保护，即使发生了类似掉包的现象，应用层的校验技术也能检测出来，然后重传就行了，况且在5G时代网络可靠性早已不成问题。应用层还在尝试着自建长连接，从而摆脱对TCP的依赖。传输层收敛的趋势导致TCP有可能被UDP取代。关于TCP被淘汰的原因可以参考我的另一篇文章：

https://jimmy.blog.csdn.net/article/details/93710140

4层协议栈模型

随着网络层和传输层的任务都渐渐转移到应用层上，https认为，整个协议栈只需要4层就足够了，从底向上分别是：物理层，网络层，安全层，应用层。

协议栈收敛的趋势直接导致了网络层和应用层之间的矛盾，具体点来说是http与电信之间的矛盾。

以前，运营商ISP（包括电信，移动，联通）销售网络层的各种服务，从dns，V**到网络安全，甚至大中华敏感词过滤系统。我们也要花钱去买那些服务，但现在协议栈收敛以后，大部分任务都由应用层的http(s)来完成了，电信给我们提供的服务也只剩下“数据包转发”了，我们向运营商购买的服务就是一种“物理线路的使用权”。电信无需再承担保障网络安全的责任了，自然也可以肆无忌惮的对我们的数据包发动攻击，而且我们根本无法察觉。

在极端的危险环境下实现极度的安全

对此https的设计者胸有成竹，他们把运营商想象成邪恶的黑客，黑客帮我们转发数据包，https的设计目标很简单：在这样一个极度危险的互联网上，实现极度的安全！

委员会的考虑非常简单：世界上任意2台设备通讯，其中一台设备将编好的二进制信号发出网线之后，这些数据可以任人宰割，宰割的手段无非分为3类：读，写，执行。

对数据的基本操作：读，写，执行。

只要从这3个方面防住黑客就能实现“极度的安全”。很明显，“执行”是没有任何危险的，因为没有黑客会无聊到把你的数据放到自己的电脑上执行一遍，所以“执行”的角度没有任何危险，那接下来只要考虑“读”和“写”就行了。

如何防止数据被读只要对数据进行加密就行了，防止数据被写则主要要实现认证。经常听到另一个概念叫做“数据完整性保护”，其实完整性保护也属于认证，因为只要数据被篡改，数据的原作者就已经从发送方变成黑客了。

综上所述，想要实现https，就是要保证数据传输过程中“读”和“写”的安全。这个目标看似非常艰巨：想要在如此危险的传输介质上实现100%安全（准确点说是99.99...%的安全）几乎不可能。但仔细想一想，其实非常容易，因为我们常常忽略了一个简单的安全事实。

对称加密就能实现HTTPS

对称加密就能实现https所渴望的加密和认证。不信可以做一个简单的思想实验：你和朋友用微信传文件，文件使用一个只有你和朋友知道的足够复杂的密码来对称加密，比如“s734@gsee%$4rhsd.90sd。。。。”，在这种情况下，即使是最拽的黑客也没办法破解你们的数据，不是吗？

对称加密不仅能防止数据被读，还能防止被写，因为现代的对称加密算法的大致运算步骤都是多轮循环的迭代位移，这一类算法会导致原始数据中每一个bit的位置完全被打乱。所以只要数据被篡改哪怕1个bit，最终解密出来的结果都会是一堆乱码，从而认证失败，当然，通过乱码来认证是人的主观感受，对于机器来说需要使用一个摘要值来认证：将原始数据的摘要值作为数据的一部分，再对整体加密，这样如果数据被“写”，最终解密出来后数据的校验一定会失败。

因此，这个思想实验证明了对称加密能初步实现https的目标，事实上，我们在浏览https网页的时候，所有网站内容都是对称加密的，并没有使用公钥和私钥，因为对称加密就足够安全了。当然这个“足够”得排除掉其他极端的因素，比如“社会工程学”的攻击。

但为什么https还需要不对称加密呢，因为使用对称加密来通讯的重要前提是，安全的密码交换。如果密码交换的过程本身就不安全，之后的一切都是扯淡。而想要安全的交换密码只有一种途径：私下交换！

更准确的说是，通过别的安全通道交换密码。最常见的一种办法就是两人面对面交换密码，这样万无一失。还有一种方式是“间接交换”，这种方式指的是我们在买电脑的时候，操作系统厂商可以在电脑中内置一些密码，内置的过程保证了安全，我们买电脑的过程也保证了安全，这样就间接实现了安全交换。事实上间接交换模式使用的非常频繁，我们再做一个思想实验：

间接交换凭证

假如谷歌公司在他们的pixel系列的每一部手机上内置一份密码，自己也保存一份，当用户买到手机后，就用这个密码来访问google.com，google.com也用这个密码来返回数据，这样确实间接实现了https的目标。显然真实情况下没人这么玩。这里只是论证间接交换的可行性。

还有一种模式是通过已经建立好的https通道来为其他人交换密码，当然这就是个先生鸡还是先生蛋的问题了。

所以，讨论了私下交换的几种安全方式，接下来就来设计https啦，很显然接下来提出的方案一就是：私下交换对称密码。

对于这个方案有许多实现手段，首先根据之前“间接交换”的可行性，可以设计在操作系统中内置对称密码的方案。不用多想，这个方案是行不通的，原因是密码数量过多无法维护：理论上n台机器两两交换密对称码总共需要存储C(n,2)份密码，这个排列组合数的增长趋势是n的平方，这种趋势是无法接受的，我们不可能在全世界每一台电脑上面预置每一个网站的密码。况且如果有新的网站出现了，难道还需要我们跑去手机专卖店更新密码吗？

TOFU原则

另一种想得到的手段是利用TOFU原则。TOFU指首次信任原则（trust on first use）：人们找到了一个偷懒的交换密码的方式，希望2台机器首次交流的时候就赶紧协商密码，然后用这个密码建立长连接，这样如果黑客错过了交换密码的那一瞬间，以后就再也没有机会攻击了。

很显然，利用TOFU原则交换密码本身就是一种侥幸心理，万一黑客就一直伏击在你们之间等待着TOFU呢？其次维护长连接也是消耗资源的。

存在100%的安全吗？

方案一还有一个缺点，就是世界上没有100%的安全，任何信息只要经过不安全的信道传输就有可能泄露，唯一绝对意义上安全的办法是将密码永远存放在本地硬盘，永生不参与网络传输，人们给这个假想中的不用参与和外界进行物质交互的密钥取了个名字叫私人密钥，简称“私钥”，至于私钥那时存不存在，人们还在寻找中。。。

但无论如何，私下交换对称密码的方案被https委员会否决了，但这个方案本身并没有淘汰，因为它仍然适用于各种长连接的场景，就比如之前的“加密文件”的思想实验，以及一些小的团体，比如部队里用于对自己人认证使用的“口令”，其实cookie和用户账户都是通过私下交换密码来实现长连接的。

此方案之所以不适用于https，主要还是由对称加密的固有属性导致的，即“完全对称”：数据的加密和解密过程拥有相同的时间复杂度。那有没有一种不对称的加密算法呢，即加密和解密的过程需要不同的时间复杂度，最好是解密的复杂度远远比加密的复杂度高？最后一句话让数学家们恍然大悟地想到了一类问题：NP问题。

数学研究的是时间与空间的关系

什么是NP问题？简单的说，在NP问题中，你只需要花一点点的空间成本就能让对方损失巨量的时间成本。NP问题还有一个特点就是，验证某一个NP问题特定的解只需要花费多项式的时间复杂度，这种复杂度的问题我们称之为P类问题。想到这儿，数学家们意识到，可以利用NP问题的固有性质来设计一套不对称加密算法：将抛出NP问题的过程作为公钥加密的过程，将验证NP特定解的过程作为私钥解密的过程，将NP问题本身的不确定性解法作为黑客可能尝试的暴力破解的过程。这样一来，NP问题刚好满足了不对称加密的3个基本条件，完美！

曾经虐了数学家几十年的NP问题现在终于能拿来利用了，数学家很开心，与此同时，无数个NP问题浮出水面，其中最经典的就是质因数分解问题，质因数分解的时间复杂度是一个指数，通常是O(e^n)，指数是数学里的魔鬼，随着空间增长而增长的速度远远超过多项式复杂度问题（P类问题），于是根据质因数分解，RSA算法诞生。

RSA是最常用的不对称加密算法，遵守“不讲技术”的原则，本文不探讨RSA的计算和证明过程，只要知道它是不对称加密的就好。不对称加密首先带来的好处就是，可以实现秘钥的复用。原来说过，对称加密理论上需要C(n,2)=n(n-1)/2份密码，但在不对称加密体系中，每台设备只要保存自己的公钥和私钥就行了，n台机器总共需要2n份密码。

不对称加密的好处远不止空间效率，还可以应用双层加密来取代摘要值：原先对称加密为了保护数据的“写”，需要利用摘要值来认证，但现在只要用对方的公钥来加密一层，再用自己的私钥加密第二层，第一层加密是为了保护“读”，第二层加密是为了保护“写”。

有了不对称加密算法RSA，设计https的难度大大降低了，很快第二条方案出台。

在方案一的基础上改进之后，由私下交换对称密码变成了私下交换公钥，为啥说https设计难度大大降低了呢？因为我们现在可以正大光明的交换公钥了：原先交换对称密码的时候既要保护“读”也要保护“写”，但是现在交换公钥只要保护“写”，因为公钥本身就是需要被扩散的。

遗憾的是，https仍然没有采用这个提案。

这个方案倒是成就了SSH：我们在用ssh连接github或者gitlab的时候不是要提前在它们的网站上手动提交自己的公钥嘛？这个过程就是一个私下交换公钥的过程。但也正是这个原因导致https没有采用方案二，因为私下交换仍然是一个手动的过程，对于一个希望在互联网上普遍适用的协议来说，需要一个自动化的机制来拯救一切。想要实现自动化就需要一个统一的安全通道来交换公钥，基于这个设想，历史上出现过一个昙花一现的备选方案：第三方公钥解析服务器。

异想天开的公钥解析服务器

当时委员会的脑回路是这样的：我们建立一个统一的第三方见证人，称之为CA（认证机构），这个见证人是一台存放着世界上所有网站公钥的服务器，就像DNS服务器一样存放着所有网站的ip地址，而且像dns或cdn服务器一样分布在世界各地，用户每次访问网站之前都要像请求域名解析一样请求一遍公钥解析，借此完成交换。

果然人类一思考上帝就发笑，公钥解析服务器方案又碰到了先有鸡还是先有蛋的瓶颈：请求公钥过程本身就要基于https或者说ssl来确保安全，否则后来的一切加密和认证都是扯淡。另一方面，请求公钥的过程破坏了点到点通讯的原则：每次访问网页都要从公钥服务器那走一趟很不合理。

第三方公证人

最终方案二也失败了，但是这个公钥解析服务器方案倒是给后面将要发生的事带来了一个重要思想：第三方。第三方公证人这个认证角色还是很必要的，终于人们想到了一个终极概念：证书。

如果存在证书，就可以用证书来交换公钥啊！什么是证书呢？证书是认证的终极手段，因为只有证书能够在第三方见证人不在场的情况下实现点到点的直接认证。上面这句话什么意思呢，可以想象生活中的证书，比如我的毕业证书：假如我将毕业证书拿到我妈眼前，她肯定直接相信我毕业了，不会说专门打电话给我的学习去核实情况，从而完成了对我的直接认证，但这一切都要基于一个事实，那就是我没有能力去伪造这样一份证书，而证书的作者一定是我的学校。

再类比到证书交换公钥的场景，就是比如你想访问google.com，你希望在通讯前先给你一份证书，这个证书需要满足2个条件：首先证书的作者必须是第三方公证人CA，其次谷歌没有能力伪造一份这样的证书。在软件中证书就是一段数据，一段话，那怎样的一段话只有CA能够说得出口，其他任何人都说不出口呢？答案显而易见了：当然是用CA自己的私钥加密后的数据没有任何人能够伪造。

终于到了设计https的最后一步，如何维护这样一个CA呢？和电信运营商不同，CA是需要被所有人信任的，这就意味着它必须被所有人监督，那么CA的数量就必须很少，几家甚至一家就够了。但最重要的问题是，CA的公钥该如何安全的给到我们呢？这又扯到了交换公钥的问题，最后发现只有一种办法能实现，就是之前提过的“间接交换”：在所有的操作系统中内置CA的公钥（顶级证书）。

这个证书中写着什么内容呢？大致就是google.com的公钥是balabala...，有效期到什么时候，以及我是谁。然后浏览器会瞟一眼你的地址栏中是否是google.com这个域名，如果是的话就会出现安全锁的标志，否则就出出现红色危险标志，再之后你和google.com会利用当前的不对称连接协商一份对称加密的密码，然后建立一个安全的对称连接，从而实现文章刚开始说的“极度安全”，至此https开发完成，方案三“证书交换公钥”完美的通过了委员会的投票，https诞生了。

由此可以看出，https从根源上就就保证了数据的安全，协议栈上唯一可能被攻击的地方只剩下应用层了，最终保护网络安全问题最终聚焦到该如何设计应用层，历经15年的变革，协议栈终于收敛完成，HTTPS卍解！

最后来几个科普。

单向认证

前面提到TOFU概念是在方案一“私下交换密码”，其中有一种省时省力的方式是通过首次通讯时的无条件信任来实现密码交换，但TOFU暴露出来的危险也显而易见，就是无条件信任的过程不安全。由于IPv6尚未普及，并不是每台机器都拥有ip地址和域名，所以并不是每台机器都拥有证书，现在的情况是，利用NAT来实现将多台机器虚拟成一台机器的虚拟化技术仍在使用，技术对所有公网ip颁发证书，NAT局域网内部仍然不安全。所以https甚至是ssh都选择了利用tofu来兼容IPv4，表现出来的事实就是单向认证，即只有一方的公钥安全的传递到对端，反之则不然（理论上不安全）。比如google.com的公钥可以通过CA证书安全的传递到我的电脑，但我的公钥却无法绝对安全的到达google.com。

但既然这只是一个科普，并没有放在正文中，说明TOFU漏洞并不重要，事实上它造成的危险程度极小，微不足道，具体原因可以参考我的这篇文章：

https://jimmy.blog.csdn.net/article/details/90544542

第二个科普是关于可怕的P=NP问题。

计算框架

之前说过，NP问题的存在是不对称加密算法的前提的前提，没有NP问题就没有RSA和https。虽然广大数学家都认为P≠NP，但我个人认为P是可以等于NP的，这涉及到计算框架的问题。

我们的理论计算机以及整个现代数学都限制在一个叫做“经典计算”的计算框架内，经典计算的所有计算成本都基于加法运算来实现原始增长，我们人类的计算思维也被死死的限制在经典计算框架之内。

但是世界上还存在着其他的计算框架，比如“量子计算”：量子计算可以通过量子比特的叠加态来实现并行计算。

还有人脑的计算框架。大脑是如何计算的一直是个谜，所以我们称这个计算框架为“智能计算”，图中的问号就代表了未知。但是有迹象表明智能计算是客观存在的，我们再做最后一个思想实验：

有一些常见的NP问题甚至是NPC问题（NPC是一类更难的NP问题）比如扫雷，俄罗斯方块还有推箱子，这些问题只要规模稍微大一点，经典计算机就要花上万年甚至可能上百万年来解决它，而让人来做的话有时候那个人灵光一闪就可以在瞬间找出眼前NP问题的解，甚至是最优解！这是很可怕的一个事情，鬼知道大脑在那灵感的一瞬间发生了怎样惊人的计算？所以与其相信奇迹，还不如相信智能计算是真实存在的。

P=NP的简单证明

前面提到的RSA所依赖的质因数分解问题之所以是一个NP问题只是由于它在经典计算框架之下感觉像一个NP，假设存在一个质因数分解的通用公式，那这个公式长成什么样子呢？可以想象，这个公式里无非就是一些加减乘除，幂，甚至超运算，以及一系列已知的经典运算符号。但如果质因数分解本身就不符合经典计算的规律，而是符合比如量子计算，那那个公式里就会出现一些人类目前还没发现的运算符号。总之，我认为NP问题并不是没有确定解法，而是我们在“经典计算”的思想钢印中看不到那个最优解而已。

。。。

以上关于对P=NP的证明纯属个人意淫，毫无科学依据，阅读完即可忘。

最后一个科普是对全文的一个总结。

为什么总是感觉电脑病毒很危险，网络攻击很可怕？其实害怕是毫无理由的，因为只要养成良好的电脑使用习惯和上网习惯，几乎不会受到任何攻击。通过今天的学习，我们可以意识到，要坚持上https的网站，拒绝访问http网站。

还要谨慎沙盒之外的“执行”操作

文章刚开始就提到了，对文件的操作无非就3种：读，写，执行。对于从互联网下载文件本身没有任何危险，对这个文件的读和写也绝对安全，唯一需要提防的是文件的“执行”操作，如果不是在浏览器这样的沙盒环境之内，千万不要随便执行文件，即使中招的可能很小，但从理论上不能保证绝对安全的操作最好不要做。

社会工程学

最后还要增强社会工程学的防范意识。社会工程学这个学科被划分到计算机行业是一件很尴尬的事情，我们也不得不面对它，关于社工也没啥好说的，主要增强防范意识，谨防上当受骗就好。

其实随着Web平台的发展，当web平台发展到彻底成熟的阶段，那时候所有的网站都强制使用https，那时候浏览器也许成为桌面上唯一一个app，那时候唯一需要加强安全意识的也就剩下社会工程学了。

我们应该感到庆幸，本世纪的计算机给我们提供了一个如此安全的浏览器沙盒环境，还赠送了一个如此完美的HTTPS协议，互联网在绝大多数情况下是非常非常安全和舒适的。

（完）