CoCalc Public FilesPollard Rho DLP.sagewsOpen with one click!
Author: Liljana Babinkostova
Views : 49
Compute Environment: Ubuntu 20.04 (Default)

Pollard Rho Method For Solving DLP

Description. This attack takes advantage of the Floyd's Cycle Finding algorithm. The SAGE function for this attack ``PRhoOnDLP" takes four inputs: prime p, primitive root g, the publuc value b=gxb=g^x mod p and the number of iterations.

def updatex(x,alpha,beta,p,g,b): if(x < (p/3)): return (b*x) % (p) if(x < (2*p/3)): return (x^2 ) % (p) return (g*x ) % (p) def updatea(x,alpha,beta, p): if(x < (p/3)): return alpha if(x < (2*p/3)): return (2*alpha ) % (p-1) return (alpha+1) % (p-1) def updateb(x,alpha,beta,p): if(x < (p/3)): return (beta+1 ) % (p-1) if(x < (2*p/3)): return (2*beta ) % (p-1) return beta def updateTuple(tupleIn, g,b): newX = updatex(tupleIn[0],tupleIn[1],tupleIn[2],tupleIn[3],g,b) newA = updatea(tupleIn[0],tupleIn[1],tupleIn[2],tupleIn[3]) newB = updateb(tupleIn[0],tupleIn[1],tupleIn[2],tupleIn[3]) return [newX,newA,newB,p] def PRhoOnDLP(g,b,p,rounds): x = 1 alpha = 0 beta = 0 highTuple = [x,alpha,beta,p] lowTuple = [x,alpha,beta,p] found = False counter = 0 while( (not found) and (counter < rounds)): lowTuple = updateTuple(lowTuple,g,b) highTuple = updateTuple(highTuple,g,b) highTuple = updateTuple(highTuple,g,b) if(highTuple[0] == lowTuple[0]): found = True print("Number of Iterations Before Reaching a Collision" , counter) u = (highTuple[1] - lowTuple[1]) % (p-1) v = (-1)*(highTuple[2] - lowTuple[2]) % (p-1) #temp1 = power_mod(g,highTuple[1],p) * power_mod(b,highTuple[2],p) % p #print(temp1) #temp2 = power_mod(g,lowTuple[1],p) * power_mod(b,lowTuple[2],p) % p #print(temp2) gcdOut = xgcd(v,p-1) #print(gcdOut) k = 0 found2 = False while (not found2): k += 1 x = ZZ( (u*gcdOut[1]+k*(p-1))/gcdOut[0]) % (p-1) tempVal = power_mod(g,x,p) if(tempVal == b): return x counter += 1 print("The attack was unsuccessful") return -1
############################################ # EXAMPLE # ############################################ p = next_prime(12345678977) g=primitive_root(p) x = 777 b = power_mod(g,x,p) b proposedVal = PRhoOnDLP(g,b,p,1000000) proposedVal if(power_mod(g,x,p) == power_mod(g,proposedVal,p)): print ("The Discrete Log Problem is solvable")
12014768744
Error in lines 6-6 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 1, in <module> NameError: name 'PRhoOnDLP' is not defined