每日快看:专访宗传明:数学奠定“后量子密码”的基础

2022-12-07 11:36:21    来源:中国科学报    

今年7月5日,美国国家标准与技术研究院(NIST)公布了4项后量子密码标准,旨在抵御未来量子计算机的攻击。

科学家普遍认为,基于量子科学原理建造的量子计算机将大大地超越电子计算机,而现代通信所利用的许多密码体系在量子计算的攻击下将不堪一击,能够抵抗这一攻击的现有或新一代密码算法就是“后量子密码”。


(资料图片)

此次公布的4项后量子密码标准中中3项基于一个古老的数学学科—格理论。换句话说,假如量子计算机在不远的将来能投入实用,格理论将是量子计算时代信息通信安全的“保护神”。

如何理解“后量子密码”?格理论如何在信息通信安全中发挥作用?为解答这些问题,《中国科学报》专访了格理论研究专家、天津大学教授宗传明。

《中国科学报》:首先感谢您接受我们的专访。先请您简单介绍一下密码,它的起源和作用。

宗传明:密码是一种防范第三方窃取信息的通信保护手段。早在古罗马时期,凯撒大帝和他的将军之间就用密码传送命令,这就是著名的“凯撒密码”。由于他们的语言当时只有23个字母,情报官将命令的每一个字母依照字母表的次序后移固定的位置(比如5个位置)然后写成新的形式交给传令兵,前线将军收到命令后再由情报官还原回去。这样,即便敌方抓获了传令兵也看不懂命令。

随着电报、电话等现代信号传输技术的发明,用于军事和外交的密码变得越来越复杂。第二次世界大战期间,密码成了某些重要战役胜负的决定因素,例如中途岛海战和击落山本五十六大将的座机等。同时,为了有效地破译敌方的密码,电子计算机应运而生。

《中国科学报》:什么是后量子密码?

宗传明:作为能量的最小单位,量子是由德国物理学家普朗克于1900年提出的。在此基础上,爱因斯坦、玻尔、德布罗意、海森伯、薛定谔、狄拉克、玻恩等建立起了量子力学理论。绝大多数物理学家将量子力学视为理解和描述微观世界的基本理论。

现在的计算机是基于电子的物理学理论,历经电子管、晶体管、集成电路,发展到今天的大规模集成电路计算机。随着计算机技术的快速发展,密码学也得到了空前的发展。特别是进入互联网时代以来,密码学也从一项技术发展成为一门跨数学与计算机科学的科学技术。

科学家普遍认为,基于量子科学原理建造的量子计算机将大大地超越电子计算机,不论是计算速度还是智能性。这样,许多电子计算机无法解决的科学问题对量子计算机来说将易如反掌。特别地,现代通信所利用的许多密码体系在量子计算的攻击下将不堪一击。所以,科学家们在加速量子科学研究和量子计算机研制的同时,也在加速准备量子计算机时代安全的密码体系。这就是后量子密码。

《中国科学报》:能否设想一下,假设有两个敌对国家,其中一个国家秘密发展了量子计算机,而另一个还停留在应对普通电子计算机的密码体系。如果前一个国家利用量子计算机对后一个国家的密码体系发动攻击,后一个国家的信息安全体系将会瞬间崩溃。

宗传明:是的,就像科幻小说《量子间谍》描写的那样。

《中国科学报》:数学给人的印象是非常抽象、非常难。它怎么会成为密码学的基础?

宗传明:的确,数学非常抽象、非常难。同时,数学是最讲究逻辑、最精确的一门学问。密码无论是对加密还是解密过程都需要精确、需要好的规律性,而为了避免被敌方破译则需要加密规律从计算上来看高度复杂。这样,从哲学的角度看,数学中的某些复杂问题成为密码学的基础是必然的。

其实,密码学的“鼻祖”凯撒密码就是建立在数学基础之上,是数论中最简单的同余方程。

随着电子计算机和互联网的高速发展,作为通讯安全保障的密码也变得越来越复杂。

1976年,两位密码学家惠特菲尔德·迪菲(Whitfield Diffie)和马丁·赫尔曼(Martin Edward Hellman)提出了密钥交换协议,改变了原来单一密钥的设计,进而提出加密密钥和解密密钥不同的密码思想。由于这一革命性的方案,他们荣获2015年度“图灵奖”。其实,也是这一方案为基础数学进入密码学开启了大门。

1977年,基于大整数分解的密码体系RSA诞生了,它是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)3位提出者首字母而命名。早在两千多年前,古希腊数学家欧几里得就已经证明:每一个自然数都可以被唯一地分解为素数方幂的乘积。但是,具体分解一个大整数在计算上非常复杂耗时,正是其复杂性成就了RSA密码体系的安全性,他们由此荣获2002年度“图灵奖”。

在RSA成功之后,又有多种基于基础数学的密码体系相继被发现,比如基于椭圆曲线的密码体系、基于格理论的密码体系、GGH密码体系、NTRU密码体系等。毫不夸张地说,数学已成为现代密码学的基础。

《中国科学报》:您提到的这些密码体系都能抵抗量子计算机攻击吗?

宗传明:当然不是。1994年,当代著名数学家和计算机科学家彼得·肖尔(Peter Shor)首次提出了大整数分解的多项式时间量子算法,并应用于密码学。他的工作表明,在量子计算时代,基于大整数分解和离散对数问题的公钥密码体系将被攻破。随着量子科技的快速发展,以及多项广泛应用的密码体系在量子计算环境下被攻破,各国科学家快速意识到了量子计算机可能给信息安全带来的危机。

2016年,美国国家标准与技术研究院(NIST)发起向全世界征集抵抗量子计算机攻击的后量子密码标准。历经4轮遴选淘汰,2022年7月5日NIST公布了4项后量子密码标准。其中的3项是基于格理论,一项基于编码理论。

《中国科学报》:什么是格理论?

宗传明:1831年,高斯提出了格的概念。它是n维空间中最有规律的离散结构。在过去的近两个世纪中,历经高斯、厄尔密特、闵科夫斯基、西格尔等大数学家的系统研究,格理论已发展成为数论、代数与几何相交叉的一个重要数学分支。

在这一领域中,2021年洛瓦兹(Lovasz)由于LLL算法的工作荣获“阿贝尔奖”,今年7月维亚佐夫斯卡(Viazovska)由于8维堆球和24维堆球的工作荣获“菲尔兹奖”。特别地,三维格理论奠定了晶体学的基础。高维格理论成就了NIST四项后量子密码标准中的三项。

《中国科学报》:为什么格密码能抵抗量子计算攻击?

宗传明:一个给定的格必定有最短的向量。早在一百多年前,大数学家闵科夫斯基已经给出估计;给定一个格,空间中的任一点一定有一个最近的格点。但是,要找到一个好的算法来确定格的最短向量(SVP)或离给定点最近的格点(CVP)却极其困难。而格密码在量子计算环境下的安全性都可以递归到这两个数学问题的计算复杂度。

早在上世纪80年代,一众著名数学家们深入系统地研究了上述两个格理论问题的的计算复杂度。他们已经证明:在电子计算机环境下求解这两个数学问题都是非常困难的。以专业术语讲,他们已经证明:随机归约求解最短向量问题是NP-hard, 而求解最近格点问题是NP-complete。

格密码最早是由美国数学家米克劳斯?阿杰泰(Miklós Ajtai))于1996年提出。由于上述数学家们的理论工作,格密码显然能够抵抗电子计算机的攻击。那时,彼得·肖尔的量子算法刚刚被提出,在其他密码体系纷纷被量子算法攻破的情况下,世界各地的密码专家更是使出洪荒之力试图利用量子算法攻破格密码。特别是在美国国家标准和技术研究院于2016年开始征集后量子密码标准以来的六年。其实,在过去的近10年当中,每届世界密码学的三大会议(美密会,欧密会和亚密会)都会设一个分会专门研讨格密码。但是,人们至今没有找到有效的量子算法攻击格密码。数学家和密码学家们反倒形成了一个共识(猜想):不存在多项式时间的量子算法能在多项式误差下求解格的最短向量问题和最近格点问题。

换句话说,格密码是能够抵抗量子计算机攻击的。

《中国科学报》:1994年还没有量子计算机的模型机。彼得·肖尔为什么能提出量子算法?人们又如何检验一个密码体系是否可以抵抗量子计算机攻击?

宗传明:在科学技术的发展过程中,有时候是技术推动科学,而大多数情况是科学推动技术。早在1994年,确实没有公开运行的量子计算机模型机。彼得·肖尔是依照量子科学的原理在理论环境下设计他的量子算法,其他数学家和密码学家也是依照量子科学的原理在理论环境下设计攻击算法来检验一个密码体系是否可以抗量子计算机攻击。

假如我们把计算机比作一个人,硬件若比作躯体,软件则可比作智力。在物理学家和计算机工程师致力于设计建造量子计算机的同时,数学家和计算机科学家也在努力赋予它智能,并且提前防范其智能对信息安全可能带来的破坏。

《中国科学报》:在当下复杂国际环境下,我们该如何应对量子科技可能会带来的挑战?

宗传明:我不懂物理,也不懂计算机,只懂很小的一个数学分支—格理论。碰巧格理论成了后量子密码的数学基础,我有责任向公众科普这一可能的危机以唤起大家的共识和重视。

从前面的访谈中大家已经看到,欧美走到后量子密码标准是在大批一流数学成果的基础之上,没有“弯道超车”,也不靠“黑科技”,而完全是一个水到渠成的过程。

我国现代科学技术起步晚,现代数学进入中国才刚刚一个世纪多一点。在有了近几年被“卡脖子”的经历后,大家一定已经有了共识:要摆脱被“卡脖子”就必需成为科技强国,要成为科技强国就必需要有一流的基础科学,要有一流的基础科学就必需有一流的数学。

在量子计算机已成为各国竞争潜在战场的今天,我们必需要有一批格理论的数学家尽快迎头赶上,搞懂前面我提到的欧美数学家为后量子密码所奠定的基础,与我国的密码学家密切合作共同打造我国的信息安全之盾。

[责任编辑:h001]

相关新闻

联系邮箱:99 25 83 5@qq.com

备案号:豫ICP备2020035338号-4 营业执照公示信息

产经时报 版权所有