ECIES is a hybrid encryption scheme that combines the best features of both symmetric-key and public-key encryption, making it an ideal candidate for secure communication in modern cryptography. In this post, we will implement Elliptic Curve Integrated Encryption Scheme or shortly ECIES in python from scratch. We will also focus on how it is used to provide secure encryption and decryption of messages.
Vlog
High level explanation of ECIES
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Python implementation from scratch
Elliptic Curve Form
Firstly, we should decide the elliptic curve form. We can adopt elliptic curves in Weierstrass, Koblitz, Edwards or Twisted Edwards forms. They all come with their own addition formulas. Let’s use Twisted Edwards curves in this experiment. You can adopt any other elliptic curve form in your experiment.
ax2 + y2 = 1 + dx2y2
According to the Edwards addition formula if (x1, y1) and (x2, y2) are points on our elliptic curve, then (x3, y3) will be on the same curve where
x3 = (x1y2 + y1x2)/(1 + dx1x2y1y2)
y3 = (y1y2 – ax1x2)/(1 – dx1x2y1y2)
The Curve
Once an elliptic curve form is decided, we should decide the specific curve that we are going to work on. Curve25519 is actively being used in EdDSA. Let’s use this curve for this experiment.
# equation of curve25519: a*x*x + y*y = 1 + d*x*x*y*y # modulo for curve25510 p = pow(2, 255) - 19 # curve arguments for curve25519 a = -1 # d = -121665/121666 d = -121665 * pow(121666, -1, p) # base point for curve25519 G = (15112221349535400772501151409588531511454012693041857206046113283949847762202 , 46316835694926478169428394003475163141307993866256225615783033603165251855960)
Implementing Addition Formulas
We decided the elliptic curve form and elliptic curve itself. Now, we will implement addition formulas in python.
from typing import Tuple
def is_on_curve(P: Tuple[int, int], p: int):
x, y = P
assert ( (a*x*x)+(y*y) ) % p == (1 + d*x*x*y*y) % p
def add_points(P: Tuple[int, int], Q: Tuple[int, int]):
x1, y1 = P
x2, y2 = Q
x3 = (((x1*y2 + y1*x2) % p) * pow(1+d*x1*x2*y1*y2, -1, p)) % p
y3 = (((y1*y2 - a*x1*x2) % p) * pow(1- d*x1*x2*y1*y2, -1, p)) % p
is_on_curve((x3, y3), p)
return x3, y3
We are also going to use double and add method for scalar multiplication. Notice that Q is a point on our elliptic curve derived from Q = k x G where k is a large integer number and G is another point on our elliptic curve. With double and add method, we can find point Q with known k and G very fast. On the other hand, finding k from given points Q and G is computationally hard. This is Elliptic Curve Discrete Logarithm Problem (ECDLP) and the hardness of elliptic curve cryptography depends on this.
def apply_double_and_add_method(G: Tuple[int, int], k: int):
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)
if current_bit == "1":
target_point = add_points(target_point, G)
is_on_curve(target_point, p)
return target_point
Alice generates her public key
Alice firstly selects a large integer number as a private key. Then, she will find corresponding point on the curve as her public key. Recommended key size length of ECC is 256-bit. This will offer same level accuracy with 3072-bit RSA.
import random # Alice's private key ka = random.getrandbits(256) # Alice's public key Qa = apply_double_and_add_method(G = G, k = ka)
Bob generates a random integer
On Bob’s side, he will firstly generate a random integer. Then, he will find 2 corresponding points on the curve with respect to the base point G and Alice’s public key Qa.
# Bob's random key rb = random.getrandbits(256) # Point U will be sent to Alice U = apply_double_and_add_method(G = G, k = rb) # Point T will keep secret and use for encryption purposes T = apply_double_and_add_method(G = Qa, k = rb)
Bob will send point U to Alice, and he will use point T for secure messaging. Notice that Point T is not going to be shared to Alice directly.
Key Derivation Function
Bob then uses sha-256 to hash 192-bit x coordinate of point T. Then, he will split the hash into 128-bit and 128-bit and obtain keys k1 and k2. Notice that key derivation function will be public and this is going to be used by Alice in later steps. Just Alice will not know Point T directly.
def derive_keys(T):
tx, ty = T
# get x coordinate of point T as binary
tx_binary = bin(tx)[2:]
# get its first 192-bit value
tx_binary_cropped = tx_binary[0:192]
# restore 192-bit x coordinate
tx_restored = str(int(tx_binary_cropped, 2))
# use sha-256 to hash
hashed_tx = bin(int(hashlib.sha256(str.encode(tx_restored)).hexdigest(), 16))[2:]
assert len(hashed_tx) == 256
# split the hash into 128-bit and 128-bit as k1 and k2
k1 = int(hashed_tx[0:128], 2).to_bytes(16, byteorder='big')
k2 = int(hashed_tx[128:], 2).to_bytes(16, byteorder='big')
return k1, k2
k1, k2 = derive_keys(T)
Encryption
Firstly, Bob uses k1 to encrypt a message with AES-128.
msg = "attack tomorrow!" # Bob uses k1 to encrypt a message m with aes-128 and obtain c obj_bob = AES.new(k1) c = base64.b64encode(obj_bob.encrypt(msg))
Secondly, he uses HMAC-SHA256 to calculate a message authentication code (MAC) r with k2 and ciphertext. The reason of usage of MAC step in ECIES is to add an extra security layer.
def find_mac(message, key):
return hmac.new(
key,
message,
hashlib.sha256
).hexdigest()
r = find_mac(c, k2)
Finally, Bob will send the tuple (U, c, r) to Alice.
Alice restores secret key
When Alice retrieved point U, she will calculate her private key times point U. Let’s call this calculation
# Alice receives U and finds ka x U T_prime = apply_double_and_add_method(G = U, k = ka)
The result of T’ is is exactly the same point Bob calculated but not shared to Alice.
Alice performs same key derivation function
Alice obtain point T. Now, she is able to obtain keys k1 and k2 from this point.
k1_prime, k2_prime = derive_keys(T_prime)
Decryption and verification
Alice uses same message authentication code from found keys k1 and k2 and compares it to given r. If they are different, then she will decide this message is invalid.
assert r == find_mac(c, k2_prime)
Thereafter, she will use k1 to decrypt ciphertext c.
obj_alice = AES.new(k1_prime) plaintext = obj_alice.decrypt(base64.b64decode(c))
This restores the original message “attack tommorrow!”
The math behind ECIES
Bob calculated two points in his side, but shared just one of them to Alice. Remember calculations Bob did:
U = r x G
T = r x Qa
Bob is sending just U to Alice. Then, she performs the operation:
T’ = ka x U
Restore U in the T’ calculation
T’ = ka x r x G
This calculation includes Alice’s private key ka times base point G. This is also equal to her public key.
T’ = r x Qa
Really, Bob performed same calculation for T.
So, if Alice calculates her private key times point U, then she obtains unshared point T.
ECDH
Alternatively, key exchange can be handled with Elliptic Curve Diffie Hellman algorithm between Alice and Bob.
Security level of the scheme
The man in the middle cannot find T from given point U because extracting Alice’s private key or Bob’s random key requires to solve Elliptic Curve Discrete Logarithm Problem which is computationally hard.
Conclusion
In conclusion, ECIES is an important encryption scheme that uses elliptic curve cryptography to provide secure communication. By combining the best features of both symmetric-key and public-key encryption, ECIES is able to provide a high level of security while still maintaining efficiency. With the increasing importance of secure communication in today’s world, ECIES is sure to play a vital role in the future of cryptography.
I pushed the source code of this experiment to GitHub. You can support this work if you star⭐ the repo.
References
Liang Xia, Implementing Elliptic Curve Integrated Encryption Scheme on Android Platforms, 2013.
Like this blog? Support me on Patreon
