密码学(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, q。…

密码学(Cryptography)简史-对称加密(Symmetric Encryption)

之前一篇文章讲过古典密码学。

这篇文章我们来聊一下对称加密(Symmetric Encryption)。

这个名字其实有点唬人，简单说就是只需要一把钥匙可以用来把文件加密，然后解密也是同一把钥匙。

比如说我们要对PDF进行加密，那就会有需要同一个密码进行打开，如果没有这个密码，你就看不了里面的内容。

文件加密之后我们就可以把文件存在一些公开的网盘里面，或者分享给其他人，然后别人通过密码就可以看了，如果没有密码，就算别人得到文件也无法知晓里面的内容。

Blocker Cipher(分组加密)

一个文件可能很大，所以密码学上一般会把内容进行固定长度的切割，然后一块内容一块内容进行加密，这个就是分组加密，与之对应的就是流加密(Steam Cipher)。

DES(Data Encryption Standard)

DES(Data Encryption Standard), 它1977年成为标准。这个名字看起来很高级，其实现在已经不用了，甚至说禁止使用，因为随着计算机算力的不断发展，它56位的密码长度很容易就被爆破出来(Brute Force)，1999年就被爆破了，但在一段时间之内，它就是标准的密码加密算法。

  • https://en.wikipedia.org/wiki/Data_Encryption_Standard

它的流程如下图，基于Feistel Network结构，16轮运算，Block Size 64位，分为左右各32位，然后进行16轮运算，每轮运算就都使用不同的密码(KDF,随称密钥派生, Key Derivation Function)，最后输出同等长度的64位密文。

后面还有3DES， 就是进过三轮DES加密，因为密码长度始终只有56位，所以也被淘汰了。

这样就不得不寻求新的加密方式

AES(Advanced Encryption Standard)

随着DES的安全性越来越弱，美国NIST在1997年发起了新的加密算法的竞算，经过多轮挑战，最终Rijndael算法被选自AES标准。

  • https://en.wikipedia.org/wiki/Advanced_Encryption_Standard_process

所以在2001年，Rijndael被当做标准，成为AES算法，这里有当年AES成为标准的提案。

最终选取

  1. Block size: 128位
…