Diffie-Hellman Flashcards
Lecture 13 (6 cards)
What is a distinguishing feature of Diffie Hellman?
Each party computes the same key separately, rather than shares it across the communication channel.
How do cyclic groups differ from standard groups i.e. in use in Diffie Hellman?
A cyclic group is a group that can be generated entirely by repeatedly applying the group operation to a single element, called the generator or primitive root.
Why is a generator number for cyclic groups with maximum order important?
A maximum order generator means that, using the group operation and the prime modulus, it generates the entire set up to the maximum possible number, before looping. Example: Z7 = {1, 2, 3, 4, 5, 6}
If you use generator = 3, then you end up with this set before looping:
{3, 2, 6, 4, 5, 1}
This includes all the numbers of the set before a loop occurs
How does Diffie Hellman work in practice?
- Person 1 and 2 agree on a large prime (p) and a generator (g) that is a primitive root of p.
- Person 1 and 2 choose private numbers a and b at random in the set defined by p.
- Person 1 calculates g^a mod p, and sends it publicly to Person 2
- Person 2 caulcates g^b mod p and sends it publicly to Person 1
- Person 1 computes the sent value (B) in this equation: B^a mod p
- Person 2 does the same with Person 1’s sent number (A^b mod p)
What is the Discrete Logarithm Problem?
The challenge of finding an integer, given the generator, the prime number, and y, such that:
g^integer is equivalent to y mod p
It’s computationally impossible when p is set as a large number.
What is a safe prime, and why does Diffie Hellman make use of it?
A safe prime is a prime number where (p - 1) /2 is also a prime number
By choosing a generator of the subgroup of large prime order, Diffie Hellman avoids attacks on small factors of the group order.
