summaryrefslogtreecommitdiff
path: root/source/know/concept/diffie-hellman-key-exchange
diff options
context:
space:
mode:
authorPrefetch2022-10-14 23:25:28 +0200
committerPrefetch2022-10-14 23:25:28 +0200
commit6ce0bb9a8f9fd7d169cbb414a9537d68c5290aae (patch)
treea0abb6b22f77c0e84ed38277d14662412ce14f39 /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.md75
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.