密码学也要超前部署!美国后量子密码标准竞赛

为了迎接后量子密码学时代来临,美国国家标准与技术局(National Institute of Standards and Technology,NIST)自2016年起举办“后量子密码学标准化竞赛”,吸引全世界团队参赛一较高下,在这场竞赛取得最终优胜者,将成为新一代标准化密码系统。最近中研院信息科学研究所杨柏因(见首图)研究员团队,以名为“Rainbow”的密码学系统通过第一、二轮考验,今年成为进入决选的7组决胜者之一,距离成为世界标准只剩一步之遥。

不论网络购物还是网络银行交易,我们的网络一举一动,都依赖严密的加密系统,保护我们隐私不让黑客盗取,守护我们的信息安全。然而随着量子计算机发展,现行加密系统却面临破解的威胁(有关目前的加密系统,请见《量子计算机到底有多霸气?即将引爆终极密码战?!》一文)。

因目前加密系统的根基,都是一道复杂的数学难题,而主流公钥加解密系统,包括RSA加密算法、椭圆曲线密码系统,背后的数学难题复杂得让古典计算机一筹莫展,却正好是量子计算机最擅长解决的问题形态。

这些数学难题的答案,皆可转化成周期性结构。理论上,只要找到答案的周期,量子计算机就可“较轻松”的破解问题。

怎么做?量子计算机的每个量子位元的数值是以几率呈现,意即每位元会有一个最高几率的数值,代表这个位元最可能的数。研究者可针对以上答案具周期性构造的数学函数,构造出相应的量子组态,使量子位元最高几率数值之间的差距,恰恰就是原本函数周期的整数倍,如函数的周期是4,量出来的差距可能是4、8、12。研究员只要测量这些差距,就能反推出函数的周期,破解古典密码学加密系统依赖的数学难题。

全球密码武林大会

幸好加密系统不只一两种,就好像武侠小说总会有武当派、峨嵋派等,各种派别都有自己的独门招式,加密系统也根据数学难题结构分成好几派,除了当红的RSA加密算法、椭圆曲线密码系统,还有晶格、调试修正码、多变量二次函数、散列函数及超通用椭圆曲线同源等。

为了因应量子计算机即将引爆的终极密码战,美国国家标准与技术局(NIST)自2016年起举办“后量子密码学标准化竞赛”,就如武林比武大会,要找出能抵御量子计算机的武林盟主,为后量子密码学时代的新标准。不过最后标准至少要有两个,分别用在数字签名和加解密,所以参赛者也很自然分成两组。

NIST负责推动美国的度量衡学、标准、技术,例如后量子密码标准化。因美国官方标准通常也会通行世界,此次密码学竞赛结果预测将决定未来全球密码学标准。(Source:NIST)

武林大会英雄帖一出,自然吸引全世界密码学高手前来较劲,而中研院信息所研究员杨柏因也是其一──他组了团队,以Rainbow算法参赛。在多变量二次函数这派别,杨柏因也算长老,这派的独门绝技就是多变量二次函数这个数学难题,也是杨柏因长期投入的主题。他和团队杀进这场武林盛会,Rainbow这个难题的核心,是要解一个多变量方程组,包括100个变量、64个二次方程组。

多变量二次函数问题的答案,没有周期性结构,不是量子计算机擅长的难题,因此在后量子密码学时代也拥有很好的安全性。

算法大乱斗

武林大会第一场比武是大乱斗──69组参赛者提出的算法,必须接受彼此攻击,如果被破解,代表安全性不够,这阶段就会被淘汰。杨柏因形容:“过程很像练蛊,最强的才能从瓮里爬出来。”2017年12月21日公布69组算法后,虽然紧接圣诞节,但才短短几天,就有不少算法被破解。“大概阿宅都不过节”,杨柏因笑称。一番厮杀后,Rainbow顺利通过考验,成为进入第二阶段的26组参赛者之一。

第二场比武要看算法的性能。一个派别的武功如果到了深山或森林等特殊环境就难以施展,就无法成为武林盟主。同理,NIST要求晋级团队将自家算法在一般计算机、计算能力较弱的微处理机、硬件芯片,都要能顺利运行,且效果不能太差。杨柏因解释:“在这阶段要做的是,保证Rainbow安全性的情况下,找出让它跑最快的参数。”

事实上,通常密码系统的复杂度可大可小,所以跑得较快的算法,相当于可修改成跑得跟其他算法一样快、但更安全的算法。

在现在的密码学,速度基本等同安全性,性能愈高,相当于实用安全性愈好。

第二阶段比武仍旧没有难倒Rainbow,一路过关斩将,Rainbow成了7组有资格站上决选擂台的候选者之一。此外,中研院信息科技创新研究中心,周彤助理研究员所属团队提出的Classic McEliece也和Rainbow一样是Finalist。7组Finalist中,中研院就占了2组,整体表现可是相当不错呢。

风雨过后见Rainbow

Rainbow晋级并非一帆风顺。Rainbow算法的关键部分,被来自中国的美籍学者丁津泰教授申请专利,当杨柏因要组队以Rainbow参赛时,曾询问丁教授是否同意“如Rainbow获选,将免费发布专利”。丁教授第一时间没有答应,后来杨柏因总算说服他,如果Rainbow获选,将放弃专利盈利。

密码学没什么非你不可,换句话说,一旦Rainbow包含一个没有发布的专利,这算法几乎不可能选上。

另一个插曲发生在第二阶段快要结束时,有人提出一个以前就有、针对Rainbow的攻击新研究,对方表示这个攻击比杨柏因的团队认为的更有效,杨柏因说:“我们重算一遍,对方说的没错,但即使照重算结果,对我们算法造成的影响也还好,只要小小调整参数即可。”后来杨柏因重新提交修改系统给NIST,有惊无险的过关了。

强敌:晶格算法

晋级最后阶段的除了7组候选团队,还有8组备选团队。总共15种算法,就有7种是“晶格派”。数字签名的3组决选者,除了Rainbow,另两组都是晶格派。晶格通常指物质内原子的规则排列,但此处指的是一个空间矢量构成的离散加法群。而“晶格派”背后的数学难题,则与空间矢量有关──若在一空间有N条矢量,要如何从这些矢量彼此加加减减中,得到最短矢量?只要矢量够多,这个难题一样复杂到让古典计算机一筹莫展,且还不像RSA算法可转换成答案有周期性结构的问题。

杨柏因承认,以目前后量子密码学的发展状况来说,晶格派是显学,原因在于以晶格算法产生出的公私钥、密文、数字签名等,长度约是现行RSA、椭圆曲线密码系统的十倍左右。相较之下,Rainbow产生的公钥长度是现行数百倍之长,这也是Rainbow所属派别最主要的弱点。

尽管有弱点,但Rainbow却很适合运用在根凭证的数字签名与验章,或是用在CPU的内码微程序更新这类应用。这类过程不需时常发送公钥,所以公钥长一点也无所谓。Rainbow数字签名与验章的速度,在候选系统中是最快的。

公钥长度很长是Rainbow的主要缺点,不过签章和验章都最快。

Rainbow的用途:数字签名

数字签名(digital signature)对信息安全的重要性,并不亚于公钥加解密。举例来说,当在研之有物网页买书时,除了不想让个人信息与研之有物传递时被黑客盗取,我们还得确定正在使用的网站真是研之有物,而不是黑客建造的假网站。

为了让购物的消费者安心,研之有物必须向第三方的凭证公司申请凭证,也就是请凭证公司证明“这个网站真的是我们,安啦!”研之有物必须提供自己的资料、自己的公钥给凭证公司,凭证公司确认后,就会在研之有物的公钥签数字签名,就好像盖印章。这数字签名只有凭证公司签得出来,其他人伪造数字签名成功的几率极小,只有2的128次方分之一。

消费者使用的浏览器,内置凭证公司的公钥,这个公钥可辨认数字签名(验章),一旦辨认成功,代表“研之有物网站是凭证公司验证过的,系金ㄟ!所以用户可以安心购物啦”。

凭证里的数字签名可认证网站的真实性,保障用户的信息安全。

传给读者的消息是凭证、公钥A、签章、其他辅助信息,但读者确认公钥A属于研之有物后,会用这个公钥A回传加密的“暂时性密钥”给研之有物,接下来双方就用这暂时性密钥互传信息。

“NIST说过,公钥加解密与数字签名会分开选择,而(两个组分别)决选出来的优胜者可能不只一个团队。”杨柏因说。即使NIST选择晶格为本的数字签名系统Falcon或是Dilithium,也有可能让Rainbow一起获选。数字签名的优异速度,可能成为Rainbow最终获选的优势。杨柏因也开始“超前部署”,正打算和信息工程专家合作,准备尝试将Rainbow放入实际网络应用,测试看看应用会不会产生问题。“Rainbow一旦成为新标准,我们马上就会需要这些东西。如果我希望Rainbow选上,应该准备实例支持。”杨柏因说。

Rainbow最后会否成为世界标准?“谋事在人,成事在天”,杨柏因对此很轻松,他说:“Rainbow的签章和验章运行表现数据确实最佳,但决定权还是在NIST手上。”身为尽责的研究者,“我会继续工作,包括继续研究Rainbow的安全性、测试Rainbow的实际应用状况,其他的就看NIST吧!”

事实上,杨柏因也加入另一个团队NTRU Prime,这队属于晶格派,且不是7组最终候选者,而是8组备选者之一,相当于进入败部,正在苦苦挣扎力争上游。他同样表示,尽力之后,就看老天爷(NIST)赏不赏光了。

(转载自研之有物)

发表评论