查看“︁陷门函数”︁的源代码

{{NoteTA|G1=IT|G2=Math}}
[[File:Trapdoor_permutation.svg|缩略图|300x300像素|陷门函数的思想是：带有陷门''t''的陷门函数''f''可以通过算法'''Gen'''生成。''f''可以有效地在概率[[时间复杂度|多项式时间内]]被计算。然而，''f''反方向的计算通常很困难，除非陷门''t'' 是已知的。 <ref>Ostrovsky, pp. 6-9</ref>]]
在[[理論計算機科學|理论计算机科学]]和[[密码学]]中，'''陷门函数'''[[函数|是]]一种在一个方向上很容易计算，但在没有特殊信息的情况下很难在相反方向上计算（寻找它的[[反函數|逆]]）的函数，称为“陷门”。陷门函数是[[單向函數|单向函数]]的一种特殊情况，广泛用于[[公开密钥加密|公钥密码学]]中。 <ref>{{Cite journal|title=Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems|last=Bellare|first=M|date=June 1998|journal=Advances in Cryptology}}</ref>

用数学术语来说，如果''f''是陷门函数，则存在一些秘密信息''t'' ，因此给定''f'' ( ''x'' ) 和''t'' ，很容易计算''x'' 。考虑一把[[挂锁]]和它的钥匙。通过推动卸扣，无需使用钥匙即可将挂锁锁上。然而，想要轻松地开锁，则必需使用钥匙。这里的钥匙是陷门，而挂锁则是陷门函数。

一个简单的数学上的陷门示例是：“6895601 是两个素数的乘积。那两个素数是多少？”一个典型的“[[蛮力攻击|蛮力]]”解决方案是尝试将 6895601 不停除以一些素数，直到找到答案。但是如果已知 1931 是其中一个数字，你可以通过在任何计算器中输入“6895601 ÷ 1931”来找到答案。这个例子不是一个可靠的陷门函数——现代计算机可以在一秒钟内猜出所有可能的答案——但是这个例子可以通过[[整数分解|使用两个更大的素数的乘积]]来改进。

随着[[惠特菲爾德·迪菲|Diffie]] 、[[馬丁·赫爾曼|Hellman]]和[[瑞夫·墨克|Merkle]]在 1970 年代中期发表了[[公开密钥加密|非对称（或公钥）加密]]技术后，陷门函数开始在[[密码学]]中崭露头角。事实上，{{Harvard citation text|Diffie|Hellman|1976}}创造了这个术语。已经提出了几个函数类，很快就发现陷门函数比最初想象的更难找到。例如，早期的建议是使用基于[[子集和問題|子集和问题]]的方案，但事实很快证明这是不合适的。

{{As of|2004}}，已知最好的陷门函数 (族) 候选函数是[[RSA加密演算法|RSA]]和[[拉宾密码系统|Rabin]]函数族。两者都是一个合数的幂取模，而且都跟[[质因数分解]]有关。

与[[离散对数|离散对数问题]]的难度相关的函数（模素数或在[[椭圆曲线密码学|椭圆曲线]]上定义的群）''不''是已知的陷门函数，因为没有关于这个群的已知“陷门”信息可以实现高效地计算离散对数。

密码学中的陷门具有上述非常具体的含义，不要与[[軟體後門|后门]]混淆（它们经常互换使用，这是不正确的）。后门是一种故意添加到密码算法（例如，密钥对生成算法、数字签名算法等）或操作系统中的机制，例如，它允许一个或多个未授权方以某种方式绕过或破坏系统。

== 定义 ==
'''陷门函数'''是[[單向函數|单向函数]]的集合 { ''f''<sub>''k''</sub> : ''D''<sub>''k''</sub> → ''R''<sub>''k''</sub> } ( ''k'' ∈ ''K'' )，其中''K'', ''D''<sub>''k''</sub>, ''R''<sub>''k''</sub>都是二进制字符串 {0, 1}<sup>*</sup>的子集，满足以下条件：

* 存在概率多项式时间 (PPT)''采样''算法 Gen st Gen(1<sup>''n''</sup> ) = (''k'', ''t''<sub>''k''</sub>) 其中''k'' ∈ ''K'' ∩ {0, 1}<sup>''n''</sup>并且''t'' <sub>''k''</sub> ∈ {0, 1}<sup>*</sup>满足 | ''t''<sub>''k''</sub> | < ''p''(''n'')，其中''p''是某个多项式。每个''t''<sub>''k''</sub>称为对应于''k''的''陷门''。每个陷门都可以被有效地采样。
* 给定输入''k'' ，也存在输出''x'' ∈ ''D''<sub>''k''</sub>的 PPT 算法。也就是说，每个''D''<sub>''k''</sub>都可以被有效地采样。
* 对于任何''k'' ∈ ''K'' ，都存在正确计算''f''<sub>''k''</sub>的 PPT 算法。
* 对于任意''k'' ∈ ''K'' ，都存在一个 PPT 算法''A'' 满足对于任意''x'' ∈ ''D'' <sub>''k''</sub>，令''y'' = ''A''(''k'', ''f''<sub>''k''</sub> (''x''), ''t''<sub>''k''</sub>)，那么我们有''f''<sub>''k''</sub>(''y'') = ''f''<sub>''k''</sub>(''x'')。也就是说，给定陷门，很容易反转。
* 对于任何''k'' ∈ ''K'' ，没有陷门''t''<sub>''k''</sub> ，对于任何 PPT 算法，能够正确反转''f''<sub>''k''</sub>的概率（即给定''f''<sub>''k''</sub>(''x'')的情况下，找到一个''x'<nowiki/>''使得''f''<sub>''k''</sub>(''x''') = ''f''<sub>''k''</sub>(''x'')) 可以忽略不计。 <ref>Pass's Notes, def. 56.1</ref> <ref>Goldwasser's lecture notes, def. 2.16</ref> <ref>Ostrovsky, pp. 6-10, def. 11</ref>

如果上述集合中的每个函数都是单向排列，则该集合也称为'''陷门排列'''。 <ref>Pass's notes, def 56.1; Dodis's def 7, lecture 1.</ref>

== 例子 ==
在下面的两个例子中，我们假设分解一个大的合数是很困难的（参见[[整数分解]]）。

=== RSA 假设 ===
在此示例中，具有''e''模 φ(''n'') 的逆，即''n''的[[欧拉函数|欧拉总函数]]，是陷门：

: <math>f(x) = x^e \mod n</math>

如果分解已知，可以计算出<math>\phi(n)</math>，那么<math>e</math>的逆<math>d</math>可以通过<math>d = e^{-1} \mod{\phi(n)}</math>计算得出，然后给定<math>y = f(x)</math>，我们可以找到<math>x = y^d \mod n = x^{ed} \mod n = x \mod n</math>。它的困难程度遵循 RSA 中的假设。 <ref>Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.</ref>

=== 拉宾的二次剩余假设 ===

设<math>n</math>是一个大的合数，使得<math>n = pq</math>，其中<math>p</math>和<math>q</math>是大素数，满足<math>p \equiv 3 \pmod{4}, q \equiv 3 \pmod{4}</math>，并且对攻击者保密。问题是在给定<math>a</math>的情况下计算<math>z</math>使得<math>a \equiv z^2 \pmod{n}</math>。这里的陷门是<math>n</math>的因式分解。使用陷门，<math>z</math>的解可以给出为<math>cx + dy, cx - dy, -cx + dy, -cx - dy</math>， 其中<math>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}</math>。有关详细信息，请参阅[[中国剩余定理]]。请注意，给定素数<math>p</math>和<math>q</math> ，我们可以找到<math>x \equiv a^{\frac{p+1}{4}} \pmod{p}</math>和<math>y \equiv a^{\frac{q+1}{4}} \pmod{q}</math>。这里的条件<math>p \equiv 3 \pmod{4}, q \equiv 3 \pmod{4}</math>保证了解<math>x</math>和<math>y</math>可以很好地定义。 <ref>Goldwasser's lecture notes, 2.3.4</ref>

== 参見 ==
* [[單向函數|单向函数]]
* [[椭圆曲线密码学]]
* [[RSA加密演算法]]

== 笔记 ==

== 参考 ==

*{{citation|first1=W.|last1=Diffie|author1-link=惠特菲爾德·迪菲|first2=M.|last2=Hellman|author2-link=馬丁·赫爾曼|title=New directions in cryptography|journal=[[IEEE Transactions on Information Theory]]|volume=22|issue=6|pages=644–654|year=1976|doi=10.1109/TIT.1976.1055638|url=http://www-ee.stanford.edu/~hellman/publications/24.pdf|citeseerx=10.1.1.37.9720|accessdate=2022-03-21|archive-date=2017-12-03|archive-url=https://web.archive.org/web/20171203090237/https://www-ee.stanford.edu/~hellman/publications/24.pdf|dead-url=no}}
* {{Citation|last=Pass|first=Rafael|title=A Course in Cryptography|url=https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf|access-date=27 November 2015|archive-date=2022-05-23|archive-url=https://web.archive.org/web/20220523234454/http://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf}}
* {{Citation|last=Goldwasser|first=Shafi|title=Lecture Notes on Cryptography|url=https://cseweb.ucsd.edu/~mihir/papers/gb.pdf|access-date=25 November 2015|archive-date=2022-04-20|archive-url=https://web.archive.org/web/20220420003617/https://cseweb.ucsd.edu/~mihir/papers/gb.pdf}}
* {{Citation|last=Ostrovsky|first=Rafail|title=Foundations of Cryptography|url=http://web.cs.ucla.edu/~rafail/PUBLIC/OstrovskyDraftLecNotes2010.pdf|access-date=27 November 2015|archive-date=2022-02-16|archive-url=https://web.archive.org/web/20220216045337/http://web.cs.ucla.edu/~rafail/PUBLIC/OstrovskyDraftLecNotes2010.pdf}}
* {{Citation|last=Dodis|first=Yevgeniy|title=Introduction to Cryptography Lecture Notes (Fall 2008)|url=http://www.cs.nyu.edu/courses/fall08/G22.3210-001/index.html|access-date=17 December 2015|archive-date=2017-11-05|archive-url=https://web.archive.org/web/20171105193922/http://www.cs.nyu.edu/courses/fall08/G22.3210-001/index.html}}
* {{Citation|last=Lindell|first=Yehuda|title=Foundations of Cryptography|url=http://u.cs.biu.ac.il/~lindell/89-856/complete-89-856.pdf|access-date=17 December 2015|archive-date=2022-01-19|archive-url=https://web.archive.org/web/20220119043828/https://u.cs.biu.ac.il/~lindell/89-856/complete-89-856.pdf}}
[[Category:密碼原語]]
[[Category:密码学]]
[[Category:密码学理论]]