CURVE25519

 ELLIPTIC CURVE CRYPTOGRAPHY: CURVE25519

Table of content:

1. Introduction
2. The Curve25519
3. The Montgomery Ladder Algorithm
4. Generating the Private key and Public key
5. Conclusion

Introduction

Curve25519 or X25519 is an Elliptic Curve Cryptography (ECC) Algorithm designed by Daniel J. Bernstein and was introduced in 2005. The purpose of X25519 is for fast and secure key exchange. ECC uses the mathematics of elliptic curves over a finite field. Some key feature of the X25519:

1. Efficiency
2. Compact representation
3. Immune to timing attack
4. Ease of implementation
5. Uses the Diffie-Hellman Key Exchange

I already have some blog in ECC and Finite field.

The Curve25519

Look at my previous blog about ECCs to know the mathematics behind it.

The Montgomery Ladder Algorithm

The curve25519 uses scalar multiplication to generate the public key using the private key and the base point. The algorithm used to calculate the scalar multiplication is the Montgomery Ladder Algorithm.

The Montgomery Ladder Algorithm uses the adding points  and doubling points arithmetic that Elliptic curves have.

Here is the logic behind it. Below is a pseudocode of the algorithm:

-----------------------------------------------------------------------------------------------------------------------------

FUNCTION Montgomery_Ladder(BasePoint, Scalar) RETURNS TUPLE
//Initialise the 2 points R0 and R1
R0 = (0,1)
R1 = BasePoint

//get the length of the binary of scalar
bit_length = scalar.BIT_LENGTH(Scalar)
FOR I <-- Bit_length -1 TO -1 STEP -1
//Get the i-th bit in the binary
bit_i = (scalar >> i ) & 1

//Select point based on the i-th bit
IF (bit_i = 0) THEN
R1 = AddPoints(R0, R1)
R0 = DoublePoint(R0)
ELSE
R0 = AddPoints(R0, R1)
R1 = DoublePoint(R1)
ENDIF

ENDFOR

RETURN R0
END FUNCTION

-----------------------------------------------------------------------------------------------------------------------------

the Montgomery Ladder Algorithm will loops for the length of the scalar in binary. If the binary is 16-bit, it will iterates 16 times.

On my blog, Elliptic Curve: Montgomery Curve, I already explained the point addition and point doubling in great details with an example.

Note: R0 and R1 are both tuples. I am using python's tuple to facilitate the pseudocode.

Generating the Private Key and Public Key

The Private key is generated randomly in the range from 1 to [2^252 + 27742317777372353535851937790883648493]. 

To compute the public key, we use the equation:

The equation uses scalar multiplication to compute the Public key. The Montgomery Ladder Algorithm can perform the Scalar Multiplication.

Here is my version of the pseudocode of the generation and computation of the public and private keys:

-----------------------------------------------------------------------------------------------------------------------------

//ASSUME THAT THE Montgomery_Ladder AND THE Encode FUNCTIONS ARE //ALREADY IMPLEMENTED.

//Global Parameters
prime_mod = POWER(2, 255) - 19
//By^2 = x^3 + Ax^2 + x
A = 486662
B = 1


BasePoint = (9, 14781619447589544791020593568409986887264606134616475288964881837755586237401)

//Generate the Private Key
PrivateKey = RANDOM.INTEGER(1, 2^252 + 27742317777372353535851937790883648493)

//Generate public key
PublicKey = Montgomery_Ladder(BasePoint, PrivateKey)

//Encoding the public key to a standard version
Encoded_PublicKey = Encode(PublicKey)

PRINT("Private key: ", PrivateKey)
PRINT("Public key: ", PublicKey)
//HEX() display the hexadecimal Version
PRINT("Public key: ", Encoded_PublicKey.HEX())

-----------------------------------------------------------------------------------------------------------------------------

You can find the whole source code of my version of Curve25519 key generation on my GitHub here.

Conclusion

This is not a full tutorial on Curve25519. There are a lot more function that it did not touch on or did not read further enough. Curve25519 was a time consuming learning project that i have made so far. To learn more about it i recommend check out the full documentation here.