CoCalc Public FilesPollard Rho DLP.sagews
Authors: Liljana Babinkostova, William Unger
Views : 172
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=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,tupleIn[3]]

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
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
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 Number of Iterations Before Reaching a Collision 98664 777 The Discrete Log Problem is solvable