陷門函數
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Trapdoor_permutation.svg/300px-Trapdoor_permutation.svg.png)
在理論電腦科學和密碼學中,陷門函數是一種在一個方向上很容易計算,但在沒有特殊資訊的情況下很難在相反方向上計算(尋找它的逆)的函數,稱為「陷門」。陷門函數是單向函數的一種特殊情況,廣泛用於公鑰密碼學中。 [2]
用數學術語來說,如果f是陷門函數,則存在一些秘密資訊t ,因此給定f ( x ) 和t ,很容易計算x 。考慮一把掛鎖和它的鑰匙。通過推動卸扣,無需使用鑰匙即可將掛鎖鎖上。然而,想要輕鬆地開鎖,則必需使用鑰匙。這裏的鑰匙是陷門,而掛鎖則是陷門函數。
一個簡單的數學上的陷門範例是:「6895601 是兩個質數的乘積。那兩個質數是多少?」一個典型的「蠻力」解決方案是嘗試將 6895601 不停除以一些質數,直到找到答案。但是如果已知 1931 是其中一個數字,你可以通過在任何計數機中輸入「6895601 ÷ 1931」來找到答案。這個例子不是一個可靠的陷門函數——現代電腦可以在一秒鐘內猜出所有可能的答案——但是這個例子可以通過使用兩個更大的質數的乘積來改進。
隨着Diffie 、Hellman和Merkle在 1970 年代中期發表了非對稱(或公鑰)加密技術後,陷門函數開始在密碼學中嶄露頭角。事實上,Diffie & Hellman (1976)創造了這個術語。已經提出了幾個函數類,很快就發現陷門函數比最初想像的更難找到。例如,早期的建議是使用基於子集和問題的方案,但事實很快證明這是不合適的。
截至2004年[update],已知最好的陷門函數 (族) 候選函數是RSA和Rabin函數族。兩者都是一個合數的冪取模,而且都跟質因數分解有關。
與離散對數問題的難度相關的函數(模質數或在橢圓曲線上定義的群)不是已知的陷門函數,因為沒有關於這個群的已知「陷門」資訊可以實現高效地計算離散對數。
密碼學中的陷門具有上述非常具體的含義,不要與後門混淆(它們經常互換使用,這是不正確的)。後門是一種故意添加到密碼演算法(例如,金鑰對生成演算法、數碼簽章演算法等)或作業系統中的機制,例如,它允許一個或多個未授權方以某種方式繞過或破壞系統。
定義
陷門函數是單向函數的集合 { fk : Dk → Rk } ( k ∈ K ),其中K, Dk, Rk都是二進制字串 {0, 1}*的子集,滿足以下條件:
- 存在概率多項式時間 (PPT)採樣演算法 Gen st Gen(1n ) = (k, tk) 其中k ∈ K ∩ {0, 1}n並且t k ∈ {0, 1}*滿足 | tk | < p(n),其中p是某個多項式。每個tk稱為對應於k的陷門。每個陷門都可以被有效地採樣。
- 給定輸入k ,也存在輸出x ∈ Dk的 PPT 演算法。也就是說,每個Dk都可以被有效地採樣。
- 對於任何k ∈ K ,都存在正確計算fk的 PPT 演算法。
- 對於任意k ∈ K ,都存在一個 PPT 演算法A 滿足對於任意x ∈ D k,令y = A(k, fk (x), tk),那麼我們有fk(y) = fk(x)。也就是說,給定陷門,很容易反轉。
- 對於任何k ∈ K ,沒有陷門tk ,對於任何 PPT 演算法,能夠正確反轉fk的概率(即給定fk(x)的情況下,找到一個x'使得fk(x') = fk(x)) 可以忽略不計。 [3] [4] [5]
如果上述集合中的每個函數都是單向排列,則該集合也稱為陷門排列。 [6]
例子
在下面的兩個例子中,我們假設分解一個大的合數是很困難的(參見整數分解)。
RSA 假設
在此範例中,具有e模 φ(n) 的逆,即n的歐拉總函數,是陷門:
如果分解已知,可以計算出,那麼的逆可以通過計算得出,然後給定,我們可以找到。它的困難程度遵循 RSA 中的假設。 [7]
拉賓的二次剩餘假設
設是一個大的合數,使得,其中和是大質數,滿足,並且對攻擊者保密。問題是在給定的情況下計算使得。這裏的陷門是的因式分解。使用陷門,的解可以給出為, 其中。有關詳細資訊,請參閱中國剩餘定理。請注意,給定質數和 ,我們可以找到和。這裏的條件保證了解和可以很好地定義。 [8]
參見
筆記
參考
- Diffie, W.; Hellman, M., New directions in cryptography (PDF), IEEE Transactions on Information Theory, 1976, 22 (6): 644–654 [2022-03-21], CiteSeerX 10.1.1.37.9720
, doi:10.1109/TIT.1976.1055638, (原始內容存檔 (PDF)於2017-12-03)
- Pass, Rafael, A Course in Cryptography (PDF), [27 November 2015], (原始內容 (PDF)存檔於2022-05-23)
- Goldwasser, Shafi, Lecture Notes on Cryptography (PDF), [25 November 2015], (原始內容 (PDF)存檔於2022-04-20)
- Ostrovsky, Rafail, Foundations of Cryptography (PDF), [27 November 2015], (原始內容 (PDF)存檔於2022-02-16)
- Dodis, Yevgeniy, Introduction to Cryptography Lecture Notes (Fall 2008), [17 December 2015], (原始內容存檔於2017-11-05)
- Lindell, Yehuda, Foundations of Cryptography (PDF), [17 December 2015], (原始內容 (PDF)存檔於2022-01-19)
- ^ Ostrovsky, pp. 6-9
- ^ Bellare, M. Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems. Advances in Cryptology. June 1998.
- ^ Pass's Notes, def. 56.1
- ^ Goldwasser's lecture notes, def. 2.16
- ^ Ostrovsky, pp. 6-10, def. 11
- ^ Pass's notes, def 56.1; Dodis's def 7, lecture 1.
- ^ Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.
- ^ Goldwasser's lecture notes, 2.3.4