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