Expand knowledge base

1 files changed, 74 insertions, 0 deletions

diff --git a/content/know/concept/diffie-hellman-key-exchange/index.pdc b/content/know/concept/diffie-hellman-key-exchange/index.pdc
new file mode 100644
index 0000000..c0af364
--- /dev/null
+++ b/content/know/concept/diffie-hellman-key-exchange/index.pdc
@@ -0,0 +1,74 @@
+---
+title: "Diffie-Hellman key exchange"
+firstLetter: "D"
+publishDate: 2021-03-06
+categories:
+- Cryptography
+
+date: 2021-03-06T16:45:48+01:00
+draft: false
+markup: pandoc
+---
+
+# Diffie-Hellman key exchange
+
+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/).