2
$\begingroup$

Given an encryption system where $c\equiv m^x \pmod p$, $p$ is a known prime,
1. Is it possible to recover $x$ with a known plaintext attack? Given $(p,\text{factorization of }\varphi(p),m,c)$
2. Is it possible to recover $x$ with a chosen plaintext attack? (Somehow with the chinese remainder theorem on the factorization of $\varphi(p)$ comes to mind)

$\endgroup$
  • $\begingroup$ Yes fgrieu are right. $\endgroup$ – Meysam Ghahramani Jan 10 '16 at 15:04
  • 5
    $\begingroup$ Hint: that's an (imprecise) statement of the Discrete Logarithm problem. Depending on parameters (including the domain for $x$, $p$, its size, the smoothness of $p-1$, the choice of $m$), that's hard, or feasible. $\endgroup$ – fgrieu Jan 10 '16 at 15:05
  • $\begingroup$ Hint: you want to consider the Pohlig-Hellman algorithm. $\endgroup$ – fgrieu Jan 10 '16 at 16:24
  • $\begingroup$ Note that $\varphi(p)$ very well can be $\varphi(p)=2q+1, q\in\mathbb P$ rendering this problem really hard. $\endgroup$ – SEJPM Jan 11 '16 at 20:32

Your Answer

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

Browse other questions tagged or ask your own question.