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
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)
gcdOut = xgcd(v,p-1)
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