0
$\begingroup$

May be a silly doubt, please rectify my confusion regarding below problem:

For concreteness assume $g=2, p=11, a=6$ and $x=9$

$$A = g^a \bmod p = 2^6 \bmod 11 = 9$$

$$X = g^x \bmod p = 2^9 \bmod 11 = 6$$

$$C = A^x \bmod p = 9^9 \bmod 11 = 5$$

To find $X$ (i.e. $g^x$) using $C$ and $a$ only is:
$X' = C^{a^{-1}} \bmod p = 5^{6^{-1}} \bmod 11 = 5^2 \bmod 11 = 3$

The answer should be $X = X'$ but it is $X \neq X'$
Why this problem, where is my mistake?

$\endgroup$
1
  • $\begingroup$ $6 \times 2 = 2 \mod \phi(11)$. $\endgroup$ Sep 2, 2015 at 11:56

1 Answer 1

2
$\begingroup$

Indeed, theoretically $$X'\equiv C^{a^{-1}}\equiv A^{x*a^{-1}}\equiv g^{x}=X\pmod p$$

should hold, given $gcd(a,p-1)=1$.

However there are two reasons why you won't get this equation to hold.

  1. You calculated $a^{-1}$ using the wrong modulus. As it is in the exponent you need to calculate $a^{-1}\bmod q$ with $q$ being the group's order instead of $a^{-1}\bmod p$. In your example $q=p-1=10$.
  2. The value you have for $a$ makes it impossible to invert. For $a^{-1}\bmod q$ to exist $gcd(a,q)=1$ must hold, but $gcd(6,10)=2\neq1$ so there's no $a^{-1}\bmod q$ for your specific choices of $a$ and $q$.
$\endgroup$
3
  • $\begingroup$ I understood my ignorance. And I need clarification regarding: 1) in general, if one require all values of exponent 'a' to have inverse in that case group order (q) should be prime number and q < p and 'a' should be in the range > 1 and < q. Is it right? $\endgroup$
    – user26489
    Sep 2, 2015 at 15:29
  • $\begingroup$ 2) In such cases, what should be the group parameters? $\endgroup$
    – user26489
    Sep 2, 2015 at 15:53
  • $\begingroup$ @user26489, "yes" to your first post. Concerning your second comment: If Inverses are required one usually constructs $p=rq+1$ with $p,q\in \mathbb P$ with $r=2$ being a somewhat common choice (for ElGamal / DH). Then you choose a generator that generates the subgroup of order $q$. For example consider $q=5$and $p=11$, as generator $g$ you'd then choose $g^r\bmod q$ meaning $g=4$. As $4$ has indeed order $5$ means you can use this group. $\endgroup$
    – SEJPM
    Sep 2, 2015 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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