一种新的构造单向一一映射的方法

1、摘要:本文论述了关于函数Fk,p(x)二xk(mod p),(0 <x&lt;p,k&gt;3)为一一映射的两个条件，并提供了一种构造单向一一映射的方法。关键词:单向函数映射数字签名散列算法所谓单向函数，指的是已知自变量求函数值容易，已知函数值求自 变量在计算上不可行的函数。单向函数在密码学中有着重要的作用。 单向函数可用于构造产生消息摘要的散列算法，也可以应用于数字签名方案。在公开密钥加密体系中，加密函数应是单向函数。定义1:若函数y=F(x),x D,对于任意的 x1,x2 D,x1工x2都有F(x1)工 F(x则称 y=F(x),x D 是一个一一映射。在诸多研究者

2、给出的单向函数的定义中，有不少并没有指出单向 函数必须是一一映射。然而，从单向函数的实际应中我们可以知道，有 价值的单向函数应该是映射或者几乎是映射。Fk,p(x)=xk(mod p)(0< x&i;RSA算法的加密函数，RSA加密体制的假设之一就是这个函数是单向函数。适当选取k和p的值，它就是一个一一映射。Oded Goldreich,Le on id A Levi n,Noam Nisa n 三人提 出过一种基于RSA算法的一一映射构造方案。利用RSA的规则选取 k和p的值。由于RSA的解密是无歧义的，那么构造出来的函数必然 是单向一一映射。然而 RSA参数的选取是比较复杂的

3、。下面笔者介绍一种新的构造基于Fk,p(x)二xk(mod p)(x Zp)的一一映射的方法。定理1:函数Fk,p(x)=xk(mod p)(x Zp,k >3是一一映射的一个充分必要条件是对于k的任意一个因子ki,都有Fki,p(x)是一一映射。充分性 的证明：设k=ki *0,由于xki=(xki(mod p)(mod p),故 Fk,p(x)=xki*k0(mod p)=(xki(mod p)k0(mod p)=F(k0,p)(F(ki,p)(x)。由 于F(ki,p)(x),F(k0,p)(x)都是一一映射，故对于任意 x1,x2 Zp,都有F(ki,p)(x1)工 F(ki,p

4、)进而 F(k0,p)(F(ki,p)(x1)工 F(k0,p)(F(ki,即(x2),F(k,p)(x1)工F(k,p)充分性得证。必要性的证明：反证法。假设F(k,p)(x)=xk(mod p)(x Zp,k >3是一 一映射，存在k的因子ki,使得F(ki,p)(x)不是一一映射。不妨设x1,x2 Zp,x1 工x2且 x1ki(mod p)=x2ki,贝卩 x1ki*k0(mod p)=x2ki*k0,即 F(k,p)(x1)=F(k,p)(x2),导致矛盾。必要性得证。推论:若 F(k,p)(x)是一一映射，则对于k的任意整数次幕ki,都有(x) 是映射。定理 2:函数 F(k

5、,p)(x)=xk(mod p)(x Zp,k >3是一一映射的一个充 分必要条件是对于p的任意一个因子pi,有p=pi*p0,且 gcd(pi,p0)=1,F(k,pi)(x)是映射。充分性的证明：反证法。假设对于p的任意一个因子pi,有p=pi*p0, 且 gcd(pi,p0)=1,F(k,pi)(x)是一一映射，而 F(k,p)(x)不是一一映射。不妨设 x1,x2 Zp,x1 工 x2且 x1k(mod p)=x2k。由 x1k(mod p)=x2k 得到x1k(mod pi)=x2k 以及 x1k(mod p0)=x2k。由于 F(k,pi)(x)是一一映射， 据给定条件也可以

6、推导出F(k,pO)(x)也是一一映射，故有x1(modpi)=x2 以及 x1(mod p0)=x2。设 x1= a 1*pi+c,x2= apl+c, a 1 a2与 c 均是非负整数。由于x1工x2故a 1 Ma不妨设 a 1& It； a 2=a+。由于x1(mod p0)=x2,故有 x1(mod p0)=x2 (mod p0)=(a*pi)(mod p0)+x1(mod p0),因此(a*pi)(mod p0)=0,即 a*pi|p_O。由于 x2&lt;p=pi*p0,故 a 2&lt;pO,a= - &lt;p0 而 gcd (pi,p0)=1,

7、所以不可能有 a*pi|pO,导出 矛盾。充分性得证。必要性的证明：只要能够证明以下两种情况下F(k,p)(x)不是一一映射即可:1.存在p的因子pi,使得F_Kp_i)(x)不是一一映射；(2)存在p的因子pi,使得gcd(pi,pO) M1第一种情况：设 x1,x2 Z(pi),x1 mx2,x1kmod pi)=x2k。令 x1k= a 1*pi+c,x2k= a 2*pi+c,则p0kx1k=p0k* a 1*pi+p0k*c,p0kx2k=p0k* *pi+pOk*c, 显然有 p0kx1k(mod pi*p0)=p0k*x2k,p0*x1,p0*x1 Z_p,故这种情况下F(k,p

8、)(x)不是一一映射。第二种情况：存在p的因子pi使得gcd (pi,p0) 河以等价地表述 成:p存在一个因子，这个因子是某个素数的平方。不妨设这个因子为 pj2。根据证明第一种情况时得到的结论，只要能证明(x)不是一一映射,就可以证明F(k,p)(x)不是一一映射。由于k>3故有(O)=(pj)=O,所以(x) 不是映射。综合两种情况，必要性亦得证。构造具有交换性的单向函数组的方法：首先选择一个较小的奇素 数k。利用穷举法计算出集合P=p1,p2,p3,pnp表示一定范围内符 合F(k,pi)(x)是一一映射的奇素数pi的集合。根据定理2可知:p二是使 F(k,p)(x)为一一映射的

9、一个值，并且可以利用计算机编写程序在很短 的时间内算出一个较大的 p。Hash函数一般要求输入至少为128bit, 那么p是一个50位的十进制数足以满足要求。根据定理2的推论,K=k,k2,k3,kri中的元素都满足(x)是一一映射，且i的值越大，函 数值序列的随机程度越高。这样，就构造出了一个单项一一映射，且可 以得到一个足够大的指数值。实例:取 k=3,穷举251以内的pi,并进行连乘，得到一个53位的十 进制的p:4772933824147488255取k=38，则F(k,p)(x)即是所求函数。参考文献1 Oded Goldreich,Leo nid A Levi n, Noam Nisa n, “On Con struct ing 1-1 On e-Way Fun cti ons ”，Electro ni Col