面向后量子时代的密码技术

2023-12-05 07:45:36 来源: 《环球》杂志

 

4月26日,观众在第二届中国(安徽)科技创新成果转化交易会上拍摄“九章”光量子计算原型机模型

 

  后量子密码学是一个充满挑战和机遇的领域,后量子密码学的研究与应用不但对密码学,也将对未来的第三代互联网和元宇宙的发展带来深远影响。

文/高承实

编辑/吴美娜

  今年1月,国际标准化组织互联网工程任务组(IETF)启动了后量子协议使用(PQUIP)工作组,以协调后量子时代加密协议的使用;3 月,抗量子网络安全供应商 QuSecure 声称已率先实现了经由卫星、能抵御量子计算攻击的端到端加密通信,这也是美国首次采用后量子密码技术保护卫星数据通信;8 月,美国国家标准与技术研究院(NIST)发布了后量子密码学(PQC)标准草案,旨在形成一个在未来免受量子网络攻击的全球框架……

  在全球范围内,传统的密码技术受到了量子技术发展带来的显见挑战,有关量子时代密码技术的讨论日渐增多,相关项目也正在落地。其实,量子计算出现之后,如何确保密码的安全就开始成为学术界和业界的持续关注焦点。

密码技术的分类和发展

  在量子时代,我们的密码还安全吗?回答这一问题,需要考虑密码技术的类别,因为不同类别密码技术建立的数学基础不同,这些密码算法所能承受的量子“攻击”程度也不相同。

  密码学的发展经历了古典密码学、近代密码学和现代密码学。我们现在所说的密码学一般都是指现代密码学。从密码体制上,现代密码一般被分为对称密码和非对称密码两种,此外还有确保通信内容完整性的哈希函数。

  根据对明文加密处理方式的不同,对称密码又可分为分组密码和流密码(也称序列密码)。分组密码是先按一定长度(如64比特、128比特等)对明文进行分组,再以组为单位实施加/解密运算;流密码则不进行分组,而是按位直接对报文进行加解密运算。

  对称密码体制要求加密密钥和解密密钥相同,或本质上相同,这也是其被称为对称密码的原因。对称密码要求密钥必须被严格保密,否则就无法实现加密信息的机密性。因此,密码通信系统的安全也就完全依赖于密钥的保密。加密以后的报文可以在不安全的信道上传输,但加解密的密钥却必须通过安全可靠的信道传递。因此,对称加密体制的最大弱点,就是保密通信的一方必须通过安全可靠的信道把密钥告诉对方,否则对方无法对接收到的保密信息解密。由此,密钥的保存和传递就成了最头疼的问题,尤其是在通信参与方比较多,又要求两两之间都实现保密通信的情况下就更是如此。

  非对称密码弥补了对称密码体制密钥管理上的不足。1976年11月,现代密码学之父、美国学者惠特菲尔德·迪菲和另一位美国密码学家马丁·埃尔曼发表了论文《密码学的新方向》,探讨了无需传输密钥的保密通信和签名认证体系问题,开创了公钥密码学,也就是非对称密码。在非对称密码体制中,每个通信参与方都有两个密钥,其中一个密钥公开,称为公钥,另一个密钥不公开,称为私钥。通信时由其中一个密钥对信息加密,可以用另外一个密钥解密,而且由公钥不能推导出私钥。每一个通信参与方都可以用接收方的公钥对信息加密,之后只有信息的真正接收方才能够用自己的私钥完成对加密信息的解密。同时,信息发送者如果用自己的私钥对信息签名,任何接收方也都可以用发送者的公钥实现对信息发送者身份的验证。因此,非对称密码体制在不需要对密钥进行保密传输的情况下就实现了保密通信。

  公钥密码学的发展是密码学发展史上最伟大的一次革命,也许可以说是唯一的一次革命。一般来说,公钥密码的安全性由相应数学问题在计算机上的难解性来保证,比如,广为使用的非对称密码算法RSA的安全性就是建立在大整数素因子分解在计算的困难性上的。

  哈希函数是一类特殊的函数,它将任意长度的信息输入,输出为固定长度的比特串,该输出称为哈希值。这种转换是一种压缩映射,也就是说,哈希值的空间会远小于输入信息的空间,因此不同的输入会被映射为相同的输出,但算法的复杂性使得通过这个输出却不可能确定到对应的输入。简单说,哈希函数就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。哈希函数在密码学中有广泛的应用,可以验证信息的完整性,保证信息的不可篡改性。哈希函数在区块链系统中也得到了广泛使用。

如何衡量密码算法的安全性?

  密码算法在安全性上有两个不同的指标,一是无条件安全,也称为完善保密性;二是计算安全,又称实际保密性。

  如果利用已知的甚至是未知的最好的算法破译一个密码系统需要至少N(某一确定的、很大的数)次运算,就称该系统为计算上安全的,也就是该算法具有实际保密性。无条件安全是指不论提供的密文有多少,密文中所包含的信息都不足以唯一地确定其对应的明文,即使具有无限计算资源(诸如时间、空间、资金和设备等)的密码分析者也无法破译某个密码系统。1945年美国数学家克劳德·E.香农在其发布的《密码学的数学原理》中,严谨地证明了一次性密码本(也称为“弗纳姆密码”,其基本原理是通过将与明文等长、完全随机,且只使用一次的密钥与明文进行异或运算来实现加密和解密),具有无条件安全性。但这种绝对安全的加密方式在实际操作中需要消耗大量资源,难以大规模使用。

  人们在现实中使用的密码算法,大部分都是计算安全的。因此,密码算法在使用时的安全性也需要随着外部计算能力的提升而不断被加强。

  比如对称分组加密算法,美国国家标准局最开始采用的是DES算法,其有效密钥长度是56比特,这也就意味着在算法安全的要求下,破解这个算法需要进行256运算。不过,随着计算能力的提升,原来用大型机甚至巨型机也难以破解的DES,目前个人电脑已可以轻易将其破解。因此,分组加密算法的标准也由DES进化到了AES,AES 每组的分组长度虽然都是128比特,但其密钥长度可以是128、192甚至是256比特,这就使得野蛮破解该算法需要更多次的运算。

  再比如非对称密码算法。原来可能256比特,最多512比特长度密钥的RSA算法就足够用了,但由于计算能力的大幅提升,目前1024比特以下的RSA算法已经不再被建议使用了。根据国际标准,目前常用的RSA算法密钥长度的范围是1024比特到4096比特,2048比特的密钥是目前RSA算法中最常用的。

后量子时代的密码技术路线

  如果说以往密码算法面临的安全威胁主要来自传统方式下的计算能力提升,那么当前密码算法面临的最大威胁可能就来自量子计算带来的算力提升了。传统方式下计算能力的提升,并不会从根本上对原有的密码加密方式带来根本性挑战,但量子力学态叠加原理使得量子计算可以在效率上相比于经典计算机具有更大潜力。

  量子计算在一些特定问题上已经显现出远优于传统计算的能力。据Quantum Algorithm Zoo网站统计,目前已有数百个基于量子计算模式的算法被用于对传统密码算法的破解,其中对传统密码算法有较大影响的量子算法主要有Shor算法、Grover算法、和Simon算法,这些算法对当前广泛使用的基于传统数学难题的密码算法构成了严重威胁,导致部分在传统计算模型下可证明安全的密码模型在量子时代不再安全。

  为了应对量子技术发展带来的挑战,后量子密码学作为一种新兴的密码技术应运而生。后量子密码学研究的目标,是提供一种能够在量子计算时代仍然保持安全性的密码算法和协议。后量子密码学也是基于量子计算仍难以有效求解的数学难题而建立起来的,目前后量子密码算法的主要技术路线有基于哈希、编码、多变量、格和同源等问题的方案。

  需要指出的是,对称密码算法和哈希函数在量子时代仍能够保持一定的安全强度,可以通过像上面所说的增加密钥长度或哈希值长度的方式对抗量子攻击。

  基于哈希算法使用Merkle树等结构生成数字签名,是后量子密码算法的一类,其安全性依赖于哈希函数的安全性,而不是依赖于数学问题的困难性假设。如果所采用的哈希函数算法被攻破,只需将哈希函数更新为更安全的函数算法,就能确保签名算法的安全性。

  基于编码的算法利用纠错码构造单向函数,是后量子密码算法的第二类,其安全性依赖于编码理论中的SD(Syndrome Decoding,伴随式解码)和LPN(Learning Parity with Noise,带噪声的子空间,一个假设问题)等难解问题,可用于构建加密算法、数字签名和密钥交换方案等。

  基于多变量的密码算法使用有限域上的多变量二次多项式组构建加密、签名和密钥交换,其安全性依赖于求解多变量方程组的困难性。

  基于格的密码算法基于格中的难解问题,可以用于构建加密、数字签名和密钥交换等密码方案。这类方案具有比较快的计算速度和较小的通信开销,在安全性、公私钥大小和计算速度方面取得了比较好的平衡,有望成为量子计算时代的标准。

  基于同源的密码算法则利用了超奇异椭圆曲线同源问题构建加密和密钥交换等密码方案,这类方案具有较短的公私钥,但运行效率较低。

  目前学术界和业界对抗量子攻击的对称密码研究相对较少,设计方案只有Saturnin等少量方案。

  中国在2018年启动了全国密码算法设计竞赛,其中非对称算法部分征集到38个算法,经过形式审查、公开评议、检测评估和专家评选,竞赛最终评出14项优胜算法。其中11个密码算法是基于格困难问题的算法,1个是基于编码问题的非对称加密算法,1个是基于超奇异椭圆曲线上同源问题的密钥交换协议,还有1个是基于置换核问题的数字签名算法。

  总体上,后量子密码学是一个充满挑战和机遇的领域,后量子密码学的研究与应用不但对密码学,也将对未来的第三代互联网和元宇宙的发展带来深远影响。

  (作者系密码学博士、中国计算机学会高级会员)

来源:2023年11月29日出版的《环球》杂志 第24期

《环球》杂志授权使用,如需转载,请与本刊联系。

更多内容敬请关注《环球》杂志官方微博、微信:“环球杂志”。

手机版