LUC El Gamal.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)

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))-1
    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):
    #print "the padded number is"
    #print 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);

import itertools
def IsIn(pt, lucgp):
    if(((pt[0]^2-lucgp[0]*(pt[1]^2)) % lucgp[1]) == (4 % lucgp[1])):
        return True
    else:
        return False
    
def LUCIdentity():
    return [2,0]

def LUCInverse(point, lucasgroup):
    return([point[0],lucasgroup[1]-point[1]])

def LUCTimes(pt1, pt2, lucgp):
    if(not IsIn(pt1,lucgp)):
        print "Point 1 is not in the group"
        raise Exception("Point is not in group")
    #print "in luctimes"
    #print pt2
    if(not IsIn(pt2,lucgp)):
        print "Point 2 is not in the group"
        raise Exception("Point is not in group")
    else:
        luctimesx=((lucgp[1]+1)/2)*(pt1[0]*pt2[0]+lucgp[0]*pt1[1]*pt2[1]) % lucgp[1];
        luctimesy=((lucgp[1]+1)/2)*(pt1[0]*pt2[1]+pt1[1]*pt2[0]) % lucgp[1];
        return([luctimesx,luctimesy])

def LUCSquare(pt,lucgp):
    lucsqx=(pt[0]^2-2) % lucgp[1];
    lucsqy=(pt[0]*pt[1]) % lucgp[1];
    lucsqresult=[lucsqx,lucsqy]
    return lucsqresult

def LUCexp(Point,scalar,Group):
    if Point == LUCIdentity() or scalar == 0:
        return LUCIdentity()
    else:
        m = scalar
        pt = Point
        x = LUCIdentity()
        for j in itertools.count(1):
            if m%2==0:
                m = m/2
            else:
                m=(m-1)/2
                x = LUCTimes(x,pt,Group)
            if m==0:
                return x
            else:
                pt = LUCSquare(pt, Group)

def LUCSearch(lower,higher,lucgp):
    ##for j in xrange(lower,higher+1):
    for j in itertools.count(lower):
        #if j >= higher:
        #    print "No point found in range"
        #    break
        luctester = (( j ^ 2 - 4 ) / lucgp[0]) % lucgp[1]
        #print luctester
        if(kronecker(luctester,lucgp[1])==1):
            foundx=j
            foundy=TonSh(luctester,lucgp[1])
            return [foundx,foundy]
        
def GroupOrder(group):
    d = group[0]
    N = group[1]
    return(N-kronecker(d,N))

def listproduct(primelist):
    x = primelist
    k = len(primelist)
    result = 1
    for i in xrange(k):
        result = result * x[i][0]^x[i][1]
    return result


def ptorder(pt, Group, factoredGpOrder):
    x = factoredGpOrder
    k = len(factoredGpOrder)
    result = listproduct(factoredGpOrder)
    for i in xrange(k):
        p = x[i][0]
        a = x[i][1]
        for j in xrange(a):
            result = result/p
            test = LUCexp(pt,result,Group)
            if (test!=LUCIdentity()):
                result = result*p
    return result

def listptorder(pt, Group, factoredGpOrder):
    x = factoredGpOrder
    k = len(factoredGpOrder)
    orderList = [];
    result = listproduct(factoredGpOrder)
    for i in xrange(k):
        p = x[i][0]
        a = x[i][1]
        ord =0
        for j in xrange(a):
            result = result/p
            test = LUCexp(pt,result,Group)
            if (test!=LUCIdentity()):
                result = result*p
                ord = ord+1
        if ord>0:
            orderlist.append([p,ord])
    return orderlist

def LUCNumberembed(xvalue,Gp,tolerance):
    if ((xvalue+1)*tolerance-1 < Gp[1]):
        pt=LUCSearch(xvalue*tolerance, (xvalue+1)*tolerance-1,Gp)
#        print "LUCNumberemed pt"
#        print pt
        return pt
    else:
        print "The embedding interval is too large for the group"

def LUCEmbed(Message,Gp,tolerance):
    AMessage = ASCIIPad(Message,QQ(Gp[1]/(tolerance+1)).floor())
    print AMessage
    numPackets = len(AMessage)
    pt = [0]*numPackets
    for j in xrange(numPackets):
        N =AMessage[j]
        pt[j]=LUCNumberembed(N,Gp,tolerance)
    return pt

def LUCUnembed(ptlist,tolerance):
    k = len(ptlist)
    X=[0]*k
    for j in xrange(k):
        X[j]=QQ(ptlist[j][0]/tolerance).floor()
    #print X
    outStr=""
    for numInX in X:
        #print numInX
        outStr=outStr+ASCIIDepad(numInX)
    return outStr

p=next_prime(25690124917473078519589117498847803496088971697834615853141266)
d=72346328764328726438722
Gp=[d,p]
g=LUCSearch(11,100,Gp) #base point
g
x=89547698435765984367549867459867459867345980678659 #Private key
b=LUCexp(g,x,Gp)
T=43 #Tolerance

[11, 1628342822613782923813271849118328187965774221410763278289230]

m=LUCEmbed("This is an example of how Lucas Groups work with El Gamal",Gp,T) #Embedding message into group
len(m) #number of packets

[184204205215132205215132197210132201220197209212208201132, 211202132204211219132176217199197215132171214211217212215, 132219211214207132219205216204132169208132171197209197208] 3

r=[0]*3 # randomly chosen numbers
r[0]=34957938474395793847
#r[0]=1234567912345679123456789123456789123456789123456789
r[1]=72345678346534278654385634978
#r[1]=23454329875239475349287594328789798797979456611592347592374957234975932759324759437
r[2]=7238346534278654385634978

s=[]
t=[]
e=[]
#Encrypted m
for j in xrange(len(m)):
    s.append(LUCexp(b,r[j],Gp))
    t.append(LUCexp(g,r[j],Gp))
    e.append(LUCTimes(m[j],s[j],Gp))
e
t

[[12978542507941831925355599870844676472485307062340579215046946, 9425837678571132093421978829744267996390889911761413886196016], [1539969592052388022440409952032274795373398190131342694347118, 20437286178065279694747620930632408755708063013238300669031323], [11212751871891993839312260025710823501731952985300283831043994, 14461032339344387130153074480413772330498220826017442854459599]] [[23942592244348157959882812324155287198745138629985975113338179, 13866923404317828534106169107228926378816121183617267774222497], [11230955370011598865311508570884433225662507640653708442491276, 11183925855208671272059615177146128241882221252578499079569966], [9360341030224142172432983253828579100333899185552216328333254, 10199688699815995078723847537373681890611269077289729490315925]]

S=[]
Decr=[]
for j in xrange(len(m)):
    S.append(LUCInverse(LUCexp(t[j],x,Gp),Gp))
    Decr.append(LUCTimes(e[j],S[j],Gp))
Decr

[[7920780824250684824250684480035684652468479996124952648679, 20860395421573180612401552938954322660748664513010107563913107], [9081691684781082422683577339565480250683362211082340125253, 19597476104097406889100286690935312772381832950772484172985413], [5685426082210906685425824296777683275949683361479995479945, 6443416298780942756753322562413327551001661620393346455522847]]

LUCUnembed(Decr,T)

'This is an example of how Lucas Groups work with El Gamal'