Elliptic Curve Menezes-Qu-Vanstone In Python From Scratch

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.

Swirl Candy Stick by pexels

Vlog

Join this video to implement ECMQV in python from scratch.


πŸ™‹β€β™‚οΈ You may consider to enroll my top-rated cryptography course on Udemy

Public Key Cryptography From Scratch

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 πŸ™






Support this blog if you do like!

Buy me a coffee      Buy me a coffee