2017-10-24 04:47:15

单向函数 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
函数
函数
编辑分类

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

基本信息

  • 中文名

    单向函数

  • 外文名

    One-way function

  • 表达式

    F(x)=y

  • 应用学科

    数学,高数

折叠 编辑本段 单向函数定义

一函数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。但若已给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 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,则为计算机上不可能。

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

折叠 编辑本段 交换性定义

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

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

阅读全文

热点资讯