Primitive Roots Matter
The other day, I happened upon a nice writeup titled Modular Exponentiation in Rust. However, after reading halfway through the article, I found some things that didn’t jive. I’ve emailed the author to notify him of the error, so the content may be fixed by now.
Modular exponention is used in Diffie–Hellman key exchange to compute public, private, and shared keys. Below, I describe the subtle problems that occur if one of the primes is not a primitive root of the other.
Before I delve into the details, it’s important to understand what makes a number a primitive root of a prime number n modulo n. A primitive root of a prime will generate all the numbers le
ss than a second prime using modular exponentiation. Said another way, if we compute (g ^ a) % p
where g
is a primitive root of p
, than for all a
[0, p-2]
, the result is a range of
all numbers [1, p-1]
. Further explanation and examples can be found here.
Setup
—
Alice:
- prime 1 (modulus):
941
- prime 2 (base):
631
- chossen secret (exponent):
289
- shareable number:
(631 ^ 289) % 941 = 854
Alice sends 941
, 631
, and 854
to Bob, and Eve cant figure out the secret 289
.
Bob:
- prime 1 (modulus):
941
- prime 2 (base):
631
- chossen secret (exponent): you choose
523
- shareable number:
(631 ^ 523) % 941 = 124
Bob replys with 124
.
Next, Alice and Bob independently compute a shared key.
Alice:
- modulus:
941
- base:
124
- exponent:
289
- shared key:
(124 ^ 289) % 941 = 349
Bob:
- modulus:
941
- base:
289
- exponent:
124
- shared key:
(289 ^ 124) % 941 = 349
The issue is that 289
is Alice’s secret, so Bob can’t possibly know this.
Instead, it should read:
Alice computes: (124 ^ 289) % 941
Bob computes: (854 ^ 523) % 941
But hold on, now if we compute (124 ^ 289) % 941
we get 934
and (854 ^ 523) % 941
results in 933
. Each party should compute the shared key separately and arrive at the same result (even though they use different values during the computation). The problem here is that g
is not a primitive root of p
. To quote wiki:
..the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p
In the above example, g=631
and p=941
, which means that in order for the math to work out, 631 must be a primitive root of p
. Listing all primitive roots of 941
using the tool here shows that 631
is indeed not a primitive root. However, 632
and 629
are both primitive roots of 941
. Using 632
in place of 631
gives us the expected results.
Alice:
- prime 1 (modulus):
941
- prime 2 (base):
632
- choosen secret (exponent):
289
- shareable number:
(632 ^ 289) % 941 = 703
Bob:
- prime 1 (modulus):
941
- prime 2 (base):
632
- choosen secret (exponent):
523
- shareable number:
(632 ^ 523) % 941 = 699
When Alice and Bob compute the shared key, they get the same answer.
Alice:
- modulus:
941
- base:
699
- exponent:
289
- shared key:
(699 ^ 289) % 941 = 839
Bob:
- modulus:
941
- base:
523
- exponent:
703
- shared key:
(703 ^ 523) % 941 = 839
Pretty cool. We now arrive at the same shared secret while using different secret keys that are never revealed. It’s all made possible by using g
631
which is a primitive root of p
941
.