单向函数满足 对于所有属于 f 定义域的任一 x ，可以很容易计算 f( x ) = y； 对于几乎所有属于 f 值域的任一 y ，则在计算上不可能求出 x 使得 y = f( x )。

单向函数定义

交换性定义

单向函数定义

一函数f若满足下列二条件，则f称为单向函数：

① 对于所有属于 f 定义域的任一 x ，可以很容易计算 f( x ) = y；

②对于几乎所有（Almost All）属于 f 值域的任一 y ，则在计算上不可能（Computationally 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。但若已给[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 Problem, 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,则为计算机上不可能。

此外，还有很多单向函数的数学问题，例如因子分解问题，背包问题等，在此无法一列举。

交换性定义

单向函数本身在近代密码学领域用处并不大。但若单向函数具有交换性，则其用处就很大。所谓交换性定义如下：

交换性（Commutatve 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 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。