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.
Homomorphic Encryption And Cloud
Homomorphic encryption enables computations on encrypted data without needing the private key. With the widespread adoption of cloud systems, homomorphic encryption has become increasingly popular. This technology allows us to store data in the cloud and leverage its processing power while keeping the private key secure. As a result, system design becomes both more cost-effective and secure. Watch this video to see how homomorphic encryption operates on both on-premises and cloud platforms.
šāāļø You may consider to enroll my top-rated cryptography course on Udemy
Vlog
High level explanation of Elliptic Curve ElGamal Encryption
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!
LightECC
We will use LightECC to perform arithmetic operations of elliptic curves in python such as addition or multiplication.
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.
from lightecc import LightECC # bitcoin's curve curve = LightECC( form_name="weierstrass", # or edwards, koblitz curve_name="secp256k1" ) # y^2 = x^3 + a*x + b = y^2 = x^3 + 7 # base point G = curve.G # order n = curve.n
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.
_2G = G + G _3G = _2G + G _5G = _3G + _2G _50G = 10 * _5G
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)
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 private key ka = random.getrandbits(256) # private of Alice # alice public key Qa = ka * G
Encryption
We will create a ciphertext pair. This requires to include a really random key.
# bob
def encrypt(m, r):
s = m * G
c1 = r * G
c2 = r * Qa
c2 = c2 + s
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 = -1 * c1
s_prime = ka * c1_prime
s_prime = c2 + s_prime
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 = m * G 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 = ( c1_x + c1_y, c2_x + c2_y ) 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 š
Support this blog if you do like!
