PollardRhoDLEC.sagews

ELLIPTIC CURVE POLLARD RHO ATTACK

import numpy
import itertools
import math
############################################################################################################################
# For all these procedures we are working with elliptic curve (EC) groups over Z_p where p is a prime number larger than 3.#
# An Elliptic Curve group will be represented by a triple [A,B,p] where                                                    #
#      (1) p is a prime number larger than 3                                                                               #
#      (2) A is the coefficient of x and                                                                                   #
#      (3) B is the constant term in  y^2 = x^3 + A*x + B mod p.                                                           #
#                                                                                                                          #
# A point in the group will be represented as a pair [x,y] where                                                           #
#      (1)  x is the x-coordinate of a solution                                                                            #
#      (2)  y is the y-coordinate of a solution                                                                            #
#      (3)  The identity will be represented by []                                                                         #
############################################################################################################################


def TonSh (a, Prime):
    if kronecker(a, Prime) == -1:
        pass
        print ("{0} does not have a square root mod {1}".format(a, Prime))
        return None
    elif Prime % 4 == 3:
        x = power_mod(ZZ(a), ZZ((Prime+1)/4),ZZ(Prime))
        return(x)
    else:
        #################################################################################
        # Determine e so that Prime-1 = (2^e)*q for some odd number q                   #
        #################################################################################

        e = ZZ(0)
        q = ZZ(Prime - 1)
        for j in itertools.count(1):
            if q % 2 == 0:
                e = ZZ(e + 1)
                q = ZZ(q / 2)
            else:
                break
        for i in range(1, 101):
            n = i
            if kronecker(n, Prime) == -1:
                break
        z = power_mod(ZZ(n),ZZ(q),ZZ(Prime))
        y = ZZ(z)
        r = ZZ(e)
        x = power_mod(ZZ(a),ZZ( (q-1)/2),ZZ( Prime))
        b = (a * x ** 2) % Prime
        x = (a * x) % Prime
        for i in itertools.count(1):
            if b == 1:
                break
            else:
                for m in itertools.count(1):
                    t = power_mod(ZZ(b), ZZ(2^m) ,  ZZ(Prime))
                    if t == 1:
                        mm = m
                        break
                t = power_mod(ZZ(y), ZZ(2^(r - mm - 1)),ZZ(Prime))
                y = power_mod(ZZ(t), ZZ(2),ZZ(Prime))
                r = mm
                x = (x * t) % Prime
                b = (b * y) % Prime
        return(x)

ECSearch is a procedure that searches for a point on a given elliptic curve with first coordinate between "lowerbound" and "upperbound". The lowerbound and the upperbound are positive random numbers.

import itertools
def ECSearch (lowerbound, upperbound, Group):
    p = Group[2]
    a = Group[0]
    b = Group[1]
    if (4 * a ** 3 + 27 * b ** 2) % p == 0:
        print ("This is not an elliptic curve.")
    else:
        for j in itertools.count(lowerbound):
            if j==lowerbound-1 or j>upperbound or j>upperbound:
                return "not found"
            j=j%p
            if kronecker(j ** 3 + a * j + b, p) == 1:
                x = (j ** 3 + a * j + b) % p
                var('z')
                L=TonSh(x,p)
                y = L
                return([j,y])

import sympy.ntheory
def FermatGreat (N):
    if sympy.ntheory.isprime(N):
        if N % 4 == 1:
            Z = two_squares(N)
            #print(Z)
            return(Z)
        else:
            print ("{0} is prime, but {1} mod 4 = 3".format(N, N))
    else:
        print ("{0} is not prime\n".format(N))

ECAdd is a procedure that computes the sum of two points on a given elliptic curve using the elliptic curve operation.

def ECAdd (Point1, Point2, Group):
    a = Group[0]
    b = Group[1]
    p = Group[2]
    if(Point1!=[]):
        x1 = Point1[0]
        y1 = Point1[1]
    if(Point2!=[]):
        x2 = Point2[0]
        y2 = Point2[1]
    if (4 * a ** 3 + 27 * b ** 2) % p == 0:
        print ("This is not an elliptic curve.")
    elif Point1 != [] and y1 ** 2 % p != (x1 ** 3 + a * x1 + b) % p:
        print ("Point 1 is not on the elliptic curve. \n")
    elif Point2 != [] and y2 ** 2 % p != (x2 ** 3 + a * x2 + b) % p:
        print ("Point 2 is not on the elliptic curve. \n")
    else:
        if Point1 == []:
            R = Point2
        elif Point2 == []:
            R = Point1
        else:
            if x1 == x2 and 0 == (y1 + y2) % p:
                R = []
            elif x1 == x2 and y1 == y2:
                R = ECDouble(Point1, Group)
            else:
                s = ((y1 - y2) / (x1 - x2)) % p
                x = (s ** 2 - x1 - x2) % p
                y = (s * (x1 - x) - y1) % p
                R = [x,y]
    return(R)

def ECDouble (Point, Group):
    a = Group[0]
    b = Group[1]
    p = Group[2]
    if Point != []:
        x1 = Point[0]
        y1 = Point[1]
        if (4 * a ** 3 + 27 * b ** 2) % p == 0:
            print ("This is not an elliptic curve.")
        elif Point != [] and y1 ** 2 % p != (x1 ** 3 + a * x1 + b) % p:
            print ("The point to double is not on the elliptic curve.")
        elif y1 == 0:
            R = []
        else:
            s = mod((3 * x1 ** 2 + a) / y1 / 2, p)
            x = (s ** 2 - 2 * x1) % p
            y = (s * (x1 - x) - y1) % p
            R = [x,y]
    else:
        R = []
    return(R)

def ECInverse (Point, Group):
    if Point == []:
        return(Point)
    else:
        p = Group[2]
        x = Point[0]
        y = Point[1]
        return([x,(p - y) % p])

ECTimes is a procedure that adds a point k-times (scalar) to itself for a given elliptic curve using the elliptic curve operation.

def ECTimes (Point, scalar, Group):
    ECIdentity=[]
    if Point == ECIdentity or scalar == 0:
        return(ECIdentity)
    else:
        E=EllipticCurve(GF(Group[2]),[Group[0],Group[1]])
        EPoint = E(Point[0],Point[1])
        cgret = scalar*EPoint
        if(cgret[0]==0 and cgret[1]==1 and cgret[2]==0):
            return ECIdentity
        return([cgret[0],cgret[1]])

def GroupOrder(Group): ############ Computes order of an elliptic curve group
    E = EllipticCurve(GF(Group[2]),[Group[0],Group[1]])
    return E.order()


def findptOrder(point,group): ############# Computes the order of a point on the elliptic curve group
    E = EllipticCurve(GF(group[2]),[group[0],group[1]])
    Ep = E(point[0],point[1])
    return Ep.additive_order()

ELLIPTIC CURVE Pollard's Rho Algorithm

def Rhof(point,P,Q,Group,j):
    if point!=[]:
        pointMod3 = ZZ(mod(point[0],3))
        if pointMod3 == 0:
            pt = ECAdd(point,P,Group)
        elif pointMod3 == 1:
            pt = ECDouble(point,Group)
        else:
            pt = ECAdd(point,Q,Group)
        return pt
    return None

def Rhofcoef(a,b,point,gorder):
    a1 = a
    b1 = b
    if point!=[]:
        pointMod3 = ZZ(mod(point[0],3))
        if pointMod3 == 0:
            a1 = ZZ(mod(a1+1,gorder))
        elif pointMod3 == 1:
            a1=(2*a1) % gorder
            b1=(2*b1) % gorder
        else:
            b1 = (b1+1) %gorder
        return [a1,b1]

def RhoOnEC(Q,P,Group,gorder):  #g --> P, y--> Q
    debug = False
    z=P
    t=P
    ab = [1,0]
    AB = [1,0]
    ############ This is Floyd's Cycle-Finding Method
    foundOne = False
    for j in itertools.count(1):
        if j>2425 and debug:
            print ("top of the loop {0}".format(j))
            print (ab)
            print (AB)
        ab = Rhofcoef(ab[0],ab[1],z,gorder)
        z = Rhof(z,P,Q,Group,j)
        if z==[]:
            d = gcd(ab[1],gorder)
            x = ZZ(mod(ab[0]/(-ab[1]), (gorder/d)))
            return x
        AB = Rhofcoef(AB[0],AB[1],t,gorder)
        t = Rhof(t,P,Q,Group,j)
        if t==[]:
            d = gcd(AB[1],gorder)
            x = ZZ(mod(AB[0]/(-AB[1]), (gorder/d)))
            return x
        AB = Rhofcoef(AB[0],AB[1],t,gorder)
        t = Rhof(t,P,Q,Group,j)
        if j==2458 and debug:
            print (t)
            print (z)
            print (z==t)
        if t==[]:
            d = gcd(AB[1],gorder)
            x = ZZ(mod(AB[0]/(-AB[1]) , (gorder/d)))
            return x
        elif z==t:
            d = gcd(AB[1]-ab[1],gorder)
            x =ZZ(mod((ab[0]-AB[0])/(AB[1]-ab[1]),(gorder/d)))
            return x

Example. The following example illustrates how elliptic curve private (encryption or signature) key can be recovered using the Pollard's Rho Attack. The public elliptic (encryption or signature) key is given by an elliptic curve group $G$, and two points $P$, $Q$ on the elliptic curve. It is known that $Q$ is a multiple of $P$ i.e. $Q=xP$. Note that this attack can be applied to elliptic curve encryption and elliptic curve signature.

p1 = next_prime(13276123213123)
A1 = 0
B1= 328
G1=[A1,B1,p1] ######################### Elliptic Curve Group
P1=[228287229281, 9234149811619]
Q1=[3412728539209, 5129210006826]
gord1 = findptOrder(P1,G1) ########### gord is the order of the point P in the elliptic curve group G

x = RhoOnEC(Q1,P1,G1,gord1)
print("The Discrete Log is x=",x)

The Discrete Log is x= 1266778

QQ1= ECTimes(P1,x,G1) ######## test the solution
Q1==QQ1

True