sage之离散对数求解ckm1607011的博客-

sage中求解离散对数我目前知道的四个函数：discrete_log(a,base,ord,operation)，discrete_log_rho(a,base,ord,operation)，discrete_log_lambda(a,base,bounds,operation)，bsgs(base,a,bounds,operation)；这四个函数分别是通用的求离散对数的方法，求离散对数的Pollard-Rho算法，求离散对数的Pollard-kangaroo算法（也称为lambda算法）以及小步大步法；

参数说明：对于discrete_log与discrete_log_rho，求解以base为底，a的对数；ord为base的阶，可以缺省，operation可以是’+’与’*’，默认为’*’；对于discrete_log_lamda，bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内。

下面分别举例使用这些函数对ElGamal的分析与Ecc的分析。

 //首先找到一个素数p p=next_prime(200520052005) //p=20052005200520052031 //定义有限域GF(p) G=GF(p) //找一个模p的原根 gp ('znprimroot(20052005200520052031)') //Mod(6, 20052005200520052031)，说明6是模p的原根 //因此6可作为生成元 g=G(6) //生成私钥 x=G(ZZ.random_element(p-1)) //公钥y=g^x mod p，由于已经定义在GF(p)上，因此g**x就是g^x mod p y=g**x //计算离散对数的通用方法 discrete_log(y,g) //验证是否求解正确 discrete_log(y,g)==x //True //计算离散对数的lambda方法 discrete_log_lambda(y,g,(floor(ZZ(x)/2),2*ZZ(x))) //同样正确求解 //小步大步法计算离散对数 bsgs(g,y,(floor(ZZ(x)/2),2*ZZ(x)))

上面是以discrete_log举例，discrete_log_rho参数列表与discrete_log一致，因此用法相同；只不过，由于discrete_log_rho是基于随机性的概率型算法，因此不一定每次都能找到，不过多一个方法总归是好的；其次，https://xz.aliyun.com/t/2780里面详细介绍了Pollard Rho算法，这个算法起作用是有条件的。

此算法适用于生成元的阶的素因子都是大数的情形，计算元素的阶的函数如下。

 //加法阶 n=g.order();n //乘法阶 n=g.multiplicative_order();n

可以看到加法阶比乘法阶大1。

下面介绍在椭圆曲线上求解离散对数。下例为2013年SECCON CTF quals 中的 Cryptanalysis。

 a = 1234577 b = 3213242 n = 7654319 //有限域GF(n)上的椭圆曲线y^2 = x^3 + a*x + b mod n E = EllipticCurve(GF(n), [0, 0, 0, a, b]) //生成元 base = E([5234568, 2287747]) //公钥 pub = E([2366653, 1424308]) //求解私钥，通用方法；注意这里的运算要换成加法 discrete_log(pub,base,operation='+') //求解私钥，Rho方法 discrete_log_rho(pub,base,operation='+') //此情形Rho方法也可以求解，而且可以感觉到比通用方法要快 ///求解私钥，lambda方法 discrete_log_lambda(pub,base,(floor(1584718/2),2*1584718),operation='+') //小步大步发计算离散对数 bsgs(base,pub,(floor(1584718/2),2*1584718),operation='+')