量子计算机决定数据加密成败

量子计算机决定数据加密成败

2016-11-09 作者: xuzhiping 浏览: 2753 次

摘要: 当数据在因特网中传输时,加密方法能保护个人识别码,不让别人知道,并且安全地储存医疗信息、确保在线交易机密性、允许电子投票以及验证数字签名。原则上,加密方法主要是靠数学运算的不可逆性(至少要具有难逆性);换言之,对于某些特定的运算,没有任何算法可以在合理时间内倒...

当数据在因特网中传输时,加密方法能保护个人识别码,不让别人知道,并且安全地储存医疗信息、确保在线交易机密性、允许电子投票以及验证数字签名。原则上,加密方法主要是靠数学运算的不可逆性(至少要具有难逆性);换言之,对于某些特定的运算,没有任何算法可以在合理时间内倒算回去。

只能单一方向求解的运算称为单向函数,“单向陷门函数”是指可以反向求解的函数,但一定要有额外信息才能解出,如密钥。举例来说,两个数字相乘很容易,但要分解乘积很难,想找出解答的人必须尝试各种可能的数,直到找出不留余数的除数为止。

这就是现在素数的乘积被用来加密信息的原因: 预期的收件者先选出两个素数,相乘之后公开乘积,想传送保密信息给他的人会用这个乘积来加密信息。只要乘积的数字够大,逆运算(也就是 将这个乘积分解为两个素数)至今仍是不可能的,通常只有拥有密钥的收件者才知道是哪两个素数,所以能解开加密信息。大素数的乘积就是一种单向陷门函数,因为把乘积分解为两个素数是不可能的……除非已经事先知道其中一个因子。

事实上,从来没有人严谨地证明在合理时间内分解大数字是不可能的。加上市面上计算机的速度一天比一天快,不断开发出复杂的算法,使得寻找合适的密钥变得愈来愈有效率,这些发展逐渐威胁到现有的加密方法,1970年时,分解一个37位的数仍是一件轰动的大事;但如今因子分解的世界纪录已高达160位。2003年4月1日(这可不是愚人节笑话),波恩的德国联邦信息科技安全办公室的5位数学家,成功地把160位这么大的数分解成两个80位数的因子,而且目前仍在不断进行这类因子分解。美国中情局、英国军情五处或以色列莫萨德情报局是否可能已经有了寻找密钥的有效算法,只是没有透露?无论对于哪种情况,为了安全的理由,目前建议使用300位以上的数来做加密。

但有一种名为量子计算机的新科技宣称,它将威胁到300位、甚至3000位的数。与只能相继出现0、1的二进制数相反,量子能同时以一种以上的状态出现,这表示量子计算机原则上可以同时处理大量数学运算。若用传统计算机来做类似大数因子分解的计算,可能需要几个世纪,但量子计算机只需要几秒。

截至目前为止,量子计算机依然只是空中楼阁。然而,信息科技官员、网页设计者及安全专家仍在寻求更好的加密方法,使安全性不再仰赖于科技,而是凭靠自然法则。最近有两位瑞士数学家提出了一项建议,他们表示这种方法或许可以对抗量子计算机。在最近期的《数学基础》上,苏黎世瑞士联邦理工学院的斯特鲁维及弗来堡大学的亨格伯勒提出了一种加密方法,这种方法以热力学第二定律为基础。热力学第二定律是自然界最基本的原则之一,说明有些物理过程是无法逆转的。举例来说,要冲泡一杯奶咖很简单,过程是煮好咖啡、加人牛奶、搅拌,但要把奶咖分离为牛奶和咖啡却完全是不可能的。因此,冲泡奶咖就是一种单向函数——没有陷门的。

第二定律的另一个例子是热流,不妨想象一片下方有蜡烛燃烧的加热板。如果最初状况(蜡烛的位置)已知,便能轻易算出热的传导;另一方面,依据第二定律,要追踪已散布开的热的起点是完全不可能的,也就是我们无法判定加热板的哪一个部分先前曾受到烛火加热。即使知道某一时刻热能在加热板上的分布状态,也无法归纳出最初的蜡烛的位置。

亨格伯勒及斯特鲁维利用这些现象,提出了新奇的“公开密钥”加密法。假设艾丽斯想送一则加密信息给鲍伯,这两位伙伴先选择加热板下蜡烛的配置,这是他们的密钥a和P。然后,艾丽斯与鲍伯利用热流算子(H)计算一分钟后加热板上的热能分布状况(aH和 * H,两人各算一次)。这些热能分布就是公开密钥,艾丽斯与鲍伯把它们作为导读文件公布,或通过公开渠道传送。因为热能分布只能单向计算,潜在的窃密者就算知道公开密钥,也无法推导出蜡烛的初始位置。

现在艾丽斯用保密的蜡烛配置及鲍伯的热能分布状况(a * PH)为其信息编码,这是两组蜡烛同时放到加热板下时的热能分布状况。因为热流算子有可交换性,无论先放置哪一组蜡烛,对结果都没有影响,因此鲍伯可以用其保密的蜡烛配置,以及艾丽斯公布的热能分布状况(P * a * H)来为此信息解码,同时也能验证寄件人是艾丽斯。这种加密方式不依赖科技,而是以经典的自然法则与热力学的数学性质为基础,所以不会受到先进的计算方法的威胁。

很不幸的是,在可见的未来,不太可能用到热加密法。个中原因是,描述热流的数学式是连续函数,而以数字计算机计算连续函数必须截断数字。这种不可避免的舍人误差可以作为窃密者的起点,无法保证百分之百安全。讽刺的是,这时量子计算机就可以挽救这种局面。1980年代中期,物理学家理费曼及多伊奇指出,因为量子计算机可以有无穷的状态,所以能够凭借舍入误差达到无限小,以模拟连续的物理系统。因此,将来有一天,量子计算机可能让传统加密方法失效,但也可能是下一代的加密工具。

关注“开源集思”公众号
获取免费资源

随机推荐


Copyright © from 2014. 开源地理空间基金会中文分会 吉ICP备05002032号

Powered by TorCMS

OSGeo 中国中心 邮件列表

问题讨论 : 要订阅或者退订列表,请点击 订阅

发言 : 请写信给: osgeo-china@lists.osgeo.org