陷门函数

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

用數學術語來說，如果 _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 (1n ) = (_k_, _t_k) 其中 _k_ ∈ _K_ ∩ {0, 1}n 並且 _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], Bibcode: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）