1
$\begingroup$

I am a web developer with only high school level knowledge of math. I wanted to understand how TLS 1.3 is better than TLS 1.2. Along the way, I bumped into the concept of Diffie Hellman Key Exchange algorithm.

I went to wikipedia to learn more about what Diffie Hellman is but I had a hard time comprehending these sentences:

The simplest and the original implementation, later formalized as Finite Field Diffie-Hellman in RFC 7919, of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p–1.

Specifically, I could not comprehend the phrase g is a primitive root modulo of p. When I tried to decipher this phrase, I was brought to other terms like coprime, congruent, equivalence relation, vector space etc..., and drilling down on these terms lead to even more terms that confused me.

So I went to chatgpt and asked the question:

Can you write me a javascript function that takes two numbers p and g as input, and return true if p is a prime number and if g is a primitive root modulo p. The function should return false otherwise.

This is ChatGPT's javascript answer:

function isPrimitiveRoot(p, g) {
    // Check if p is a prime number
    if (!isPrime(p)) {
        return false;
    }

    // Check if g is in the range [1, p-1]
    if (g <= 0 || g >= p) {
        return false;
    }

    // Check if g^i mod p generates all numbers in the range [1, p-1]
    var generated = [];
    for (var i = 1; i < p; i++) {
        var result = modularExponentiation(g, i, p);
        if (generated.includes(result)) {
            return false; // Not a primitive root
        }
        generated.push(result);
    }
    
    return true; // g is a primitive root modulo p
}

// Function to check if a number is prime
function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;
    for (var i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }
    return true;
}

// Function for modular exponentiation (g^i mod p)
function modularExponentiation(base, exponent, modulus) {
    if (modulus === 1) return 0;
    var result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    return result;
}

I understand the logic expressed by these series of Javascript functions. However, I do not know if this Javascript code correctly defines the phrase g is a primitive root modulo of p. Can someone confirm if the Javascript code correctly defines the phrase g is a primitive root modulo of p?


Alternatively, I also know PHP, Python and Go programming language. My goal is to just learn what is meant by g is a primitive root module of p in a language that I understand.

$\endgroup$
2
  • 1
    $\begingroup$ You want « g is a primitive root modulo p » where there is « g is a primitive root module of p ». And as pointed in that answer, the code given is not applicable to parameters of cryptographic interest because it needs $p\le94906249$. Plus it's abominably slow. More generally, don't (at least, yet) trust AIs on hard science questions, or when a wrong result could have damageable consequences. For nontrivial questions, ChatGPT's best achievement is to make an answer that looks like right to one not knowing the subject. $\endgroup$
    – fgrieu
    Apr 14 at 15:24
  • $\begingroup$ "later formalized as Finite Field Diffie-Hellman in RFC 7919, of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p" - However, in RFC 7919, $g$ is not a primitive root modulo $p$. Hence for TLS, asking about primitive roots turns out to be irrelevant, as it doesn't use them. $\endgroup$
    – poncho
    Apr 16 at 11:25

2 Answers 2

3
$\begingroup$

In the wikipedia page you link for DH, the phrase "primitive root modulo p" is a HYPERLINK to https://en.wikipedia.org/wiki/Primitive_root_modulo_n which provides the definition you ask for. Note the general definition talks about "all numbers [meaning integers] coprime to n" (the modulus); when the modulus is prime (and we denote it p), which is the case for DH (and the DH page says so), this is all integers that aren't multiples of p.

Because modular arithmetic forms equivalence classes -- n+3 and 2n+3 etc are equivalent to 3 -- in practice we only work with 0 to n-1 and "all integers in 0 to p-1 coprime to p" or all integers in 0 to p-1 not multiples of p IS all integers 1 to p-1, and that's what ChatGPT's logic tests. However the javascript implementation only works for numbers up to $2^{53}$ (because javascript uses IEEE arithmetic which becomes inexact above that point) and the brute-force primality test is practical only for numbers up to about $2^{70}$ or a little more if you want it to finish while you're still alive. But real cryptographic DH requires much larger numbers -- nowadays $2^{2048}$ is the official minimum in most standards, although somewhat smaller numbers would actually be safe at least for a while.

Python can do correct arithmetic on large integers (I don't think PHP does and I don't know about Go) but the simple logic provided by ChatGPT, translated to Python, is hopelessly impractical for the sizes of numbers we (need to) use for DH -- its runtime would be so much longer than the lifetime of the universe that writing out that multiple wouldn't fit in a StackExchange answer.

Plus in practice we don't actually require a primitive generator -- one that generates the entire (multiplicative) group. We only require a generator of a cyclic subgroup (usually by requiring it to have prime order) that is sufficiently large to be secure. Because possible attacks on the subgroup are different from possible attacks on the outer group, it is sufficient for the subgroup to have a size around $2^{128}$ to $2^{256}$ even while the outer group must have size near 2^2048 or more.

What we actually do is choose a prime $p$ (using more advanced primality testing methods) where $p - 1$ has a known factorization; thus all possible orders of an element can be easily enumerated. Then we test an arbitrarily chosen element to see if it has the desired large-enough prime order; if it fails we try another until we succeed, and it rarely takes many tries.

PS: DH is not really a difference between TLS 1.2 and 1.3, or indeed anything back to SSL 3. All supported it, although up to roughly 2010 when only SSL 3 and TLS 1.0 were common, people often used plain-RSA-wrap (rather than DH including DH-signed-by-RSA).

$\endgroup$
1
  • $\begingroup$ The brute force primality test given here is slow, but not that slow. For n=2^70 it only does 2^35 / 3 = a bit over 11 billion divisions. That should be around a minute. 2^108 in a year, 2^128 in 32 years. In that range, wait a few years to buy your computer because its higher speed will make up for the computing time lost. $\endgroup$
    – gnasher729
    Apr 16 at 11:18
1
$\begingroup$

There is a much faster way to detect that x is a primitive root of a prime p:

There is a theorem that every prime p has a primitive root g (rather hard to prove, but proven). The way primitive roots are defined, every number 1 <= x <= p-1 equals g raised to some power, that is x = g^k. Note that g and k are both unknown.

Find all unique prime factors of p-1 in O(sqrt p) time or faster. If q is a factor of p-1, and r = (p-1) / q, then (g^q)^r = g^(p-1) = 1 modulo p. The same is true for g^2q, g^3q etc. If x = g^nk then x^r = 1 modulo q.

We do this for all prime factors q of p-1: We calculate r = (p-1) / q for each q, and if x^r = 1 modulo p for one r, then x is not a primitive root. Otherwise it is a primitive root.

Factoring p in O(sqrt p) is trivial, factoring in O(p^(1/4) is not hard. There are fewer than log p prime factors, and those powers can easily be calculated in O(log p).

It is also easy to find a primitive root: Just try random numbers from 2 to p-2 until you find a primitive root. The probability that a random x is a primitive root is the product of (1-1/q) over the prime factors of p-1. The smallest p where fewer than one in eight numbers are primitive root is 1 plus the product of the primes from 2 to 79, around 2.6 x 10^29.

$\endgroup$
4
  • $\begingroup$ Actually, for the primes in RFC 7919, $p-1$ is easy to factor; the complete factorization is $p-1 = 2q$ where $q$ is also prime. $\endgroup$
    – poncho
    Apr 16 at 14:41
  • $\begingroup$ So then x is a primitive root unless either x^2 or x^q equals 1 modulo p. If p-1 is product of two large primes, say two 500 bit primes, but the factors are unknown, then finding the prime factors is hard but practically ever random integer other than 1 and p-1 is a primitive root. Of course if I give you x and ask “is it a primitive root” then you should expect that I know the factors and gave you one of the rare numbers that are not primitive roots. $\endgroup$
    – gnasher729
    Apr 17 at 2:01
  • $\begingroup$ "If p-1 is product of two large primes, say two 500 bit primes, but the factors are unknown, then finding the prime factors is hard but practically ever random integer other than 1 and p-1 is a primitive root."; well, no, $p-1$ has 2 as a factor (for $p>2$), and so less than half if the values between 1 and $p-1$ are primitive roots. $\endgroup$
    – poncho
    Apr 17 at 2:18
  • $\begingroup$ @poncho Brain not working properly… Yes, p-1 is never the product of two large primes because it is even. If it is 2*r*s for two large primes r and s, then for half the integers x^(rs) = 1 modulo p and it is not a primitive root, and that part is trivial. For the other half, you’d have to find r or s, but the chance of being not a primitive root is 1/r + 1/s. $\endgroup$
    – gnasher729
    Apr 17 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.