24 Oct 2025

Key Exchange Mechanisms

key exchange mechanisms

If \(p\) is a very large prime number then a value \(\alpha\) is called the primitive root of the prime if \(\alpha \mod\ p, \alpha^2 \mod\ p, \dots \alpha{}^{(p-1)} \mod\ p\) all form the modulo set wrt \(p\).
Alternately, for any \(b \in \{1, \dots p - 1\}\), there exists a unique \(i\) s.t. \(b \equiv \alpha^i \mod\ p\). \(i\) is called the discrete logarithm of \(b\) for base \(\alpha\) and modulus \(p\).
There can be multiple primitive roots.

We have publicly known numbers \(\alpha\) and \(p\) as noted above. Let the two users be A and B.
A generates \(X_A\) and sends to B \(Y_A = \alpha^{^{X_A}} \mod\ p\)
B generates \(X_B\) and sends to A \(Y_B = \alpha^{^{X_B}} \mod\ p\)
Both raise the publicly exchanges stuff to their own private keys
The final key \(K = \alpha^{X_AX_B} \mod\ p\)
Susceptible to MITM if the attacker in between is present even during key exchange itself. He can simply exchange his own set of private keys with each party.

Key distribution centre KDC.
Every user \(X\) has a secret key with the KDC \(K_X\).
Create a session key \(K_S\) for two users trying to communicate to each other.
A -> KDC: IDA || E[K_a, (IDA || IDB || N₁)]
KDC -> A: KDC || E[K_a, (K_s || IDA || IDB || N₁)] || E[K_b, (K_S || IDA || IDB)]
A -> B: IDA || E[K_b, (K_s || IDA || IDB)]
- This is susceptible to replay attacks.
B -> A: IDB || E[K_s, N₂]
A -> B: IDA || E[K_s, f(N₂)]
Here E can be any symmetric key cryptography algorithm. ChaCha20 is a popular choice.

For the above, we can also introduce a third nonce to prevent replay.

A -> B: E[PU_B, (N1 || ID_A)]
B -> A: E[PU_B, (f(N₁)|| N₂)]
A then generates a session key K_S
A -> B: E[PU_B, (f(N₂) || K_S || E[PR_A, H(K_S)])] (last part acts as a signature)
B -> A: E[K_S, N₃]
A -> B: E[K_S, F(N₃)]

This ensures authenticity. If you remove the signature, it does not ensure authenticity but saves steps.