# 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 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 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

The paper is behind a paywall, but 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).$