Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Avatar for Foundations of Public Key Cryptography.
 Download
1537 views
ubuntu2004
Tweet
Share
Share

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,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 1. Let p= 12345679007, g=5, b=12014768744. Solve the DLP b=gxb=g^x using PRhoOnDLP.


p = 12345679007
g= 5
b = 12014768744
proposedVal = PRhoOnDLP(g,b,p,1000000)
print("The value the PRhoOnDLP returned was" , proposedVal)
if(b == power_mod(g,proposedVal,p)):
    print ("The Discrete Log Problem is solvable")
Number of Iterations Before Reaching a Collision 98664 The value the PRhoOnDLP returned was 777 The Discrete Log Problem is solvable

Example 2. Let p= 1561561567, g=5, b=26268860. Solve the DLP b=gxb=g^x using PRhoOnDLP.

p = 1561561567
g = 117
b = 26268860
proposedVal = PRhoOnDLP(g,b,p,1000000)
print("The value the PRhoOnDLP returned was" , proposedVal)
if(b == power_mod(g,proposedVal,p)):
    print ("The Discrete Log Problem is solvable")
Number of Iterations Before Reaching a Collision 48293 The value the PRhoOnDLP returned was 987654321 The Discrete Log Problem is solvable