Elliptic-curve Diffie–Hellman

The following example illustrates how a shared key is established. Suppose Alice wants to establish a shared key with Bob, but the only channel available for them may be eavesdropped by a third party. Initially, the domain parameters (that is, $(p,\; a,\; b,\; G,\; n,\; h)$ in the prime case or $(m,\; f(x),\; a,\; b,\; G,\; n,\; h)$ in the binary case) must be agreed upon. Also, each party must have a key pair suitable for elliptic curve cryptography, consisting of a private key $d$ (a randomly selected integer in the interval $[1,\; n-1]$) and a public key represented by a point $Q$ (where $Q\; =\; d\; \backslash cdot\; G$, that is, the result of adding $G$ to itself $d$ times). Let Alice's key pair be $(d\_\backslash text\{A\},\; Q\_\backslash text\{A\})$ and Bob's key pair be $(d\_\backslash text\{B\},\; Q\_\backslash text\{B\})$. Each party must know the other party's public key prior to execution of the protocol.

Alice computes point $(x\_k,\; y\_k)\; =\; d\_\backslash text\{A\}\; \backslash cdot\; Q\_\backslash text\{B\}$. Bob computes point $(x\_k,\; y\_k)\; =\; d\_\backslash text\{B\}\; \backslash cdot\; Q\_\backslash text\{A\}$. The shared secret is $x\_k$ (the x coordinate of the point). Most standardized protocols based on ECDH derive a symmetric key from $x\_k$ using some hash-based key derivation function.

The shared secret calculated by both parties is equal, because $d\_\backslash text\{A\}\; \backslash cdot\; Q\_\backslash text\{B\}\; =\; d\_\backslash text\{A\}\; \backslash cdot\; d\_\backslash text\{B\}\; \backslash cdot\; G\; =\; d\_\backslash text\{B\}\; \backslash cdot\; d\_\backslash text\{A\}\; \backslash cdot\; G\; =\; d\_\backslash text\{B\}\; \backslash cdot\; Q\_\backslash text\{A\}$.

The only information about her key that Alice initially exposes is her public key. So, no party except Alice can determine Alice's private key (Alice of course knows it by having selected it), unless that party can solve the elliptic curve discrete logarithm problem. Bob's private key is similarly secure. No party other than Alice or Bob can compute the shared secret, unless that party can solve the elliptic curve Diffie–Hellman problem.

The public keys are either static (and trusted, say via a certificate) or ephemeral (also known as ECDHE, where final 'E' stands for "ephemeral"). Ephemeral keys are temporary and not necessarily authenticated, so if authentication is desired, authenticity assurances must be obtained by other means. Authentication is necessary to avoid man-in-the-middle attacks. If one of either Alice's or Bob's public keys is static, then man-in-the-middle attacks are thwarted. Static public keys provide neither forward secrecy nor key-compromise impersonation resilience, among other advanced security properties. Holders of static private keys should validate the other public key, and should apply a secure key derivation function to the raw Diffie–Hellman shared secret to avoid leaking information about the static private key. For schemes with other security properties, see MQV.

If Alice maliciously chooses invalid curve points for her key and Bob does not validate that Alice's points are part of the selected group, she can collect enough residues of Bob's key to derive his private key. Several TLS libraries were found to be vulnerable to this attack.{{cite journal

| url = https://www.nds.ruhr-uni-bochum.de/media/nds/veroeffentlichungen/2015/09/14/main-full.pdf

| title = Practical Invalid Curve Attacks on TLS-ECDH

| author1 = Tibor Jager

| author2 = Jorg Schwenk

| author3 = Juraj Somorovsky

| date = 2015-09-04

| journal = European Symposium on Research in Computer Security (ESORICS'15)

}}

The shared secret is uniformly distributed on a subset of $[0,\; p)$ of size $(n+1)/2$. For this reason, the secret should not be used directly as a symmetric key, but it can be used as entropy for a key derivation function.

Let $A,\; B\; \backslash in\; F\_p$ such that $B(A^2\; -\; 4)\; \backslash neq\; 0$. The Montgomery form elliptic curve $E\_\{M,A,B\}$ is the set of all $(x,y)\; \backslash in\; F\_p\; \backslash times\; F\_p$ satisfying the equation $By^2\; =\; x(x^2\; +\; Ax\; +\; 1)$ along with the point at infinity denoted as $\backslash infty$. This is called the affine form of the curve. The set of all $F\_p$-rational points of $E\_\{M,A,B\}$, denoted as $E\_\{M,A,B\}(F\_p)$ is the set of all $(x,y)\; \backslash in\; F\_p\; \backslash times\; F\_p$ satisfying $By^2\; =\; x(x^2\; +\; Ax\; +\; 1)$

along with $\backslash infty$. Under a suitably defined addition operation, $E\_\{M,A,B\}(F\_p)$ is a group with $\backslash infty$ as the identity element. It is known that the order of this group is a multiple of 4. In fact, it is usually possible to obtain $A$ and $B$ such that the order of $E\_\{M,A,B\}$ is $4q$ for a prime $q$. For more extensive discussions of Montgomery curves and their arithmetic one may follow.{{cite web |last1=Montgomery |first1=Peter L. |title=Speeding the Pollard and elliptic curve methods of factorization |url=https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdf |publisher=Mathematics of Computation, 48(177):243–264, 1987}}{{cite web |last1=Bernstein |first1=Daniel J. |last2=Lange |first2=Tanja |title=Montgomery curves and the Montgomery ladder |date=2017 |url=https://eprint.iacr.org/2017/293 |publisher=In Joppe W. Bos and Arjen K. Lenstra, editors, Topics in Computational Number Theory inspired by Peter L. Montgomery, pages 82–115. Cambridge University Press, 2017.}}{{cite journal |last1=Costello |first1=Craig |last2=Smith |first2=Benjamin |title=Montgomery curves and their arithmetic - the case of large characteristic fields |journal=Journal of Cryptographic Engineering |date=September 2018 |volume=8 |issue=3 |pages=227–240 |url=https://link.springer.com/article/10.1007/s13389-017-0157-6 |publisher=J. Cryptographic Engineering, 8(3):227–240, 2018.|doi=10.1007/s13389-017-0157-6 |arxiv=1703.01863 }}

For computational efficiency, it is preferable to work with projective coordinates. The projective form of the Montgomery curve $E\_\{M,A,B\}$ is $BY^2Z\; =\; X(X^2\; +\; AXZ\; +\; Z^2)$. For a point $P\; =\; [\; X\; :\; Y\; :\; Z\; ]$ on $E\_\{M,A,B\}$, the $x$-coordinate map $x$ is the following: $x(P)\; =\; [\; X\; :\; Z\; ]$ if $Z\; \backslash neq\; 0$ and $x(P)\; =\; [\; 1\; :\; 0\; ]$ if $P\; =\; [\; 0\; :\; 1\; :\; 0\; ]$ . Bernstein{{cite web |last1=Bernstein |first1=Daniel J. |title=Can we avoid tests for zero in fast elliptic-curve arithmetic? |url=https://cr.yp.to/ecdh/curvezero-20060726.pdf}} introduced the map $x\_0$ as follows: $x\_0(X\; :\; Z)\; =\; XZ^\{p\; -\; 2\}$ which is defined for all values of $X$ and $Z$ in $F\_p$. Following Miller,{{cite book |last1=Miller |first1=Victor S. |title=Advances in Cryptology — CRYPTO '85 Proceedings |chapter=Use of elliptic curves in cryptography |series=Lecture Notes in Computer Science |date=1986 |volume=218 |pages=417–426 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-39799-X_31 |publisher=In Advances in Cryptology - CRYPTO’85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings, pages 417–426. Springer Berlin Heidelberg, 1985|doi=10.1007/3-540-39799-X_31 |isbn=978-3-540-16463-0 }} Montgomery and Bernstein,{{cite book |last1=Bernstein |first1=Daniel J. |title=Public Key Cryptography - PKC 2006 |chapter=Curve25519: New Diffie-Hellman Speed Records |series=Lecture Notes in Computer Science |date=2006 |volume=3958 |pages=207–228 |chapter-url=https://doi.org/10.1007/11745853_14 |publisher=In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg|doi=10.1007/11745853_14 |isbn=978-3-540-33851-2 }} the Diffie-Hellman key agreement can be carried out on a Montgomery curve as follows. Let $Q$ be a generator of a prime order subgroup of

$E\_\{M,A,B\}(F\_p)$. Alice chooses a secret key $s$ and has public key $x\_0(sQ)$;

Bob chooses a secret key $t$ and has public key $x\_0(tQ)$. The shared secret key of Alice and Bob is $x\_0(stQ)$. Using classical computers, the best known method of obtaining $x\_0(stQ)$ from $Q,x\_0(sQ)$ and $x\_0(tQ)$ requires about $O(p^\{1/2\})$ time using the Pollards rho algorithm.{{cite web |last1=Pollard |first1=John M. |title=Monte Carlo methods for index computation mod p |url=https://www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf |publisher=Mathematics of Computation, 32:918–924, 1978}}

The most famous example of Montgomery curve is Curve25519 which was introduced by Bernstein. For Curve25519, $p\; =\; 2^\{255\}\; -\; 19,\; A\; =\; 486662$ and $B\; =\; 1$.

The other Montgomery curve which is part of TLS 1.3 is Curve448 which was introduced

by Hamburg.{{cite web |last1=Hamburg |first1=Mike |title=Ed448-goldilocks, a new elliptic curve |date=2015 |url=https://eprint.iacr.org/2015/625 |publisher=ACR Cryptology ePrint Archive, 2015:625, 2015}} For Curve448, $p\; =\; 2^\{448\}\; -\; 2^\{224\}\; -\; 1,\; A\; =\; 156326$ and $B\; =\; 1$. Couple of Montgomery curves named M[4698] and M[4058] competitive to Curve25519 and Curve448 respectively have been proposed in.{{cite journal |last1=Nath |first1=Kaushik |last2=Sarkar |first2=Palash |title=Security and Efficiency Trade-offs for Elliptic Curve Diffie-Hellman at the 128- and 224-bit Security Levels |journal=Journal of Cryptographic Engineering |date=2022 |volume=12 |pages=107–121 |url=https://link.springer.com/article/10.1007/s13389-021-00261-y |publisher= J Cryptogr Eng 12, 107–121 (2022)|doi=10.1007/s13389-021-00261-y }}, Code available at https://github.com/kn-cs/x25519 For M[4698], $p\; =\; 2^\{251\}\; -\; 9,\; A\; =\; 4698,\; B\; =\; 1$ and for M[4058], $p\; =\; 2^\{444\}\; -\; 17,\; A\; =\; 4058,\; B\; =\; 1$. At 256-bit security level, three Montgomery curves named M[996558], M[952902] and M[1504058] have been proposed in.{{cite journal |last1=Nath |first1=Kaushik |last2=Sarkar |first2=Palash |title=Efficient Elliptic Curve Diffie-Hellman Computation at the 256-bit Security Level |journal=IET Information Security |date=2020 |volume=14 |issue=6 |pages=633–640 |url=https://doi.org/10.1049/iet-ifs.2019.0620 |doi=10.1049/iet-ifs.2019.0620 }}, Code available at https://github.com/kn-cs/mont256-dh and https://github.com/kn-cs/mont256-vec For M[996558], $p\; =\; 2^\{506\}\; -\; 45,\; A\; =\; 996558,\; B\; =\; 1$, for M[952902], $p\; =\; 2^\{510\}\; -\; 75,\; A\; =\; 952902,\; B\; =\; 1$ and for M[1504058], $p\; =\; 2^\{521\}\; -\; 1,\; A\; =\; 1504058,\; B\; =\; 1$ respectively. Apart from these two, other proposals of Montgomery curves can be found at.{{cite web |last1=Bernstein |first1=Daniel J. |last2=Lange |first2=Tanja |title=Safecurves: choosing safe curves for elliptic- curve cryptography |url=https://safecurves.cr.yp.to/equation.html |access-date=April 15, 2024}}

• Curve25519 is a popular set of elliptic curve parameters and reference implementation by Daniel J. Bernstein in C. Bindings and alternative implementations are also available.
• Curve448, an elliptic curve potentially offering 224 bits of security, developed by Mike Hamburg of Rambus Cryptography Research.
• LINE messenger app has used the ECDH protocol for its "Letter Sealing" end-to=ncryption of all messages sent through said app since October 2015.{{cite web|author1=JI|title=New generation of safe messaging: "Letter Sealing"|url=https://engineering.linecorp.com/en/blog/detail/65/|website=LINE Engineers' Blog|publisher=LINE Corporation|access-date=5 February 2018|date=13 October 2015|archive-date=1 February 2019|archive-url=https://web.archive.org/web/20190201120244/https://engineering.linecorp.com/en/blog/detail/65/|url-status=dead}}
• Signal Protocol uses ECDH to obtain post-compromise security. Implementations of this protocol are found in Signal, WhatsApp, Facebook Messenger and Skype.

• Elliptic-curve cryptography
• Diffie–Hellman key exchange
• Forward secrecy

{{Cryptography navbox | public-key}}

{{DEFAULTSORT:Elliptic curve Diffie-Hellman}}

Category:Key-agreement protocols

Category:Elliptic curve cryptography