技術分享丨後比特幣時代與量子霸權危機(一)

買賣虛擬貨幣
引言關於中央第十八次集體學習時強調區塊鏈技術的報道,行業媒體們已經給予了充分的重視。然而,人們卻對兩天之後的另一條重要報道,沒有表現出應有的重視。這條報道是,10月26日,十三屆全國人大常委會第十四次會議26日下午表決透過《中華人民共和國密碼法》,將自2020年1月1日起施行。從中央開展對區塊鏈技術的學習,在戰略層面對區塊鏈技術予以承認,到正式出臺的密碼法,偶然中也蘊含著必然。區塊鏈技術分散式、防篡改、可溯源的好處已經人盡皆知,但所謂萬物相生,事實證明,區塊鏈技術難以脫離密碼學而單獨存在,原因有二:第一,與傳統技術思路不同,區塊鏈技術大大削弱了單一中心的控制力,各參與方的資料安全性離不開密碼學的保護。比特幣誕生已超過十年,在恰當的密碼學的保障下,去中心化的比特幣始終保持著較為平穩安全的執行。
第二,在實際應用中,許多參與節點不希望自己的資料被完全公開出來,因此不願意資料上鍊,這顯然限制了區塊鏈技術的應用落地。如何維護鏈上資料的隱私性成為區塊鏈應用的一大難題,密碼學則大大有利於為這一點提供補充。談到區塊鏈,就繞不開比特幣,更加離不開密碼學。本文旨在探討以橢圓加密演算法(以下簡稱ECC)為代表的密碼學的由來、價值、現狀,以及在未來量子計算機時代中密碼學的前景。從RSA到ECC區塊鏈最著名的應用莫過於比特幣,而作為比特幣的保鏢,基於ECC的橢圓曲線數字簽名演算法(以下簡稱ECDSA)對區塊鏈的價值不可謂不顯著。可以說,ECC與區塊鏈可謂休慼相關。在談ECC之前,我們先介紹一下RSA演算法。密碼本是二戰影視劇有一個重要的題材。對交戰國來說,國之重器不是大炮坦克,也不是金銀鈔票,甚至不是航母飛機,而是那個不太起眼的密碼本。

1942年,太平洋海戰重要的轉折點——中途島海戰中,美軍之所以取得勝利,一個重要的因素就是美軍獲得了日本的加密檔案,並破譯出日本即將攻擊中途島的重要情報。

1943年,日本聯合艦隊司令,海軍大將山本五十六在視察部隊時,座機被美軍擊落而斃命,直接原因就是通訊密碼被美軍破譯。

二戰前後,諸如此類的事例不勝列舉。即便到了冷戰時期,破譯密電也是美蘇情報部門的一項主要工作。到了1977年,Rivest、Shamir和Adleman三位教授用名字的首字母命名一種新演算法:RSA。不同於以往的對稱加密需要厚厚的密碼本,RSA演算法屬於非對稱加密。所謂非對稱加密,是指將秘鑰分為公鑰和私鑰,公鑰和私鑰必須成對出現,不能單獨生成。公鑰任何人都可以知道,用以加密;私鑰只有接受資訊的人才能知道,用以解密。

RSA的誕生可謂歷史性突破,堪稱古典與現代密碼學的分水嶺。只要RSA的質數足夠大,解密將會耗費巨大的算力和時間,短期內難以破解。

但所謂福禍相依,為了追求安全性,RSA需要非常大的質數作為基礎,拉長秘鑰會大大增加加密成本,降低速度。更要命的是,RSA演算法在應對量子計算機的威脅時頗為力不從心。

此時,ECC應運而生。ECC於1985年由Koblitz和Miller兩位教授發明。與RSA演算法一樣,ECC同樣屬於非對稱加密,但ECC在使用中的便捷性和安全性大大強過RSA。

什麼是ECC呢?可能大家對這一點很感興趣。

我們定義平行線相交於無窮遠點P∞,使平面上所有直線都統一為有唯一的交點,而區別於無窮遠點的原來平面上的點為平常點。透過無窮遠點和平常點我們可以引入射影平面的概念。

射影平面:平面上全體無窮遠點與全體平常點構成射影平面。

而橢圓曲線,指的就是在射影平面上滿足威爾斯特拉斯方程(Weierstrass)所有點的集合,且曲線上所有點都是非奇異的。

所謂非奇異,指的是曲線上任意一點的偏導數不能同時為0。

明白了橢圓曲線的由來,我們再來看橢圓曲線在密碼學上應用的方案。首先面對的問題就是橢圓曲線是連續的,並不適合用於加密。因此,橢圓曲線密碼學的第一要務就是把橢圓曲線定義在有限域上,(有限域Fp ,p為素數),並提出一條適於加密的曲線:y2=x3+ax+b (modp)。

相比起在商業中被廣泛採用的RSA加密演算法,ECC優勢是可以使用更短的金鑰,來實現與RSA相當或更高階別的安全。

透過下圖我們清楚的發現,160位ECC加密安全性相當於1024位RSA加密,而210位ECC加密安全性甚至相當於2048位RSA加密。ECC中256位數的金鑰與RSA演算法中3072位數金鑰所提供的安全強度相同。

因此,ECC具備計算量更小,處理速度更快,佔據儲存空間更小的優點,在資源、算力有限的前提下,ECC比RSA具備顯著的優勢。這些優勢已經使得ECC逐漸完成了對RSA的取代,成為了新一代的通用公鑰加密演算法。

如今,ECC早已無處不在:我們的第二代身份證都基於ECC,美國政府部門也用ECC加密內部通訊,FireFox和Chrome瀏覽器、蘋果的iMessage服務都使用ECC。

那麼,ECC、ECDSA等密碼技術在應用過程中有哪些值得關注的地方呢?另外,近期火熱的“量子霸權”講的又是什麼,它會對密碼學產生什麼影響呢?

在後續的系列文章中,我們將會繼續對其展開討論。

推薦閱讀:RSA的基本原理 

我在此前的文章寫道,密碼學問題,本質上是數學問題。RSA演算法自然也不例外,其原理並不複雜,幾個數字即可講明白。

我們先引入三個中學數學概念,質數,互質、取模。

質數:指在大於1的自然數中,除了1和它本身以外不再有其他因數的自然數。比如,2、3、5、7…
互質:是指公約數只有1的兩個數。比如,2和3,3和5,4和5均互質。
取模:指求餘運算,運算子是mod,比如4 ÷ 3 = 1餘1,所以,4mod 3 = 1。

在明白上述概念後,我們來看一組簡單的RSA加密方案:

1、找到一組互質數,P和Q,相乘後得到N
2、將P和Q分別減去1,再次相乘,得到M
3、確定加密公鑰E,使得E與M互質
4、確定解密私鑰D,使得D乘以E除以M餘1,即(D × E) mod M = 1

比如,挑兩個互質數,P=5和Q=8,N=P*Q=40,M=(P-1)*(Q-1)=28

隨機選取公鑰E=5,則私鑰D=45.

從這裡,我們可以設計出一對公鑰私鑰,加密公鑰KU={E,N}={5,40},解密私鑰KR={D,N}={45,40}。

1、在加密過程中,需要將加密數字自乘(E-1)次,當自乘結果超過N時,需要將結果取模後再乘,最後得到安全密文。

2、在解密過程中,用密文自乘(D-1)次,同樣,當自乘結果超過N時,需要將結果取模後再乘,最後得到加密數字。

感興趣的朋友可以透過我們給出的加密方案來對一些簡單的數字進行加密,由於秘鑰數字P和Q很小,用紙筆或者簡易的計算器就能夠計算出來。

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;