## Abstract

Bernstein’s design implementation of elliptic Curve25519 in key exchange is claimed to be highly secure and efficient. This curve is, for example, used in the key exchange scheme of TextSecure for Instant Messaging. In this paper, we present an implementation of elliptic Curve25519 in the simplified Elliptic Curve Integrated Encryption Scheme, thus showing that elliptic Curve25519 can also serve other purposes than key exchange. The curve is in Montgomery form, which makes it possible to use Montgomery ladder. Point compression, point decompression, encryption, and decryption algorithms are presented for the simplified Elliptic Curve Integrated Encryption Scheme.

### Keywords

- elliptic curve
- cryptography
- Montgomery ladder
- integrated encryption scheme

## 1. Introduction

Curve25519 is an elliptic curve in Montgomery form with base field *Fp* and *p = 2255–19*. In [1], Bernstein explains its design implementation, which is claimed to be highly secure and efficient. It is, for example, used in the key exchange scheme of TextSecure for Instant Messaging [2]. The advantage of using this curve is that for some point operations, we can use only the *x*-coordinate, which simplifies the computations and also saves storage.

In previous papers we have presented implementations of elliptic curves in Weierstrass form in a binary field: the implementation of a binary field arithmetic operation algorithm [3, 4] and the implementation of the simplified Elliptic Curve Integrated Encryption Scheme (S-ECIES) in a binary field [5]. In the current paper, we present the implementation of Curve25519 in S-ECIES, thus showing that Curve25519 can also serve other purposes than key exchange.

## 2. Elliptic curve Montgomery form

Before defining Curve25519, we will give some basic theory on elliptic curves. This paper is only concerned with elliptic curves in Montgomery form, not Weierstrass form. An elliptic curve over *Fp* in Montgomery form is defined by the equation.

where *A*(*B*^{2} − 4) ≠ 0.

On the points of the elliptic curve, we may define point addition, negation, and doubling. We define point negation as follows: let *E* be an elliptic curve over *Fp* and point *P*(*x,y*) be a point on E. We define point negation of *P* as *–P*(*x, −y*). Let *P*(*x1,y1*) and *Q*(*x2,y2*) be two distinct points on *E*. Then the point addition is *P+Q*(*x3,y3*), where

*P* = *Q*, then the doubling point *P* + *P* is *2P*(*x*_{4}*,y*_{4}), where

and

The points on the elliptic curve along with point at infinity *O* form a commutative group with point addition as its operation.

We define scalar point multiplication as follows: given a positive integer *m*, scalar point *mP* is defined by *mP* = *P+P+...+P* (*m* times addition of *P*).

The advantage of using Montgomery form rather than Weierstrass form is that in Montgomery form, it is possible to operate without *y*-coordinates.

Elliptic curve operation in Montgomery form without *y*-coordinates can be done as follows [6]: let (*X:Y:Z*) be the projective representation of point *P*(*x,y*) in *E*, define *nP =* (*Xn:Yn:Zn*), and write (*x,y*) as (*X/Z,Y/Z*). It is clear that (*m+n*)*P = mP+nP*. If *Pm*(*x1,y1*) = *mP* and *Pn*(*x2,y2*) = *nP, x*_{1} = *Xm/Zm* and *x*_{2} = *Xn/Zn*, then point addition is *Pm+Pn* (*x3,y3*) = (*m+n*)*P*, where *x*_{3} = *Xm+n/Zm+n* and

Point doubling is *2Pn*(*x4,y4*) = *2nP* = *P2n*, where *x*_{4} = *X2n/Z2n* and

Based on the work by Okeya and Sakurai reported in [7], we can recover the *y*-coordinate in projective coordinates. Let *P*(*x,y*), *P1*(*x1,y1*)*, P2*(*x2,y2*) be points on a Montgomery-form elliptic curve. Express *P1 =* (*X1/Z1,Y1/Z1*)*, P2 =* (*X2/Z2, Y2/Z2*), and define *X1rec*, *X2rec*, *X3rec* as follows:

Assuming *P2 = P1+P*, then in projective coordinates the relation

## 3. Curve25519 and simplified ECIES

Curve25519 is the elliptic curve of Montgomery form

on *Fp2*, where *p* is the prime number 2^{255}-19. Based on Bernstein’s paper [1], there are two subgroups of Curve25519 with large-size order, i.e., {*O*} ∪ {*E*(*Fp2*) ∩ (*Fp×Fp*)} with size order 8 × (2^{252} + 277423177773723535358 51937790883648493) and {*O*} ∪ {*E*(*Fp2*) ∩ (*Fp × √2Fp*)} with size order 4 × (2^{253}–5548463555474470 7071703875581767296995).

S-ECIES is based on the elliptic curve discrete logarithm problem described as follows [8]: let *p* be a prime number larger than 3. Let *E* be an elliptic curve over *Fp* such that E contains a cyclic subgroup *H*, generated by *P*, of prime order *m*. The plaintext space is *Fp** and the ciphertext space is (*Fp × F2*) × *Fp**. The key space is L = {(*E, P, Q, n, m*)*: Q = nP*}. Curve *E* and points *P*, *Q*, and *m* become public keys, and *n* becomes the private key.

For every *a* ∈ *Fp** and a secret number *k* ∈ [1*, n* − 1], the encryption function is

where *a0 ≠ 0* is the absis of *kQ.*

For every (*V, c*) ∈ (*Fp × F2*) *× Fp**, the decryption function is

where (x_{0}, y_{0}) is the coordinate of Point-Decompress(V).

We know that the groups {*O*} ∪ {*E*(*Fp2*) ∩ (*Fp × Fp*)} and {*O*} ∪ {*E*(*Fp2*) ∩ (*Fp × *√2F_{p})} are finite with group size at 8 × *p1* and 4 × *p2*, respectively, for some primes *p1* and *p2*. Hence, *E* contains a subgroup with prime order; therefore, Curve25519 can be implemented in ECIES.

## 4. Implementation

In this section, we will give several algorithms in Curve25519 for implementation in S-ECIES, i.e., Montgomery ladder, point compression, point decompression, and others.

An advantage of using an elliptic curve in Montgomery form is that Montgomery ladder can be used for scalar point multiplication.

**Algorithm 1** Montgomery Ladder.

INPUT: scalar *n,* point *P*

OUTPUT: *nP*

*R0 ←O**R1 ← P*for

*i ←m*down to*0*if

*di = 0**R1←R0+R1*(*Point Addition*)*R0←2R0*(*Point Doubling*)else

*R0←R0+R1*(*Point Addition*)*R1←2R1*(*Point Doubling*)end if

end for

return(

*R0*)

Now, we can talk about point compression and point decompression in Curve25519. The algorithm for point compression is straightforward from the existence of two points with the same *x*-coordinate on an elliptic curve, but with a different y-coordinate, i.e., point (*x,y*) and point (*x,-y*), which is equal to point (*x,p-y*). Because *p* is odd prime, if *y* is an odd number, then *p-y* is an even number and vice versa. Hence, we can compress point (*x,y*) by (*x, y* mod 2), of which the possible result is (*x,0*) or (*x,1*).

Remember that in Curve25519 the *y*-coordinate is defined when *y* is not a quadratic residue or (*x,y*√2). By the same argument, if (*x,y*√2) is on E, then (*x-*(*p-y*) √2) is also on E. However, before we can compress a point with form (*x,y*√2), we have to divide the *y*-coordinate with √2 to avoid problems in real computation. Then, the possible result when we compress the point with form (*x,y*√2) is also (*x,0*) or (*x, 1*).

**Algorithm 2.** Point Compression

INPUT: Point(*x,y*).

OUTPUT: Point(*x,i*)

if

*y*quadratic residue modulo p then*i←y*mod 2return (

*x,i*)else

*y←y*/√2.*i←y*mod 2return (

*x,i*)end if

The inverse algorithm for point compression is point decompression, i.e., recalling the “real” y-coordinate from point compression.

**Algorithm 3.** Point Decompression.

INPUT Point (*x,i*).

OUTPUT Point (*x,y*)

*z← x3+486662x2+x*if

*z*quadratic residue modulo p then*y←*√z mod*p*if

*y = i*mod 2 thenreturn (

*x,y*)else

return(

*x,p-y*)end

else

*z←z/2*mod*p**y←√z*mod*p*if

*y = i*mod 2 thenreturn (

*x,y√2*)else

return(

*x,*(*p-y*)*√2*)end

end

The next algorithms are used to recover the *y*-coordinate in elliptic curve Montgomery form, because we need it in ECIES.

Now we can give the algorithms for encryption and decryption. For a point generator P in Curve25519 that has a prime order n, if Alice sends message *x* to Bob with private key m so Q = mP, then Alice encrypts the message with the following algorithm:

**Algorithm 4.** Encryption in Simplified ECIES

INPUT: Plaintext *a*

OUPUT: Ciphertext (*V*(*x1,y1*)*,c*)

*k←*random([*1,n-1*])*R*(*x1,z1*)*←*(*k-1*)*P**Q*(*x2,z2*)*←R*(*x1,y1*)*+P**R*(*y1*)*←Recovery-Y*(*P,R*(*x1,z1*)*,Q*(*x2,z2*))*U*(*x3,y3*)*←R+P**V*(*x3,y3*)*←*Point-Compression(*U*(*x3,y3*))*V*(*x4,y4*)*←kQ**y←x0.a*return(

*V*(*x3,y3*)*,y*)

Note that in the above algorithm in line 4, there is the command “Recovery-Y.” This command is based on Okeya and Sakurai [7].

If Bob wants to read the actual message from Alice, then Bob decrypts Alice’s message using the following algorithm:

**Algorithm 5.** Decryption in Simplified ECIES.

INPUT: Ciphertext(*y1,y2*)

OUTPUT: Plaintext *a*

(

*x0,y0*)*←mPoint-Decompress*(*y1*)*a←x0−1**b←y2a**return b*

Since this elliptic curve contains a cyclic subgroup of prime order, it is possible to apply S-ECIES. For example, fix base point *P*(*X:Y:Z*) with *X =* 9, *Z* = 1 (because in Curve25519, *z1* always has a value of 1), and the *y*-coordinate can be chosen randomly between odd and even integers that satisfy *y2 = x3 + 486662x2 + x.* The chosen base point *P* has prime point order, with point order *m* = 2^{252} + 2774231777737235353585 937790883648493. Hence, the curve can be implemented in S-ECIES.

Then, we choose a random integer, *k*, between 1 and *m*-1. Then, scalar multiplication of *k* with point *x = 9* by using the Montgomery ladder algorithm produces *kP*(*Xk::Zk*), and by using a *y*-coordinate recovery algorithm we can get *kP*(*Xk:Yk:Zk*). After that, we convert the projective coordinates to affine coordinates to get *kP*(*Xk/Zk,Yk/Zk*), and we use *Point-Compress*(*kP*). Then the *y*-coordinate of ciphertext is the multiplication of plaintext *x* with *x3*, where we get *x3* from *kQ =* (*x3,y3*). Since we only use the *x*-coordinate of *kQ*, we can use Montgomery ladder with scalar *k* and point *Q = nP.*

For decryption, we first decompress *V*(*x1,y1*) and then use private key *n* to get scalar multiplication *nV*, using only the Montgomery ladder algorithm. The last step is multiplying the *y*-coordinate of ciphertext with the inverse of the *x*-coordinate of *nV* to get the plaintext *x*. This inverse exists, because we are working in a prime field and the *x*-coordinate of *V* is not zero.

Now, we discuss arithmetic in *Fp* with *p* = 2^{255}–19. There are two operations in *Fp*, addition and multiplication. However, in *Fp* with p = 2^{255}–19, it is not that easy. Bernstein [1] used radix 2^{25.5}, which is a polynomial with form ∑α_{i}x_{i} with *i* is a number between 0 and 9 and *αi* is a multiple of 2^{[25.5i]} (where [*x*] is the smallest integer that is larger than *x*) and *αi*/2^{[25.5i]} is an integer between −2^{25} and 2^{25}. With the restriction that if *i* is an odd number then α_{i}/2^{[25.5i]} is between −2^{24} and 2^{24}, while if *i* is an even number then α_{i}/2^{[25.5i]} is between −2^{25} and 2^{25}, therefore, every element in *Fp* with *p* = 2^{255}–19 can be converted in radix polynomial form. The following algorithm converts integers to radix as follows:

**Algorithm 6.** Integers to radix 2^{25.5}

INPUT: *n*

OUTPUT: *R*(*x*)

*d←*BINARY(*n*)*p←*LENGTH(*d*)*a←0*while

*p > 26*doif

*a = 0 mod 2*then*p←p-26**ka←26*else

*p←p*-25*ka←25*end

*a ←a+1*end

*sum←ZEROS*(*1,a*)*ka←p-1*for

*i←1 to p*doif

*d*(*i*)*=1*then*sum*(*a*)*←sum*(*a*)*+2ka*end

end

for

*i←a-1*downto*0*do*l←ki-1*for

*j←p+1*to*p+ki*doif

*d*(*j*)*=*1 then*sum*(*i*)*←sum*(*i*)+2*l*end

*l←l-*1end

*p←p+ki*end

*g*(*x*)*←*(*sum*(*0*)*+...+sum*(*a*)*xa*)Return

*g*(*x*)

From the above algorithm, first convert the integer to binary representation, and then from the right partition every 26,25,26,25,...,*k*, with 0 ≤ k ≤ 25, as an example of an integer with length of binary representation is 231, then partition from the right 26,25,26,25,26,25,26,25,26,1. Every partition states the value sum of d(i)2*i−1*, with d(i) is the value of the order of the binary representation that is either 0 or 1. Also, the *j*-th partition is the coefficient of x*j−1*.

Example: Suppose we have a 15-digit number, 325606250916557, which has binary representation “1001010000010001100 01110 01110 11000 01010 10110 01101.” For integers, 325606250916557 has two partitions, i.e., 00111011000010101011001101 and 10010100000100011000111. Therefore, the coefficient of x0 is 0.2^{25} + 0.2^{24} + 1.2^{23} + ... + 0.2^{1} + 1.2^{0}, which if we calculated would be the value 15477453. In the same way, coefficient x1 would be the value 4851911. Thus, the number 325606250916557 represented by radix 2^{25.5} would be 4851911x + 15477453. Also, we can use.

addition and multiplication in radix 2^{25.5}.

After we have converted any integer, there is an additional problem when the coefficient of radix 2^{25.5} exceeds our definition. For this problem, Bernstein [1] has already provided a solution.

## 5. Applications

Communication systems in the future are expected to interact between diverse types of devices. This allows the user to construct a personal distributed environment using a combination of different communication technologies. The security of transmitted data between these devices is a very important aspect.

Nowadays instant messaging is popular for personal and business communications instead of short messages (SMS) on mobile devices. However, most mobile messaging applications do not protect confidentiality or message integrity. Supervision over private communications conducted by the NSA motivates many people to use alternative messaging solutions for security and privacy of communication on the Internet. A messaging app that claims to be secure instant messaging and has attracted a lot of attention is TextSecure.

Elliptic curve cryptosystem (ECC) is a public-key cryptography suitable for use in environments with limited resources such as mobile devices and smart cards. In cryptography, Curve25519 is an elliptic curve that offers 128 security bits and is designed for use in the Elliptic Curve Diffie-Hellman (ECDH) key agreement key design scheme. This curve is one of the fastest ECC curves and more resistant to the weak number random generator.

In the TextSecure application, Curve25519 is used for key exchanges and authentication. However, in this paper we show that Curve25519 can also be implemented in simplified Elliptic Curve Integrated Encryption Scheme (S-ECIES). Therefore Curve25519 serves for key exchange, authentication, encryption, and decryption. As Curve25519 is built in such a way as to avoid potential attacks on implementation and avoid side channel attacks and random number generator issues, one may expect more secure communication systems.

## 6. Conclusion

The curve being used in this paper is *y2 = x3 + 48666x2 + x,* a Montgomery curve, over the prime field 2^{255}–19. This protocol uses elliptic point compression (only the *X*-abscissa), allowing for efficient use of Montgomery ladder for ECDH, which uses only *XZ* coordinates.

In this research we develop efficient algorithms for elliptic curve cryptography using Curve25519 which is implemented in security of instant messaging.

Several algorithms have been established for the implementation of Curve25519 in simplified ECIES: Montgomery ladder for scalar point multiplication, point compression and point decompression, encryption and decryption in simplified ECIES, and the algorithm integer to radix for the arithmetic in *Fp* with *p = 2255–19.*

In a future research, implementation of Curve25519 in Elliptic Curve Digital Signature Algorithm may be attempted.

## Acknowledgments

This research is funded by Hibah Riset KK ITB 2017.