单向陷门函数

末蓝、 2022-05-24 06:42 190阅读 0赞

定义：

单向陷门函数是有一个陷门的一类特殊[单向函数][Link 1]。单向陷门函数包含两个明显特征：一是单向性，二是存在陷门。所谓单向性，也称不可逆性，即对于一个函数y=f(x)，若已知x要计算出y很容易，但是已知y要计算出x=f ^(-1) (y)则很困难。单向函数的命名就是源于其只有一个方向能够计算。所谓陷门，也成为后门。对于单向函数，若存在一个z使得知道z则可以很容易地计算出x=f ^(-1) (y)，而不知道z则无法计算出x=f ^(-1) (y)，则称函数y=f(x)为单向陷门函数，而z称为陷门。

## 简介 ##

编辑

它首先是一个单向函数，在一个方向上易于计算而反方向却难于计算。但是，如果知道那个秘密陷门，则也能很容易在另一个方向计算这个函数。即已知x，易于计算f（x），而已知f（x），却难于计算x。然而，一旦给出f（x）和一些秘密信息y，就很容易计算x。在 [公开密钥][Link 2]密码中，计算f（x）相当于加密，陷门y相当于私有密钥，而利用陷门y求f（x）中的x则相当于解密。

## 详解 ##

编辑

1976年，美国学者Diffie和Hellman为解决密钥的分发与管理问题发表了著名论文《密码学的新方向》New Direction in Cryptography，提出一种密钥交换协议，允许在不安全的媒体上通过通讯双方交换信息，安全地传送秘密密钥，并提出了建立“ [公开密钥密码体制][Link 3]”(Public Key)的新概念。这篇文章中提出的公钥密码的思想：若每一个用户A有一个加密密钥ka，不同于解秘密钥ka’，加密密钥ka公开，ka’保密，当然要求ka的公开不至于影响ka’的安全。若B要向A保密送去明文m，可查A的 [公开密钥][Link 2]ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密钥ka’对c进行解密得到m。当时他们还没有实现这种体制的具体算法。公开密钥密码基于单向陷门函数。

所谓 [单向函数][Link 1]，人们认为有许多函数正向计算上是容易的，但其求逆计算在计算上是不可行的，也就是很难从输出推算出它的输入。即已知x，我们很容易计算f（x）。但已知f（x），却难于计算出x。

在物质世界中，这样的例子是很普遍的，如将挤出的牙膏弄回管子里要比把牙膏挤出来困难得多；燃烧一张纸要比使它从灰烬中再生容易得多；把盘子打碎成数千片碎片很容易，把所有这些碎片再拼成为一个完整的盘子则很难。类似地，将许多大素数相乘要比将其乘积因式分解容易得多。数学上有很多函数看起来和感觉像 [单向函数][Link 1]，我们能够有效地计算它们，但我们至今未找到有效的求逆算法。我们把离散 [对数函数][Link 4]、RSA函数作为单向函数来使用，但是，目前还没有严格的数学证明表明所谓这些单向函数真正难以求逆，即单向函数是否存在还是未知的。

在密码学中最常用的单向函数有两类，一是 [公开密钥][Link 2]密码中使用的单向陷门函数、二是消息摘要中使用的 [单向散列函数][Link 5]。

单向函数不能用作加密。因为用单向函数加密的信息是无人能解开它的。但我们可以利用具有陷门信息的单向函数构造公开密钥密码。

[Link 1]: https://baike.baidu.com/item/%E5%8D%95%E5%90%91%E5%87%BD%E6%95%B0/5886135
[Link 2]: https://baike.baidu.com/item/%E5%85%AC%E5%BC%80%E5%AF%86%E9%92%A5/7453570
[Link 3]: https://baike.baidu.com/item/%E5%85%AC%E5%BC%80%E5%AF%86%E9%92%A5%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6/11048976
[Link 4]: https://baike.baidu.com/item/%E5%AF%B9%E6%95%B0%E5%87%BD%E6%95%B0/6013318
[Link 5]: https://baike.baidu.com/item/%E5%8D%95%E5%90%91%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0/1742203