[PYTHON] ElGamal encryption on elliptic curves

ElGamal encryption on elliptic curves

Key generation

1. Generate an elliptic curve $ E/F_p $ and a base point $ G $ with an order $ l . ( p, l $ are prime numbers)
2. Generate the private key $ x $ with random numbers and calculate $ Y = xG $ on $ E $.

Private key $ x $, public key $ E, G, Y $

encryption

Let $ m $ be the message you want to send.

1. $ r $ w Generate with random numbers and calculate $ U = rG = (u_x, u_y) $.
2. Using the public key $ Y $, $ V = xU = (v_x, v_y) $ and $ c = v_x \ oplus m $ $ \ Oplus $ is the exclusive OR
3. Send $ (U, c) $ as a ciphertext.

Decryption

1. Combine as follows. V=xU=(v_x,v_y),m=v_x\oplus c

code

#random number
r = 3
#Private key
key = 3
#Base point
g = [2,2]
#Order
l = 5
# y^2 = x^3 + ax +b
a = 0
b = 1

def Mod(x,y):
  if x < 0:
    x = x+y
  return x%y

def invMod(x,y):
  count = 1
  while True:
    tmp = x*count
    if tmp%y == 1:
      return count
    count += 1

def Ellipse(p,r):
    for _ in range(r):
        s = Mod(Mod((3*p[0]*p[0]+a),l)*invMod((2*p[1]),l),l)
        x = Mod(s*s-p[0]-p[0],l)
        y = Mod(s*(p[0]-x)-p[1],l)
    return [x,y]

def encrypt(G,Y, m):
    U =Ellipse(G,r)
    V =Ellipse(Y,r)
    #Take an exclusive OR
    c = V[1] ^ m
    return U,c

def decrypt(U, c, key):
    V = Ellipse(U,key)
    m = V[1] ^ c
    return m

def main():

    #Creating a public key
    Y = g
    Y = Ellipse(Y, key) 
    print("Public key:",[a,b], g,Y)

    #Plaintext
    message = 4
    print("Plaintext:", message)

    #encryption
    U,c = encrypt(g, Y, message)
    print("secret message:",U,c)

    #Decryption
    decrypt_message = decrypt(U, c, key)
    print("Decryption message", decrypt_message)
    
if __name__ == "__main__":
    main()