4
$\begingroup$

An encryption scheme is based on the DLP: $c = a^x mod ~b$, where $x$ is hard to find. How hard is it to find $a$, given all the other values, $c$, $x$ and $b$?

Would this make the problem easy to solve?

$c^{1/x} = (a^x)^{1/x} mod ~b$

An example would be great to better understand.

$\endgroup$
  • $\begingroup$ $c^{x^{-1}\pmod {\phi(b)}}=a \pmod b$ $\endgroup$ – Meysam Ghahramani Mar 17 '17 at 18:07
3
$\begingroup$

If you know the factorization of $b$, it's easy. One way would be to compute $x^{-1}$, the multiplicative inverse modulo $\phi(b)$, and then compute $c^{x^{-1}} \bmod b$

If you don't know the factorization of $b$, it's hard; in fact, it's essentially the RSA problem.

$\endgroup$
  • 1
    $\begingroup$ why would i need to compute the multiplicative inverse modulo if it wont be used in the computation $c^{x^{-1}} mod ~b$ ? $\endgroup$ – user123 Mar 17 '17 at 18:12
  • $\begingroup$ @user123: $c^{x^{-1}} \bmod b$ is meant as a sorthand for$$c^{(x^{-1}\bmod\phi(b)\;)} \bmod b$$ and thus makes use of $x^{-1}\bmod\phi(b)$, the multiplicative inverse of $x$ modulo $\phi(b)$. $\endgroup$ – fgrieu Mar 17 '17 at 18:27

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.