ECEmbed.sagews

Elliptic Curve Embedding

import math
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 []                                                                         #
############################################################################################################################

1. Koblitz Embedding of a message into an Elliptic Curve Group: ECEmbed(Message, Group, Tollerance Parameter)
2. Koblitz Unembedding of an Eliptic Curve group element to a message: ECUnembed(Group Element, Tollerance Parameter)

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

Example. Embed the plaintext "Data Privacy Day is an international event that occurs every year on 28 January" into the group $$y^2=x^3+2x+12\; mod\;111372849328749456464564594837594837598435984375503$$ using a tolerance parameter T=40. The embeded plaintext is represented by 5 points in the elliptic curve group:

• [6727888647885287208568208727887968845286727888843, 32854152900797780223685776356973672727544281140438]
• [5288208605287888405288208408648048568407888648200, 27814776229677670024234415355169389176662105417080]
• [8448407888325288048728048408645288648167888645282, 108722806482736255145408973542651102334000896330604]
• [8447967968688568605288048728048568845288848047881, 46525767831756816282648267526217685495666590869802]
• [8565288448405286006245286967888408687888568843, 95647711591715781059539655025908232090100039972726]

TextPoint=ECEmbed("Data Privacy Day is an international event that occurs every year on 28 January",[2,12,next_prime(111372849328749456464564594837594837598435984375311)],40)
print("The embedded message is a string of 5 elliptic curve points\n", TextPoint)

The embedded message is a string of 5 elliptic curve points [[6727888647885287208568208727887968845286727888843, 32854152900797780223685776356973672727544281140438], [5288208605287888405288208408648048568407888648200, 27814776229677670024234415355169389176662105417080], [8448407888325288048728048408645288648167888645282, 108722806482736255145408973542651102334000896330604], [8447967968688568605288048728048568845288848047881, 46525767831756816282648267526217685495666590869802], [8565288448405286006245286967888408687888568843, 95647711591715781059539655025908232090100039972726]]

##################################################################################################################################################
#The ECUnembed function converts a point on the elliptic curve to a readable message. The tollerance parameter used in ECUnembed must the same as# 
# the tollerance parameter used in ECEmbed. The tolerance parameter T is an interger between 40 < T < 50.                                        #
##################################################################################################################################################

ECUnembed (TextPoint,40)

'Data Privacy Day is an international event that occurs every year on 28 January'

TextPoint[0]
ECUnembed ([TextPoint[0]],40)

[6727888647885287208568208727887968845286727888843, 32854152900797780223685776356973672727544281140438] 'Data Privacy Day'

TextPoint[1]
ECUnembed ([TextPoint[1]],40)

[5288208605287888405288208408648048568407888648200, 27814776229677670024234415355169389176662105417080] ' is an internati'

TextPoint[2]
ECUnembed ([TextPoint[2]],40)

[8448407888325288048728048408645288648167888645282, 108722806482736255145408973542651102334000896330604] 'onal event that '

TextPoint[3]
ECUnembed ([TextPoint[3]],40)

[8447967968688568605288048728048568845288848047881, 46525767831756816282648267526217685495666590869802] 'occurs every yea'

TextPoint[4]
ECUnembed ([TextPoint[4]],40)

[8565288448405286006245286967888408687888568843, 95647711591715781059539655025908232090100039972726] 'r on 28 January'