diff options
author | Prefetch | 2022-10-14 23:25:28 +0200 |
---|---|---|
committer | Prefetch | 2022-10-14 23:25:28 +0200 |
commit | 6ce0bb9a8f9fd7d169cbb414a9537d68c5290aae (patch) | |
tree | a0abb6b22f77c0e84ed38277d14662412ce14f39 /source/know/concept/diffie-hellman-key-exchange |
Initial commit after migration from Hugo
Diffstat (limited to 'source/know/concept/diffie-hellman-key-exchange')
-rw-r--r-- | source/know/concept/diffie-hellman-key-exchange/index.md | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/source/know/concept/diffie-hellman-key-exchange/index.md b/source/know/concept/diffie-hellman-key-exchange/index.md new file mode 100644 index 0000000..0947e29 --- /dev/null +++ b/source/know/concept/diffie-hellman-key-exchange/index.md @@ -0,0 +1,75 @@ +--- +title: "Diffie-Hellman key exchange" +date: 2021-03-06 +categories: +- Cryptography +layout: "concept" +--- + +In cryptography, the **Diffie-Hellman key exchange** is a method +for two parties to securely agree on an encryption key, +when they can only communicate over an insecure channel. + +The fundamental assumption of the Diffie-Hellman scheme, +upon which its security rests, +is that the following function $f(n)$ is a **trapdoor function**, +which means that calculating $f$ is easy, +but its inverse $f^{-1}$ is extremely hard to find: + +$$\begin{aligned} + f(n) = g^n \bmod p +\end{aligned}$$ + +Where $n$ is a natural number, and $p$ is a prime. +The natural number $g$ is a so-called *primitive root modulo* $p$. +Importantly, $g$ and $p$ have been specifically chosen +such that $f(n)$ can take any value in $\{1, ..., p \!-\! 1\}$ +for $n$ in $\{0, ..., p \!-\! 2\}$. +The trapdoor assumption is that, given $g$, $p$ and $f(n)$, +there is no efficient algorithm to recover $n$. + +Suppose that Alice and Bob want to exchange encrypted data in the future, +so they need to agree on an encryption key to use. +However, they can only exchange messages with each other over +an insecure channel, which is being eavesdropped. + +After they publicly agree on the values of $g$ and $p$, +Alice and Bob each choose a secret number from $\{0, ..., p \!-\! 2\}$, respectively $a$ and $b$, +and then privately calculate $A$ and $B$ as follows: + +$$\begin{aligned} + A = g^a \bmod p + \qquad \quad + B = g^b \bmod p +\end{aligned}$$ + +Finally, they transmit these numbers $A$ and $B$ +to each other over the insecure connection, +and then each side calculates $k$, which is the desired secret key: + +$$\begin{aligned} + \boxed{ + k = A^b \bmod p = B^a \bmod p = g^{ab} \bmod p + } +\end{aligned}$$ + +The point is that $k$ includes both $a$ *and* $b$, +but each side only needs to know *either* $a$ *or* $b$. +And, due to the trapdoor assumption, +the eavesdropper knows $A$ and $B$, +but cannot recover $a$ or $b$. + +This assumption is just that: an assumption. +So far, nobody has been able to prove or disprove it +for classical computation. +However, for quantum computers, +it has already been *dis*proven! +In this case, another method must be used, +for example the [BB84 protocol](/know/concept/bb84-protocol/). + + + +## References +1. J.B. Brask, + *Quantum information: lecture notes*, + 2021, unpublished. |