密码学(Cryptography)简史–后量子计算机时代你的数据还安全吗

最近可能大家也看到了一些关于量子计算机进展的新闻，比如Google 推出「量子迴聲」算法，量子计算机实际应用里程碑

  • https://blog.google/intl/zh-tw/company-news/technology/quantum-echoes-willow-verifiable-quantum-advantage/

当看到这些新闻的时候，你是否心里再想真厉害，量子计算机能够实现指数级的运算速度的提升。

所以呢，人类最近一直在想办法解决量子计算机发展对加密算法的威胁。

但量子计算机对哪些加密算法有威胁呢？估计没有多少人能说的清楚。

首先我们要知道量子计算机和传统计算机不一样，计算速度能够指数级提升，那对于破解我们现在的加密算法，是否也能指数级提升？

要回答这个问题，我们要一步步展开讲。

对称加密和非对称加密

我们先要有个概念，我们加密算法一般分为对称加密和非对称加密，使用的原理不一样，具体操作过程先放到一边。

对称加密，比如AES，基于各种替换转换操作(SPN)

  • AES – ECB
  • AES – CBC
  • AES – CTR
  • AES – GCM

非对称加密，比如

  • RSA， 数学原理基于大整数的因式分解
  • DH，基于离散对数难解问题(DLP)
  • ECC，基于椭圆曲线难解问题

所以非对称加密算法基本都是基于一些难解的数学问题，而刚好这些问题有可能被某些量子计算机算法破解。

Shor算法

Shor算法，详见维斯百科，1994年发明

  • https://en.wikipedia.org/wiki/Shor%27s_algorithm

我们都说量子计算机对加密算法有威胁，这个威胁其实就是来自于Shor算法。

具体的算过程我也看不懂，但简单来说这个算法可以在量子计算机上快速计算大整数的因式分解，也就是RSA基于的两个大整数(质数)p, q相乘得到N = p * q, 当知道N的情况下无法推导出p, …

密码学(Cryptography)简史-非对称加秘(Asymmetric Encryption)

之前讲过对称加密，比如DES, AES, 还有AES对应到的各种模式，比如ECB, CBC, CTR, GCM.

对称加密唯一保密的就是密钥(Key), 有了这个密码你就能解密其中的内容。

公开通信信道(Channel)

数字世界中的通信信道其实可以类比真实物理世界， 我们要从上海到北京就要经常各种各样的道路，比如走高速公路，就可能要经常各种检查站，收费站，理论上这些站点都可以对你的车进行全方位的搜索检查，看有没有携带违禁品。互联网世界一样，你的数据要经常中间的各种Wifi, 路由，网关，光纤，每个路由网关理论上都可以把你的传输数据拦截下来，甚至篡改，所以我们要知道公开的这些通信信道是不安全不可信任的。

所以想想我们的数据在这些不可信任的路途中穿梭还是挺可怕的。

动机(Motivation)

现在我们已经可以通过AES加密数据了，把加密的内容传输出去。但是密码要怎么传输出去了，因为密码是明文的，它在这些公开通信信息里面传输就一定会可能被黑客拦截到，还有一个问题，如果你一直用同一个密码，那么黑客就可以一直拦截你的信息，甚至在得到密码之前就一直在拦截，直到某一天得到密码了，那么黑客就可以同时解密之前已经存在很的加密信息了，如果密码不改，那将来的加密信息也一样会被黑客解密。

所以密码学科学家们绞尽脑汁想设计出来一种方法，可以解决在不安全信道中交互密钥的问题

于是就设计出了一种通过密钥对的加解密方式，同时生成一对密钥

  • 私钥(Private Key) — 自己保留，绝对保密
  • 公钥(Public Key) — 公开发布，分享给其它人

公钥加密，私钥解密。这样别人就可以拿到你的公钥把需要保密的信息进行加密发给你，你收到后通过私钥进行解密。

这个想法很奇妙，然后真的就做出来了。

RSA(Rivest, Shamir, Adleman)

RSA就是其中一种非对称加密算法，它就是可以生成一对公钥，私钥。可能大家以为这个是最近才发明的，但其实这个是很早，在1977年，RSA就发明了，一直用到现在。

它基于的数学原理其实很简单，简单到一个小学生都容易理解

  • 大整数的因式分解

假设我们有两个质数p, q, N=p*q, 那当我们只知道N的时候是没办法算出p和q的，这个基本原理就是RSA的本质。

其实想想很简单，但总会觉得有点不可思议对吧，但现实就是这样，如果有谁能过够在只知道N的情况下算出p和q,那么RSA就完蛋了。

RSA的计算过程很简单

选择两个质数
…