RSA加密曾被视为最可靠的加密算法,直到秀尔算法出现,打破了RSA的不灭神话。

作为RSA加密技术的终结者——“太多运算,无法读取”的秀尔算法(Shor’s algorithm)不是通过暴力破解的方式找到最终密码的,而是利用量子计算的并行性,可以快速分解出公约数,从而打破了RSA算法的基础(即假设我们不能很有效的分解一个已知的整数)。同时,秀尔算法展示了因数分解这问题在量子计算机上可以很有效率的解决,所以一个足够大的量子计算机可以破解RSA。

http://math.nist.gov/quantum/zoo/ - Quantum Algorithm Zoo

后量子密码替代品的加密方法:

  • 基于格的加密 (Lattice-based cryptography),安全性是基于最坏情况下格问题的困难,Ajtai在1996年提出“Collision-ResistantHash Function”,Goldreichet al.在1997年提出“PKE and signature schemes”,Ajtai和Dwork在1997年提出“PKE scheme”;
    优点:可证明安全:基于最坏情况硬度的强安全性证明;相对高效的实现;非常简单;多用途,许多先进的密码体制的提出,例如:IBE、ABE、FHE;
    缺点:暂无。
  • 基于散列的方案 (Hash-based signatures),安全依赖于底层的哈希函数的抗碰撞性;
    优点:安全要求是最小的;
    缺点:只能用于量子签名方案(签名/验签)。
  • 椭圆曲线同源加密算法
  • 多变元加密 (Multivariate-quadratic-equations-cryptography),多变量密码体制(MPKC)被认为是能够抵御基于量子计算机攻击的新型公钥密码体制之一,利用减扰动方法构造出了一种基于MPKC的新型签名方案,其计算效率,主要指中心映射求逆的效率高于两个著名的多变量签名体制Sflash和Quartz;
    优点:与基于hash的签名方案相比,签名较短;
    缺点:与传统的RSA、ECC等系统相比,密钥非常大;还有在MPKCs的可证明安全性没有实质性的结果。
  • 基于编码的加密 (Code-based cryptography),算法原语(底层单向函数)使用纠错码,第一个基于编码密码(公钥加密方案)是由Robert J. McEliece在1978年提出的;
    优点:加解密速度快;
    缺点:大型公钥大小(100KBS-几MBS),签名/验签成本大。

现在密码学术界,对于后量子密码的方案基本上是基于哈希函数签名和基于格密码两者结合的,基于哈希函数签名用于抗量子密码体系的签名/验签,基于格密码用于抗量子密码体系的加密/解密。