文章閱讀頁通欄

河南22选5第2019175期:后量子密碼指南

來源: 格密鏈 作者:
對于TLS(安全傳輸層協議)流量、醫學數據庫和區塊鏈等許多高安全性應用而言,前向保密(forward secrecy)是絕對必要的。同時,僅僅阻止攻擊者立即解密......
對于TLS(安全傳輸層協議)流量、醫學數據庫和區塊鏈等許多高安全性應用而言,前向保密(forward secrecy)是絕對必要的。同時,僅僅阻止攻擊者立即解密敏感信息是不夠的。本文的威脅模型包含了這樣一種情況:攻擊者在收集密文之后,可能會花費多年時間來解密密文。在這種情況下,密文的保密性很可能被打破。例如,增加的計算能力和數字理論的突破都會使得攻擊當前的密碼學體制變得相對容易。然而,除非有人找到一個多項式時間內的算法來分解大整數,否則這種風險對于當前密碼學的最佳實踐來說是最小的。所以,我們應當更加關注量子計算機,因為它的成功開發將使我們今天使用的大多數加密技術變得不安全。

1、量子計算入門

量子計算機不僅僅是大規模并行的經典計算機。通常認為,由于一個量子比特可以同時占據0和1,那么一個n位量子計算機可以同時處于2n個狀態,因此計算NP-complete問題的速度非???。但事實并非如此,因為測量量子態會破壞大部分原始信息。例如,量子系統可以完全知曉一個物體的動量和位置,但是任何動量的測量都會破壞關于位置的信息,反之亦然。這就是海森堡不確定性原理。因此,實用的量子算法必須包括一系列量子比特的變換,這樣,在計算結束時,測量系統的狀態就不會破壞所需的信息。事實上,已經表明,不存在任何量子算法可以同時嘗試解決某些NP-complete問題并輸出正確的輸入?;瘓浠八?,任何解決經典困難問題的量子算法都是利用手邊的困難問題構造的特定算法。目前,有兩種這樣的算法可以用于密碼分析。

快速分解大整數的能力將破壞RSA和基于離散對數的密碼學。整數分解最快的算法是通用數域篩選法,它在亞指數時間內運行。然而,在1994年Peter Shor發明了一種量子算法用于整數分解,該算法在多項式時間內運行,因此能夠打破任何RSA或基于離散對數的密碼體制(包括那些使用橢圓曲線的)。這意味著,如果有人建立了量子計算機,所有廣泛使用的公鑰加密都是不安全的。

第二個是Grover的算法,它的時間復雜度為O(√n)。這種算法將從根本上降低對稱密鑰加密的安全性,因此AES-256將只提供128位的安全性。同樣,找到256位哈希函數的原像只需2128次。由于將哈希函數或AES的安全性提高兩倍并不是很麻煩,所以Grover的算法不會對對稱密碼體制構成嚴重威脅。此外,量子計算機的發明不會影響用于加密的所有偽隨機數生成器,除了由Grover的算法引起的O(√n)因子。

后量子算法的分類

后量子密碼學研究的是可以在經典計算機上運行的密碼體制,但即使對手擁有量子計算機也是安全的。最近,NIST發起了一項后量子密碼標準化的進程,目前正在審查第一輪提交的文方案。這些提交的方案中最有希望的是那些基于格(lattices)、isogenies、哈希函數(hash functions)和編碼(codes)的密碼體制。

河南22选5第202期开奖 www.lyedr.com 在深入研究每一類提交的方案之前,我們簡要地總結了每種密碼體制固有的權衡,并將其與當前(非后量子)橢圓曲線密碼學進行了比較。請注意,編碼和isogenies是能夠設計數字簽名的,但沒有向NIST提交這樣的方案。

在安全性證明方面,上述任何一種密碼體制都不能歸約到NP-hard(或NP-complete)問題上。就格和編碼而言,這些密碼體制是基于輕微修改的NP-hard問題?;詮:拿藶胩逯埔覽滌諏己玫墓:?,并且無需其它的加密假設。最后,基于isogenies的密碼體制是基于一個被推測為很難的問題,但與NP-hard問題或之前的加密假設不同。然而,值得一提的是,正如我們不能證明任何經典算法在多項式時間內都是不可破解的(因為P可以等于NP),同樣這也是量子計算機所面臨的難題。此外,一個不能歸約為NP-hard或NP-complete問題的密碼體制并不意味著就要放棄它,例如整數分解和離散對數問題,它們并不被認為是NP-complete問題。

2、格

在所有后量子密碼體制中,格是研究最活躍和最靈活的。它們具有很強的安全性,能夠進行密鑰交換、數字簽名,以及構造出像全同態加密這樣復雜的算法。盡管格密碼體制的優化和安全性都需要非常復雜的數學證明,但基本思想只需要基本的線性代數。假設你有一個如下線性方程組:


求解x是一個經典的線性代數問題,可以用高斯消元法快速求解。另一種思考方式是我們有一個神秘的函數,

給定向量a,我們在不知道x的情況下,得到了ax的結果,在查詢這個函數足夠多次之后,我們可以在短時間內學習f(通過求解上面的方程組)。通過這種方式,我們可以將線性代數問題重新定義為機器學習問題。

現在,假設我們在函數中引入了少量噪音,即在x和a相乘之后,我們加上一個誤差項e,然后整體模上一個(中等大小的)素數 q,最后我們包含噪音的神秘函數看起來是這樣的:


學習這種帶噪音的神秘函數已經在數學上被證明是極其困難的。直覺告訴我們,在這種情況下使用高斯消元,它的每一步都會使誤差項e變得越來越大,直到它超過關于函數的所有有用信息。在密碼學文獻中,這被稱為錯誤學習問題(LWE)。

基于LWE的密碼學之所以被稱為是基于格的密碼學,是因為LWE的困難性證明依賴于這樣一個事實,即在格中找到最短向量,已知它屬于NP-hard問題。在這里,我們不會深入討論格的數學問題,但我們可以把格看作是n維空間的平鋪圖:

格是由坐標向量表示的。在上面的例子中,通過結合e1、e2和e3(通過法向量加法)可以到達格中的任何點。最短向量問題(SVP):給定一個格,找到向量長度最短的元素。這很難直觀的原因是因為并非所有給定格的坐標系都同樣易于使用。在上面的例子中,我們可以用三個非常長且非常接近的坐標向量來表示格,這使得找到接近原點的向量變得更加困難。事實上,有一種規范的方法可以找到格的“最壞可能”表示。當使用這種表示時,已知最短向量問題為NP-hard問題。

在討論如何使用LWE進行抗量子密碼研究之前,我們應該指出的是LWE本身并不是NP-hard問題。它不是直接歸約為SVP,而是歸約為SVP的近似值,根據推理,它實際上不是NP-hard問題。盡管如此,目前還沒有多項式(或次指數)時間內的算法來求解LWE。

現在讓我們使用LWE問題來構建一個實際的密碼體制。最簡單的方案是由Oded Regev在他最初的論文中構造的,同時他也證明了LWE問題的困難度。這里,密鑰是一個n維的整系數模q的向量,也就是上面提到的LWE私鑰。公鑰是前面討論的矩陣A,以及LWE函數的輸出向量。

這個公鑰的一個重要特性是,當它乘以向量(-sk,1)時,我們得到誤差項,大約為0。

為了加密一位消息m,我們取A的隨機列之和,并在結果的最后一個坐標中編碼m,即如果m為0,就加0,如果m為1,就加q/2?;瘓浠八?,我們選擇一個元素為0或1的隨機向量x,然后計算:

直觀地說,我們已經求解了LWE函數(我們知道它很難被破解)的值,并在這個函數的輸出中編碼了m。

解密是有效的,因為知道了LWE私鑰就將允許接收方收回消息,外加一個小的錯誤項。

正確選擇錯誤分布后,它將不會使消息失真超過q/4。接收方可以測試輸出是否接近于0或q/2 mod q,并相應地解碼出m。

該體制的一個主要問題是它需要很大的密鑰。要加密一位消息,需要在安全參數中使用大小為n2的公鑰。然而,格密碼體制的一個吸引人的方面是它們的速度非???。

自從Regev的第一篇論文發表以來,圍繞基于格密碼體制的研究進行了大量工作。其中關于改進其實用性的一個關鍵突破是Ring-LWE,Ring-LWE是LWE問題的一個變體,其中密鑰是由若干多項式表示的。這導致了密鑰大小的二次減少,加速了加密和解密,僅使用n*log(n)次操作(使用快速傅立葉變換,FFT)。

NIST PQC標準考慮了許多基于格密碼體制的方案,特別值得一提的兩個基于格構造的方案是Kyber和Dilithium。

Kyber是一種密鑰封裝機制(KEM),它遵循與上述系統類似的構造,但是使用了一些奇特的代數數論來獲得比Ring-LWE更好的性能。對于合理的安全參數,密鑰大小約為1kb(仍然很大),但加密和解密時間大約為0.075毫秒??悸塹秸庵炙俁仁峭ü砑迪值?,Kyber KEM似乎很有希望用于后量子密碼中的密鑰交換。

Dilithium是一種基于與Kyber類似技術的數字簽名方案。它的細節超出了本文的范圍,但值得一提的是,它也實現了相當不錯的性能。公鑰大小約為1kb,簽名為2kb。這也非常高效。在Skylake處理器上,計算簽名所需的平均周期約為200萬次。驗證的平均周期為39萬次。

3、編碼

糾錯碼的研究在計算機科學文獻中有著悠久的歷史,可以追溯到Richard Hamming和Claude Shannon的突破性研究。雖然我們甚至無法在一篇簡短的博文中觸及這一深層領域的表層,但我們給出了一個快速的概述。

在傳遞二進制消息時,錯誤可能以位翻轉的形式出現。糾錯碼提供了以犧牲消息緊湊性為代價來承受一定數量的位翻轉的能力。例如,我們可以通過編碼將0(000)和1(111)來防止單比特位的翻轉。這樣接收方就能通過對三個比特位進行多數表決的方式確定101實際上是111,或者001是0。但該編碼不能糾正兩個位被翻轉的錯誤,因為當111變成001時,解碼結果為0,而不是1。

糾錯碼中最為突出的是線性碼,可以用k * n的矩陣表示,其中k是原始消息的長度,n是編碼消息的長度。通常,在不知道底層線性碼的情況下解碼消息在計算上是困難的。這種困難度是McEliece公鑰密碼體制安全性的基礎。

在較高層次上,McEliece體制中的私鑰是一組稱為Goppa碼的隨機碼(表示為矩陣G)。公鑰是矩陣SGP,其中S是一個具有二進制項的可逆矩陣,P是一個置換矩陣。為了加密消息m,發送方計算c = m(SGP) + e,其中e是一個隨機錯誤向量,精確地表示編碼能夠糾正的錯誤數量。為了解密,我們計算cP-1 = mSG + eP-1,使mS是G的碼字,其可以校正添加的錯誤項e,通過計算mSS-1可以很容易地恢復消息。

與格一樣,基于編碼的加密技術也面臨著密鑰是大矩陣這一事實。使用推薦的安全參數,McEliece公鑰大約為1 mb,私鑰為11 kb。目前正在嘗試使用一種稱為準循環中等密度奇偶校驗碼(quasi-cyclic moderate density parity-check codes)的特殊編碼,這種編碼可以比Goppa碼更簡潔地表示,但這些編碼的安全性比Goppa碼研究得要少。

4、Isogenies

橢圓曲線密碼學領域因使用大量晦澀難懂的數學理論而臭名昭著。isogenies更是如此。在橢圓曲線密碼學中,我們使用Diffie-Hellman型協議來獲取共享的秘密,但是我們不是將群中元素提升到某個冪,而是遍歷橢圓曲線上的點。在基于isogenies的密碼學中,我們再次使用Diffie-Hellman型協議,但不是遍歷橢圓曲線上的點,而是通過一系列橢圓曲線。

isogeny是一個將一條橢圓曲線轉換為另一條橢圓曲線的函數,使得第一條曲線的群結構在第二條曲線中得到反映。對于那些熟悉群理論的人來說,它是一個同態群,有一些附加的結構來處理每條曲線的幾何形狀。當我們把注意力限制在超奇異橢圓曲線上時(我們不會在這里定義它),每條曲線都保證從它到其他超奇異曲線都有固定數量的isogenies。

現在,我們來看看這個圖,它是通過檢查從起始曲線得到的所有的isogenies,然后是這些曲線的所有isogenies,以此類推。這張圖被證明是高度結構化的,因為如果我們從第一個曲線開始隨機游走,碰到另一個曲線的概率會很?。ǔ俏頤淺手甘兜刈吆芏嗖劍?。在數學術語中,我們說通過檢查所有這些isogenies生成的圖是一個擴展圖(也是Ramanujan)。這種擴展特性正是使基于isogenies的密碼學安全的原因。

對于Supersingular Isogeny Diffie-Hellman(SIDH)方案,私鑰是一條由isogenies構成的鏈,公鑰是曲線。當Alice和Bob組合這些消息時,他們得到的曲線是不同的,但是有相同的不變量j。對于密碼學來說,j是什么并不重要,重要的是,一旦Alice和Bob完成密鑰交換,就可以很容易地計算出這個數字。

與其他后量子方案相比,基于isogeny的密碼學擁有非常小的密鑰大小,公鑰只使用330bytes。不幸的是,在本文討論的所有技術中,它們是最慢的,在密鑰生成和共享秘密計算中都需要11-13毫秒。然而,他們確實支持完美的前向保密,這是其他后量子密碼體制所不具備的。

5、基于哈希的簽名

已經有很多關于基于哈希的簽名的介紹,因此我們將對它們進行簡單的討論。簡而言之,哈希簽名使用哈希函數的輸入作為私鑰,輸出作為公鑰。這些密鑰僅適用于一個簽名,因為簽名本身包含了私鑰的一部分。這種極端低效的簽名方案通常使用Merkle樹來減少空間消耗(是的,與比特幣中使用的Merkle樹相同)。

遺憾的是,無法使用哈希構造KEM或公鑰密碼方案。因此,基于哈希的簽名并不是一個完整的后量子密碼解決方案。此外,它們不是空間有效的;一個比較有前途的簽名方案是SPHINCS,它產生的簽名大小為41kb,公鑰/私鑰大小為1kb。另一方面,基于哈希的方案非???,因為它們只需要計算哈希函數。它們還具有非常強的安全性證明,僅僅基于存在具有抗碰撞和抗原像性的哈希函數的假設。由于沒有跡象表明像SHA3或BLAKE2這樣當前廣泛使用的哈希函數容易受到這些攻擊,因此基于哈希的簽名是安全的。

6、小貼士

后量子密碼學是一個令人難以置信又令人興奮的研究領域,在過去的十年里已經取得了巨大的進展。盡管這篇文章中描述的四種密碼體制受到了學術界的廣泛關注,但沒有一種密碼體制得到NIST的批準,因此目前不推薦用于一般用途。許多方案的最初版本都不具備性能,并且受到各種優化的影響,這些優化可能會影響安全性,也可能不會影響安全性。事實上,多個為McEliece體制使用更節省空間而設計的編碼方案都已經被證明是不安全的。就目前而言,從后量子密碼體制中獲得最佳安全性需要犧牲一定的空間或時間?;詬衩藶胙У難芯吭諏榛钚苑矯媸親鈑星巴鏡模ㄇ┟蚄EM和全同態加密),但其所基于的假設只是經過了幾年的深入研究。目前,最安全的做法是將McEliece與Goppa碼一起使用,因為它已經經受了幾十年的密碼分析。

然而,每個用例都是唯一的。如果您認為您可能需要后量子密碼,請與您關系不錯的密碼學專家聯系。其他人應該等待NIST完成后量子密碼的標準化。


轉自:公眾號(格密鏈

更多區塊鏈信息:www.qukuaiwang.com.cn/news

關鍵詞: 量子計算  后量子密碼  
0/300
?