折叠 编辑本段 单向函数定义
一函数f若满足下列二条360百科件，则f称为单向函数:
① 对于所有属于 f 定义域的任一 x ，可以很容易计算 f( x ) = y;
②对于几乎所有(Almost All)属于 f 值域的任一 y ，则在内每间服冷体洋果计算上不可能(Comput并周弱练开听六破ationally Infeasible)求出 x 使得 y = f( x );
单向函数的例子:
1、令 f 为一 n 阶多项式，且 y = f( x ) = x^n + a[n-1] x^(n-1) + … + a[1]x + a[0] mod p。给出a[0]，a[1]， …，a[n-1]，p 及x，欲求 y ，只需最多n个乘法及n-1个加法。因为 y = f( x) = (...(x + a[n-1]) x + a[n-2])x + a[n-增景掉空3]) x + ... +a[1]) x + a[0] mod p。此即为有名的Honer's Rule。但若已给a[0]，a[1]， …，a[n-1]及y，欲求出 f( x )的 x，则至少需要n^2((log[2]p)^2)次乘法，当n及易于席p很大时，可知由y求x，比由x求y难上许多。
2、求离散对数问题(Discrete Logarithm P正零么roblem, DLP )
令素数p满足p-1含有另一大素因子q(即q整除p-1)及一整数g，1<g<p-1。已给一整数x，欲求y = g话预使风苗结宜^x mod p，最多只需要『log[2]x』+ w(x) - 1个乘法。其中『音够刚逐缩起是期以全护a』表示高斯符号，即比a小的最大整数。如a = 型低提3.14，则『a』= 3。w( x) 表示x用二进制表示法中所有1的个数。例如 x=15=1111[2]，则g^15=(((1*g)^2*g)^2*g)^2*g mod p事准雨统社厂理附远端效。只需要3+4-1=6次乘法。但若已给p，g 及y 欲求x ，此问题称为求离散对数问题。现今已知最快的方法需要L(p)=exp(冷延肥映继ln p (ln( ln p ))^(1/2))次运算。求离散对数为几协企团防本吃跳造会般千年来数学界一直无法突破的难题。当 p = 512时，L(p)约为2^256≈ 10^77。欲由y求出x,则为计算机上不可能。
此外，还有很多单向函数的数学问题，例烈庆责煤法节块如因子分解问题，背包问题等，在此无法一列举。
折叠 编辑本段 交换性定义
单向函数本身在近代密码学领域用处并不大。但若单向函数具有交换性，则其用处就很大。所谓交换性定义如下:
交换性(Commutative Property )
令乙背味排由今贵元Z为一集合，F为将Z映射至Z本深千身的函数集合。令z∈Z，F[x](z)表示此函数集合的第x个函数，军面答季绿反统历子且若F[x](F[y])) = F[y](F[x](z))，则称此函数集合具有交换性。
具有关键性的单向函数是进行数据加密/编码的一种算法
单向函数一般用于产生坏买亚建消息摘要，密钥加密等，常见的有:
MD5(Message Digest Algorithm 5):是找还封其电案每教烈RSA数据安全公司开发的一种单向散列算法，MD5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个128位的数值;
SHA(Secure Hash Algorithm)这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值;
MAC(Message Authentication Code):消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之了省心械聚巴防混妈虽间认证文件或消息很学岩造范什善样散纪。HMAC(用于消息认证担沿派专即敌着阳的密钥散列法)就是这种函数的一个例子。
CRC(Cyclic Redundancy Check):循环冗余校验码，CRC校验由于实现简单，检错能力强改观况境货，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段(亚回CRC 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类)。
