单向函数举例 1离散对数问题 Discrete logarithm Problem(DP 令素数p满足p-1含有另一大素数q(q整除p-1)及一整数 g,1<g<p-1 若给定整数X,求y= gx mod p,最多需要Llog2X」 +W(X)-1次乘法,W(X)为X中所有1的个数。如X=15,即 X=(111)2,Wx)=4,则g15=(g2)g)2·g)2gmod p,只需要3+4-1=6次乘法。 但是若给定p,g及y,求x,则为DLP问题,最快方法需 要L(p)=exp{(np)l/3(n(np)2/3}次运算。 当p=512位时,L(p)约为2256≈1077,计算上不可行, 因为2100%1030,计算要1016年。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 11/81mfy@ustc.edu.cn 现代密码学理论与实践 11/81 1.离散对数问题Discrete Logarithm Problem (DLP) 令素数p满足p-1含有另一大素数q (q整除p-1)及一整数 g, 1<g< p-1。 若给定整数x, 求y = gx mod p, 最多需要Llog2x｣ +w(x)-1次乘法, w(x)为x中所有1的个数。如x =15, 即 x =(1111)2 , w(x)=4, 则g15 =((g2)g)2·g)2·g mod p, 只需要3 + 4 -1=6次乘法。 但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需 要L(p)=exp{(lnp) 1/3(ln(lnp)) 2/3 }次运算。 当p=512位时, L(p)约为2256≈1077 , 计算上不可行, 因为2100≈1030 , 计算要1016年