公钥密码学的理论基础.docx

公钥密码学的理论基础—单向函数 1976年，Diffie W.和Hellman M.E.在他们的《密码学的新方向》一文中提出了公钥密码的概念。随后，在1978年，Rivest R.L.，Shamir A.和Adleman L.M.在其文《实现数字签名和公钥密码体制的一种方法》中最先提出了一种可行的实现方法，这就是我们现在广泛使用的RSA体制。RSA体制的提出真正使得互不相识的通信双方在一个不安全的信道上进行安全通信最终成为可能，也是我们今天CA服务的源泉。然而，人们很少关心当前幸福生活的背后有一位默默的奉献者—单向函数。 　　单向和陷门单向函数的概念是公钥密码学的核心，可以说公钥密码体制的设计就是陷门单向函数的设计。那么什么是单向函数？什么是陷门单向函数？他们的密码学意义何在？本文试图作一个初浅的介绍。 　　1 单向函数 　　给定任意两个集合X和Y。 函数f：X Y 称为单向的，如果对每一个x属于X，很容易计算出函数f(x)的值，而对大多数y属于Y， 要确定满足y=f(x)的x是计算上困难的(假设至少有这样一个x存在)。注意，不能将单向函数的概念与数学意义上的不可逆函数的概念混同，因为单向函数可能是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却不一定是单向函数。 　　目前，还没有人能够从理论上证明单向函数是存在的。单向函数存在性的证明将意味着计算机科学中一个最具挑战性的猜想P=NP，即NP完全问题的解决，而关于NP完全性的理论却不足以证明单向函数的存在。有幸的是，现实中却存在几个单向函数的“候选”。说他们是“候选”，是因为他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定是单向函数。 　　一个最简单的、大家熟知的“侯选”单向函数就是整数相乘。众所周知，不管给定两个多大的整数，我们很容易计算出它们的乘积，而对于一个300位左右的十进制整数，即使已知它是两个大小差不多(150位左右的十进制数)的素数之积，用世界上计算能力最强的计算机，也没有办法在一个合理的时间内分解出构成这个整数的两个素数因子来。这里讲的“合理的时间”是指一个可度量的相当长的时间，比如人类或者地球的寿命等。 　　另一个单向函数的侯选就是固定基数和模数的模指数运算。设n和a是整数，而且1 　　2 陷门单向函数 　　显然，单向函数不能直接用作密码体制，因为如果用单向函数对明文进行加密，即使是合法的接收者也不能还原出明文了，因为单向函数的逆运算是困难的。与密码体制关系更为密切的概念是陷门单向函数。一个函数f：X Y 称为是陷门单向的，如果该函数及其逆函数的计算都存在有效的算法，而且可以将计算f的方法公开，即使由计算f的完整方法也不能推导出其逆运算的有效算法。其中，使得双向都能有效计算的秘密信息叫做陷门(trap door)。 　　第一个陷门单向函数与上面介绍过的第二个单向函数候选类似：固定指数和模数的模指数运算。不同的是这次是固定指数和模数，前面是固定基数和模数。设m和n是整数，Zn同上，关于指数m和模n的模指数运算函数gm,n:：Zn Zn由gm,n(a)=am mod n定义。又与实数域上概念类似，其逆运算也叫作求x模 n的m次根，即：给定整数m、n和x，求整数a使得am mod n=x成立(如果这样的a存在的话)。例如，5就是16模21的4次根，因为54 mod 21=16。显然，2也是16模21的4次根。大家可以尝试着求出16模21的另一个4次根，或者求一个整数x，它模21没有4次根。 　　只要m和n是固定的，学过计算机的人都很容易设计出一个算法，对任何a，可以有效地计算出gm,n(a)的值。与前面的离散对数问题相反，我们确切知道，也存在有效算法，对任何x，可以容易地求出x 模 n的m次根。有意思的是，如果只知道m和n，如何构造出该有效的算法却不得而知。换言之，gm,n(a)不是单向函数，因为它的求逆不是困难的，尽管我们还不知道如何去做。然而，如果除了知道m和n以外，还知道构成n的素因子，就很容易构造出求模 n的m次根的有效算法。因此，gm,n可以作为陷门单向函数，其中m和n可以用做公开信息，而n的因子分解就是秘密的陷门。 　　模指数的一个特殊情况是当模n具有特殊形式，仅由两个素数p和q构成，即n=pq。著名的RSA体制就是根据这个陷门单向函数设计出来的。 　　需要提醒的是，不能顾名思义地认为陷门单向函数是单向函数。事实上，陷门单向函数不是单向函数，它只是对于那些不知道陷门的人表现出了单向函数的特性。 　　3 单向函数的密码学应用 　　前面说过，单向函数不能直接用作密码体制，因为它的求逆困难，用它加密的信息谁都不能解密。但是，单向函数在密码学领域里却发挥着非常重要的作用。一个最简单的应用就是口令保护。我们熟知的口令保护方法是用对称加密算法进行加