从4大关键问题搞懂PQC与密码学竞赛

近年来,量子运算带来的威胁持续成议题,量子密码学(Post-Quantum Cryptography,PQC)的发展也备受关注,而随着NIST举行的“后量子密码学标准化”竞赛,在2020年后进入最后阶段,因此,不只是密码学界,现在已经是各界都在关注PQC的最新发展。

基本上,这是一项对于公钥密码系统的考验,NIST的目的很简单,就是要选出可以不受量子计算机威胁的新密码系统,成为美国的国家新标准,但由于制定完成后,全世界都会采用,因此,其效果就是成为世界的新标准。

NIST是何方神圣?他们是美国国家标准暨技术研究院,在诸多产业都有多年标准制定经验,而信息技术与网络安全也是他们的重点,包括网络安全与隐私保护、密码学及密码验证等9大领域。

由于量子计算机威胁的议题,近年来PQC逐渐受到关注,加上NIST举办相关竞赛要选出新标准,但大多人对此议题可能还不熟悉,因此,这次我们找到这方面的专家──台大数学系兼任助理教授陈君明,帮助我们更进一步了解。

而为了让大家对PQC与NIST密码学竞赛能更有概念,因此,我们整理出四大面向的问题,让大家能够一步步了解。

问题1最近时常听到量子运算突破的新闻,以及现有加密系统将会被破解的消息,这与后量子密码学(PQC)有何关联?

随着量子运算的出现,让传统加密系统出现危机,尤其是将对当今的非对称式密码系统带来极大影响,这是指那些密码系统?其差异为何?

简单来说,密码系统分成两大类,一类是对称式密码,AES就是一例,另一类是公开密钥密码,也就是非对称式密码。陈君明指出,所谓的量子破密,主要影响的是非对称式密码系统,例如,公钥密码系统,也就是现今普遍的公钥基础架构,包括RSA或ECC这类非对称加密算法。

基本上,加密算法都是创建在特定数学难题的基础之上。以RSA而言,以往之所以安全,是创建在极大整数质因素分解的数学难题,对传统计算机而言,需要花费太长时间运算,而量子计算机则可于多项式时间破解这样的难题。

至于对称式密码系统,虽然也会受到量子计算机攻击的影响,但影响程度算是有限。举例来说,原本AES 256的强度变成AES 128的强度,因此,只要密钥长度加倍就可因应。

那么,为何过去DES演进到AES时,没有出现类似后量子密码学这样的新名词定义?陈君明表示,DES与AES都是对称式密码相当明确,而在公钥密码方面,虽然RSA、ECC与PQC都是这个范畴,但由于前两者都会被量子计算机破解,因此,专注在不会被量子计算机破解的公钥密码系统,就需要有一个新的名称。

同时,他也指出,全球在因应量子计算机破密的威胁上,其实有两大路线,除了基于密码学的PQC,还有基于量子技术的量子密钥分发(Quantum Key Distribution,QKD)等。

不过,自2020年10月后,PQC可能将会更受重视。

陈君明表示,主要原因在于,美国国家安全局公开表示,他们不看好QKD与量子加密(Quantum Cryptography,QC),而且也说明QKD的5个技术限制,包括需要专用设备,以及需要增加基础设施成本与内部威胁风险等,他们甚至直言,日后将只会关注在PQC的发展。因此,就现在的态势来看,除了持续关注量子计算机的最新进展,关注后量子密码的标准制定也是重点。

问题2现在大家在关注的后量子密码学,它是现在才新出现的吗?还是其实已经发展了很多年?

在2020年7月,由美国NIST所举办的“后量子密码学标准化竞赛”(Post-Quantum Cryptography Standardization),公布第三轮决选名单,此事也让我们注意到,原来因应量子运算威胁的PQC,发展已久。

例如,这项竞赛从2016年就开始对外公开征选,甚至他们是在2012年开始准备PQC计划,而更早NIST在2009年就有这方面的调查。

对于后量子密码学的发展与演进,陈君明表示,其实,全球最早注意到量子运算的威胁,已经是20多年前。

从1994年开始,当时AT&T贝尔实验室的数学家Peter Shor有了一项重大发现,他提出大整数质数分解的第一个量子算法,称之为Shor’s算法,因此打开了量子破密的里程碑。

而后续提出的Grover算法,也发现会使对称式密码系统的安全等级减半。

陈君明指出,当时整个密码学界就开始关注这件事,但还不是那么急迫要去因应,主要原因,当时大家公认量子计算机还不会那么快迈向成熟。

不过,约自2000年开始,其实全球密码学界都已在关注,并且一直陆续都有针对这方面的相关研究。

另外,我们也好奇,难道20年前就有后量子密码学一词吗?他解释,关于PQC一词,其实是由Daniel J. Bernstein提出。

而在更早之前,像是美国NIST与NSA是以“Quantum Resistant”称呼这类密码学。

因此,我们看到早年NIST对于PQC的一项调查研究,当时是称之为Quantum Resistant Public Key Cryptography,不过,现在大家几乎都是以PQC来统一其称呼。

问题3关于NIST举办密码学标准化竞赛,吸引来自全世界的团队参赛一较高下,这样的密码学竞赛多吗?

除了这次的Post-Quantum Cryptography的竞赛以外,我们其实看到NIST共列出4个竞赛,包括:Block Cipher(AES)、Hash Function(SHA-3),以及Lightweight Crypto,这些竞赛有何不同?

陈君明表示,其实,NIST并非第一次举办这类密码学的竞赛。在20年前,NIST就举办过AES高端加密标准的竞赛。他们是在1997年1月开始公开征选,然后在2000年制定出新标准,当时,这项竞赛是为了选出取代早期的DES标准,成为新的对称式加解密的标准。

特别的是,这也是他们第一次,举办全世界都可以参与的竞赛。因为,在1976年制定的DES标准,仅是由IBM的一个团队,先设计了对称式加解密,然后再经由美国国家安全局NSA参与修改,才确立为国家标准,因此当时并没有对外公开征求候选者。

而在NIST这么做之后,也打开了标准竞赛举办的风气,因为,其他国家也开始举办这类的全国性标准竞赛,像是韩国、日本与中国等。

不仅如此,约在10年前,NIST又举办了SHA-3第三代安全散列算法的竞赛。简单而言,这是因为SHA-1被发现严重的问题,而SHA-2又与SHA1设计原理类似,因此NIST要选出一个设计原理非常不一样的成为新标准。后续,SHA-3与SHA-2并行成为美国政府的散列函数的国家标准。

至于现阶段,陈君明说,NIST其实是有两项竞赛正在进行,除了PQC的竞赛之外,另外还有一项名为Lightweight Crypto的竞赛。

他解释,这是一个轻量级的密码学竞赛,主要因为现在有越来越多IoT设备,但是,在这些设备上执行AES并不易,因此,需要有一个执行计算资源需求较少,又能维持基本安全性,短时间破不了的密码的系统。这项竞赛在2019年才发起,目前有57个投稿。

问题4这次PQC竞赛时间漫长,若是这段期间如果有新算法提出,难道就不能成为标准吗?

从上述PQC的发展与NIST的这些竞赛来看,我们还是很好奇,例如,以这次PQC标准化竞赛的评选进程,似乎比之前AES竞赛时间要更长,而这么多年的时间下来,难道就不会有新的技术被提出,而无法入选成为新的标准吗?

陈君明解释,其实我们并没有办法严格证明某一个密码系统的安全,因此,能够做的事情,就是将算法公开,让大家来攻击后,如果大家都破解不了,就代表越安全。

“在密码学的领域,并不是技术越新越好,而是要越经得起考验越好。”他说,以这次NIST PQC标准化竞赛为例,名为McEliece的密码学系统是第三轮入选之一,它已经被提出40年之久,就是因为大家都破解不了,而且被大家普遍使用的时间越久,这代表着越经得考验,因此大家相信它的程度就会越高。

另外,他也以这次其他竞赛投稿为例,像是NTRU已被提出超过25年之久,而Rainbow也已经提出有15年。

反之,新提出的密码学系统,通常没有经过长时间的考验,因此大家对它的信心也会较低,而NIST也不会选择它去作为标准。

发表评论