文档介绍：公钥密码学的理论基础—单向函数
1976年,Diffie 《密码学的新方向》一文中提出了公钥密码的概念。随后,在1978年,Rivest .,Shamir 《实现数字签名和公钥密码体制的一种方法》中最先提出了一种可行的实现方法,这就是我们现在广泛使用的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 2