最近可能大家也看到了一些关于量子计算机进展的新闻，比如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, q。…