Add group parameters checks to SRP6IntegerVariable

[Glusk]

• check if a variable is a safe prime of the form: p = 2q + 1, where p and q are prime numbers
• check if a variable is generator or a primitive root modulo N

[Glusk]

Generators

If p is a prime, and g is less than p, then g is a generator mod p if

• for each b from 1 to p - 1, there exists some a where g^a ≡ b (mod p).

Another way of saying this is that g is primitive with respect to p.

For example, if p = 11, 2 is a generator mod 11:

• 2¹⁰ = 1024 ≡ 1 (mod 11)
• 2¹ = 2 ≡ 2 (mod 11)
• 2⁸ = 256 ≡ 3 (mod 11)
• 2² = 4 ≡ 4 (mod 11)
• 2⁴ = 16 ≡ 5 (mod 11)
• 2⁹ = 512 ≡ 6 (mod 11)
• 2⁷ = 128 ≡ 7 (mod 11)
• 2³ = 8 ≡ 8 (mod 11)
• 2⁶ = 64 ≡ 9 (mod 11)
• 2⁵ = 32 ≡ 10 (mod 11)

Every number from 1 to 10 can be expressed as 2^a (mod p).

For p = 11, the generators are 2, 6, 7, and 8. The other numbers are not generators. For example, 3 is not a generator because there is no solution to

• 3^a = 2 mod 11

In general, testing whether a given number is a generator is not an easy problem. It is easy, however, if you know the factorization of p - 1. Let q₁, q₂,..., q_n be the distinct prime factors of p - 1. To test whether a number g is a generator mod p, calculate

• g^{(p- 1)/q} mod p

for all values of q = q₁, q₂,..., q_n.

If that number equals 1 for some value of q, then g is not a generator. If that value does not equal 1 for any values of q, then g is a generator.

For example, let p = 11. The prime factors of p - 1 = 10 are 2 and 5. To test whether 2 is a generator:

• 2^{(11- 1)/5} mod 11 = 4
• 2^{(11- 1)/2} mod 11 = 10

Neither result is 1, so 2 is a generator.

To test whether 3 is a generator:

• 3^{(11- 1)/5} mod 11 = 9
• 3^{(11- 1)/2} mod 11 = 1

Therefore, 3 is not a generator.

If you need to find a generator mod p, simply choose a random number from 1 to p - 1 and test whether it is a generator. Enough of them will be, so you’ll probably find one fast.

[Source]: Applied Cryptography: Protocols, Algorithms, and Source Code in C (2nd Edition) by Bruce Schneier