Elliptical Curve Cryptography

Wiki: elliptical curve

Elliptical curves allow smaller keys to provide equivalent security, compared to cryptosystems based on modular exponentiation such as RSA.
A 256-bit ECDH key has approximately the same safety factor as a 128-bit aes key (which is even higher than 2048 bit RSA)

In TLS, Elliptical Curve Cryptography is used primarily for:

1. Key Exchange: Generating a shared secret which later form the symmetric key
2. Certificate Signing and Verfication: Used to verfiy authenticity of the server using Public Key Infrastructure and X.509 certificates

Elliptical Curve Cryptography on its own can not be used for encryption and decryption. Instead, its always paired with Symmetric Encryption algorithms in cypher suites.

The math

Have a look at this youtube video to understand the math.

In summary:

1. The machine generates a random 32 byte number which becomes the private key (pk).
2. The generator function (G) is determined based on:
   1. The curvature (e.g. prime256v1, curve25519)
   2. Other curve parameters if any
3. The public key (P) is derived using the formula: $P=pk\cdot G$
   Notes:
4. The function G and public key P are part of the public information during any elliptical curve based algorithm.
5. Public key can be derived from private key, but vice-versa is impossible.
6. Unlike RSA, the public and private keys are not interchangable.

ECDH

Elliptic-curve Diffie–Hellman or ECDH uses DH key exchange, and Elliptical Curve Cryptography method to generate the secret.

ECDHE (where final ‘E’ stands for “ephemeral”) schemes like X25519 are widely used in TLS cypher suite for initial key exchange. Python’s cryptography library has a seperate implementation of X25519 key exchange

General algorithm:

Let’s assume a scenario where 2 systems, A and B wish to communicate securely, for which they need to generate a shared secret using ECDH.

1. A creates random private key ($p{k}_A$), selects elliptical curve parameters which determines generation function $G$, and generates public key ($P_A$) using the formula: $P_A=p{k}_A.G$
2. A sends the $P_A$ and information about elliptical curve params to B.
3. B also generates its own random private key ($p{k}_B$). It uses the ellptical curve params from A to get the same generation function $G$, and computes its own public key $P_B$: $P_B=p{k}_B.G$
4. B sends its public key $P_B$ to A.
5. Finally, similar to standard Diffie-Hellman key exchange, the shared secret is the private key multiplied with the public key of other system.
   $shared\_secret=p{k}_A.P_B=p{k}_B.P_A=p{k}_A.p{k}_B.G$

ECDSA

Elliptical Curve Digital-Signature Algorithms is a family of Digital Signing and Authentication algorithms based on Elliptical curve cryptography..

Ed25519

Ed25519 is an implementation of ECDSA (or EdDSA to be specific) used widely for user authentication, like in ssh. It is based on Edward Curves.

To try hands-on of Ed25519 signing, refer python’s cryptography module documentation

For detailed explaination of Algorithm, visit this note