Editing Diffie–Hellman key exchange (section)

=== 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, ...).