ELLIPTIC CURVE DIGITAL SIGNATURE

import numpy
import itertools
import math
import sympy.ntheory
############################################################################################################################
# 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 range(1, e + 1):
        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)


def ASCIIPad(Mess,Mod):
    K = []
    for letter in Mess:
        K.append(ord(letter))
    L = Mod.ndigits()
    l = len(K)
    y = ZZ(math.floor(L/3))
    count = 0
    padded = []
    buffer = ""
    for numChar in K:
        numChar+=100
        buffer+=str(numChar)
        count+=1
        if count==y:
            padded.append(ZZ(buffer))
            buffer = ""
            count = 0
    if len(buffer)>0:
        padded.append(ZZ(buffer))
    return padded

def ASCIIDepad(Number):
    N = "";
    n = Number.ndigits() % 3;
    if (n > 0):
        print("This is not a padded ASCII string\n");
    else:
        L = [((Number - (Number % (1000^i)))/1000^i)%1000 - 100 for i in range(Number.ndigits()/3)];
        for i in range(Number.ndigits()/3):
            N = chr(L[i]) + N;
    return(N);

def ECEmbed (Message, gp, tolerance):
    p = ZZ(math.floor(gp[2] / (tolerance + 1)))
    M = ASCIIPad(Message, p)
    packets = len(M)
    pointlist = [0]*packets
    for j in range(0, packets ):
        N = M[j]
        pointlist[j] = ECSearch(tolerance * N, tolerance * (N + 1) - 1, gp)
    return(pointlist)

def ECUnembed (pointlist, tolerance):
    k = len(pointlist)
    paddedasciilist=[0]*k
    for j in range(0, k ):
        pointlist[j][0]=ZZ(pointlist[j][0])
        toType = ZZ(QQ((pointlist[j][0])/tolerance).floor())
        paddedasciilist[j] = ((pointlist[j][0])/tolerance).floor()
    returnStr = ""
    for paddedItem in paddedasciilist:
        buffer = ASCIIDepad(paddedItem)
        returnStr+= buffer
    return returnStr

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])

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)

ECDouble is a procedure that computes P+P where P is a point on a given elliptic curve group G.

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)

ECInverse is a procedure that finds an inverse of a group element P on an elliptic curve group G.


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]])

findptOrder is a procedure that computes order of a group element (point) in an eliptic curve group E. The command for computing order of an elliptic curve group E in sage is E.order( ) or E.cardinality( ).

def findptOrder(point,group):
    E = EllipticCurve(GF(group[2]),[group[0],group[1]])
    Ep = E(point[0],point[1])
    return Ep.additive_order()

The elliptic curve group is
 G= [453247983724987324739287983275982375923, 0, 48756928743475984375947598473598437598473597439857498375948375984375984375983551]
The order of the elliptic curve group is 48756928743475984375947598473598437598473597439857498375948375984375984375983552
The base point is g= [78657644, 16991537913472596716592338071192242226000171060940316650383793820397326594624617]
24378464371737992187973799236799218799236798719928749187974187992187992187991776

EXAMPLE 1. The following example illustrates how to generate a signature on the plaintext "Today" using the Elliptic Curve Digital Signature Schema (EC DSA). The signature is generated using the ASCII padded version of the plaintext and the EC DSA.

#Generate an elliptic curve group
A=453247983724987324739287983275982375923
B=0
p=next_prime(48756928743475984375947598473598437598473597439857498375948375984375984375983475)
G=[A,B,p] ############# Elliptic Curve Group
print("The elliptic curve group is\n G=",[A,B,p])
#################################################
# COMPUTE THE ORDER OF THE ELLIPTIC CURVE GROUP #
#################################################
E=EllipticCurve(GF(p),[A,B])
Gp = E.order() ##### Order of the elliptic group G
print("The order of the elliptic curve group is",Gp)

################################################
# CHOOSE A POINT ON THE ELLIPTIC CURVE GROUP G #
################################################
g=ECSearch(78657643,894579475973497, G)
print("The base point is g=",g)

##################################################################
# COMPUTE THE ORDER OF THE POINT g ON THE ELLIPTIC CURVE GROUP G #
##################################################################
gorder=findptOrder(g,G) ############# order of the point g
print("The order of the base point g is",gorder)

#########################
# CHOOSE A PRIVATE KEY  #
#########################
x= 3267452870001
print("The private key is x=", x)

#############################################
# COMPUTE THE PUBLIC ELLIPTIC CURVE POINT   #
#############################################

b=ECTimes(g,x,G)
print("The public elliptic curve point is\n b=", b)

The elliptic curve group is
 G= [453247983724987324739287983275982375923, 0, 48756928743475984375947598473598437598473597439857498375948375984375984375983551]
The order of the elliptic curve group is 48756928743475984375947598473598437598473597439857498375948375984375984375983552
The base point is g= [78657644, 16991537913472596716592338071192242226000171060940316650383793820397326594624617]
The order of the base point g is 24378464371737992187973799236799218799236798719928749187974187992187992187991776
The private key is x= 3267452870001
The public elliptic curve point is
 b= [17566544735431983712026375755888836036365834903701605548573320082144981869265965, 23848130856677747270630665750802737393249426947106690074248083069291730803714563]

EXAMPLE 2. The following example illustrates how to generate a signature on the plaintext "Today" using the Elliptic Curve Digital Signature Schema (EC DSA). The signature is generated using the ASCII padded version of the plaintext and the EC DSA and the key from Example 1.

# Step 1. Choose a plaintext
message = "Today"
m1 = ASCIIPad(message,(p/48).floor()) ######### ASCII padded version of the plaintext
m =m1[0]

# Step 2. Choose a random number r such that gcd(r, gorder)=1
r = 892173201 ###################### random number such that gcd(r, gorder)=1

# Step 3. Compute the point R on the elliptic curve group G using the base point g and the random number r
R = ECTimes(g,r,G)
Y=R[0] ####### this is the first coordinate of the point R

# Step 4. Compute the S using the ASCII padded message m, private key x, random number r and the elliptic curve point R.

m = ZZ(m)
x = ZZ(x)
Y= ZZ(Y)
r = ZZ(r)
S= mod((m+x*Y)/r,gord)

print("The elliptic curve signature is the pair \n Y=", Y, "\n S=", S)

The elliptic curve signature is the pair 
 Y= 9724134493832687712733750210292829353053460158844222041596059403416761384520382 
 S= 5473315643055236073462204269053253014519496239893926482579871838753145354487923

EXAMPLE 3. The following example illustrates how to verify the signature on the plaintext "Today" using the Elliptic Curve Digital Signature Schema (EC DSA).

U1 = ZZ(mod(m/S,gord))
U2 = ZZ(mod(Y/S,gord))
V=ECAdd(ECTimes(g,U1,G),ECTimes(b,U2,G),G)
if V==R:
    print ("Valid Signature")
else:
    print ("Invalid Signature")

Valid Signature