Diffie-Hellman

• Two parties can jointly agree a shared secret over an insecure channel
• Mathematically, both calculating the same value mod a prime p
• $p$ 600+ decimal digits
• The parties separately compute the same key, rather than share it

Groups

1. Operation is closed
2. Operation is associative
3. Neutral element
4. Each $a \in G$ called a neutral element such that ...
5. A group $G$ is abelian (commutative)

$\Z^*_n$ consists of the integers 1,2,..,n-1 for which $gcd(i,n)=1$ . This set forms an abelian group under multiplicative n

Group Cardinality

• The cardinality of a group is the number of elements in that group $|\Z^*_p|=p-1$

Cyclic Groups

...

• A group that contains an element $g$ of maximum order is called a cyclic group
• Any element of maximum order is called a primitive root, or generator

Subgroups

• For all primes, ..., is an abelian finite cyclic group
• Will always be a size of 1,2,5 or 10

Order of an element

Cracking

• Brute force: $O(|G|)$
• Shanks Baby-Step Gian-Step: $O(\sqrt{|G|})$ and ~$~ \sqrt{|G|}$
• Pollards Rho: $O(\sqrt{|G|})$
• Pohlig-Hellman: Prime factorisation of $|G|$
  • Discrete log problem is solved mod each prime factor and the results combined using the Chinese remainder theorem
• Index Calculus directly attacks .. and is the reason EC is so much more efficient

Which prime?

• To avoid unexpected small subgroup attacks, DH primes are safe primes
• A safe prime is a prime $p$ where $(p-1)/2$ is also prime