How do you pick the generator g?

[gogo9th]

Hi,

I have one conceptual question and I would really appreciate it if you could give me an answer... What is your rule of selecting the generator g? Is g any number random selected between 1 and pq? Or is there more constraint on it?

And I read that g is a generator of an RSA group, but I didn't quite understand this... What does it mean by an RSA group? Is this a ring Z_N where N=pq? I don't think g can generate all numbers between 0 and N-1.

[whaatt]

Hi there! You are correct about what we describe as an RSA group, namely a ring Z_N with N = pq (and we specifically use RSA-2048, a public modulus for which primes p and q were thrown away at the time of generation).

You're also correct that RSA groups are not cyclic, but an arbitrary element g is likely to generate a high-order subgroup. For our security purposes, it remains difficult to take a discrete log base g (DLOG of an arbitrary element is about as hard as factoring the original composite modulus).

We simply use g = 2 in our implementation of the group, rather than the random generator suggested in the original BBF paper. This decision is discussed further in #43.

Please let me know if you have any more questions!

[gogo9th]

Hi,

Thanks very much for your full explanations. I now understand it.

My additional thought is that if we ever randomly pick g, g should be coprime to N. The reason is because phi(N) should be (a multiple of) the order of the generator g. According to Euler's Theorem, if gcd(g, n) = 1, then 1 ≡ g^{phi(n)} mod n. Therefore, if we randomly pick some g such that gcd(g, N) = 1, phi(n) is always guaranteed to be (a multiple of) the order of g modulo n, because multiplying g as many times as phi(n) will be 1 mod n (fully iterating all group elements of g). The constraint to make this hold is to pick some g such that gcd(g, n) = 1. If we randomly pick any prime g, the constraint is always satisfied, because gcd(g, pq) = 1, where pq = n.