We often use elliptic curves for public key cryptography tasks such as key exchange and digital signature tasks. Because these curves serve faster implementations than other trusted algorithms such as Diffie Hellman or RSA. Rarely, we can adapt elliptic curves for symmetric key encryption tasks. This idea is mainly based on ElGamal encryption schema and elliptic curves. In this post, we will create a python implementation of this concept.
Vlog
High level explanation of Elliptic Curve ElGamal Encryption
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Elliptic Curve ElGamal Encryption in Python From Scratch
🐍 Python Library
In this post, we will mostly focus on the math behind the cryptosystem and implement it from scratch. If you are interested in how to use the algorithm easy and fast instead of its mathematical foundation, then you may consider to use LightPHE.
LightPHE is a lightweight partially homomorphic encryption library for python. It wraps many partially homomorphic algorithms such as RSA, ElGamal, Exponential ElGamal, Elliptic Curve ElGamal, Paillier, Damgard-Jurik, Okamoto–Uchiyama, Benaloh, Naccache–Stern, Goldwasser–Micali. With LightPHE, you can build homomorphic crypto systems with a couple of lines of code, encrypt & decrypt your data and perform homomorphic operations such as homomorphic addition, homomorphic multiplication, homomorphic xor, regenerate cipher texts, multiplying your cipher text with a known plain constant according to the built algorithm.
# pip install lightphe from lightphe import LightPHE # build a cryptosystem cs = LightPHE(algorithm_name = 'EllipticCurve-ElGamal') # define plaintexts m1 = 17 m2 = 23 # calculate ciphertexts c1 = cs.encrypt(m1) c2 = cs.encrypt(m2) # performing homomorphic addition on ciphertexts assert cs.decrypt(c1 + c2) == m1 + m2 # scalar multiplication (increase its value 5%) k = 1.05 assert cs.decrypt(k * c1) == k * m1
You may consider to watch the LightPHE demo video.
Now, let’s turn back to understand and implement the crypto system from scratch!
Curve configuration
Elliptic curves satisfy the equation y2 = x3 + ax + b. Here, a and b specify the characteristic feature of the curve. Also, we define elliptic curves over prime fields to produce points including integer coordinates. This definition transforms the equation as y2 (mod p) = x3 + ax + b (mod p).
We will use the following configuration in this post. Notice that bitcoin protocol adopts same curve configuration.
#curve configuration: secp256k1
# y^2 = x^3 + a*x + b = y^2 = x^3 + 7
a = 0; b = 7
# base point
G = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
32670510020758816978083085130507043184471273380659243275938904335757337482424)
# modulo
p = pow(2, 256) - pow(2, 32) - pow(2, 9) - pow(2, 8) - pow(2, 7) - pow(2, 6) - pow(2, 4) - pow(2, 0)
# order
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Addition law
We are going to need the addition law of Weierstrass curves. Besides, we will do scalar multiplication with double and add method to calculate nxP faster where n is an integer and P is a point on our curve.
def add_points(P, Q, p):
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == y2:
beta = (3*x1*x2 + a) * pow(2*y1, -1, p)
else:
beta = (y2 - y1) * pow(x2 - x1, -1, p)
x3 = (beta*beta - x1 - x2) % p
y3 = (beta * (x1 - x3) - y1) % p
is_on_curve((x3, y3), p)
return x3, y3
def is_on_curve(P, p):
x, y = P
assert (y*y) % p == ( pow(x, 3, p) + a*x + b ) % p
def apply_double_and_add_method(G, k, p):
target_point = G
k_binary = bin(k)[2:] #0b1111111001
for i in range(1, len(k_binary)):
current_bit = k_binary[i: i+1]
# doubling - always
target_point = add_points(target_point, target_point, p)
if current_bit == "1":
target_point = add_points(target_point, G, p)
is_on_curve(target_point, p)
return target_point
Alternatively, you can adopt Koblitz, Edwards or Twisted Edwards of course. But you need to change the curve configuration in that case.
Preprocessing the message
We can apply additions and multiplications over elliptic curves. Here, we want to encrypt a message. We need to express the message numerically if we want to talk the same language with elliptic curve cryptography.
def textToInt(text):
encoded_text = text.encode('utf-8')
hex_text = encoded_text.hex()
int_text = int(hex_text, 16)
return int_text
message = 'hi'
m = textToInt(message)
print("message: ", message, ". it is numeric matching is ", m)
Now, we can calculate the numeric message times base point on an elliptic curve to find the corresponding point. In this way, we can map the plaintext to a coordinate. This would be the plain coordinates that we will actually encrypt. We must keep secret both message, plaintext and plain coordinates. Besides, please notice that Alice will decrypt that corresponding point instead of plain message. Finding plain message from a point requires ECDLP and this is computationally hard problem.
Public key generation
We can produce our public key. Public key would be independent from plaintext. We will pick a secret key and calculate secret key times base point. That would be our public key.
# alice's private key ka = random.getrandbits(256) # private of Alice # alice's public key Qa = apply_double_and_add_method(G = G, k = ka, p = p)
Encryption
We will create a ciphertext pair. This requires to include a really random key.
# bob
def encrypt(m, r):
s = apply_double_and_add_method(G = G, k = m, p = p)
c1 = apply_double_and_add_method(G = G, k = r, p = p)
c2 = apply_double_and_add_method(G = Qa, k = r, p = p)
c2 = add_points(c2, s, p)
return c1, c2
# --------------------------
import random
r = random.getrandbits(128)
c1, c2 = encrypt(m, r)
Encryption phase is over. We will send ciphertext point (c1, c2) pairs. Also, public key and public curve configuration are publicly known information.
Decryption
ElGamal decryption scheme is based on the following equation.
decryption = c2 – secretKey * c1
We will adapt this equation into elliptic curves. We have already known how to add points over elliptic curves but the term in the above includes subtraction. Reflecting the sign to multiplier point handles subtraction.
decryption = c2 + secretKey * (-c1)
Notice that elliptic curves in weierstrass form are symmetric about x-axis. This means that negative of a point (x, y) is equal to (x, -y)
If you adopt Koblitz curves, then negative point of (x, y) will be (x, -(x+y)). If you adopt Edwards curves, then negative point of (x, y) will be (-x, y). But we adopted Weierstrass curves in this experiment, so negative point of (x, y) will be (x, -y).
# alice
# s_prime = c2 - ka x c1
# s_prime = c2 + ( ka x -c1)
# (x, y) + (x, -y) = O
def decrypt(c1, c2):
c1_prime = (c1[0], (-1*c1[1]) % p)
s_prime = apply_double_and_add_method(G = c1_prime, k = ka, p = p)
s_prime = add_points(P = c2, Q = s_prime, p = p)
return s_prime
s_prime = decrypt(c1, c2)
Even though Alice does not know the message m itself, I will show its corresponding point here to understand decrypted point is really equal to it.
s_real = apply_double_and_add_method(G = G, k = m, p = p) assert s_prime == s_real
Finally, please notice that Alice decrypts the corresponding point of m which is S = m x G instead of plain message. So, elliptic curve elgamal encryption is a protocol to encrypt & decrypt points on an elliptic curve. On the other hand, finding m from known S and G pair requires to solve ECDLP which is computationally hard.
Partially Homomorphic Elliptic Curve ElGamal
Similar to regular ElGamal, Elliptic Curve ElGamal is partially homomorphic with respect to the addition. In other words, addition of two encrypted texts is equal to the encryption of addition of two plaintexts.
We encrypted message and random key pairs as show below:
(m1, r1) -> (r1G, r1Q + m1G)
(m2, r2) -> (r2G, r2Q + m2G)
Here, ciphertexts consist of point pairs on our curve. Besides, r values are random integers, G is the base point and Q is the public key.
What if we add those two encrypted values. Encrypted texts were 2 points on our curve and each point has x and y coordinate. Addition of two points requires to add x coordinates to x coordinates, and y coordinates to y coordinates. Addition refers to point addition on our elliptic curve.
(r1G, r1Q + m1G) + (r2G, r2Q + m2G)
(r1G + r2G, r1Q + m1G + r2Q + m2G)
((r1+r2)G, (r1+r2)Q + (m1+m2)G)
On the other hand if we encrypted the addition of 1st and 2nd message with the addition of random keys, then we will have same result
(m1+m2, r1, r2) -> ((r1+r2)G, (r1+r2)Q + (m1+m2)G)
You can find the test of this feature in the notebook of this study.
m1 = 333
m2 = 777
r1 = random.getrandbits(128)
r2 = random.getrandbits(128)
c1_x, c2_x = encrypt(m1, r1)
c1_y, c2_y = encrypt(m2, r2)
m1_encrypted_plus_m2_encrypted = (
add_points(
P = c1_x,
Q = c1_y,
p = p
),
add_points(
P = c2_x,
Q = c2_y,
p = p
)
)
m1_plus_m2_encrypted = encrypt(m1+m2, r1+r2)
assert m1_encrypted_plus_m2_encrypted == m1_plus_m2_encrypted
Please notice that partially homomorphic features are serving on points on the curve instead of plain values. On the other hand, regular ElGamal serving this for plain values.
Still, if you use the corresponding point of your salary, it will be fast to solve ECDLP problem because I suppose no one ıs getting 1M USD as a base salary. You just need to build a for loop between [0, 1M] to extract k from known G and kG.
Conclusion
So, we can encrypt a point and restore it successfully by combining Elliptic Curve and ElGamal concepts. Also, the cryptosystem comes with partially homomorphic features.
However, this is a conceptual, theoretical encryption schema and hard to apply in real world because you cannot encrypt & decrypt plain messages. Finding plain message from the decrypted point requires elliptic curve discrete logarithm problem which is computationally hard. Similarly, even though it is additively homomorphic, you can just use this feature on point addition.
On the other hand, one can encrypt a point with someone’s public key and use this point as a key in symmetric key encryption algorithm such as DES or AES. Then, that person can decrypt this message and get the plain point on the curve and use this to decrypt message. We are running this use case in ECIES and ECMQV schemes. So, Elliptic Curve ElGamal can be an alternative to these integrated encryption schemes.
I pushed the source code of this post into GitHub. You can support this work with starring⭐ its repo 🙏
Like this blog? Support me on Patreon
