區塊鏈:密碼學技術何以為信？深究背后的計算困難性理論

作者：李昊軒?

來源：

微眾銀行區塊鏈

隱私保護為何選用密碼學算法？密碼學算法背后有哪些神奇的數學理論？3何時比9大？計算可逆性錯覺究竟是如何在數學領域被打破？

這里，我們將從密碼學信任的理論基礎出發，分享在隱私保護技術方案中應用密碼學技術的一些思考：如何理解密碼學算法的能力邊界，如何客觀地比較不同密碼學算法對于隱私保護方案有效性的影響。

這一切，要從密碼學神奇的“不對稱性”說起。

神奇的“不對稱性”

早在公元前，古埃及、古羅馬、古希臘等古文明均已開始使用密碼技術來保護信息的機密性，歷史上最早的不對稱性表現為選用特殊的信息編碼方式，如果第三方不知道具體的編碼方式，則難以解碼對應的信息。

大約經過4000多年的發展，也就是近代20世紀初，現代密碼學正式成型，引入了關于不對稱性更為嚴謹的數學定義。比較有代表性的早期論文包括1929年LesterS.Hill在美國數學月刊上發表的《CryptographyinanAlgebraicAlphabet》。

海南大學密碼學院獲批國家重點研發計劃“區塊鏈”重點專項項目:金色財經報道，近日，海南大學密碼學院教授曹春杰牽頭，聯合中科院信息工程研究所、西安電子科技大學、中國電子科技集團有限公司、國家信息中心等單位科研團隊申報的國家重點研發計劃“區塊鏈”重點專項項目獲得立項批復。

該項目在海南落地實施，并開展區塊鏈技術在金融科技、政務民生、社會治理等場景下的示范應用，將有利于推動海南自貿港開放環境下區塊鏈應用生態的健康發展，為我國區塊鏈監管技術的創新發展探索路徑、積累經驗、提供示范。（南海網海南新聞）[2022/3/21 14:08:26]

20世紀末，隨著因特網的普及，大量敏感數據在網絡上進行傳輸，產生了大量的數據內容保護的需求，密碼學技術也因此得到飛速發展。

在現代密碼學中，關于不對稱性，大家最熟悉的概念莫過于“公鑰”和“私鑰”。

以加密通信為例，主人公小華要向他的朋友美麗通過加密的方式發送一份電子郵件，可以先找到美麗的公鑰，使用公鑰對郵件內容進行加密，并將加密后的得到密文發送給美麗。美麗收到郵件內容的密文之后，通過自己的私鑰進行解密，最終得到郵件內容的明文。

以上過程中，密碼學算法神奇的不對稱性體現在以下問題中：

為什么只有美麗可以解密郵件內容？

為什么其他人不能通過美麗的公鑰反推出她的私鑰？

這些問題的答案，都要歸結于密碼學中的計算困難性理論。

《衛報》：部分密碼學家對市場使用“Crypto”的方式感到不滿:11月22日消息，據英國《衛報》報道，隨著Crypto在加密貨幣行業使用越來越廣泛，用戶在 Google 上搜索“crypto”會看到大量指向比特幣和以太坊等加密貨幣的熱門搜索結果，但根據韋伯斯特字典對“crypto”的定義，它指的是密碼學，而密碼學又被定義為“信息的計算機編碼和解碼”。“這種詞匯轉變給密碼學家帶來了沉重的負擔，”該報道稱，過去幾年許多密碼學家一直在社交媒體上重復“crypto is cryptography”的口號，但收效甚微。密碼學專家Matt Blaze表示，“我認為將加密貨幣稱為 'crypto' 是一個糟糕的選擇，這對密碼學和加密貨幣都會產生不良后果。”[2021/11/22 22:08:04]

計算困難性理論

在隱私保護場景中，計算困難性理論具體表現為，對同一隱私數據主體，通過不同計算路徑，獲得相同信息的計算難度具有不對稱性。不對稱性中，相對容易的計算方式被用來構造授權的數據訪問，而困難的計算方式被用來避免非授權的數據泄露。

構造這樣的不對稱性的方式有很多，最經典的方式之一，就是千禧年七大難題之一——P和NP問題。

P問題是確定性圖靈機，即通用計算機計算模型，在多項式時間(O(n^k))內可以計算獲得答案的一類問題。NP問題是確定性圖靈機在多項式時間內可以驗證答案的正確性，但不一定能計算出答案的一類問題。

聲音 | 觀點：密碼學人才短缺，影響了馬來西亞的區塊鏈發展:私人投資公司MW Partners Group Holdings Pte Ltd顧問Mark Pui表示，密碼學領域的人才短缺，拖累了馬來西亞數字賬本技術的發展。

Mark聲稱：“我認為，現實是我們沒有密碼技術，這影響了我們領導區塊鏈技術發展的能力。在馬來西亞和全世界，區塊鏈技術的應用仍然有限。但在發展方面，我們落后于其他所有人，因為我們沒有技能，沒有深厚的密碼學技能。”（The Malaysian Reserve）[2019/11/29]

關于同一份答案，驗證過程比計算過程要容易很多，由此我們可以構造出密碼學算法所需要的計算難度不對稱性。

NP問題是否能夠通過有效的多項式時間算法轉化成P問題，由此破解計算難度不對稱性？目前學術界尚無定論。

理論研究進一步表明，對于NP問題集合中的核心問題，即NP完全問題，如果能夠找一個有效的多項式時間算法來解決任何一個NP完全問題，那其他所有NP問題都可以基于這個算法來構造出有效的多項式時間算法。由此，之前提到的計算難度不對稱性將不復存在。

幸運的是，經過將近70年的科學探索，這樣的算法并沒有被發現。在有限時間內，現代計算機難以求解這些問題的答案，所以現代密碼學可以比較安全地基于這些NP完全問題來構造有效的密碼學算法。

聲音 | “現代密碼學之父”迪菲：量子計算不會威脅到區塊鏈:據澎湃消息，3月27日，被譽為“現代密碼學之父”的圖靈獎得主惠特菲爾德?迪菲（Whitfield Diffie）在博鰲亞洲論壇上接受澎湃新聞采訪時表示，量子計算只會威脅到密碼學中非常窄、但非常重要的一個領域，上世紀70年代建立起來的公鑰加密體系會變得脆弱。但密碼學中的許多技術，包括區塊鏈用到的哈希編碼在量子計算面前并不脆弱。[2019/3/27]

神奇的“計算困難問題”

形象地講，計算困難性理論的核心就是構造一個迷宮，如果不知道捷徑，是很難到達出口的。

我們日常所用的各類密碼學算法，其有效性都與這一理論息息相關，這里重點以非對稱密碼學算法為例，介紹其中經典的迷宮構造藍圖，即三大計算困難問題：

大數分解困難問題

離散對數困難問題

橢圓曲線上的離散對數困難問題

大數分解困難問題

給定兩個大素數p和q，計算n=p*q是容易的。然而，給定n，求解p、q則是困難的。

整數的素數分解是數論中最著名的問題之一，目前，求解素數分解最有效的方法稱為數域篩法，即通過構造代數數域不停地對整數可能的集合進行迭代運算。

聲音 | 肖風：密碼學已在理論上有很多成果可供解決數據隱私保護問題:今日在“Web 3.0時代隱私計算構建新數據共享世界”峰會上，萬向區塊鏈董事長肖風表示，隨著人工智能的興起，隱私計算成為世界性話題。然而，并非所有數據都存在于互聯網平臺上，也不是所有數據都是法律法規允許共享的。因此隱私計算的概念才得以提出，而恰恰密碼學已在理論上有很多成果可供我們來探討解決數據隱私保護問題。[2018/12/1]

目前，大整數分解問題仍不存在更有效的分解方法，因此密碼學一些方案利用大數分解困難問題構造相應協議，如RSA系列算法將其困難性規約為大數分解困難問題。如果大整數分解困難問題被破解，使用RSA密碼方案保護的隱私數據也會相應遭到破譯。

離散對數困難問題

在模為n，生成元為g的有限域中，給定整數a，計算g^a=b是容易的。然而，給定b和g計算a則是困難的。

許多新接觸密碼學的讀者都會對離散對數問題產生計算可逆性的錯覺，看起來就是進行一次log運算的事情，但真相并非如此。

在實數域，元素有一個非常重要的性質，全序關系，所以很容易比較大小。例如，在實數域中9>2且3>2，一定能推出9>2。

在計算log2(9)時，計算機會對以元素9為輸入的函數結果進行二分查找法，首先計算(9/2)^2和9進行比較，再計算/2)^2…。通過不停比較元素大小的性質，從而計算log最終的結果。

然而，在有限域中，元素之間并不存在全序關系。在模為7的有限域中，可以看到諸如9等于2，3比9大的關系存在。

因此，無法通過有效的算法計算上述過程中的a。許多著名的密碼協議安全性都是建立在離散對數困難性上的，如Diffie-Hellman密鑰交換協議、ElGamal加密、DSA算法等。

橢圓曲線上的離散對數困難問題

當前，橢圓曲線密碼學算法是當前密碼應用的主流，每一個隱私數據都能以坐標(x,y)的形式，表示為橢圓曲線上的一個點。與一般離散對數困難問題類似，橢圓曲線上的離散對數困難問題可以表示為：

在有限域F上的橢圓曲線群，點P為曲線上某個點，給定整數a，計算a*P=Q是容易的。然而，根據P和Q計算a則是困難的。

有別于普通代數運算，橢圓曲線上的點運算定義如下：

可以看到，橢圓曲線上的點運算和普通實數域上的運算有很大差別，當前尚未存在一種有效的算法對橢圓曲線離散對數問題進行破譯。目前，最常用的公鑰密碼算法體系ECDSA、EdDSA、國密SM2等都是基于這一困難問題。

客觀比較不同的密碼學算法

由于不同的密碼學算法構造使用了不同的困難問題，對應地，不同的困難問題也勢必會引入不同的安全假設。

理解這些安全假設，是企業進行技術選型，客觀地判斷基于不同密碼學算法構造隱私保護方案孰強孰弱的關鍵。

這里，我們需要進一步引入“安全參數”的概念。

安全參數是一個衡量密碼學算法保護隱私數據強度的數值。對位于“同一等級"的安全參數值來說，不同密碼學算法的安全級別基本相同，即面對已知最有效的攻擊方式，算法被破解導致隱私數據泄露的概率相同。

一般情況下，安全參數值的大小，直接體現為密鑰長度的長短。在同一等級下，安全參數值有大有小，對應的密鑰長度也有長有短。

基于不同困難問題的密碼學算法密鑰最小長度，美國國家標準與技術研究院NIST作如下推薦，其中，每個單元格表示需要使用密鑰長度的最小比特數。

通過上表，我們可以看到，即便密鑰長度相同，選用不同困難問題獲得的安全級別是不同的。一般而言，基于同一困難問題構造的技術方案，密鑰長度越長，安全性越高，相應地，系統效率越低，其中往往也伴隨其他系統設計上的取舍。

不同場景應按照業務需求選擇適合的技術方案和密鑰長度，具體有以下幾點需要特別注意：

隱私保護技術方案的安全性取決于其使用的密碼學算法實現中最低的安全參數等級。

在未指明安全參數的前提下，進行密碼學算法的安全性比較沒有實際意義。

如果安全參數值很小，一般表現為對應的密鑰長度很短時，無論密碼學算法設計多么精妙，實際效果可能都是不安全的。

由于困難問題選用上的差異，密碼學算法的理論強度沒有最強，只有在滿足特定安全假設下的夠強，強行比較基于不同困難問題的密碼學算法哪個更強通常沒有實際意義。

計算困難問題歸根結底還是一個計算問題，隨著計算機計算能力的增強，或是算法理論研究進展的推進，這些困難問題的安全性都會發生變化。如RSA加密算法，NIST密鑰管理準則認為，2010年后，1024位的密鑰不再安全，需要增加到2048位的密鑰長度，預計其安全有效性可以保持至2030年。

對于企業而言，這里的啟示在于，不能簡單地認為，隱私保護技術方案現在有效，就保證了10年后依舊有效。無論什么樣的隱私保護技術方案都有其時效性。

企業如果能夠根據權威技術組織推薦的安全參數、算法方案及時更新現有的系統，困難性理論就能夠有效保障隱私保護技術方案的有效性歷久如新。

正是：密碼學技術易守難攻，困難性理論當居首功！

作為密碼學安全的基石，計算困難問題和相關的安全參數，是企業有效進行密碼學算法選型的關鍵考察點。企業應用落地時，需充分考慮隱私數據保密的有效期，選擇合適的密碼學算法和密鑰長度，對數據安全性和系統效率進行必要衡量。

除了與密碼學算法直接相關的計算困難問題，一個完整的隱私保護技術方案通常還需要構造密碼學協議，來組合多種密碼學算法。密碼學協議引入了多方之間的交互，由此也引入其他重要的安全假設。

這些安全假設對評價隱私保護技術方案的整體安全性、有效性、實用性至關重要，具體分析，敬請關注下文分解。

Tags：區塊鏈CRYPTCRYPCRY魔獸幣應用區塊鏈嗎BlockchaincryptobankCrypto MafiaBig Crypto Game

MEXC