单向函数

单向函数 (One-way function)是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算（多项式时间），但是给出一个随机输入的函数值，算出原始输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。 单向函数是否存在仍然是计算机科学中的一个开放性问题。事实上，如果单向函数存在，将证明复杂性类P/NP问题中，P不等于NP。

简介背景1976年，Diffie W.和Hellman M.E.在他们的《密码学的新方向》一文中提出了公钥密码的概念。随后，在1978年，Rivest R.L.，Shamir A.和Adleman L.M.在其文《实现数字签名和公钥密码体制的一种方法》中最先提出了一种可行的实现方法，这就是我们广泛使用的RSA体制。RSA体制的提出真正使得互不相识的通信双方在一个不安全的信道上进行安全通信最终成为可能，也是CA服务的源泉。然而，人们很少关心当前幸福生活的背后有一位默默的奉献者—单向函数。1

给定任意两个集合和。 函数称为单向的，如果对每一个属于，很容易计算出函数的值，而对大多数y属于， 要确定满足的是计算上困难的(假设至少有这样一个x存在)。注意，不能将单向函数的概念与数学意义上的不可逆函数的概念混同，因为单向函数可能是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却不一定是单向函数。

还没有人能够从理论上证明单向函数是存在的。单向函数存在性的证明将意味着计算机科学中一个最具挑战性的猜想，即完全问题的解决，而关于完全性的理论却不足以证明单向函数的存在。有幸的是，现实中却存在几个单向函数的“候选”。说他们是“候选”，是因为他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定是单向函数。

一个最简单的、大家熟知的“侯选”单向函数就是整数相乘。众所周知，不管给定两个多大的整数，我们很容易计算出它们的乘积，而对于一个300位左右的十进制整数，即使已知它是两个大小差不多（150位左右的十进制数）的素数之积，用世界上计算能力最强的计算机，也没有办法在一个合理的时间内分解出构成这个整数的两个素数因子来。这里讲的“合理的时间”是指一个可度量的相当长的时间，比如人类或者地球的寿命等。

单向函数公式定义函数是一个单向函数当且仅当可以用一个多项式时间的算法计算，但是对于任意一个以为输入的随机化多项式算法，任意一个多项式，和足够大,使得

陷门单向函数显然，单向函数不能直接用作密码体制，因为如果用单向函数对明文进行加密，即使是合法的接收者也不能还原出明文了，因为单向函数的逆运算是困难的。与密码体制关系更为密切的概念是陷门单向函数。一个函数称为是陷门单向的，如果该函数及其逆函数的计算都存在有效的算法，而且可以将计算的方法公开，即使由计算f的完整方法也不能推导出其逆运算的有效算法。其中，使得双向都能有效计算的秘密信息叫做陷门(trap door)。

第一个陷门单向函数与上面介绍过的第二个单向函数候选类似：固定指数和模数的模指数运算。不同的是这次是固定指数和模数，前面是固定基数和模数。设和是整数，同上，关于指数和模的模指数运算函数,由,定义。又与实数域上概念类似，其逆运算也叫作求模的次根，即：给定整数、和，求整数使得成立(如果这样的a存在的话)。例如，5就是16模21的4次根，因为54 mod 21=16。显然，2也是16模21的4次根。大家可以尝试着求出16模21的另一个4次根，或者求一个整数，它模21没有4次根。

只要和是固定的，学过计算机的人都很容易设计出一个算法，对任何，可以有效地计算出,的值。与前面的离散对数问题相反，我们确切知道，也存在有效算法，对任何，可以容易地求出模的次根。有意思的是，如果只知道和，如何构造出该有效的算法却不得而知。换言之，不是单向函数，因为它的求逆不是困难的，尽管我们还不知道如何去做。然而，如果除了知道和以外，还知道构成n的素因子，就很容易构造出求模的次根的有效算法。因此，可以作为陷门单向函数，其中和可以用做公开信息，而的因子分解就是秘密的陷门。

模指数的一个特殊情况是当模具有特殊形式，仅由两个素数和构成，即。著名的RSA体制就是根据这个陷门单向函数设计出来的。

需要提醒的是，不能顾名思义地认为陷门单向函数是单向函数。事实上，陷门单向函数不是单向函数，它只是对于那些不知道陷门的人表现出了单向函数的特性。

密码应用中的单项函数前面说过，单向函数不能直接用作密码体制，因为它的求逆困难，用它加密的信息谁都不能解密。但是，单向函数在密码学领域里却发挥着非常重要的作用。一个最简单的应用就是口令保护。我们熟知的口令保护方法是用对称加密算法进行加密。然而，对称算法加密一是必须有密钥，二是该密钥对验证口令的系统必须是可知的，因此意味着验证口令的系统总是可以获取口令的明文的。这样在口令的使用者与验证口令的系统之间存在严重的信息不对称，姑且不说系统提供者非法获取用户口令的情况，一旦系统被攻破，可能造成所有用户口令的泄露。使用单向函数对口令进行保护则可以很好地解决这一问题。系统方只存放口令经单向函数运算过的函数值，验证是将用户口令重新计算函数值与系统中存放的值进行比对。动态口令认证机制多是基于单向函数的应用来设计的。

单向函数的另一个应用是大家熟知的用于数字签名时产生信息摘要的单向散列函数。由于公钥密码体制的运算量往往比较大，为了避免对待签文件进行全文签名，一般在签名运算前使用单向散列算法对签名文件进行摘要处理，将待签文件压缩成一个分组之内的定长位串，以提高签名的效率。MD5和SHA-1就是两个曾被广泛使用的、具有单向函数性质的摘要算法。有些学者把现实中使用的密码算法分成三类，单向散列函数就是其中很重要的一类，另外两类分别是公开钥(或非对称、双钥)算法和秘密钥(或对称、单钥)算法。2

陷门单向函数与公钥密码体制可以毫不夸张地说，公钥密码体制的设计就是寻找陷门单向函数。1976年，Diffie W.和Hellman M.E.提出公钥密码思想和陷门单向函数概念时，并没能给出一个陷门单向函数的实例。第一个陷门单向函数和第一个公钥密码体制RSA是Rivest R.L.，Shamir A.和Adleman L.M.在1978年才提出的。此后，人们又尝试过很多种单向函数的设计方法，比如利用背包问题、纠错码问题、因子分解问题、离散对数问题、有限自动机合成问题等，但当前除了离散对数和因子分解问题，其他陷门单向函数都被证明存在安全缺陷或者因为其复杂性不能归约到某个困难问题而无法得到广泛的认可。

基于离散对数问题的密码体制主要有数字签名标准（DSS）、椭圆曲线密码体制（ECC）和Diffie-Hellman密钥交换算法等。也有人认为Diffie-Hellman算法是第一个公钥密码算法，它发表的时间要早于RSA体制，但实际上，它并不能用于加密解密，而只能用于在非安全信道上进行密钥分配，真正第一个可以用于加密解密的公钥算法是RSA。

基于因子分解问题的密码体制除了大家熟知的RSA以外，还有Rabin算法、Feige-Fiat-Shamir算法等。后两个算法不被大家熟悉的主要原因是，一个只能用于身份认证，另一个虽然被证明其破译难度与大整数因子分解一样，但不能抵抗选择密文攻击。

基于有限自动机的密码体制FAPKC是我国著名学者陶仁骥教授于1985年首次提出的，该体制在1995年被攻破。后来有一些变种，但因为所基于的自动机理论不是广泛熟悉的理论，以及其前身被破解等原因，没有能够从安全性上得到人们广泛的认同。

背包密码体制是基于一般背包问题求解是NP难的，而递增背包的求解存在快速算法的原理来设计的。该体制提出后不久就被破解，而且破解方法同样适用于其所有变种。基于纠错码的第一个体制是McEliece体制，它是基于Goppa的解码存在快速算法而一般线性码的解码是NP难的原理设计的。该体制也在1992年被破解。基于类似的方法，国内知名学者王新梅等也提出了一系列基于纠错码的公钥密码体制，但在1992年前后都被破解。

有关陷门单向函数的具体设计有兴趣的读者可以参考有关文献。只有了解了单向和陷门单向函数的概念以及陷门单向函数的设计，才能真正了解公钥密码体制的安全性。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学