二十世纪末诞生了两个伟大的思想：利用量子力学原理来进行保密通信——量子通信， 和利用量子力学原理来进行计算 。 这两类基于量子力学的技术， 可以统归于量子信息技术， 代表着未来信息处理技术的发展方向 。 尽管都是用到量子力学原理， 不过二者是有很大差别的， 并非相近相类技术 。 我经常被人问及量子通信的专业话题， 弄得我很尴尬——其实我对量子通信了解并不深 。 我相信同样地有很多量子通信专家会被问及量子计算的专业话题 。 因为是接着公钥密码系统的话题， 所以这里先讲讲量子计算 。
上世纪90年代一个数学家彼得·肖， 发现一种基于量子逻辑的算法——Shor算法， 这种算法最吸引人的地方是， 它能够将质因数分解问题的复杂度， 从指数难度降低到近多项式难度 。 熟悉计算机科学的人一定知道， 一个多项式复杂度的问题， 对目前的计算机而言， 就是“可解”的 。 换句话说， 问题的复杂度增加， 并不会带来所需计算资源的灾难性增加 。 这种问题称之为P问题 。 其反面就是NP问题：不确定多项式问题 。 这里的不确定， 意味着在当前的数学水平下无法得到多项式复杂度的算法 。 在数学界， 有很多人为证明“NP=P？”这个问题奋战争论很多年， 到目前没有结论， 甚至少有线索 。 普遍的观点是接受NP≠P的 。
质因数分解问题在经典计算中是一个NP问题， 到目前为止没有低于指数难度的算法 。 互联网上最常用的公钥密码——RSA密码， 就是基于质因数难分解而易验证的原理 。 RSA密码自问世以来， 有记录的破解有三次， 分别是1999年的RSA-155、2002年的RSA-158及2009年的RSA-768， 其中RSA-768用了768位（二进制位）密码 。 目前流行的RSA-1024从未有被破解过， 考虑到768已经比较接近1024， 且计算机发展速度飞快， 已有人建议采用RSA-2048 。 有人评估过， 在经典计算机上破解RSA-2048需要10亿年（以超算能力进行估计， 这个数字会随着技术进步而不断缩小 。 不过这并不重要， 即便将摩尔定律无限外延， 10亿年要缩短到年也需要60年， 这还是在假定RSA密码在这段时间里原地踏步的情况） 。
小资料
RSA-2048密码破解所需时间之估算
为了破解一个以RSA密码为基础的证书（比如由DigiCert所提供的）， 我们必须对组成RSA模数的一个超级大数做质数分解 。 当所用电脑达到了证书相关的RAS模数分解的平均时间[换句话说， 它（分解）可能发生在第1年， 也可能发生在第6万亿年， 平均时间可能是尝试所有可能性所需总时间的一半]， 我们就认为这个证书被“破解”了 。 2009年12月， Lenstra等人声称破解了一个768比特的RSA模数（见：http://eprint.iacr.org/2010/006.pdf）——这是一个232位（十进制）的数， 是当时（很可能到现在也是）分解的最大的一般整数 。
分解一个大数最有效的方法——也是上面的破解纪录所用的方法——是通过数字场筛选， 这个方法比暴力破解（试遍所有组合）要快得多， 所以暴力破解将耗费与之相比更多的时间 。 Lenstra小组估算了一下， 破解一个1024位（二进制， 后面如无说明均指二进制数）的RSA模数要比他们破解768位数困难1000倍 。 也就是说， 在相同的硬件设备和条件下， 破解耗费的时间要长1000倍 。 他们同时也估计了一下， 如果将处理能力归一化到当时的一台标准台式电脑配置（含一个2.2GHzAMD羿龙处理器， 具有2G内存）， 那么他们实现的纪录需时为1500年 。 所以换句话说， 按照Lenstra等人的估计， 破解1024位RSA密码在普通台式机上需要150万年 。 目前的超级计算机的计算能力是普通台式机的百万倍以上 。 即使用超级计算机解密也需花一年左右时间 。
推荐阅读
- 我国学者研究“多节点量子网络”取得基础性突破
- 量子计算陷入难解困境，未来发展将何去何从？
- 语文初一作文
- 推翻时间箭头：量子计算机或将改变时间向前流动方向
- 给纠缠态“做个CT” 让未来量子网络更安全
- 首台基于三维芯片的光量子计算系统问世
- 为什么量子通讯绝对安全？随机数是关键
- 5G通信与人工智能、计算三者将相辅相成
- 人工量子系统中量子纠缠新途径被发现
- 时间“倒流”首次在量子计算机上实现