Secure communication lies at the heart of our interconnected world, and cryptography plays a pivotal role in safeguarding our digital interactions. Among the many cryptographic protocols available, Elliptic Curve Menezes-Qu-Vanstone or shortly ECMQV stands as a powerful and efficient method for key agreement. By leveraging the mathematical elegance of elliptic curves, MQV offers a robust framework for establishing shared secrets between two parties over an insecure channel and authentication. In this blog post, we embark on a journey to implement ECMQV in Python from scratch. Through a step-by-step exploration of the underlying concepts, we’ll delve into the intricacies of elliptic curves, key agreement, and the MQV protocol.
Vlog
Join this video to implement ECMQV in python from scratch.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Elliptic Curve Form
Firstly, we are going to decide the elliptic curve form because we will have different addition laws according to the curve. Weierstrass, Koblitz, Edwards and Twisted Edwards are the most common elliptic curve forms. We will adopt Weierstrass curves in this experiment. This curve satisfies y2 = x3 + ax + b equation and it comes with the following addition law.
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
return x3, y3
Independent from the curve type, we can do scalar multiplication fast with double and add method.
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)
return target_point
Curve Configuration
In this experiment, we will adopt secp256k1 curve which is adopted by the bitcoin protocol. This specific curve has the equation y2 = x3 + 7. Fixed base point G, modulo p, order n and cofactor h values are mentioned in the following snippet. Notice that these values are totally public.
# Secp256k1 curve formula
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
# cofactor
h = 1
Bar function
Suppose that R is a point on the elliptic curve with (x, y) coordinates. We will transform this elliptic curve point to an integer according to the formula:
R’ = (x mod 2L) + 2L
In other words, R’ is the first L bits of the point R.
Here, L calculation requires ceil and floor operations respectively.
def bar(P: Tuple):
l = math.ceil( (math.floor(math.log(n, 2)) + 1) / 2 )
x, y = P
P_bar = ( x % pow(2, l) ) + pow(2, l)
return P_bar
Public key generation
The both Alice and Bob generate an integer for their private keys. Besides, the both parties need to generate a random integer. Recommended key size for ECC is 256 bit. Finally, they will find the corresponding points on the curve with double and add method.
# private key of Alice ka = random.getrandbits(256) # public key of Alice Qa = apply_double_and_add_method(G = G, k = ka, p = p) # random key of Alice (secret) ra = random.getrandbits(256) # random point of Alice (public) Ra = apply_double_and_add_method(G = G, k = ra, p = p) # private key of Bob kb = random.getrandbits(256) # public key of Bob Qb = apply_double_and_add_method(G = G, k = kb, p = p) # random key of Bob (secret) rb = random.getrandbits(256) # random point of Bob (public) Rb = apply_double_and_add_method(G = G, k = rb, p = p)
Signatures
Once they generated their public key values, Alice and Bob will calculate their signature values. This requires to find their random key plus corresponding random point’s first L bits of x coordinate times their private key in modulo order of the elliptic curve group. Then, Alice and Bob will share these signature values on a public channel publicly.
# Alice sends sa to Bob sa = ( ra + bar(Ra) * ka ) % n # Bob sends sb to Alice sb = ( rb + bar(Rb) * kb ) % n
Key Exchange
Alice will do the following calculation:
Ja = h x sa x (Rb + Rb‘ x Qb)
This requires the signature of Alice, random point of Bob (rb was kept secret by Bob but its corresponding point will be public), first L bit of its x coordinate, and finally public key of Bob (this is public, too).
Meanwhile, Bob will do the following calculation:
Jb = h x sb x (Ra + Ra‘ x Qa)
Finally, Alice and Bob must calculate the same point!
# Alice calculate Ja Ja = apply_double_and_add_method(G = Qb, k = bar(Rb), p = p) Ja = add_points(P = Rb, Q = Ja, p = p) Ja = apply_double_and_add_method(G = Ja, k = h*sa, p = p) # Bob calculates Jb Jb = apply_double_and_add_method(G = Qa, k = bar(Ra), p = p) Jb = add_points(P = Ra, Q = Jb, p = p) Jb = apply_double_and_add_method(G = Jb, k = h*sb, p = p) assert Ja == Jb
Proof
Let’s prove why this must be same always. Let’s represent the random point and public key calculations. Random point (Rb) was calculated by random integer of Bob (rb) times base point G, and public key of Bob (Qb) was calculated by the private key of Bob (kb) times base point G.
Ja = h x sa x (Rb + Rb‘ x Qb)
Ja = h x sa x (rb x G + Rb‘ x kb x G)
In the paranthesis, two statements have base point G multiplier. We can represent this as:
Ja = h x sa x (rb + Rb‘ x kb) x G
Now, the statement in the paranthesis is exactly the same with signature of Bob (sb)
Ja = h x sa x sb x G
Let’s do same arrangements for the Jb.
Jb = h x sb x (Ra + Ra‘ x Qa)
Jb = h x sb x (ra x G + Ra‘ x ka x G)
Jb = h x sb x (ra + Ra‘ x ka) x G
Jb = h x sb x sa x G
As you can see Ja must be equal to Jb!
Key Derivation Function
Once Alice and Bob shared same elliptic curve point, they can use a key derivation function (KDF) to generate two different keys. They can hash the first 192-bit of the x coordinate of the shared point with SHA-256 algorithm. This will generate a 256 bit key. Then, this can be splitted into two 128-bit keys. We used same KDF in ECIES experiment.
def derive_keys(T):
tx, ty = T
tx_binary = bin(tx)[2:]
#192-bits
tx_binary_cropped = tx_binary[0:192]
tx_restored = int(tx_binary_cropped, 2)
#sha-256
hash_hex = hashlib.sha256(str.encode(str(tx_restored))).hexdigest()
hash_binary = bin(int(hash_hex, 16))[2:]
k1 = int(hash_binary[0:128], 2).to_bytes(16, byteorder="big")
k2 = int(hash_binary[128:], 2).to_bytes(16, byteorder="big")
return k1, k2
Notice that this key derivation function will be public whereas input point T will be secret. Alice and Bob will feed the shared point into this function.
# Bob uses KDF and gets k1, k2 pair k1b, k2b = derive_keys(Jb) # Alice uses KDF to find k1, k2 pair k1a, k2a = derive_keys(Ja) assert k1a == k1b assert k2a == k2b
Alice and Bob should generate same k1 and k2 key pair.
Message Authentication Code
Once they derived the key, they will use the second derived key for message authentication code (MAC).
# Bob finds MAC for the message with k2 key
# Notice that an attacker does not know k2, so the attacker cannot find tb
msg = f"2BobAlice{Rb[0]}{Rb[1]}{Ra[0]}{Ra[1]}"
tb = find_mac(message = bytes(msg, "utf-8"), key = k2b)
# ---------------------------------------------
# Alice uses k2 to validate tb coming from Bob
msg = f"2BobAlice{Rb[0]}{Rb[1]}{Ra[0]}{Ra[1]}"
t = find_mac(message = bytes(msg, "utf-8"), key = k2a)
assert t == tb
# Then she finds the mac of the message with k2 key
# Notice that Bob already knows k2, so he can validate ta
msg = f"2AliceBob{Ra[0]}{Ra[1]}{Rb[0]}{Rb[1]}"
ta = find_mac(message = bytes(msg, "utf-8"), key = k2a)
# Now Alice sends ta to Bob
# ---------------------------------------------
# Bob verifies ta coming from Alice
msg = f"2AliceBob{Ra[0]}{Ra[1]}{Rb[0]}{Rb[1]}"
t = find_mac(message = bytes(msg, "utf-8"), key = k2b)
assert t == ta
Because no one will know k2 key except Alice and Bob, this cannot be verified if mac is created by someone else.
Symmetric Key Encryption
When they confirm the coming messages with k2 key, they can use k1 key for symmetric key encryption such as AES.
# bob will encrypt a message with k1
msg = "attack tomorrow!"
obj_bob = AES.new(k1b)
c = obj_bob.encrypt(msg)
print(f"ciphertext is {c}")
# alice will decrypt a message with k1
obj_alice = AES.new(k1a)
plaintext = obj_alice.decrypt(c)
print(f"restored plaintext is {plaintext}")
Conclusion
As we reach the end of our journey through the implementation of Elliptic Curve MQV in Python, we have gained a deeper understanding of the inner workings of this powerful cryptographic protocol. By harnessing the beauty and complexity of elliptic curves, we have witnessed the strength of MQV in establishing secure key agreements between parties. Throughout our exploration, we have encountered the intricacies of elliptic curve operations, the principles of key agreement, and the step-by-step implementation of the MQV protocol. Armed with this knowledge, we are now equipped to employ Elliptic Curve MQV in real-world scenarios, ensuring the confidentiality and integrity of our communications. As the realm of cryptography continues to evolve, we encourage you to further explore this fascinating field, discover new cryptographic techniques, and contribute to the advancement of secure communication. Remember, the key to secure communication lies in our hands, and with the power of cryptography, we can build a safer digital future.
As a side node, NSA dropped ECMQV in Suite B which determines a set of cryptographic standards. Elliptic Curve Diffie Hellman is still available in this list as a key agreement protocol.
I pushed the source code of this study into GitHub. You can support this work if you star⭐ its repo 🙏
Like this blog? Support me on Patreon
