单向函数

女爷i 2022-05-20 06:41 126阅读 0赞

# 单向函数 #

单向函数 (One-way function)是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算（多项式时间），但是给出一个随机输入的函数值，算出原始输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。 单向函数是否存在仍然是计算机科学中的一个开放性问题。事实上，如果单向函数存在，将证明复杂性类P/NP问题中，P不等于NP。  
用人话说，就是一个数经过一个函数变化，得出一个结果。你知道结果，就是不能反推出这个数是多少，实际上这个命题并没有被证明完全成立。

# 陷门单向函数 #

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

# 密码应用中的单项函数 #

前面说过，单向函数不能直接用作密码体制，因为它的求逆困难，用它加密的信息谁都不能解密。但是，单向函数在密码学领域里却发挥着非常重要的作用。一个最简单的应用就是口令保护。我们熟知的口令保护方法是用对称加密算法进行加密。然而，对称算法加密一是必须有密钥，二是该密钥对验证口令的系统必须是可知的，因此意味着验证口令的系统总是可以获取口令的明文的。这样在口令的使用者与验证口令的系统之间存在严重的信息不对称，姑且不说系统提供者非法获取用户口令的情况，一旦系统被攻破，可能造成所有用户口令的泄露。使用单向函数对口令进行保护则可以很好地解决这一问题。系统方只存放口令经单向函数运算过的函数值，验证是将用户口令重新计算函数值与系统中存放的值进行比对。动态口令认证机制多是基于单向函数的应用来设计的。  
单向函数的另一个应用是大家熟知的用于数字签名时产生信息摘要的单向散列函数。由于公钥密码体制的运算量往往比较大，为了避免对待签文件进行全文签名，一般在签名运算前使用单向散列算法对签名文件进行摘要处理，将待签文件压缩成一个分组之内的定长位串，以提高签名的效率。MD5和SHA-1就是两个曾被广泛使用的、具有单向函数性质的摘要算法。有些学者把现实中使用的密码算法分成三类，单向散列函数就是其中很重要的一类，另外两类分别是公开钥(或非对称、双钥)算法和秘密钥(或对称、单钥)算法。

# 陷门单向函数与公钥密码体制 #

可以毫不夸张地说，公钥密码体制的设计就是寻找陷门单向函数。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年前后都被破解。  
有关陷门单向函数的具体设计有兴趣的读者可以参考有关文献。只有了解了单向和陷门单向函数的概念以及陷门单向函数的设计，才能真正了解公钥密码体制的安全性。

以上来自百度百科