陷門函數

陷門函數的思想是：帶有陷門t的陷門函數f可以通過算法Gen生成。f可以有效地在概率多項式時間內被計算。然而，f反方向的計算通常很困難，除非陷門t 是已知的。

在理論計算機科學和密碼學中，陷門函數是一種在一個方向上很容易計算，但在沒有特殊信息的情況下很難在相反方向上計算（尋找它的逆）的函數，稱為「陷門」。陷門函數是單向函數的一種特殊情況，廣泛用於公鑰密碼學中。

用數學術語來說，如果f是陷門函數，則存在一些秘密信息t ，因此給定f ( x ) 和t ，很容易計算x 。考慮一把掛鎖和它的鑰匙。通過推動卸扣，無需使用鑰匙即可將掛鎖鎖上。然而，想要輕鬆地開鎖，則必需使用鑰匙。這裡的鑰匙是陷門，而掛鎖則是陷門函數。

一個簡單的數學上的陷門示例是：「6895601 是兩個素數的乘積。那兩個素數是多少？」一個典型的「蠻力」解決方案是嘗試將 6895601 不停除以一些素數，直到找到答案。但是如果已知 1931 是其中一個數字，你可以通過在任何計算器中輸入「6895601 ÷ 1931」來找到答案。這個例子不是一個可靠的陷門函數——現代計算機可以在一秒鐘內猜出所有可能的答案——但是這個例子可以通過使用兩個更大的素數的乘積來改進。

隨着Diffie 、Hellman和Merkle在 1970 年代中期發表了非對稱（或公鑰）加密技術後，陷門函數開始在密碼學中嶄露頭角。事實上，Diffie & Hellman (1976)創造了這個術語。已經提出了幾個函數類，很快就發現陷門函數比最初想象的更難找到。例如，早期的建議是使用基於子集和問題的方案，但事實很快證明這是不合適的。

截至2004年 (2004-Missing required parameter 1=month!)，已知最好的陷門函數 (族) 候選函數是RSA和Rabin函數族。兩者都是一個合數的冪取模，而且都跟質因數分解有關。

與離散對數問題的難度相關的函數（模素數或在橢圓曲線上定義的群）不是已知的陷門函數，因為沒有關於這個群的已知「陷門」信息可以實現高效地計算離散對數。

密碼學中的陷門具有上述非常具體的含義，不要與後門混淆（它們經常互換使用，這是不正確的）。後門是一種故意添加到密碼算法（例如，密鑰對生成算法、數字簽名算法等）或操作系統中的機制，例如，它允許一個或多個未授權方以某種方式繞過或破壞系統。

定義

陷門函數是單向函數的集合 { f_k : D_k → R_k } ( k ∈ K )，其中K, D_k, R_k都是二進制字符串 {0, 1}^*的子集，滿足以下條件：

• 存在概率多項式時間 (PPT)採樣算法 Gen st Gen(1ⁿ ) = (k, t_k) 其中k ∈ K ∩ {0, 1}ⁿ並且t _k ∈ {0, 1}^*滿足 | t_k | < p(n)，其中p是某個多項式。每個t_k稱為對應於k的陷門。每個陷門都可以被有效地採樣。
• 給定輸入k ，也存在輸出x ∈ D_k的 PPT 算法。也就是說，每個D_k都可以被有效地採樣。
• 對於任何k ∈ K ，都存在正確計算f_k的 PPT 算法。
• 對於任意k ∈ K ，都存在一個 PPT 算法A 滿足對於任意x ∈ D _k，令y = A(k, f_k (x), t_k)，那麼我們有f_k(y) = f_k(x)。也就是說，給定陷門，很容易反轉。
• 對於任何k ∈ K ，沒有陷門t_k ，對於任何 PPT 算法，能夠正確反轉f_k的概率（即給定f_k(x)的情況下，找到一個x'使得f_k(x') = f_k(x)) 可以忽略不計。

如果上述集合中的每個函數都是單向排列，則該集合也稱為陷門排列。

例子

在下面的兩個例子中，我們假設分解一個大的合數是很困難的（參見整數分解）。

RSA 假設

在此示例中，具有e模 φ(n) 的逆，即n的歐拉總函數，是陷門：

$f(x)=x^{e}\mod n$

如果分解已知，可以計算出$\phi (n)$，那麼$e$的逆$d$可以通過$d=e^{-1}\mod {\phi (n)}$計算得出，然後給定$y=f(x)$，我們可以找到$x=y^{d}\mod n=x^{ed}\mod n=x\mod n$。它的困難程度遵循 RSA 中的假設。

拉賓的二次剩餘假設

設$n$是一個大的合數，使得$n=pq$，其中$p$和$q$是大素數，滿足$p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$，並且對攻擊者保密。問題是在給定$a$的情況下計算$z$使得$a\equiv z^{2}{\pmod {n}}$。這裡的陷門是$n$的因式分解。使用陷門，$z$的解可以給出為$cx+dy,cx-dy,-cx+dy,-cx-dy$， 其中$a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$。有關詳細信息，請參閱中國剩餘定理。請注意，給定素數$p$和$q$ ，我們可以找到$x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$和$y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$。這裡的條件$p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$保證了解$x$和$y$可以很好地定義。

參見

• 單向函數
• 橢圓曲線密碼學
• RSA加密演算法

參考

• 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）