所谓单向函数, 指的是已知自变量求函数值容易, 已知函数值求自变量在计算上不可行的函数。单向函数在密码学中有着重要的作用。单向函数可用于构造产生消息摘要的散列算法, 也可以应用于数字签名方案。在公开密钥加密体系中, 加密函数应是单向函数。
定义1:若函数y=F (x) , x∈D, 对于任意的x1, x2∈D, x1≠x2, 都有F (x1) ≠F (x2) , 则称y=F (x) , x∈D是一个一一映射。
在诸多研究者给出的单向函数的定义中, 有不少并没有指出单向函数必须是一一映射。然而, 从单向函数的实际应中我们可以知道, 有价值的单向函数应该是一一映射或者几乎是一一映射。
Fk, p (x) =xk (mod p) (0≤x
定理1:函数Fk, p (x) =xk (mod p) (x∈Zp, k≥3) 是一一映射的一个充分必要条件是对于k的任意一个因子ki, 都有Fki, p (x) 是一一映射。
充分性的证明:设k=ki×k0, 由于x ki= (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) (x2) , 进而F (k0, p) (F (ki, p) (x1) ) ≠F (k0, p) (F (ki, p) (x2) ) , 即F (k, p) (x1) ≠F (k, p) (x2) , 充分性得证。
必要性的证明:反证法。假设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, 都有F (ki, p) (x) 是一一映射。
定理2:函数F (k, p) (x) =xk (mod p) (x∈Zp, k≥3) 是一一映射的一个充分必要条件是对于p的任意一个因子pi, 有p=pi*p0, 且gcd (pi, p0) =1, F (k, p i) (x) 是一一映射。
充分性的证明:反证法。假设对于p的任意一个因子pi, 有p=pi*p0, 且gcd (pi, p0) =1, F (k, p i) (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, p i) (x) 是一一映射, 据给定条件也可以推导出F (k, p0) (x) 也是一一映射, 故有x1 (mod pi) =x2以及x1 (m o d p0) =x2。设x1=α1*pi+c, x2=α2*pi+c, α1、α2与c均是非负整数。由于x1≠x2, 故α1≠α2, 不妨设α1<α2=a+α1。由于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_0。由于x2
必要性的证明:只要能够证明以下两种情况下F (k, p) (x) 不是一一映射即可:1.存在p的因子pi, 使得F_ (k, p_i) (x) 不是一一映射;
(2) 存在p的因子pi, 使得gcd (pi, p0) ≠1。
第一种情况:设x1, x2∈Z (pi) , x1≠x2, x1k (mod pi) =x2k。令x1k=α1*pi+c, x2k=α2*pi+c, 则p0kx1k=p0k*α1*p i+p0k*c, p0kx2k=p0k*α2*pi+p0k*c, 显然有p0kx1k (mod pi*p0) =p0k*x2k, p0*x1, p0*x1∈Z_p, 故这种情况下F (k, p) (x) 不是一一映射。
第二种情况:存在p的因子pi使得gcd (pi, p0) ≠1可以等价地表述成:p存在一个因子, 这个因子是某个素数的平方。不妨设这个因子为pj2。根据证明第一种情况时得到的结论, 只要能证明 (x) 不是一一映射, 就可以证明F (k, p) (x) 不是一一映射。由于k≥3, 故有 (0) = (p j) =0, 所以 (x) 不是一一映射。综合两种情况, 必要性亦得证。
构造具有交换性的单向函数组的方法:首先选择一个较小的奇素数k。利用穷举法计算出集合P={p1, p2, p3, …, pn}, P表示一定范围内符合F (k, pi) (x) 是一一映射的奇素数pi的集合。根据定理2可知:p=是使F (k, p) (x) 为一一映射的一个值, 并且可以利用计算机编写程序在很短的时间内算出一个较大的p。Hash函数一般要求输入至少为128bit, 那么p是一个50位的十进制数足以满足要求。根据定理2的推论, K={k, k2k3, …, kn}中的元素都满足F (ki, p) (x) 是一一映射, 且i的值越大, 函数值序列的随机程度越高。这样, 就构造出了一个单项一一映射, 且可以得到一个足够大的指数值。
实例:取k=3, 穷举251以内的pi, 并进行连乘, 得到一个53位的十进制的p:
p=11921339843026105141727226869027254772933824147488255。
取k=38, 则F (k, p) (x) 即是所求函数。
摘要：本文论述了关于函数Fk, p (x) =xk (mod p) , (0≤x<p, k>3) 为一一映射的两个条件, 并提供了一种构造单向一一映射的方法。
关键词：单向函数,一一映射,数字签名,散列算法
参考文献
[1] Oded Goldreich, Leonid A Levin, NoamNisan“, On Constructing 1-1 One-WayFunctions”, Electronic Colloquium onComputational Complexity (ECCC) , 2 (29) , 1995.
[2] Oded Goldreich, Foundations ofCryptography:Basic Tools, CambridgeUniversity Press, 2001.