# Primitive root in a finite field

Wen-Her Yang and Shiuh-Pyng Shieh proposed two password authentication schemes by employing smart cards, one is timestamp-based and the other one is nonce-based. Their scheme consists of 3 phases: Registration, login and authentication phase.

Considering timestamp-based scheme, step 3 of registration phase says:

Find an integer $$g$$ which is a primitive element in both $$\operatorname{GF}(p)$$ and $$\operatorname{GF}(q)$$, where $$g$$ is the system's public information.

What happens if we use a $$g$$ that is not a primitive element of those two fields? How can this affect scheme security?

I myself think that by selecting a $$g$$ that is not a primitive element, we end up using a smaller group which probably can make things easier for an attacker to solve discrete logarithm problem $$h_i=g^{\mathit{pw}_i\cdot d}$$ and obtain $$\mathit{pw}_i\cdot d$$.

• If $g$ has order $k$ modulo $n$, then there are only $k$ equivalence classes of passwords that system can distinguish. But that just means $g$ should have large order modulo $n$, not that it should generate all of $\operatorname{GF}(p)$ and $\operatorname{GF}(q)$. Conceivably if $k$ were really small you could discover it (say, with Floyd's cycle-finding algorithm), and by Lagrange's theorem it would be a nontrivial factor of $\phi(n) = (p - 1) \cdot (q - 1)$ which might help to find $\phi(n)$ and thereby factor $n$—but it's not immediately clear after ten minutes of thought how to do that. – Squeamish Ossifrage Mar 2 '18 at 23:07
• Obviously if you knew the order of $g$ and it were small, that would also help to compute discrete logs in the group it generates. But if you could find the order of $g$ and it were large (too large to run Floyd's algorithm, for instance, or, in the attacker's best case, equal to $\phi(n)$) then you could presumably use that to break RSA. – Squeamish Ossifrage Mar 2 '18 at 23:24

You're right. In general if a $$g$$ is not a primitive element of $$\operatorname{GF}(p)$$ it generates a smaller subgroup of $$\operatorname{GF}(p)^{\ast}.$$ Since $$|\operatorname{GF}(p)^{\ast}|=p-1$$ is divisible by 2, this subgroup can be as small as 2 in size, and its size can take on any value $$w,$$ where $$w \mid (p-1).$$