ECelgamal-example.sagews

import numpy
import itertools

############################################################################################################################
# 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 range(1, Prime):
        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)

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
            #print "test "+str(j)
            #print (kronecker(j ** 3 + a * j + b, p) )
            if kronecker(j ** 3 + a * j + b, p) == 1:
                x = (j ** 3 + a * j + b) % p
                var('z')
                #print("stuck here")
                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])
        #print type(EPoint)
        cgret = scalar*EPoint
        #print cgret[0]
        if(cgret[0]==0 and cgret[1]==1 and cgret[2]==0):
            return ECIdentity
        return([cgret[0],cgret[1]])
 

G=[3,2,next_prime(11696876878768768767867687687687687678768768766876879878111)]
G ####### Elliptic Curve Group
g=ECSearch(2378648723, 8927492873972973,G)
g ####### base element 
x=34239473274983742
x ####### private key 
b=ECTimes(g,x,G)

[3, 2, 11696876878768768767867687687687687678768768766876879878131] [2378648723, 6207257298628741512609567607483777943219211043692587796100] 34239473274983742

def listproduct (primelist):
    x = primelist
    k = len(primelist)
    print k
    result = 1
    for i in range(0, k):
        result = result * x[i][0] ^ x[i][1] #op(1, op(i, x)) ** op(2, op(i, x))
    return(result)

def listptorder (pt, Group, factoredGpOrder):
    ECIdentity = []
    x = factoredGpOrder
    k = len(factoredGpOrder)
    orderlist = set([])
    result = listproduct(factoredGpOrder)
    for i in range(0, k ):
        p =  x[i][0] #op(1, op(i, x))
        a =  x[i][1] #op(2, op(i, x))
        ord = 0
        for j in range(0, a ):
            result = result / p
            test = ECTimes(pt, result, Group)
            if test != ECIdentity:
                result = result * p
                ord = ord + 1
        if 0 < ord:
            orderlist = orderlist | set([[p,ord]])
    return(convert(orderlist, list))


def primeHPSonEC (y,g,Group,p):
    newg = []#ECIdentity
    for j in range(0, p ):
        if y == newg:
            break
        newg = ECAdd(newg, g, Group)
    return(j)


def powerHPSonEC (y,g,og,p,a,Group):
    gp = ECTimes(g, og / p, Group)
    newog = og
    newy = y
    c = 0
    partx = 0
    for i in range(0, a ):
        newy = ECAdd(y, ECInverse(ECTimes(g, partx, Group), Group), Group)
        newog = newog / p
        ypower = ECTimes(newy, newog, Group)
        c = primeHPSonEC(ypower, gp, Group, p)
        partx = partx + c * p ** i
    return(partx)

def HPSonEC (y,g,Group,factoredGpOrder):
    X = 0
    Ord = 1
    K = listptorder(g, Group, factoredGpOrder)
    k = len(K)
    ordg = listproduct(K)
    for j in range(1, k + 1):
        p = K[j][0]#op(1, op(j, K))
        powerp = K[j][1]#op(2, op(j, K))
        partx = powerHPSonEC(y, g, ordg, p, powerp, Group)
        if j == 1:
            X = partx
            Ord = p ** powerp
        else:
            X = crt([X,partx], [Ord,p ** powerp])
            Ord = Ord * p ** powerp
    return(X)

import math

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 = "";
    #Number = ZZ(Number[0])
    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):
            #print L[i]
            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)
    #print packets
    pointlist = [0]*packets
    for j in range(0, packets ):
        N = M[j]
#        N:=(op(0,op(1,M))[j]);
        pointlist[j] = ECSearch(tolerance * N, tolerance * (N + 1) - 1, gp)
        #print pointlist
    return(pointlist)

def ECUnembed (pointlist, tolerance):
    #print pointlist
    k = len(pointlist)
    paddedasciilist=[0]*k
    for j in range(0, k ):
        #print type(pointlist[j][0]/tolerance)
        #print pointlist
        #print paddedasciilist        
        #print "test this "+str((pointlist[j][0]/tolerance))
        #.floor() returns correct while math.floor() does not work
        #print (pointlist[j][0])
        pointlist[j][0]=ZZ(pointlist[j][0])
        toType = ZZ(QQ((pointlist[j][0])/tolerance).floor())
#        typed = type(toType)
#        print typed
        paddedasciilist[j] = ((pointlist[j][0])/tolerance).floor()
    returnStr = ""
    for paddedItem in paddedasciilist:
        #print paddedItem
        buffer = ASCIIDepad(paddedItem)
        returnStr+= buffer
        #print buffer
    return returnStr

Example. Create an elliptic curve public and private key.

G=[3,2,next_prime(1169687687876876876786768768768768767876876876687687987811546546545646541)]
G ####### Elliptic Curve Group
g=ECSearch(2378648723, 8927492873972973,G)
g ####### base element 
x=34239473274983742
x ####### private key 
b=ECTimes(g,x,G)
b

[3, 2, 1169687687876876876786768768768768767876876876687687987811546546545646659] [2378648723, 251129725725808360916423247622071249545935346397519406481708557006516860] 34239473274983742 [102185937035780644447440724514674909408114529521257498878576073830758885, 29294782479764415939896071953678258471598161093478693795502004627180723]

Example. Encrypt the plaintext "Cryptology" using the the elliptic curve and the key created in the previous example. The tolerance parameter is T=40.

m=ECEmbed("Cryptology",G, 40)
m ###### embedded plaintext into an elliptic curve group
r=34239473274983742
r ##### random number
h=ECTimes(g,r,G)
h
s=ECTimes(b,r,G)
s
c=ECAdd(m[0],s,G)
c
################################## The CIPHERTEXT is the pair of group elements h and c #####################################

[[6688568848488648448328448128842, 30713016421388513534069392095726691904699597855212477624228805094571897]] 34239473274983742 [102185937035780644447440724514674909408114529521257498878576073830758885, 29294782479764415939896071953678258471598161093478693795502004627180723] [531594751936260343069237726792546775307287241364648309851908704952472378, 62836598762052693815835015170177315163174591233643267255681661239022069] [60725488831383488099275639299974627203302101759526710107542683749459307, 786886098612758367049369768966181063935118105698230786854120868069958151]

%html
<strong>Example.</strong> Decrypt the ciphertext from the previous example. IN CLASS!

Example. Decrypt the ciphertext from the previous example. IN CLASS!

Example. Encryption of a plaintext represented by a list of points in the elliptic curve group G.

#########################################################################################################################
# Note: When running this example make sure you run them in order so that other cell's definitions are not used by sage # 
#########################################################################################################################

m=ECEmbed("This is a longer example. It uses multiple points. The points are listed right below and then the random number chosen and the last output is how many points are needed.",G, 40)
m ###### embedded plaintext into an elliptic curve group
r=3423947327498374254646554654645
r ##### random number
numPoints = len(m)
numPoints
h=[0]*numPoints
s=[0]*numPoints
c=[0]*numPoints
for counter in xrange(numPoints):
    h=ECTimes(g,r,G)
    s=ECTimes(b,r,G)
    c[counter]=ECAdd(m[counter],s,G)

[[7368168208605288208605287885288328448408128048565288048807888368488320, 121486482953176117528000809881749947571671902330970782925843120215624872], [8045845286928645288688608048605288368688328648208488328045288488448200, 903695374841292322370271174415204218208659055675797121100003842392500926], [8408648605845287368168045288488448208408648605287888568045288328208600, 452563156195183222674654981175834124068138520541249589841058897891287244], [8648048005288568208128168645287928048328448765287888408005288648168040, 354133454203841855971589741317387587553570850607256693528118869301689901], [8405288648168045288567888408008448365288408688367928048565287968168440, 566116327420959706426335734957260808053541488054698602617229920903468133], [8608048405287888408005288648168045288327888608645288448688648488688641, 190989246142380934866236751363212697612118794496744686603811386587621417], [5288208605288168448765288367888408845288488448208408648605287888568041, 425171620928964741474599056379821932316091568940530183178971060551595853], [5288408048048008048005840, 1036270550319895031743093327765070280126725147090778246179870977799274707]] 3423947327498374254646554654645 8

h
s
c

[502800681108808127999931477346298640902458497799276570157831511464842627, 249433093957737059630763632764052800806824499724831296249200563703070996] [758836381415980725873880391356898132106948925841767677664020161182662238, 172885080124927030627775664387974993851680223072695154225919344264781309] [[993011997632563665090520795819224461956877820256329108993458876624168267, 486967488472059785832649245344787601820108477716142036228174305706008047], [1025130127158111391286114497628784310721816018761263921410307202662962155, 1046214728711544478045606234428908877874990102826941182072699504231466650], [702163857070541572271486478402213299769149650327011285713214313411220209, 964390034282681070472559926854266573294570007713258722688970731401446070], [545974440942587589793355643326618406027250242128080874758407596428510512, 761850948586179337743907452723161818650832861623511156392451479702387930], [1007560043455625957074409098454581056661266112007216804759867237444073697, 568301847329160573315400903846138202220379078132258736522271094761757556], [197721450177956824925214814076136877509231101020546157774722389794437045, 364710051200340597882807263315974397500183542853128578183482144214813413], [1040787630887710087842592894781064728294150449155777473810980176110345869, 209262206482771129037093161089704974346792207851381833556910011562779092], [817585719106595758704863067855703256513213471986817100166846551663829691, 537939259557282367210288215732191700156429531225372888960276076554578723]]

z=ECTimes(h,x,G)
z
d = [0]*len(c)
for counter in xrange(len(c)):
    d[counter] = ECAdd(c[counter],ECInverse(z,G),G)
d
ECUnembed(d,40)

[758836381415980725873880391356898132106948925841767677664020161182662238, 172885080124927030627775664387974993851680223072695154225919344264781309] [[7368168208605288208605287885288328448408128048565288048807888368488320, 121486482953176117528000809881749947571671902330970782925843120215624872], [8045845286928645288688608048605288368688328648208488328045288488448200, 903695374841292322370271174415204218208659055675797121100003842392500926], [8408648605845287368168045288488448208408648605287888568045288328208600, 452563156195183222674654981175834124068138520541249589841058897891287244], [8648048005288568208128168645287928048328448765287888408005288648168040, 354133454203841855971589741317387587553570850607256693528118869301689901], [8405288648168045288567888408008448365288408688367928048565287968168440, 566116327420959706426335734957260808053541488054698602617229920903468133], [8608048405287888408005288648168045288327888608645288448688648488688641, 190989246142380934866236751363212697612118794496744686603811386587621417], [5288208605288168448765288367888408845288488448208408648605287888568041, 425171620928964741474599056379821932316091568940530183178971060551595853], [5288408048048008048005840, 1036270550319895031743093327765070280126725147090778246179870977799274707]] 'This is a longer example. It uses multiple points. The points are listed right below and then the random number chosen and the last output is how many points are needed.'

import numpy
import itertools

############################################################################################################################
# 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 range(1, Prime):
        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)

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
            #print "test "+str(j)
            #print (kronecker(j ** 3 + a * j + b, p) )
            if kronecker(j ** 3 + a * j + b, p) == 1:
                x = (j ** 3 + a * j + b) % p
                var('z')
                #print("stuck here")
                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])
        #print type(EPoint)
        cgret = scalar*EPoint
        #print cgret[0]
        if(cgret[0]==0 and cgret[1]==1 and cgret[2]==0):
            return ECIdentity
        return([cgret[0],cgret[1]])
 

G=[3,2,next_prime(11696876878768768767867687687687687678768768766876879878111)]
G ####### Elliptic Curve Group
g=ECSearch(2378648723, 8927492873972973,G)
g ####### base element 
x=34239473274983742
x ####### private key 
b=ECTimes(g,x,G)

[3, 2, 11696876878768768767867687687687687678768768766876879878131] [2378648723, 6207257298628741512609567607483777943219211043692587796100] 34239473274983742

def listproduct (primelist):
    x = primelist
    k = len(primelist)
    print k
    result = 1
    for i in range(0, k):
        result = result * x[i][0] ^ x[i][1] #op(1, op(i, x)) ** op(2, op(i, x))
    return(result)

def listptorder (pt, Group, factoredGpOrder):
    ECIdentity = []
    x = factoredGpOrder
    k = len(factoredGpOrder)
    orderlist = set([])
    result = listproduct(factoredGpOrder)
    for i in range(0, k ):
        p =  x[i][0] #op(1, op(i, x))
        a =  x[i][1] #op(2, op(i, x))
        ord = 0
        for j in range(0, a ):
            result = result / p
            test = ECTimes(pt, result, Group)
            if test != ECIdentity:
                result = result * p
                ord = ord + 1
        if 0 < ord:
            orderlist = orderlist | set([[p,ord]])
    return(convert(orderlist, list))


def primeHPSonEC (y,g,Group,p):
    newg = []#ECIdentity
    for j in range(0, p ):
        if y == newg:
            break
        newg = ECAdd(newg, g, Group)
    return(j)


def powerHPSonEC (y,g,og,p,a,Group):
    gp = ECTimes(g, og / p, Group)
    newog = og
    newy = y
    c = 0
    partx = 0
    for i in range(0, a ):
        newy = ECAdd(y, ECInverse(ECTimes(g, partx, Group), Group), Group)
        newog = newog / p
        ypower = ECTimes(newy, newog, Group)
        c = primeHPSonEC(ypower, gp, Group, p)
        partx = partx + c * p ** i
    return(partx)

def HPSonEC (y,g,Group,factoredGpOrder):
    X = 0
    Ord = 1
    K = listptorder(g, Group, factoredGpOrder)
    k = len(K)
    ordg = listproduct(K)
    for j in range(1, k + 1):
        p = K[j][0]#op(1, op(j, K))
        powerp = K[j][1]#op(2, op(j, K))
        partx = powerHPSonEC(y, g, ordg, p, powerp, Group)
        if j == 1:
            X = partx
            Ord = p ** powerp
        else:
            X = crt([X,partx], [Ord,p ** powerp])
            Ord = Ord * p ** powerp
    return(X)

import math

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 = "";
    #Number = ZZ(Number[0])
    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):
            #print L[i]
            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)
    #print packets
    pointlist = [0]*packets
    for j in range(0, packets ):
        N = M[j]
#        N:=(op(0,op(1,M))[j]);
        pointlist[j] = ECSearch(tolerance * N, tolerance * (N + 1) - 1, gp)
        #print pointlist
    return(pointlist)

def ECUnembed (pointlist, tolerance):
    #print pointlist
    k = len(pointlist)
    paddedasciilist=[0]*k
    for j in range(0, k ):
        #print type(pointlist[j][0]/tolerance)
        #print pointlist
        #print paddedasciilist        
        #print "test this "+str((pointlist[j][0]/tolerance))
        #.floor() returns correct while math.floor() does not work
        #print (pointlist[j][0])
        pointlist[j][0]=ZZ(pointlist[j][0])
        toType = ZZ(QQ((pointlist[j][0])/tolerance).floor())
#        typed = type(toType)
#        print typed
        paddedasciilist[j] = ((pointlist[j][0])/tolerance).floor()
    returnStr = ""
    for paddedItem in paddedasciilist:
        #print paddedItem
        buffer = ASCIIDepad(paddedItem)
        returnStr+= buffer
        #print buffer
    return returnStr

Example. Create an elliptic curve public and private key.

G=[3,2,next_prime(1169687687876876876786768768768768767876876876687687987811546546545646541)]
G ####### Elliptic Curve Group
g=ECSearch(2378648723, 8927492873972973,G)
g ####### base element 
x=34239473274983742
x ####### private key 
b=ECTimes(g,x,G)
b

[3, 2, 1169687687876876876786768768768768767876876876687687987811546546545646659] [2378648723, 251129725725808360916423247622071249545935346397519406481708557006516860] 34239473274983742 [102185937035780644447440724514674909408114529521257498878576073830758885, 29294782479764415939896071953678258471598161093478693795502004627180723]

Example. Encrypt the plaintext "Cryptology" using the the elliptic curve and the key created in the previous example. The tolerance parameter is T=40.

m=ECEmbed("Cryptology",G, 40)
m ###### embedded plaintext into an elliptic curve group
r=34239473274983742
r ##### random number
h=ECTimes(g,r,G)
h
s=ECTimes(b,r,G)
s
c=ECAdd(m[0],s,G)
c
################################## The CIPHERTEXT is the pair of group elements h and c #####################################

[[6688568848488648448328448128842, 30713016421388513534069392095726691904699597855212477624228805094571897]] 34239473274983742 [102185937035780644447440724514674909408114529521257498878576073830758885, 29294782479764415939896071953678258471598161093478693795502004627180723] [531594751936260343069237726792546775307287241364648309851908704952472378, 62836598762052693815835015170177315163174591233643267255681661239022069] [60725488831383488099275639299974627203302101759526710107542683749459307, 786886098612758367049369768966181063935118105698230786854120868069958151]

%html
<strong>Example.</strong> Decrypt the ciphertext from the previous example. IN CLASS!

Example. Decrypt the ciphertext from the previous example. IN CLASS!

Example. Encryption of a plaintext represented by a list of points in the elliptic curve group G.

#########################################################################################################################
# Note: When running this example make sure you run them in order so that other cell's definitions are not used by sage # 
#########################################################################################################################

m=ECEmbed("This is a longer example. It uses multiple points. The points are listed right below and then the random number chosen and the last output is how many points are needed.",G, 40)
m ###### embedded plaintext into an elliptic curve group
r=3423947327498374254646554654645
r ##### random number
numPoints = len(m)
numPoints
h=[0]*numPoints
s=[0]*numPoints
c=[0]*numPoints
for counter in xrange(numPoints):
    h=ECTimes(g,r,G)
    s=ECTimes(b,r,G)
    c[counter]=ECAdd(m[counter],s,G)

[[7368168208605288208605287885288328448408128048565288048807888368488320, 121486482953176117528000809881749947571671902330970782925843120215624872], [8045845286928645288688608048605288368688328648208488328045288488448200, 903695374841292322370271174415204218208659055675797121100003842392500926], [8408648605845287368168045288488448208408648605287888568045288328208600, 452563156195183222674654981175834124068138520541249589841058897891287244], [8648048005288568208128168645287928048328448765287888408005288648168040, 354133454203841855971589741317387587553570850607256693528118869301689901], [8405288648168045288567888408008448365288408688367928048565287968168440, 566116327420959706426335734957260808053541488054698602617229920903468133], [8608048405287888408005288648168045288327888608645288448688648488688641, 190989246142380934866236751363212697612118794496744686603811386587621417], [5288208605288168448765288367888408845288488448208408648605287888568041, 425171620928964741474599056379821932316091568940530183178971060551595853], [5288408048048008048005840, 1036270550319895031743093327765070280126725147090778246179870977799274707]] 3423947327498374254646554654645 8

h
s
c

[502800681108808127999931477346298640902458497799276570157831511464842627, 249433093957737059630763632764052800806824499724831296249200563703070996] [758836381415980725873880391356898132106948925841767677664020161182662238, 172885080124927030627775664387974993851680223072695154225919344264781309] [[993011997632563665090520795819224461956877820256329108993458876624168267, 486967488472059785832649245344787601820108477716142036228174305706008047], [1025130127158111391286114497628784310721816018761263921410307202662962155, 1046214728711544478045606234428908877874990102826941182072699504231466650], [702163857070541572271486478402213299769149650327011285713214313411220209, 964390034282681070472559926854266573294570007713258722688970731401446070], [545974440942587589793355643326618406027250242128080874758407596428510512, 761850948586179337743907452723161818650832861623511156392451479702387930], [1007560043455625957074409098454581056661266112007216804759867237444073697, 568301847329160573315400903846138202220379078132258736522271094761757556], [197721450177956824925214814076136877509231101020546157774722389794437045, 364710051200340597882807263315974397500183542853128578183482144214813413], [1040787630887710087842592894781064728294150449155777473810980176110345869, 209262206482771129037093161089704974346792207851381833556910011562779092], [817585719106595758704863067855703256513213471986817100166846551663829691, 537939259557282367210288215732191700156429531225372888960276076554578723]]

z=ECTimes(h,x,G)
z
d = [0]*len(c)
for counter in xrange(len(c)):
    d[counter] = ECAdd(c[counter],ECInverse(z,G),G)
d
ECUnembed(d,40)

[758836381415980725873880391356898132106948925841767677664020161182662238, 172885080124927030627775664387974993851680223072695154225919344264781309] [[7368168208605288208605287885288328448408128048565288048807888368488320, 121486482953176117528000809881749947571671902330970782925843120215624872], [8045845286928645288688608048605288368688328648208488328045288488448200, 903695374841292322370271174415204218208659055675797121100003842392500926], [8408648605845287368168045288488448208408648605287888568045288328208600, 452563156195183222674654981175834124068138520541249589841058897891287244], [8648048005288568208128168645287928048328448765287888408005288648168040, 354133454203841855971589741317387587553570850607256693528118869301689901], [8405288648168045288567888408008448365288408688367928048565287968168440, 566116327420959706426335734957260808053541488054698602617229920903468133], [8608048405287888408005288648168045288327888608645288448688648488688641, 190989246142380934866236751363212697612118794496744686603811386587621417], [5288208605288168448765288367888408845288488448208408648605287888568041, 425171620928964741474599056379821932316091568940530183178971060551595853], [5288408048048008048005840, 1036270550319895031743093327765070280126725147090778246179870977799274707]] 'This is a longer example. It uses multiple points. The points are listed right below and then the random number chosen and the last output is how many points are needed.'