抗量子密碼技術漫談

2020-12-07 騰訊網

受持續升溫的量子技術的影響，抗量子密碼也成為人民大眾經常談起的話題。在正式的內容展開之前，讓我們先從兩個小故事來建立必須的基本概念。

故事1：一日去國家密碼管理局開會，行至門口遇到兩位散步的老兩口盯著門口的牌子在聊天。老爺爺說：「都說很多國家部門人浮於事，這次我算漲見識了，連密碼都要有一個專門局來管理」。老奶奶回覆說：「嗯，這也算是國家為老百姓著想，否則像咱們這樣經常忘記密碼的人該多痛苦啊，下次再忘了銀行存摺的密碼就來這個部門尋求幫助好了」。

概念區分1-密碼與口令：對於非密碼專業的人們，一般說到的密碼是指的我們登陸電腦、郵箱、微信、QQ等系統或應用的口令，或者銀行卡、網上轉帳等交易的口令。口令技術本身是一種基本的身份認證技術，用於識別用戶的合法性。在複雜的安全協議中，口令經常作為密碼算法的安全要素之一進行使用。本文介紹的密碼技術是一種基於數學或物理技術的信息變換技術，主要用於保護信息的機密性和完整性。通俗的說，就是防止壞人偷看我們的信息，防止壞人冒充好人進行通信或交易。密碼是一門古老的技術，其起源可以追溯到公元前四世紀，在兩千多年的發展歷程中一直是一種披著神秘面紗的軍事技術。隨著信息技術的不斷進步，在民用和商用領域強大需求的推動下，密碼技術逐漸走下神壇，從一種只有極少數人掌握的專用技術變成一種幾乎無所不在的信息防護之盾。從我們日常生活中的身份證、銀行卡、公交卡、手機、安防攝像頭，到工作中的電腦、數字政務系統、數字辦公系統、門禁，再到國家的基礎設施中的電力、交通等，信息技術所到之處均需要密碼技術的保駕護航。

故事2：今年科技周我們在軍事博物館擺了個展位科普抗量子密碼技術，一位來參觀的科技愛好者盯著我們簡陋的科普幻燈片認真思索了片刻之後向我詢問到：「潘院士已經修了京滬量子幹線，發射了墨子號量子衛星，你們為什麼還要做量子密碼呢？」

概念區分2-抗量子密碼與量子密碼：我們通常所說的抗量子密碼是指傳統密碼中可以抵抗量子計算攻擊的密碼算法，其安全性一般基於數學困難問題設計，目前主要包括格密碼、基於編碼的密碼、多變量密碼、基於散列函數的密碼、同源密碼等類型。而量子密碼是指基於量子力學的物理原理設計的密碼，其安全性基於不可克隆、測不準原理等物理原理，目前主要包括量子密碼交換（QKD）。在應用方面二者最顯著的區別是抗量子密碼算法可以運行於經典的計算機和通信系統之上，而量子密碼需要部署於量子通信和計算系統之上。

量子計算機為什麼能夠攻破現在的密碼？

作為一種攻防對抗型的技術，基本哲學原理決定了不存在絕對安全的密碼技術，所有的安全性都有其前提條件。當前應用最廣泛的密碼算法之一RSA，基於的前提條件是大整數分解問題的困難性。雖然我們讀小學的時候已經掌握了因子分解的技能，可以把一個整數拆解為一些素數的乘積，然而當這個整數非常大的時候，這個問題就變得非常複雜。

舉個例子，如果一個600位的十進位大整數包含了兩個300位左右的素因子，我們要找到這兩個素因子，即使動用每秒能算10億億次的神威太湖之光巨型計算機也需要計算10億年的時間才能找到答案。

量子計算機與傳統的電子計算機的最大區別在於量子態疊加性質使得單個量子比特可以同時表示0和1兩種狀態，隨著量子比特數的增加其能夠表達的數據呈現指數級增加，例如1024個量子比特可以同時表達2^1024個數據。這就使得量子計算天然具備指數級的並行計算能力，可以輕鬆解決指數級數據空間的搜索問題。因此，基於量子計算的Shor算法可以輕鬆破解原本非常困難的因子分解問題和離散對數問題，從而攻破目前使用的RSA算法和ElGamal算法。

量子計算機什麼時候能夠攻破現有的密碼？

按照最原始的Shor算法估計，破解2048比特的RSA算法需要2048*3個量子比特的通用量子計算機。根據公開的數據，目前技術進展最順利的超導量子計算機還停留在20-70個量子比特之間，而且尚未完成糾錯和全糾纏等運行Shor算法需要的功能。提升量子比特的數目和量子糾錯都帶來巨大的技術挑戰。根據谷歌最新公布的糾錯技術估計，破解2048位的RSA算法需要2千萬個物理比特。因此，目前尚無法精確預測量子計算機什麼時候能夠真正破解RSA。

然而，密碼算法的生命周期非常長，例如根據歐盟的標準數據需要50年的保密期，再考慮到制訂和推廣密碼算法標準需要5-10年時間，因此我們需要考慮的是量子計算機60年之後是否可以破解RSA。

三體小說中描述的故事告訴我們，智慧文明在科技的發展過程中會發生爆炸式增長，因此60年內能發生的技術進步是難以精確預測的。這就是歐美等國家決定啟動抗量子密碼算法標準徵集來應對量子計算威脅的原因。

D-Wave 2000Q

IBM Q System One

目前的抗量子密碼技術是否已經成熟？

雖然量子計算表面上具備了指數級的計算能力，可以對任何困難問題進行暴力搜索求解，但是最終想要的計算的結果也淹沒在指數級的數據之中，必須設計精巧的量子算法才能得到正確的結果。

目前對密碼算法產生影響的主要是Shor,Simon和Grover等算法，其中威脅最大的是Shor算法對公鑰密碼算法的多項式級破解。因此，目前國際上對抗量子密碼算法的研究主要集中在公鑰密碼領域。

在公鑰密碼領域除了工業界熟悉的RSA和ElGamal兩個類型的密碼算法之外，還有許多其他的類型，其中有五種類型的公鑰密碼算法尚未發現有效的量子計算攻擊，它們被統一稱為後量子密碼算法，包括：格密碼、基於編碼的密碼、多變量密碼、基於散列的數字籤名、同源密碼。

這些密碼算法中基於編碼的密碼和基於散列的數字籤名已經有40年的研究歷史，多變量密碼已經發展了30多年，格密碼和同源密碼已經發展了20多年。這些密碼算法的設計與分析理論已經取得了許多成果，在量子計算複雜性分析方面尚未完全成熟，經典安全性和效率已經接近實用化需求。在國際標準化需求的大力推動下有望在未來3-5年內取得較大發展，最終形成實用化的密碼算法標準。

在抗量子密碼技術方面我們與國際先進水平相差有多大？

在抗量子密碼領域歐美起步早，做出了大量原創性成果，我國在該領域起步較晚，缺乏原創性成果，這些差距很難用精確的距離來描述。需要指出的是，缺乏原創性成果並不會從根本上阻礙我國推動抗量子密碼算法的標準化和產業應用，正如我國在移動通信領域的原創性成果缺乏並未阻礙華為公司在5G應用方面的國際領先地位。

目前，在抗量子密碼算法標準制訂和產業推廣方面美國NIST走在最前面，美國NIST於2009年發布了後量子密碼算法的綜述，2012年正式啟動後量子密碼算法標準項目，2016年發布後量子密碼算法徵集公告，評估工作分為3輪進行，每輪18個月左右，預計2024年之前完成。

在徵集過程中，NIST共收到來自全球的82份提案，經過審查有69個算法符合要求進入第一輪評估，2019年初發布了進入第二輪評估的26個算法。這些候選算法來自全球各國，其中歐洲是最大的來源地，歐盟的PQCRYTO項目是該領域的旗艦型項目，第一輪的69個候選算法有22個來自該項目組，第二輪的26個有15個來自該項目。

歐美之間的合作非常密切，所以很多算法是來自歐美公司、科研機構、高校聯合設計的。中國團隊是首次參加這類活動，短時間內無法完成設計、分析、實現的全部工作，因此最終只有3個團隊提交了算法，只有1個算法進入了第二輪評估。

美國NIST後量子項目

歐盟ETSI量子安全計劃

量子計算會對整個密碼領域帶來什麼樣的影響？

從公元前四世紀到二戰的機械密碼，到電子計算機興起之後的現代密碼再到目前量子計算技術推動的抗量子密碼，密碼學的發展一直與整個人類的科技進步密切相關。從密碼學科發展的角度來看，量子計算是圖靈炸彈之後推動密碼學發展的又一次裡程碑式的事件。

雖然通用大規模量子計算機的研製還困難重重，但是量子計算對基礎複雜性理論帶來的革命性變化足以促使密碼算法設計與分析理論迎來一次大的飛躍。從基礎的計算複雜性理論到形式化的安全性證明理論都將受到量子計算的影響，密碼學家需要在量子計算環境下重新構建密碼學的大廈。

作者：路獻輝 / 中國科學院信息工程研究所

來源：中國科學院北京分院

編輯：時小七

相關焦點

  • 潮科技丨國際抗量子密碼發展現狀(一)
    編者按：本文來自微信公眾號「量子計算最前沿」（ID：QC-Frontier），作者QC仔，36氪經授權發布。 隨著量子計算技術的不斷進步，基於經典計算複雜性理論的現有密碼算法安全性受到了嚴重威脅，制訂下一代抗量子計算的密碼算法標準已經成為保障未來量子計算環境下網絡空間安全的重要任務。
  • 中國抗量子密碼算法有望四年後開始標準化
    6日，由歐洲電信標準化協會主辦的第六屆量子安全國際會議在京開幕。會上，中國科學院信息工程研究所副所長荊繼武表示，中國或將於2022年左右開展抗量子密碼算法標準化工作，於2025年左右實現商業化應用落地。所謂抗量子密碼算法，抗的就是量子計算機。量子計算機的信息單位是量子比特。
  • 擔憂中國量子科技優勢，美國計劃構建抗量子密碼體系
    就在近日，中國科學家成功驗證了光量子計算機——九章的「量子優越性」，成為繼美國之後，第二個實現「量子霸權」的國家。根據報導，中國的光量子計算原型機其運算速度要遠高於美國去年實現量子霸權的谷歌的量子計算機。
  • 近代量子理論若干專題漫談
    >主講人：張永德教授（中國科學技術大學）教育及工作經歷：1955年進入北京大學物理系，1959年畢業於北京大學技術物理系 教學情況：主講《量子力學》、《量子力學專題》、《高等量子理論》、《近代量子理論中疑難爭議問題》、《高等量子理論專題》、《多道散射量子理論》、《量子場論（上、下）》、《量子場論專題》、《泛函積分量子場論》、《量子信息物理原理》、《量子資訊理論專題
  • Hcash:見證量子計算和後量子密碼的「矛盾較量」
    今天，量子計算的落地速度正在超出很多人的想像，如果稍有不慎，將對現有公鑰密碼體制帶來毀滅性的打擊，網際網路世界甚至也將蕩然無存。不過，Hcash正在見證量子計算和後量子密碼的「矛盾較量」，甚至在區塊鏈的競爭中通過後量子密碼的技術突破獲得競爭優勢。
  • 量子十問之五:量子密碼就是量子通信嗎?
    (圖片來源於網絡)量子密碼的研究已有30多年曆程，目前達到的實際水平是：在百公裡範圍的城域網，量子密碼體系可以做到密鑰分配在現有技術保證的各種攻擊下是安全的，安全密鑰生成率在25 公裡可確保高清視頻「一次一密」，在100 公裡內能確保音頻、文字、圖片等的「一次一密」。因此可以制定「量子密碼標準」，推廣應用。
  • 抗量子計算加密標準將於2022年發布
    美國國家標準技術研究所（NIST）近日宣布，三年多的抗量子加密算法第二輪評審已經結束，評委會對入圍第二輪的26個提議方案進行了評判，最終確定為15項。NIST早在2016年4月就發布了抗量子密碼技術現狀的報告，隨後於2016年12月進行了跟進，呼籲公眾提交可能抵禦量子計算機「暴擊」的後量子算法。
  • 都說量子計算下密碼都是渣,所以清華突破後量子密碼硬體加速技術
    隨著近幾年來量子技術的研究以肉眼可見的速度在發展，我們很多人開始對於量子計算、量子計算機有了初步的了解。量子計算的強大，我們都是時有耳聞。即便我們都沒遇到過量子計算的演示，但一人客覺得我們從科普和技術資訊和嚴肅書籍文章上也能見微知著，明白它的極強算力，在我們目前傳統計算機領域，面對世界頂級最快的計算機量子計算都是王者一般的存在。可以這麼說，現有的一切傳統計算機在量子計算機（由當前理論研究推演）面前都是小弟，一切密碼——哪怕你再複雜位數再長——在量子計算下都會被秒成渣。
  • 量子計算機破解密碼誰能防？國內首份量子安全白皮書發布
    這意味著，基於量子物理的「量子密碼技術」（包括量子密鑰分發QKD和量子隨機數等）與基於新型數學難題的「抗量子計算密碼技術」（PQC）這兩種技術路線探索融合發展已經邁開腳步。量子時代的信息安全經典密碼通常依賴於計算複雜性，在量子計算機面前或會失守，或是安全性有所下降。而量子安全技術指的是能夠抵禦量子計算威脅的信息安全技術。
  • 量子密碼是量子通信嗎?其實真正的量子通信離實際應用還很遠
    (圖片來源於網絡)量子密碼的研究已有30多年曆程，目前達到的實際水平是：在百公裡範圍的城域網，量子密碼體系可以做到密鑰分配在現有技術保證的各種攻擊下是安全的，安全密鑰生成率在25 公裡可確保高清視頻「一次一密」，在100 公裡內能確保音頻、文字、圖片等的「一次一密」。因此可以制定「量子密碼標準」，推廣應用。
  • 多國軍隊推進量子密碼技術:未來戰爭「神器」!
    （原標題 量子密碼：未來戰爭「神器」）　　自軍事通信使用密碼技術以來，無論是戰時還是平時，各國軍隊圍繞密碼破譯與反破譯的鬥爭就一刻沒有停止過。以量子力學為理論基礎發展起來的量子信息技術衍生出量子密碼和量子計算，前者從理論上提供一種不可截獲和破譯的絕對安全的新型密碼體制，而後者極其強大的並行計算能力可以輕易破解基於數學問題的經典密碼體制。因此，誰先搶佔這一技術領域的戰略制高點，誰就能把握決定未來信息化戰爭勝敗的關鍵因素。
  • 在量子計算機到來之前,請準備好抗量子破解的密碼學
    如果量子計算在未來取得突破性進展，一直守護著網際網路的安全系統將變得岌岌可危。世界從此會變成怎樣？第一個研發出實用量子計算機的政府或機構將會得到整個世界的秘密嗎？事情並沒有想像中那麼糟糕。事實上，即便有了量子計算機，許多經典的保密算法仍將是有效的，更何況量子保密技術也在蓬勃發展。
  • 後量子時代公鑰密碼取得重大進展 中國量子通信工程恐成擺設
    2020年7月22日是公鑰密碼技術發展史上的又一個重要的裡程碑，美國國家標準與技術研究院(NIST)公布了進入第三輪評審的七種後量子時代公鑰密碼算法，引起了國際密碼學界的高度關注[1]。公鑰密碼目前是足夠安全的，但是量子計算機的進步和傳統電子計算機的飛速發展對公鑰密碼的未來安全投下了陰影。
  • 量子技術窮追不捨
    但是有了合適的量子計算機，能夠以指數級的速度處理信息嗎?突然間，看似堅不可摧的東西變得輕而易舉，不到 10 分鐘就能被破解。對加密貨幣來說，量子計算問題並不新鮮，許多專家認為，我們至少還要十年或更長時間才能提出抗量子密碼學。然而，一些觀察人士表示，近期的快速進展可能大幅縮短這一時間。最激進的估計是，到 2027 年比特幣將會被攻破。
  • 日媒:全球競相開發量子密碼技術 商務軍事或迎變革
    據參考消息網7月18日報導援引日媒報導，可以防止通信數據被監聽的量子密碼新技術正備受關注。這是史上最強的、利用光子的密碼技術。如果量子密碼技術實現實用化，則必將引發商務和軍事等領域的巨大變革。各國正不遺餘力地進行開發競爭。 量子密碼通信的理論模式是，發送方首先將用於解讀密碼文的「密匙」信息寫入一粒光子並發送給接收方。
  • 日本開始大規模開發新一代密碼技術「量子加密通信」
    日本將在本月開始一個大規模開發項目，此項目參加者包含眾大企業及大學，以被稱為「量子加密通信」的新一代密碼技術於世界上的拓展為目標。 在網絡上，各種各樣的數據被加密在進行傳輸通信，如果能全面使用計算能力遠超超級電腦量子計算機，現今的密碼就能很簡單被解讀，因此世界上正加速開發新一代的密碼技術「量子加密通信」。
  • 日本使用量子密碼通信技術傳送人類基因組實驗成功
    據日本《共同社》獲悉，日本東芝公司和日本東北大學東北Medical Megabank機構（仙臺市）近日宣布，成功開展了利用可防止信息被偷窺的新一代技術「量子密碼通信」傳送人類遺傳信息（基因組）完整數據的實證試驗。
  • 後量子密碼晶片構架出現，公鑰密碼將被取代
    近日，有媒體報導稱，清華大學魏少軍、劉雷波教授的科研團隊在第 22 屆密碼硬體與嵌入式系統會議（CHES 2020）上發表了後量子密碼硬體構架的相關論文報告。據悉，該論文報告屬於國際後量子密碼晶片領域，提出了後量子密碼算法的新型構架。該論文的第一作者是清華大學博士生張能，這也是中國大陸的科研人員首次在該領域論文報告中擔任第一作者的身份。
  • 院士說丨王小雲院士:密碼技術與區塊鏈
    中國科學院院士，國際密碼協會會士(IACRFellow），清華大學高等研究院「楊振寧講座」教授王小雲發表《密碼技術與區塊鏈》主題演講，她認為密碼技術解決信息安全性，哈希函數保障數據完整性，哈希函數和數字籤名算法一起保障可認證性和抵賴性。其中，哈希函數與區塊鏈關係十分密切，保障了區塊鏈的安全性。
  • 技術領先被認可 中國或主導量子密碼國際標準制定(附股)
    來源：金融界網站據《日本經濟新聞》6月13日報導，中國將主導防止機密信息被第三方監聽的新一代密碼技術「量子密碼」的規則制定。中國提出制定量子密碼安全的國際評估標準的構想，已經獲得國際標準化組織（ISO）批准。