Editing Diffie–Hellman key exchange (section)

== Description ==

=== General overview ===
[[File:Diffie-Hellman Key Exchange.svg|thumb|250px|Illustration of the concept behind Diffie–Hellman key exchange]]
Diffie–Hellman key exchange establishes a shared secret between two parties that can be used for secret communication for exchanging data over a public network. An analogy illustrates the concept of public key exchange by using colors instead of very large numbers:

The process begins by having the two parties, [[Alice and Bob]], publicly agree on an arbitrary starting color that does not need to be kept secret. In this example, the color is yellow. Each person also selects a secret color that they keep to themselves – in this case, red and cyan. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colors. Finally, each of them mixes the color they received from the partner with their own private color. The result is a final color mixture (yellow-brown in this case) that is identical to their partner's final color mixture.

If a third party listened to the exchange, they would only know the common color (yellow) and the first mixed colors (orange-tan and light-blue), but it would be very hard for them to find out the final secret color (yellow-brown). Bringing the analogy back to a [[real-life]] exchange using large numbers rather than colors, this determination is computationally expensive. It is impossible to compute in a practical amount of time even for modern [[supercomputer]]s.

=== Cryptographic explanation ===
The simplest and the original implementation,<ref name="Diffie 1976" /> later formalized as '''Finite Field Diffie–Hellman''' in RFC 7919,<ref>{{cite book |title=Real World Cryptography |url=https://books.google.com/books?id=Qd5CEAAAQBAJ |chapter=Key exchange standards |last=Wong |first=David |publisher=Manning |year=2021 | isbn=9781617296710 |chapter-url=https://archive.today/20200921005545/https://freecontent.manning.com/key-exchange-standards/ |via=Google Books}}</ref> of the protocol uses the [[Multiplicative group of integers modulo n|multiplicative group of integers modulo]] ''p'', where ''p'' is [[prime number|prime]], and ''g'' is a [[Primitive root modulo n|primitive root modulo]] ''p''. To guard against potential vulnerabilities, it is recommended to use prime numbers of at least 2048 bits in length. This increases the difficulty for an adversary attempting to compute the discrete logarithm and compromise the shared secret. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to {{nowrap|''p'' − 1}}. Here is an example of the protocol, with non-secret values in {{blue|blue}}, and secret values in '''{{red|red}}'''.
# [[Alice and Bob]] publicly agree to use a modulus ''{{blue|p}}'' = {{blue|23}} and base ''{{blue|g}}'' = {{blue|5}} (which is a primitive root modulo 23).
# Alice chooses a secret integer '''''{{red|a}}''''' = 4, then sends Bob ''{{blue|A}}'' = ''{{blue|g}}<sup>'''{{red|a}}'''</sup>'' mod ''{{blue|p}}''
#* ''{{blue|A}}'' = {{blue|5}}<sup>'''{{red|4}}'''</sup> mod {{blue|23}} = {{blue|4}} (in this example both ''{{blue|A}}'' and '''''{{red|a}}''''' have the same value 4, but this is usually not the case) 
# Bob chooses a secret integer '''''{{red|b}}''''' = 3, then sends Alice ''{{blue|B}}'' = ''{{blue|g}}<sup>'''{{red|b}}'''</sup>'' mod ''{{blue|p}}''
#* ''{{blue|B}}'' = {{blue|5}}<sup>'''{{red|3}}'''</sup> mod {{blue|23}} = {{blue|10}}
# Alice computes '''''{{red|s}}''''' = ''{{blue|B}}<sup>'''{{red|a}}'''</sup>'' mod ''{{blue|p}}''
#* '''''{{red|s}}''''' = {{blue|10}}<sup>'''{{red|4}}'''</sup> mod {{blue|23}} = '''{{red|18}}'''
# Bob computes '''''{{red|s}}''''' = ''{{blue|A}}<sup>'''{{red|b}}'''</sup>'' mod ''{{blue|p}}''
#* '''''{{red|s}}''''' = {{blue|4}}<sup>'''{{red|3}}'''</sup> mod {{blue|23}} = '''{{red|18}}'''
# Alice and Bob now share a secret (the number 18).

Both Alice and Bob have arrived at the same values because under mod ''p'',
: <math>{\color{Blue}A}^{\color{Red}\boldsymbol{b}}\bmod {\color{Blue}p} = {\color{Blue}g}^{\color{Red}\boldsymbol{ab}}\bmod {\color{Blue}p} = {\color{Blue}g}^{\color{Red}\boldsymbol{ba}}\bmod {\color{Blue}p} = {\color{Blue}B}^{\color{Red}\boldsymbol{a}}\bmod {\color{Blue}p}</math>

More specifically,
: <math>({\color{Blue}g}^{\color{Red}\boldsymbol{a}}\bmod {\color{Blue}p})^{\color{Red}\boldsymbol{b}}\bmod {\color{Blue}p} = ({\color{Blue}g}^{\color{Red}\boldsymbol{b}}\bmod {\color{Blue}p})^{\color{Red}\boldsymbol{a}}\bmod {\color{Blue}p}</math>

Only ''a'' and ''b'' are kept secret. All the other values – ''p'', ''g'', ''g<sup>a</sup>'' mod ''p'', and ''g<sup>b</sup>'' mod ''p'' – are sent in the clear. The strength of the scheme comes from the fact that ''g<sup>ab</sup>'' mod ''p'' = ''g<sup>ba</sup>'' mod ''p'' take extremely long times to compute by any known algorithm just from the knowledge of ''p'', ''g'', ''g<sup>a</sup>'' mod ''p'', and ''g<sup>b</sup>'' mod ''p''. Such a function that is easy to compute but hard to invert is called a [[one-way function]]. Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel.

Of course, much larger values of ''a'', ''b'', and ''p'' would be needed to make this example secure, since there are only 23 possible results of ''n'' mod 23. However, if ''p'' is a prime of at least 600 digits, then even the fastest modern computers using the fastest known algorithm cannot find ''a'' given only ''g'', ''p'' and ''g<sup>a</sup>'' mod ''p''. Such a problem is called the [[discrete logarithm problem]].<ref name=imperfectfs/> The computation of ''g<sup>a</sup>'' mod ''p'' is known as [[modular exponentiation]] and can be done efficiently even for large numbers.
Note that ''g'' need not be large at all, and in practice is usually a small integer (like 2, 3, ...).

=== Secrecy chart ===
The chart below depicts who knows what, again with non-secret values in {{blue|blue}}, and secret values in '''{{red|red}}'''. Here [[Alice and Bob#Cast of characters|Eve]] is an [[Eavesdropping#Network attacks|eavesdropper]] – she watches what is sent between Alice and Bob, but she does not alter the contents of their communications.
* ''<span style="color:blue">g</span>'', public (primitive root) base, known to Alice, Bob, and Eve. ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
* ''<span style="color:blue">p</span>'', public (prime) modulus, known to Alice, Bob, and Eve. ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
* '''''<span style="color:red">a</span>''''', Alice's private key, known only to Alice. '''''<span style="color:red">a</span>''''' = '''<span style="color:red">6</span>'''
* '''''<span style="color:red">b</span>''''', Bob's private key known only to Bob. '''''<span style="color:red">b</span>''''' = '''<span style="color:red">15</span>'''
* ''<span style="color:blue">A</span>'', Alice's public key, known to Alice, Bob, and Eve. ''<span style="color:blue">A</span>'' = ''<span style="color:blue">g</span><sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:blue">p</span>'' = <span style="color:blue">8</span>
* ''<span style="color:blue">B</span>'', Bob's public key, known to Alice, Bob, and Eve. ''<span style="color:blue">B</span>'' = ''<span style="color:blue">g</span><sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>'' = <span style="color:blue">19</span>

{| border="0" cellspacing="0" cellpadding="2"
|-
| valign="top" |
{| class="wikitable"
|+ Alice
|- style="text-align:center;" 
! Known
! Unknown
|-
| ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
|
|-
| '''''<span style="color:red">a</span>''''' = '''<span style="color:red">6</span>'''
| '''''<span style="color:red">b</span>'''''
|-
| ''<span style="color:blue">A</span>'' = <span style="color:blue">5</span><sup>'''''<span style="color:red">a</span>'''''</sup> mod <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">A</span>'' = <span style="color:blue">5</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">8</span>
|
|-
| ''<span style="color:blue">B</span>'' = <span style="color:blue">19</span>
| 
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">B</span><sup>'''''<span style="color:red">a</span>'''''</sup> mod <span style="color:blue">23</span>
|
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">19</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|}
| valign="top" | 
{| class="wikitable"
|+ Bob
|- style="text-align:center;" 
! Known
! Unknown
|-
| ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
|
|-
| '''''<span style="color:red">b</span>''''' = '''<span style="color:red">15</span>'''
| '''''<span style="color:red">a</span>'''''
|-
| ''<span style="color:blue">B</span>'' = <span style="color:blue">5</span><sup>'''''<span style="color:red">b</span>'''''</sup> mod <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">B</span>'' = <span style="color:blue">5</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">19</span>
|
|-
| ''<span style="color:blue">A</span>'' = <span style="color:blue">8</span>
| 
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">A</span><sup>'''''<span style="color:red">b</span>'''''</sup> mod <span style="color:blue">23</span>
|
|-
| '''''<span style="color:red">s</span>''''' = <span style="color:blue">8</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|}
| valign="top" | 
{| class="wikitable"
|+ Eve
|- style="text-align:center;" 
! Known
! Unknown
|-
| ''<span style="color:blue">p</span>'' = <span style="color:blue">23</span>
|
|-
| ''<span style="color:blue">g</span>'' = <span style="color:blue">5</span>
|
|-
|
| '''''<span style="color:red">a</span>''''', '''''<span style="color:red">b</span>'''''
|-
| &nbsp;
| &nbsp;
|-
| &nbsp;
| &nbsp;
|-
| ''<span style="color:blue">A</span>'' = <span style="color:blue">8</span>, ''<span style="color:blue">B</span>'' = <span style="color:blue">19</span>
| 
|-
| &nbsp;
| &nbsp;
|-
|
| '''''<span style="color:red">s</span>'''''
|}
|}

Now '''''<span style="color:red">s</span>''''' is the shared secret key and it is known to both Alice and Bob, but ''not'' to Eve. Note that it is not helpful for Eve to compute ''<span style="color:blue">AB</span>'', which equals ''<span style="color:blue">g</span>''<sup>'''''<span style="color:red">a</span>'''''+'''''<span style="color:red">b</span>'''''</sup> mod <span style="color:blue">p</span>.

Note: It should be difficult for Alice to solve for Bob's private key or for Bob to solve for Alice's private key. If it is not difficult for Alice to solve for Bob's private key (or vice versa), then an eavesdropper, [[Alice and Bob#Cast of characters|Eve]], may simply substitute her own private / public key pair, plug Bob's public key into her private key, produce a fake shared secret key, and solve for Bob's private key (and use that to solve for the shared secret key). [[Alice and Bob#Cast of characters|Eve]] may attempt to choose a public / private key pair that will make it easy for her to solve for Bob's private key.

=== Generalization to finite cyclic groups ===
Here is a more general description of the protocol:<ref>{{cite book|url=https://books.google.com/books?id=BuQlBQAAQBAJ&pg=PA190|title=Introduction to Cryptography|last=Buchmann|first=Johannes A.|publisher=Springer Science+Business Media|year=2013|isbn=978-1-4419-9003-7|edition=Second|pages=190–191}}</ref>
# Alice and Bob agree on a natural number ''n'' and a [[Generating set of a group|generating]] element ''g'' in the finite [[cyclic group]] ''G'' of order ''n''. (This is usually done long before the rest of the protocol; ''g'' and ''n'' are assumed to be known by all attackers.) The group ''G'' is written multiplicatively.
# Alice picks a random [[natural number]] ''a'' with 1 < ''a'' < ''n'', and sends the element ''g<sup>a</sup>'' of ''G'' to Bob.
# Bob picks a random natural number ''b'' with 1 < ''b'' < ''n'', and sends the element ''g<sup>b</sup>'' of ''G'' to Alice.
# Alice computes the element {{math|1=(''g<sup>b</sup>'')<sup>''a''</sup> = ''g<sup>ba</sup>''}} of G.
# Bob computes the element {{math|1=(''g<sup>a</sup>'')<sup>''b''</sup> = ''g<sup>ab</sup>''}} of G.

Both Alice and Bob are now in possession of the group element ''g<sup>ab</sup>'' = ''g<sup>ba</sup>'', which can serve as the shared secret key. The group ''G'' satisfies the requisite condition for [[secure communication]] as long as there is no efficient algorithm for determining ''g<sup>ab</sup>'' given ''g'', ''g<sup>a</sup>'', and ''g<sup>b</sup>''.

For example, the [[Elliptic-curve Diffie–Hellman|elliptic curve Diffie–Hellman]] protocol is a variant that represents an element of G as a point on an elliptic curve instead of as an integer modulo n.&nbsp;Variants using [[Hyperelliptic curve cryptography|hyperelliptic curves]] have also been proposed. The [[supersingular isogeny key exchange]] is a Diffie–Hellman variant that was designed to be secure against [[quantum computers]], but it was broken in July 2022.<ref name=castryckdecru2023>{{cite journal|last1=Castryck|first1=Wouter|last2=Decru|first2=Thomas|date=April 2023|title=An efficient key recovery attack on SIDH|journal=Annual International Conference on the Theory and Applications of Cryptographic Techniques|pages=423–447|url=https://eprint.iacr.org/2022/975.pdf|archive-url=https://web.archive.org/web/20240926174200/https://eprint.iacr.org/2022/975.pdf|archive-date=2024-09-26}}</ref>