Zero Knowledge Proofs Series #7 [Diffie-Hellman Key Exchange , Elliptic Curves II]

Exploring Cryptographic Functions: From Graphs to Elliptic Curves

Understanding the mathematical functions that describe graphs is crucial for cryptography. From linear to quadratic to polynomial functions, each offers unique characteristics that impact their suitability for encryption algorithms.

Linear Functions

A linear function is the simplest form of a graph, described by the equation ( y = mx + c ), where ( m ) represents the slope and ( c ) represents the y-intercept. Linear functions produce straight lines on a graph.

Consider the linear function:

[ y = 2x + 1 ]

This function satisfies the points:

Quadratic Functions

Quadratic functions introduce a U-shaped curve to the graph, described by the equation ( y = ax^2 + bx + c ).

Consider the quadratic function:

[ y = x^2 - x + 2 ]

This function satisfies the points:

Polynomial Functions

Polynomial functions provide curves with various shapes and degrees, offering higher complexity and flexibility. They are described by equations like ( y = a_nx^n + ... + a_1x + a_0 ).

Consider the polynomial function:

[ y = x^3 - x^2 + x - 1 ]

This function satisfies the points:

Transition to Elliptic Curve Cryptography (ECC)

While polynomial functions provide increased complexity and flexibility, they still have limitations for certain cryptographic applications. This is where elliptic curve cryptography (ECC) steps in.

Elliptic Curve Cryptography Fundamentals

Elliptic curve cryptography operates on points of an elliptic curve defined over a finite field. Key operations in ECC include:

• Point Addition: Combining two points on the curve to find a third point that lies on the curve.
• Scalar Multiplication: Repeatedly adding a point to itself by a scalar value.
• Infinity Point: The point at infinity serves as the identity element for point addition.
• Base Point: A fixed point on the curve used as a reference for scalar multiplication.

For a visual understanding of these operations, you can watch https://www.youtube.com/watch?v=XmygBPb7DPM

Turning Classical Cryptosystems into Elliptic Curve Versions

Exploring Secure Key Exchange: Diffie-Hellman and Elliptic Curve Diffie-Hellman

In the realm of secure communication, one of the fundamental challenges is how to exchange cryptographic keys over an insecure channel without the risk of interception. This challenge is elegantly addressed by two widely used protocols: Diffie-Hellman key exchange (DHE) and its elliptic curve counterpart, Elliptic Curve Diffie-Hellman (ECDH). In this blog post, we delve into the inner workings of these protocols, shedding light on their mechanisms and the security they provide.

Understanding Diffie-Hellman Key Exchange

Setup:

• Alice and Bob agree on a large prime number ( p ) and a base ( G ) (generator) in a finite field.

Key Generation:

• Alice chooses a private key ( a ) and computes her public key ( G^a ).
• Similarly, Bob chooses a private key ( b ) and computes his public key ( G^b ).

Key Exchange:

• Alice sends her public key ( G^a ) to Bob, and Bob sends his public key ( G^b ) to Alice.

Shared Secret:

• Alice computes ( (G^b)^a = (G^a)^b ) and Bob computes ( (G^a)^b = (G^b)^a ).
• Now, both Alice and Bob possess the same shared secret ( G^{ab} ), which can be used for secure communication.

The Beauty of Elliptic Curve Diffie-Hellman

While DHE operates in a finite field, ECDH operates on points of an elliptic curve, providing equivalent security with smaller key sizes. The principles are similar, but the operations are performed on elliptic curve points.

Setup:

• Alice and Bob agree on an elliptic curve and a base point ( P ) on that curve.

Key Generation:

• Alice chooses a private key ( a ) and computes her public key ( aP ).
• Bob chooses a private key ( b ) and computes his public key ( bP ).

Key Exchange:

• Alice sends her public key ( aP ) to Bob, and Bob sends his public key ( bP ) to Alice.

Shared Secret:

• Alice computes ( (bP)^a = a(bP) ).
• Bob computes ( (aP)^b = b(aP) ).
• They both arrive at the same shared secret ( abP ) without explicitly exchanging it over the network.

Elgamal Crypto System

Setup:

• Alice and Bob agree on a large prime number ( p ) and a base ( G ) (generator) in a finite field.

Bob's Encryption:

• Bob generates a random ephemeral key ( k ). He computes ( G^k ) and sends it to Alice along with the ciphertext ( C = M \times (G^a)^k ).

Alice's Decryption:

• Alice receives ( G^k ) and ( C ).
• She computes the shared secret ( S = (G^k)^a = G^{ka} ) using her private key ( a ).
• She calculates the multiplicative inverse of ( S ) to obtain ( (S^{-1}) = (G^{ka})^{-1} = (G^a)^{-k} ).
• Alice then decrypts the ciphertext ( C ) by computing ( M = C \times (S^{-1}) ).

Now, let's address your question about how the decryption process works:

[ M = C \times (S^{-1}) ]

Substituting ( C = M \times (G^a)^k ):

[ M = (M \times (G^a)^k) \times (S^{-1}) ]

Since ( (G^a)^k = G^{ka} ):

[ M = M \times G^{ka} \times (G^{ka})^{-1} ]

Multiplicative inverses cancel out:

[ M = M ]

So, when Alice decrypts the ciphertext using her private key ( a ), she effectively cancels out the effect of the ephemeral key ( k ), leaving her with the original message ( M ). This process ensures that only Alice, possessing the private key ( a ), can decrypt the message successfully, even if an eavesdropper intercepts the communication.

Transition to Elliptic Curve ElGamal

Setup:

• Alice and Bob agree on an elliptic curve and a base point ( P ) on that curve.

Key Generation:

• Alice chooses a private key ( a ) and computes her public key ( aP ).
• Bob chooses a private key ( b ) and computes his public key ( bP ).

Shared Secret:

• Alice computes ( abP = (bP)^a ).
• Bob computes ( abP = (aP)^b ).
• They both arrive at the same shared secret ( abP ) without explicitly exchanging it over the network.

Message from Bob

Bob's Encryption:

• Bob generates a random ephemeral key ( k ). He computes ( kP ) and sends it to Alice along with the ciphertext ( C = M + (aP)k ). Alice's Decryption:
• Alice receives ( kP ) and ( C ).

The description provided seems to describe a combination of both the Diffie-Hellman key exchange and the ElGamal encryption scheme.

Here's a breakdown of the elements mentioned:

Key Exchange:

• The initial part about Alice and Bob exchanging public keys (( G^a ) and ( G^b )), and computing the shared secret (( G^{ab} )), corresponds to the Diffie-Hellman key exchange.

Encryption:

• The later part about Bob encrypting a message (( M )) using an ephemeral key (( k )) and the public key of Alice (( (aP) )), (( M + (aP)k )), corresponds to the ElGamal encryption scheme.

So, to clarify, the process described involves:

• Key Exchange: Diffie-Hellman
• Encryption: ElGamal

Both schemes are fundamental cryptographic techniques used for different purposes. Diffie-Hellman is primarily used for key exchange, while ElGamal is a public-key cryptosystem used for encryption and digital signatures.

Conclusion

Understanding the foundational principles of graph functions and their role in cryptography provides insights into designing secure communication systems. From linear to polynomial functions, each offers unique characteristics that impact encryption algorithms. Transitioning to elliptic curve cryptography further enhances security and efficiency, making it a preferred choice for modern cryptographic applications. By exploring these concepts, we can build robust systems that safeguard sensitive information in an increasingly connected digital world.