量子电脑到底有多霸气?终极「密码战」即将引爆?

 

量子电脑与密码学

2019年10月Google宣布实现「 量子霸权 」,全世界都惊呆了!量子电脑已经无所不能了吗?其实量子霸权的意义在于:人类已经让量子电脑做到一件古典电脑很难达成的事。不过,量子电脑的进度条的确正快速更新,未来可能带给人类巨大的福祉,但也会颠覆现今保护我们隐私的加密系统。

中研院资讯科学研究所钟楷闵副研究员,形容密码学就像一场好人与坏人的战争,站在量子密码学研究前缘的他,将为研之有物的读者揭密这场没有烟硝的资安保卫战。

《量子电脑到底有多霸气?终极「密码战」即将引爆?》

中研院资讯科学研究所钟楷闵副研究员,专长为理论计算机科学、量子密码学、量子复杂度理论……换成白话,就是一位在资讯科学所用理论/ 数学研究方法研究资讯科学的科学家,专攻量子计算如何影响密码学,及其潜力与极限。
摄影│林洵安

量子电脑跟传统电脑差在哪?

量子电脑和传统电脑的不同,在于它利用了各种神奇的量子特性,也就是当我们以微观的角度观察这个世界时,那些与巨观世界不同的特性,像是让薛丁格的猫介于死和没死之间的「 叠加态 」,或是两个量子即使相距很远,仍旧会依据对方状态而决定自己当下状态的「 缠结效应 」。 (有关量子效应可参考「研之有物」相关文章量子电子元件hen夯,但如何掌握像情人心难测的量子位元? )当电脑拥用这些比科幻还科幻的量子特性,将克服古典电脑无法解决的难题。

不过,钟楷闵立刻猛划重点强调:

量子电脑不是无所不能,或是每秒钟能做的事情比较多,它只在某些「特定(但很重要)问题」上,有比古典电脑更快的解法,只需要更少的空间和步骤。

举例来说,未来量子电脑可能用于模拟细菌的固氮作用 ,将大大提升农业上制造氮肥的效率。因为细菌进行固氮作用时,有些关键步骤具有量子效应,模拟这些效应的复杂度将超越了古典电脑的极限。而量子电脑「刚刚好」是以量子效应运作,当然较有希望成功。

不幸的是,量子电脑可攻克的「特定问题」,也包括时刻保护我们交易安全和隐私的加密系统……

坚不可摧的加密系统

登入网购平台,输入帐号密码,选好商品放入购物车(又剁了好几根手指)之后,再填好地址及电话,按下结帐,输入信用卡卡号,接下来只要等商品来到家门口,啊~多美好的日常……等等,你算过在刚刚那五分钟里,亲手传出多少个人资讯吗?这个问题细思极恐,事实上不必太担心,因为密码学正默默保护着我们。

早在两千年前凯撒大帝打仗时,就懂得使用「暗号」来保护军事书信。只有知道暗号的人可以「解读」信件内容,对于不知道暗号的敌人来说,就算拿到书信也只是一堆乱码。

但这套方式有个致命伤,那就是「如何一开始让所有合法的使用者拿到一样的暗号,又不会让暗号外泄呢?」当代的密码学家想出一套称为「 非对称加密 」的方式,利用成对的公钥和私钥来加密暗号,公钥就像是一个盖上就锁住的盒子,私钥是可以打开这个盒子的钥匙。如此一来,就能让素昧平生的合法使用者,先利用比较安全的非对称加密传递暗号,接下来就能靠暗号秘密通讯了。当你登入网购平台买东西,你的电脑和平台之间的通讯,就是透过类似的方式保护你的个资。

举例来说,当顾客登入网路书店,申请刷卡购买「研之有物」的新书。网路书店会立刻制造一对公钥和私钥,把公钥传给客户的电脑。客户端的电脑再将自己的暗号,以公钥加密后传回网路书店。坏人没有私钥,就算中途拦截了信息也无法破解。最后,网路书店用私钥解密,得到客户的暗号,接下来就可以靠暗号传送信用卡卡号等个资了。

《量子电脑到底有多霸气?终极「密码战」即将引爆?》

细心的读者可能会有疑问:那为什么不直接把所有讯息透过非对称加密传递,还需要先传暗号,再用暗号保护讯息呢?原因在于,非对称加密的效率非常低,而透过暗号加密(称为对称式加密)的效率很高。因此,目前网路架构中,仅利用非对称加密传递短短的暗号,接下来主要的通讯就使用高效率的对称式加密。
图说设计│ 林洵安、黄晓君

当然,网路上并不是真的有一个盒子在传输!目前的加密系统能如此安全,关键是它的核心有一个难以解开的数学难题,需要公钥加上私钥才能解开。所以即使坏人拿到加了密的讯息,没有私钥还是解不了密码。

这类数学难题很多,像是超大数字的质因数分解。随机找两个很大的质数相乘,比如97 乘上113 ,就会得到一个超大数字10961 ,很简单吧?但是,如果一开始给你10961,你算得出它是哪两个质数相乘吗?

这不是国小老师偷懒没教,而是人类还没找到有效率的方法(多项式时间的演算法)来计算质因数分解这类问题。所以理论上,只要数字够大,即使是全世界性能最强大的超级电脑,也可能花费上万年才能破解。

简言之,加密系统核心的数学难题愈困难,古典电脑就需要花愈长的时间破解,加密系统也就愈安全。

破解古典密码,量子电脑hen会

然而,现今密码学看似坚不可破的数学难题,在量子电脑的面前变得不堪一击。因为这些问题的答案都可以转化成周期性的结构,刚好量子电脑擅长破解。 (哭哭)

什么是周期性结构?再以质因数分解问题举例:想要找出N 这个数字是由哪两个质数(P 与Q) 相乘所得,可以先任意选择一个数字A ,用A 去除N ,得到一个余数a1 ,接下来依序用A2 、 A3 、 A4 ……不断地除N ,就会得到余数a1 、 a2 、 a3 、 a4 ……最后某一次的操作,余数会回到a1 ,形成周期性的结构。一旦能找到周期,就能「比较有效率」的分解N。

不过,对于古典电脑来说,当数字相当巨大时,寻找余数的周期仍是十分困难的任务,但对于具有叠加作用的量子电脑,却是小事一桩。

总之,目前我们所仰赖的加密系统,在量子电脑出现之后将变得不再安全……可是IBM 、 Google 不断更新量子电脑发展的进度条,我们已经暴露在资讯外泄的风险之下了吗?

别担心!小亚瑟还没长成恶魔小丑

其实,量子电脑目前还只是个婴孩阶段。以Google 用来实现量子霸权的量子电脑来说,只有53 个位元。

相较古典电脑,早在1970 年即已发布Intel 1103 ,为容量1 kb (1024 位元) 的记忆体。 「古典电脑如果只有53 个位元的记忆体,连程式都没办法写,英文字母只能存7 个,可以想像现在的量子电脑Size 有多迷你。」钟楷闵笑着继续解释:「而且如果把Google 做的事情画成一个量子电路,这台电脑能执行的电路深度最多只有20 层。」翻译成大白话,意思是:每个位元只能运算20 次!

「20 次?!这么少?」你发现重点了!量子位元操作时很容易受到环境影响而坏掉, 20 次的操作已是目前的极限。

《量子电脑到底有多霸气?终极「密码战」即将引爆?》

Google 公布的53 个位元量子电脑。上图每个灰色X 皆是一个量子位元,白色的X 是坏掉的量子位元,下图为几公分大的量子电脑晶片,量子位元统统挤在这小小的晶片中。
图片来源│《Nature》

不只如此, Google 这次霸气外漏的宣告,他们让量子电脑做的事情,其实是……模拟量子电脑自己! 「哈哈,这题目有点作弊嫌疑啦!不过,这依然是一个很重要的结果,证明了即使现在量子电脑这么小,已经可以做到一件古典电脑做不到的事了。」钟楷闵笑着解释。

这个任务有多难?如果古典电脑试图模拟同样的量子系统,必须先将量子态用0 与1 记录下来,再计算这些0 与1 经过20 次量子运算会有什么改变,最后才能得到结果。可是古典电脑光是要把这53个量子位元的状态写下来,就需要2 53个位元的空间,更别提运算和模拟了!根据Google 论文宣称,古典电脑要完成这件事得花一万年,但这台小小的量子电脑只需花200 秒。

Google实验的意义在于:我们已经可以控制53个量子位元完成20次的操作,这是一件目前古典电脑做不到的事。

但是,这距离真正「有用」的量子电脑还有很远的路!拿量子电脑模拟细菌固氮效应来说,量子电脑得拥有100个左右的量子位元,并且可以运算操作10 14次……。想想,Google 的量子电脑只有53 个位元不说,而且只能操作20 次,简直天壤之别!至于量子电脑破解现在的加密系统,根据专家预测,嗯……至少还要30 年的时间。

终极密码战,现在就开打!

虽然如此,但密码学已深入现代生活的层层面面,不早点找出应对之策,届时可就来不及了。想想全世界在千禧年危机的手忙脚乱、损失惨重……

从2017年起, 美国国家标准暨技术研究院 (NIST)开始着手「后量子密码标准化计画」,募集全世界密码学家研发、可对抗量子电脑的密码系统。这些密码系统的核心同样有个数学难题,但这个难题无法转化成量子电脑擅长的周期性问题,中研院资讯所杨柏因研究员团队也参与这个计画,并通过第二轮选拔。

「整个过程就像选秀节目一样,」钟楷闵笑着形容:「主办单位先海选出合适的密码系统,然后经过两轮筛选,订定标准化的各项参数,预计在2022 ~ 2024 年间公布最终标准。」

简言之,在3-5年后,我们很可能就会开始逐步更新密码系统,正式进入「后量子时代」。

这场密码学的竞赛,就像好人与坏人的战争。究竟是坏人会先利用量子电脑破解加密系统,击溃目前的资讯安全网,还是好人会先做出安全的后量子时代加密系统,筑起更安全的防御墙,关键就在这几十年量子电脑的发展。

科技进步不会停止,在量子电脑发展过程中,密码学家正努力追赶进度,为人类预先设下资讯安全网。下次在网路上输入个人资料时,不妨感谢一下在萤幕后头默默努力着的密码学家们(合十)。

原来量子电脑还在婴儿阶段,只能运算20次啊……想要它的运算次数快速成长,有没有什么好办法?

其实,不太可能期待一个量子态经过多次的运算操作还不会坏掉,所以我们应该换一个概念:当做了一定的计算,量子态开始有一点点坏掉时,立刻修复它。换句话说,如果能成功帮量子位元随时除错,那它的计算次数就可以无限多。

为此,科学家正在研发如何替量子位元编码,变成「逻辑量子位元」。所以有人认为,量子电脑的下一个目标,应该是先实现逻辑量子位元。

另一种有趣的想法是,如果把操作有限的小型量子电脑,配上古典电脑,也许可以相当于大型量子电脑……

小型量子电脑+古典电脑=大型量子电脑,这个点子感觉有戏!

可惜的是,没有这么便宜的事!我的团队最新的研究,在某个模型下,反驳了英国密码学家乔兹萨(Richard Jozsa)提出的类似想法「乔兹萨猜想」。

乔兹萨猜想的意思是:所有可以被大型量子电脑解决的问题,运算步骤都可被拆解,然后由小型量子电脑(只能进行少数次数操作)搭配上古典电脑解决。如果这样的猜想为真,意味着不需要强大的量子电脑(能够进行很多次操作),只要小型量子电脑和古典电脑合作,也能解决所有大型量子电脑可以做的事。

《量子电脑到底有多霸气?终极「密码战」即将引爆?》

资料提供│钟楷闵图片重制│林洵安

我的团队则在密码学的一个「 预言机模型」 (oracle model)下提出一个问题,证明量子操作次数不够多的时候,这个问题无法解开,为这个猜想找到了一个反例。

真可惜……除了量子电脑本身,钟老师对于量子密码学还在进行什么研究呢?

我另一项研究重点,与密码学的安全性证明有关。前面说过,密码系统的核心是一个数学难题,换句话说,一个密码系统的安全性必须仰赖这个数学难题是无法被破解。

我们可以用数学来证明这些密码系统的构造有多安全,但对应的量子版本我们还在研究中。

因为愈好的证明,愈能确保加密系统的安全性。尤其在NIST 正如火如荼找出后量子时代加密系统的现在,我们能做到多好的证明,也会影响标准化的参数要怎么设定,才能满足运算速度够快,但又非常安全的需求。这是现代密码学家非常重要的任务。

点赞

说点什么

avatar
  Subscribe  
提醒