A Deep Dive into X25519
Curve25519 is a Montgomery curve built by Bernstein in 2006, in which 25519 indicates that the characteristic of the bottom prime number field on which the elliptic curve depends is 2²⁵⁵-19. Based on Curve25519, Bernstein constructed the Diffie-Hellman key exchange protocol X25519. Compared with the ECDH key exchange protocol, the most notable feature of the X25519 protocol is that it only depends on the x coordinate of the point on the elliptic curve. The idea of constructing an ECDH key exchange protocol using only x coordinates originally came from the paper published by Victor Millier in 1985, “Use of Elliptic Curves in Cryptography”, which was believed to be the cornerstone of this field.
The initial contact with the ECDH protocol, which relies only on the x-coordinates, always feels a bit strange. However, considering the x-coordinate and curve equations, it is basically possible to completely determine a point to help eliminate this strange feeling. It is impossible to completely determine a point based on the x-coordinate. The reason is that the points P = (x, y) and -P = (x, — y) have the same x coordinate. That means the x coordinate of the point can uniquely represent elements in the quotient in the perspective of the quotient of the inverse mapping. Intuitively, in the quotient of inverse mapping, point P and point-P collapse into the same element x(P) = x(-P). Furthermore, the k-multiplication result of point P and point-P, which is kP, and k(-P) also collapse into the same element x(k(-P))= x(-kP) = x(kP) in the quotient. It can be intuitively understood that the ECDH key exchange protocol can be constructed based only on the x coordinate.
The calculation only based on the x-coordinate can be constructed on the elliptic curves of various forms, but using the algebraic structure of the point group (the presence of the 4th order point) on the Montgomery curve is less computationally intensive with the Montgomery Ladder Algorithm and is easier to implement in constant time. This is why Bernstein chose the Montgomery curve. In addition to the underlying mathematical structure design, the X25519 key exchange protocol also takes into consideration the problems often encountered in actual deployment and, based on the observation of the Montgomery curve, has ingeniously circumvented such problems, simplifying the implementation and application deployment of X25519.
In the practical application of ECDH, top priority should be given to the check of messages received. In the typical ECDH protocol, both parties participating in the protocol will receive the temporary public key sent by the other party. To ensure security (to ensure their private key information will not leak), it is usually necessary to first check the legality of the received point. If the received point is the point deliberately constructed by the other party, the other party may steal the private key information through the interaction process of the ECDH protocol. If the check of the point is ignored, it may cause small subgroup attacks or invalid-curve attacks, etc. Similar problems exist in ECDH key exchange protocols that rely only on x coordinates. The difference is that it is more difficult to check the validity of the public key at this time, which is to determine whether the amount of received public key x calculated by the curve equation is the quadratic residual on the prime field. Since the square operation on the domain is a 2-to-1 mapping, only half of the x values are legal. In order to solve this problem, the design of the X25519 protocol innovatively takes into consideration the elliptic curve point group on the quadratic expansion domain, while considering the two elliptic curve point groups on the base domain and the quadratic expansion domain. Then the arbitrary value in the number field on the bottom layer can be used as a legal public key. In the perspective of modulo operation, furthermore, any 32-byte array can be used as a legal public key value, thereby eliminating the need to check the validity of the public key. It is noteworthy that although the second expansion is introduced, all operations are still performed on the prime field of the underlying layer, that is, the introduction of the quadratic extension does not increase the computational complexity. Since the discrete logarithm remains difficult in the two curve point groups, the X25519 key exchange protocol is also safe.
Although the design of the X25519 protocol has made the use of the protocol as error-prone as possible, security loopholes have been introduced to the Tendermint Core project, in the design of its own encrypted communication protocol based on X25519, due to improper protocol design. For details of the Curve25519, principle and operation rules of the X25519 protocol and detailed analysis of the X25519 application in Tendermint Core, please click here.
This article is written by longcpp
Source: https://github.com/longcpp/CryptoInAction/blob/master/intro-ed25519/190902-intro-x25519.pdf
