3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Mar 2 '18 at 23:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Mar 2 '18 at 23:24
1
$\begingroup$

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).$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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