有沒有一種加密演算法可以識別不同密鑰加密的同一明文?
由http://www.zhihu.com/question/20405326/answer/146762338
想到的。甲方和乙方都不希望泄漏自己的數據(設為數據A和數據B),又想知道雙方的數據是否相同。因此設計一種演算法:雙方用各自的密鑰加密數據A和B,將加密後的數據a和b進行比對,若滿足某種性質,則雙方可知數據A和B是同一數據。請問這種演算法是否存在?如果存在,原理是什麼?
謝邀。
長答案預警,建議在WiFi環境下瀏覽。
=============================
0. 前言
回答專業的問題還是要經過科學的論證。經過了2天比較細緻的思考,與@玄星和 @劉健深入交流和討論後,最終形成了這個答案。特別感謝@玄星和 @劉健百忙之中能和我討論這個問題,完善論證,提供不同情境下的解決思路!
這道題說簡單也簡單,說難也難。想論述清楚這個問題,最重要的是界定場景的功能和攻擊者的攻擊能力。本答案儘力給出各種方案的實現方法,以及對應的安全模型。本答案也儘力包含可以實現、或可能實現的各種方法。
=============================
1. 問題描述
解決一個問題的前提是要把問題描述清楚。根據題目論述:
甲方和乙方都不希望泄漏自己的數據(設為數據A和數據B),又想知道雙方的數據是否相同。因此設計一種演算法:雙方用各自的密鑰加密數據A和B,將加密後的數據a和b進行比對,若滿足某種性質,則雙方可知數據A和B是同一數據。
將甲方設置為Alice、乙方設置為Bob,為了和Alice與Bob區分,Alice所擁有的數據為a,Bob所擁有的數據為b。下面的論述中,把潛在的攻擊者叫做Eve。題目沒有要求其它第三方參與。功能:Alice和Bob執行某個協議,實現a和b的相等性比較。
注意,由於Alice和Bob需要互相確定a和b是否為同一個數據,因此實現這一功能的協議至少需要Alice和Bob各發送一次數據。也就是說,Alice至少要給Bob發個東西,Bob至少要給Alice發個東西,否則似乎無法實現雙向確定。
=============================
2. 方法一:Hash
————————————————
2.1 方案描述
很多答主提到用哈希函數(Hash)。Hash的實現方法很簡單:
- Alice和Bob分別計算數據的Hash值,將結果發送給對方;
- 收到對方的Hash值後,對比結果與自己計算的結果是否相等,如果相等,則認為a=b。
這個方法其實已經挺不錯的了,因為:
- 由於Hash的抗碰撞特性,很難找到,使得,因此如果,則的概率趨近於1。方案是正確的。
- 同樣由於Hash的抗碰撞特性,被動攻擊者得到和後,很難求解得到a或者b。雖然a和b的保密性達不到特別高,但至少是不可計算的。
- 這是個Two-Pass方案,即Alice和Bob的交互過程可以獨立、並行執行,沒有先後順序。同時,這個方案的效率很高,畢竟就算了一次Hash嘛。
————————————————
2.2 安全問題
對於被動攻擊者來說這個方法雖然不錯,但是這個方法無法抵禦主動攻擊。所謂主動攻擊,意思是攻擊者不光可以觀察到Alice與Bob的通信內容,還可以對通信內容進行創建、修改、偽造等。這個方法最顯然的安全問題是:無法抵禦重放攻擊。攻擊方法如下:
- Alice計算,發送給Eve。
- Eve直接把返回給Alice。
這樣一來,即使Eve不知道a的值,Eve也可以讓Alice可以認為其手上的數據等於a。
Can we do better?
=============================
2. 方法二:Time Hash和Random Hash
————————————————
2.1 Time Hash
抵禦重放攻擊的思路比較清晰,只要在通信中加入狀態信息就好了。有兩種典型的方法:加時間戳信息,加隨機量。這兩種都是可行的。先來看加時間戳的方法:
- Alice取time,計算Hash(Time || a),將結果發送給Bob;
- Bob收到Alice的Hash值後,計算Hash(Time || b),如果Hash(Time || a) = Hash(Time || b),則認為a = b;
- Bob可同時取另一個time",Hash(Time" || b),將結果發送給Alice,Alice驗證過程相同。
這個方法可以進一步抵禦重放攻擊,因為如果Eve進行重放攻擊後,Alice會發現時間信息沒變,從而知道Eve在作假。
————————————————
2.2 Random Hash
再來看隨機量方法:
- Alice取隨機數R,計算Hash(R || a),將R和Hash結果發送給Bob;
- Bob收到Alice的R和Hash結值後,計算Hash(R || b),如果Hash(R || a) = Hash(R || b),則認為a = b;
- Bob可同時取另一個R",Hash(R" || b),將結果發送給Alice,Alice驗證過程相同。
這個方法同樣可以抵禦重放攻擊,因為如果Eve進行重放攻擊後,Alice會發現隨機量沒變,從而知道Eve在作假。此外,隨機量Hash比時間戳Hash更好一些,因為隨機量會把Hash值本身也隨機化,可以嚴格說明被動攻擊者無法從通信數據中獲得有關a或者b的任何信息。
———————————————— 2.3 安全問題
這個方法的安全問題是,主動攻擊者不僅可以進行重放,還可以對通信內容進行篡改。舉個例子,Eve可以進行中間人攻擊,截獲Alice發送給Bob的信息,對信息進行篡改後發送給Bob。這樣就可以破壞協議的正確性:即使a=b,Eve也可以通過修改數據,使得Bob認為a不等於b。
Can we do better?
=============================
3. 方法三:Hash with Pre-share Key
————————————————
3.1 方案描述
數據篡改是很麻煩的問題,因為我們幾乎無法阻止攻擊者對數據進行篡改。但是,我們可以通過一些方法檢測攻擊者是否對數據進行了篡改,從而知道協議的執行過程有問題。說到防止數據篡改,最直接的方法就是使用數字簽名方案對通信信息進行簽名。不過數字簽名需要引入第三方的參與,為雙方證明公鑰的可靠性。
既然這樣,我們不如用另一種方法:HMAC。HMAC要求Alice和Bob事先共享了一個相同的密鑰K。通信時,雙方在通信內容後面加上一個HMAC值。收到對方的通信信息後,先驗證HMAC值是否正確。如果正確後再執行後續協議。下圖給出隨機量Hash+HMAC的實現方法。
不過這個方法要求Alice和Bob事先共享出相同的密鑰K。如何共享密鑰K呢?很容易想到用Diffie-Hellman密鑰協商協議。不過這個協議本身無法抵抗中間人攻擊。即使使用密碼學中的Password Authenticated Key Exchange(PAKE)(可參考論文:Encrypted key exchange: password-based protocols secure against dictionary attacks),至少也需要一個可以實現身份認證的第三方…
我個人認為,如果想抵禦攻擊者的主動攻擊,引入第三方似乎是不可避免的事情。
感謝@土裡巴人的評論,答案後面的方法沒有引入第三方,也同樣無法抵禦主動攻擊。後面的方法主要解決另一個比較棘手的問題。
————————————————
3.2 安全問題
這個方法的安全問題沒那麼顯然,不過有些答主已經意識到了:如果a或者b的取值範圍很小,則Eve可以窮舉a和b的可能值。這實際上比 @劉天任所論述的攻擊方法更一般化一點:如果a和b所包含的信息熵很小,取值範圍是多項式級的,則Eve直接把a或者b的所有取值都遍歷一遍,分別計算Hash結果做對比即可。
這種攻擊方法在安全協議設計中叫做Offline Attack。而且要注意,這是個被動攻擊方法!Eve不需要對通信數據進行任何修改,就可以實現攻擊了。上述方法必須要求a或b的取值範圍是指數級的,而且是不可預測的。這樣才能防止Offline Attack攻擊。注意,並不需要要求a或b的取值滿足均勻隨機特性。
Can we do better?
=============================
4. 方法四:不經意傳輸(Oblivious Transfer,OT)
如果a或者b的取值範圍本身就很小,能不能實現上述功能呢?答案當然是肯定的,但是實現方法需要引入密碼學中的一些技術了。很多答主提到了安全多方計算(Multi-Party Computation,MPC)。這當然是一種最通用的解決方法。不過,安全MPC的構造相對比較複雜,在這個場景下有沒有什麼比較簡單的實現方法呢?
實際上,學者們很早前就開始考慮一些特定場景下的安全MPC實現方法。不經意傳輸(OT)就是一種很典型的場景。我們來看看OT的定義(來自Oblivious transfer):
In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.
意譯:
密碼學中,不經意傳輸(OT)協議是指,發送方可以向接收方傳輸一系列信息中的某一部分,接收方可以正確收到信息,但不知道信息屬於整體的哪個部分。
有關OT,可以進一步參考論文https://www.iacr.org/museum/rabin-obt/obtrans-eprint187.pdf。應用OT就可以實現a和b的相等性判斷,而且a和b的取值範圍可以很小。之所以能做到抵禦Offline Attack,是因為OT(或者其它安全MPC協議)中增加了更多的隨機量,而這些隨機量攻擊者是無法獲知的。這個思路和選擇明文安全的公鑰加密有些像,由於隨機量的參與,每個明文對應的密文都變成了指數級的。
更進一步,學者們不光考慮了a和b相等性的判斷,甚至考慮了更複雜的情況:Alice和Bob分別擁有一個集合,執行某個協議,使得Alice和Bob知道集合的交集有哪些元素。實現這一功能的方案叫做Private Set Intersection:
Private set intersection (PSI) allows two parties to compute
the intersection of their sets without revealing any
information about items that are not in the intersection.
實際上,這個功能最簡單的方法也是用Hash:
When confronted with the PSI problem,
most novices come up with a solution where both
parties apply a cryptographic hash function to their inputs
and then compare the resulting hashes.
然而,如何構造更安全、效率更高的方法還是一個挺不好解決的問題。在USENIX Security 2014(信息安全Top 3會議)上,Benny Pinkas等人研究了如何使用OT實現高效PSI的方法:
In this work, we give an overview on existing PSI protocols
that are secure against semi-honest adversaries.
We take advantage of the most recent efficiency improvements
in OT extension to propose significant optimizations
to previous PSI protocols and to suggest a new PSI
protocol whose runtime is superior to that of existing protocols.
上述三段引用全部來自他們的論文:https://www.usenix.org/system/files/conference/usenixsecurity14/sec14-paper-pinkas.pdf。
還有什麼其它的實現方法嗎? @劉天任所提出的方法應用了一個同態加密(Homomorphic Encryption,HE)方案,也能實現這樣的功能。他的方法本質思想是什麼呢?
Can we do better?
=============================
5. 方法五:安全重複數據刪除(Secure Deduplication)
雲計算中有一個很典型的應用,叫做安全重複數據刪除(Secure Deduplication),這個方法的來源是:用戶上傳到雲中的數據被加密了,但如果數據相同,加密結果不同,則雲上會出現很多重複數據。如何安全刪除這些重複數據就是降低雲存儲開銷的好方法。
這個題目的應用場景和安全重複數據刪除的場景很類似呀。所幸的是, @劉健同學就是這個領域研究的佼佼者,他定義了一個通用的安全模型,應用PAKE、HE實現了一個高效安全重複數據刪除方案。這個方案發表在CCS 2015(信息安全Top 3會議)上。@劉天任所給出的方案本質上也是類似的,不過我們可以通過 @劉健的方案得到嚴格的安全論述。感興趣的知友可以參考論文:https://eprint.iacr.org/2015/455.pdf。
=============================
6. 其他
據我所知,很多學者還在進一步研究類似場景的安全實現。@張源提到的不可區分混淆(indistinguishability Obfuscation,iO)也是一種很好的解決思路。不過iO相對來說實現起來就複雜多了…
Can we do better?這也是問給相關領域全體研究人員的問題。
深入思考,深入討論,總能發現更大的世界…
沒有這樣的「演算法」,除非增加交互輪數。
先說明為什麼這樣的「演算法」不存在,再給出一個基於 Diffie–Hellman 的互動式解法。//最後如果你熟悉密碼學中的 MPC,就不用往後讀了。
------------------- 知乎的公式編輯真難用 ----------------------------------
按照密碼學的常用的稱呼,不妨稱雙方為 Alice(縮寫為 A)和 Bob(縮寫為 B),雙方分別持有私有輸入 。然後目標是知道 是否相等。
如果題主設想成真,那題主的「演算法」可以被進行如下的抽象:Alice 發送 ,其中 是 Alice 的演算法, 是 Alice 的隨機帶。同時 Bob 發送 ,其中 是 Bob 的演算法, 是 Bob 的隨機帶。只要再對 進行簡單的計算,就可以知道 是否相等。
這樣的「演算法」幾乎沒有安全性。Bob 得到 後,可以對 Alice 進行有效的攻擊。例如 Bob 已經知道 Alice 的私有輸入可能是 ,那 Bob 只需私下計算 ,然後對 進行簡單的計算,就可以知道 是否等於 。
=========== Multi-Party Computation? =====================
為了保證安全性,就需要 Alice 和 Bob 多進行幾輪交互。其實只要最低限度的交互(Alice 給 Bob 發信息,Bob 回復 Alice 一條消息)就可以兼顧正確性和安全性。
當然在給出一個安全的構造之前,應該先定義一下安全性:當 時,Alice Bob 會得知對方的私有輸入,這時就沒有任何東西需要保密了。但當 時,Alice 和 Bob 都不希望對方學到任何額外的信息。對任意的互不相等的 ,假設 Bob 的私有輸入是 ,Alice 的私有輸入 且 Bob 也知道 Alice 的私有輸入是 之一,Bob 也不應該學到任何有關 的額外信息。在對稱的定義下,Alice 也不能學到任何關於 Bob 私有輸入的額外信息。
下面基於 DH 進行構造。DH 實際上提供了一個 Add-HE over ( 上的加同態加密),滿足如下性質
- 作為一個加同態加密,自然由密鑰生成演算法 G,加密演算法 E,解密演算法 D,以及同態加法 Eval 構成。為了簡化記號,我不顯式地寫出密鑰及密鑰生成過程,也不顯式地寫出隨機串,並記 。另外下文中 常用來表示 的密文分布。
- 正確性:
- 安全性:
- 同態運算:,這裡 是 上的加法。
- 再隨機:有 的一個密文 c,可以將 c 再隨機化,得到一個新密文與 同分布(且與 c 獨立)。
構造如下:
首先 Alice 給 Bob 發送消息 s.t.
從 Bob 視角看,Bob 要選取 。注意到,如果 ,那 就全是 E(0);否則 ,則 中有部分是 E(1),數目等於 。如果將 發給 Alice,Alice 除了學到 是否相等,還知道它們在哪幾位不等。
為了消除這些額外信息。Bob 選取一個隨機的 可逆矩陣 。我們利用隨機可逆矩陣的性質:對任意非零 ,向量 是個隨機非零向量。Bob 向 Alice 發送 n 個密文 s.t. 是再隨機化的 。這樣 其實就是 的第 i 位的密文。
回到 Alice 的視角。她收到的 就是 的按位加密。如果 ,那 就都是 E(0);否則是一個隨機的非零向量的按位加密。不管是那種情況,Alice 收到的消息的分布,都只取決於 是否相等。
上面描述的做法,對 Alice 的私有輸入做到了 computational secure(計算安全),對 Bob 的私有輸入做到了 information-theoretic secure(資訊理論安全)。這時 Bob 還不知道 是否相等,可以讓 Alice 把答案告訴 Bob(代價是加一次交互),或者同時進行景象的 protocol(代價是 Bob 對 Alice 不再有資訊理論安全)。
這。。分兩部分。
如果不允許多放計算的話 答案是很簡單的不存在。這樣的一個加密演算法的IND-CPA是存在顯然的攻擊的。
如果允許多方計算,這個又是一個很顯然的可以。只要用YAO"s garbling circuit 證明a&<=b 然後再反過來證明 b&>=a。就可以了。。首先,如果確認相同了,那麼信息豈不是已經泄露給對方了?因為對方知道自己的是啥(比如 A),知道你我一樣(A=B),不就知道你的是啥了么(B 是啥)
如果不想要他人知道。那很簡單,用 rsa 就好了,一次公鑰解密,一次私鑰解密,別人因為不知道雙方私鑰,所以無法解密。
但是 rsa 很慢。。。rsa 是計算上不可逆,理論上不可碰撞。另一個思路的話,保證當 A != B 的時候對方也不知道你的秘文,用 diffie hellman 的思路。取一個足大的 cyclic group G,然後取一個 element g 保證 g 能夠 generate 足夠多的 element(防碰撞)
然後公開 G 和 g,雙方用自己的密文做密鑰,發送給對方 g^A 和 g^B,如果兩個相同,則很可能兩人密文相同(如果 g 選的好的話是可以完全確定相同的)這個其實也是很慢的。。。尤其是 A 和 B 比較大的話。A 和 B 的推薦大小是 256 bits,(大約是 10^77 這個水平)這個方式是計算上不可逆,理論上可以實現無碰撞其實,以上都是理論,現實生活中還是用哈希,又快,而且理論上不可逆,難碰撞。不存在這樣的演算法,也不希望存在這樣的演算法。因為如果題主設想的這種加密演算法可能存在大量弱密鑰,對演算法安全是有巨大隱患的。
要在不公開數據的情況下驗證雙方擁有同樣數據,最直觀的方法有兩個:
方案一,零知識證明。方案二,兩人分別公布自己數據的雜湊值,對比雜湊值是否一致就可以了。如果擔心一次雜湊存在碰撞風險,可以將原數據串聯上時間、日期、地址或其他固定字元串,重複幾次雜湊運算,判斷雙方的雜湊值是否都一致。如果擔心有一方造假,還可以採用交互協議的方式進行。比如A和B同時宣稱自己擁有某數據M。1. A將該數據串聯上字元1,計算出新數據串的雜湊值1,將字元串1和雜湊值1公開。2. B也按照同樣的方式計算雜湊值,如果兩者運算結果不同,則B可確定A和B擁有的數據必然不同,交互結束。3. 如果雜湊值相同,B將原數據串聯上新的字元串2,計算新數據串的雜湊值2,將字元串2和雜湊值2公開。4. A可以驗證雜湊值2是否相同,從而判斷B的數據是否跟自己一致。如果擔心碰撞風險,可以重複上述過程。當然方案二也可以看作方案一的一種具體實現方式,也就是可以基於雜湊演算法來構造零知識證明。哈希
姚氏百萬富翁問題。用這個方法可以比較兩個數的大小。姚院士的貢獻。
一個好的加密方法加密後的數據是毫無規律的,所以加密甚至可以用來生成隨機數。所以題主所說的 「將加密後的數據a和b進行比對,若滿足某種性質」,用現有的加密方法都是沒戲的。除非密鑰、明文和 IV 完全相同,那麼密文就完全相同;若這三個之中有任何一個不同,甚至是只有一點點不同,則密文之間就毫無規律可循(雪崩效應)。
而根據題主的案例,Hash 是一個比較方便的解決方案,但此時是雙方使用了相同的加密演算法,只是由於 Hash 很難求逆所以很難復原,Hash 沒有逆運算。此方法僅適合分享較長的原文,短的原文容易被彩虹表等方式破解但可以通過加鹽等慢加密方式避免,(至於很短的原文,沒有合適的加密方法)
其實類似的用例我已經我做過一個這個 Web App:新開發的網頁軟體:「猜猜我說了什麼」 - ZE3kr,它可以在本地自動地將原文生成為 Hash,然後可以通過分享頁面的方式讓別人來 「猜」,只存在原文完全匹配和原文不完全匹配兩個結果。這個原本是用來一方加密,然後公開分享,讓所有人猜;或者是到時候公布原文,所有人都可以驗證(用例:抽獎環節,在開獎之前公布加密後的中獎號碼,在開獎之後公布那些號碼,所有人都可以證明開獎過程沒有作弊)。
這種模式稍作修改即可以達到題主的用例:雙方可以同時使用這個方法「加密」,分別使用了不同的 Salt,然後通過安全的方式分別向對方傳送加密後的 Hash 和 Salt,這樣對方就能夠驗證數據是否一樣了。但是這需要雙方的誠信,任何一方都需要如實傳送 Hash 和 Salt。
至於什麼是安全的方式傳送?端到端加密即可。比如 WhatsApp FAQ - 端到端加密技術。
來驗證一下你的秘密和我的是不是一樣:猜猜我說了什麼 (SHA-256-short-v2),提示詞:Hello, World! 的中文
嘿嘿,抖個機靈:找可信的第三方,兩人把信息告訴第三方,第三方判斷兩人信息相不相同,完美符合題主要求。(逃
最近研究的方向剛好相關
Public Key Encryption with Equality Test(PKEET)【PKEET定義】
PKEET由Yang等人於2010年的CT_RSA上首次提出,其中心思想是設計一種公鑰密碼體制來檢驗外包資料庫中由不同用戶公鑰加密的密文是否包含相同的明文信息。
相等性測試表述如下:
設C, C』 為用兩個不同密鑰加密的密文, 即C = Encrypt(M; PK),C』 = Encrypt(M』; PK』)。
雲服務商可以運用相等性測試演算法檢驗 M = M』是否成立?
【PKEET前沿背景】
PKEEET的前身為Public key encryption with keyword search(PKES),即公鑰加密關鍵字搜索。PKES可以在不知明文的情況下對密文進行操作,搜索相應的關鍵字,但此演算法只能對用同一公鑰加密的密文進行運算。
隨著雲計算時代的來臨,為保護用戶數據隱私性,主流方法是採用密碼體制來加密上傳到雲端的數據。相應的,我們需要一種方法來對加密數據進行操作,在不能恢復明文的前提下得到我們想知道的信息。PKEET就是這樣的一種演算法,可以在不知道明文的情況下,對密文進行操作得到相等性信息。這跟演算法沒關係吧?不管雙方的數據相不相同,加密之後最後一定測出來是不同的。這是心理學問題。
有些回答提到了哈希,是很好的方法,計算明文哈希是可行的,但是不總是安全。因為如果明文空間有限的話,某一方可以通過窮舉攻擊來得出另一方的明文。當然,如果明文有一個很高的最小熵,計算明文哈希沒什麼問題~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
假設兩方為A,B,對應的密文為CA,CB。用不可區分的混淆器(indistinguishability obfuscation,iO),做一個混淆程序,A產生自己的混淆程序,輸入是明文,常數是自己的密鑰,輸出是密文。然後A將密文CA和這個混淆程序發送給B。B收到後,將明文作為輸入,執行混淆程序,拿得出的結果和收到的CA比較。同樣,B也產生一個類似的混淆程序並發送給A,A也執行類似的計算,最後如果A和B的對比結果有衝突,說明有一方惡意,產生了「錯誤的」混淆程序,或是給了偽造的密文;若沒衝突,則接受該結果。利用的原理就是iO可以隱藏秘密。或者說,iO可以使任何一個對稱加密演算法變為公鑰加密演算法,或對稱環境下的「數字簽名」MAC變為一個公鑰簽名演算法。題主不妨換個思路,通信中的雙方都把自己的加密方式隱藏起來。Alice與Bob只提供加密後的信息。具體實現方式可參考同態加密。
這個東西,在WinRAR早期版本已經做到了。現在沒有了……
使用Winrar早期版本使用不同密碼加密,打開壓縮文件然後可以看到文件的CRC32值,比對即可……
因為實在太簡單匿了……同態加密。
呃……hash一下不就行了嗎。話說知道是同一個數據不就知道對方的數據是什麼了嗎……
通過SSL傳輸哈希值,使用雙向認證。個人覺得,應用中使用這個,比較簡單穩妥。然而需要一些準備工作,例如pki。
不想讓對方知道內容但是想確認對方知道 這不是零知識證明么(偷笑) 這是密碼學的一個重要分支啊
計算下哈希值不行嗎?
這個應該屬於安全多方計算的範疇
密文從原理的角度來說應該與原文沒有映射關係。
兩個不同的密文竟然可以有關聯。
說明2個獨立的加密演算法之間有不可說的貓膩啊。推薦閱讀:
※有什麼理論複雜但是實現簡單的演算法?
※如何更好的理解和掌握 KMP 演算法?
※編程語言是怎麼設計出來的?
※Leetcode的weekly contest半小時AC 4題的那些人是怎麼做到的?
※遊戲設計製作時是否會用到類似 ACM 中的演算法設計?