Dev Notes

Software Development Resources by David Egan.

Diffie Hellman Key Exchange


Cryptography
David Egan

The fastest encryption schemes are symmetric - both participants have a copy of a secret key, which is used to encrypt and decrypt messages.

In order to set up such a scheme, Alice and Bob would need to share the secret key by means of a secure channel - and this is where symmetric encryption schemes can be problematic.

If Alice and Bob have a secure communication channel by which to transfer a secret key, it obviates to some extent the necessity for symmetric encryption - they could simply exchange their private message over the secret channel. If they don’t have a secure communication channel, they can’t securely exchange a private key and symmetric encryption is therefore not possible.

Diffie Hellman Key Exchange allows participants to independently compute a shared secret key such that it is computationally infeasible for an adversary to determine the key. Once the “secret” key has been computed by the participants, they can communicate using symmetric encryption.

Neither participant chooses the secret key - but by the end of the algorithm, they each share a copy.

Algortihm

Shared Values (Public)

Participants Alice and Bob agree on two shared values, q and g.

  • q: A large prime number.
  • g: Primitive root of q.

These values are public - they are available to any potential adverary.

Private (Secret) Keys

Alice and Bob each selects a large random number X that serves as their individual private key.

They do not share their private keys - the security of the system is dependent upon these values remaining secret.

  • Alice’s private key: Xa
  • Bob’s private key: Xb

Public Keys

Each particpant computes their Public key by raising g to the power of their private key, modulo q:

Y = gX modulo q

  • Alice’s public key: Ya = gXa modulo q
  • Bob’s public key: Yb = gXb modulo q

These public keys are then shared. Public sharing of these keys does not affect the security of the system.

Compute Shared Key

Each participant computes a shared private key by raising the other participant’s Public key to the power of their own Private key.

This results in each participant having the same secret key - but computation of the secret key is not computationally feasible without the particpant’s Private key that they used to generate the Public key.

Summary of Values

Value Alice Bob
Random number: private Xa Xb
Computed public key Ya = gXa mod q Yb = gXb mod q
Keys swapped Ya, Yb Yb, Ya
Computed shared key Kab = YbXa Kba = YaXb

Because:

Ya = gXa mod q

and

Yb = gXb mod q

For Alice:

(gXb)Xa = gXb . Xa

For Bob:

(gXa)Xb = gXa . Xb

This works because powers of powers are commutative:

(ab)c = abc = acb = (ac)b

Summary of the Private & Exchanged Values

Participant Private Key Shared Public Key Shared Key: computed individually
Alice Xa gXa mod q gXb . Xa
Bob Xb gXb mod q gXa . Xb

Alice and Bob now share a key that is known uniquely to themselves.

They each used their individual private key along with the other participants “public” key.

So long as the public keys are computed with the same values of g and q, the key that they each compute independently will be identical.

Security: Discrete Logarithm Problem

It is hard to compute the private key from the public key.

For example, given Alice’s public key (Ya = gXa mod q), it is hard to determine the private key Xa from gXa. This is known as the discrete logarithm problem.

Given gec mod q, it is difficult to compute e when g (the original generator), c(a public key) and q (the modulus) are known.


comments powered by Disqus