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$
  • $\begingroup$ $6 \times 2 = 2 \mod \phi(11)$. $\endgroup$ – Henrick Hellström Sep 2 '15 at 11:56
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$.
| improve this answer | |
$\endgroup$
  • $\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 '15 at 15:29
  • $\begingroup$ 2) In such cases, what should be the group parameters? $\endgroup$ – user26489 Sep 2 '15 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 '15 at 17:12

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.