陷门函数 在理论计算机科学和密码学中陷门函数是一种在一个方向上很容易计算但在没有特殊信息的情况下很难在相反方向上计算寻找它的逆的函数称为陷门陷门函数是单向函数的一种特殊情况广泛用于公钥密码学中 用数学术语来说如果f是陷门函数则存在一些秘密信息t 因此给定f  x  和t 很容易计算x 考虑一把挂锁和它的钥匙通过推动卸扣无需使用钥匙即可将挂锁锁上然而想要轻松地开锁则必需使用钥匙这里的钥匙是陷门而挂锁则是陷门函数 一个简单的数学上的陷门示例是 是两个素数的乘积那两个素数是多少一个典型的蛮力解决方案是尝试将  不停除以一些素数直到找到答案但是如果已知  是其中一个数字你可以通过在任何计算器中输入  来找到答案这个例子不是一个可靠的陷门函数现代计算机可以在一秒钟内猜出所有可能的答案但是这个例子可以通过使用两个更大的素数的乘积来改进 随着Diffie Hellman和Merkle在  年代中期发表了非对称或公钥加密技术后陷门函数开始在密码学中崭露头角事实上Diffie  Hellman 创造了这个术语已经提出了几个函数类很快就发现陷门函数比最初想象的更难找到例如早期的建议是使用基于子集和问题的方案但事实很快证明这是不合适的 截至年 Missing required parameter monthupdate已知最好的陷门函数 族 候选函数是RSA和Rabin函数族两者都是一个合数的幂取模而且都跟质因数分解有关 与离散对数问题的难度相关的函数模素数或在椭圆曲线上定义的群不是已知的陷门函数因为没有关于这个群的已知陷门信息可以实现高效地计算离散对数 密码学中的陷门具有上述非常具体的含义不要与后门混淆它们经常互换使用这是不正确的后门是一种故意添加到密码算法例如密钥对生成算法数字签名算法等或操作系统中的机制例如它允许一个或多个未授权方以某种方式绕过或破坏系统