2
$\begingroup$

I have ElGamal signature scheme implemented in finite field $\mathbb{F}_p$. The thing is that I need to apply Pollard's Rho Method on elliptic curve $E(\mathbb{F}_p)$ to this scheme, solve discrete logarithm problem and find private key $x$. In ElGamal scheme I have $a^x\equiv b\ (mod\ p)$ where $a,\ b\in \mathbb{F}_p$ and in Pollard's Rho Method I have $Q=dP$ where $P,Q\in E(\mathbb{F}_p)$.
So how can I get $P,\ Q$ from $a,\ b$ and, after I get $d$, how can I get $x$ from it?
Is it even possible or am I totally wrong?

$\endgroup$
3
$\begingroup$

In the question you said that $a^x\equiv b\ (mod\ p)$ and $P,Q\in E(\mathbb{F}_p)$. In general case, the number of elliptic curve points $\#E(\mathbb{F}_p)$ is not equal to $p$. So these two groups are not isomorphic and your question is wrong.

If $\#E(\mathbb{F}_p)=p$ the curve is called anomalous and we can find the map $\psi : E(\mathbb{F}_p) \to \mathbb{Z}_p$ in polynomial time. In this state, $a=\psi(P),b=\psi(Q)$ and $x=d$.

The main idea behind Pollard’s rho algorithm is to find distinct pairs $(c' , d' )$ and $(c'' , d'' )$ of integers modulo $n$ such that $c' P + d' Q = c'' P + d'' Q$. So $(c' − c'' ) = (d'' − d' )d \pmod n$. Hence $d$ can be obtained by computing $$d = (c' − c'' )(d'' − d' )^{ −1} \pmod n.$$

For more details you can see page $156,168$ of "Guide to elliptic curve cryptography", Hankerson, ....

$\endgroup$
  • $\begingroup$ Thank you for your reply! That makes sense. I'm gonna ask my teacher about that. I guess I can count your reply as an answer. $\endgroup$ – Gleb Ignatieff Apr 30 '17 at 16:19
0
$\begingroup$

Pollard's Rho Method is a general method for finding discrete logarithms in a finite group. It doesn't use any of the properties of Elliptic Curves.

So just use the same algorithm, over the multiplicative group of $\mathbb F_p$ instead of $E(\mathbb F_p)$.

$\endgroup$
  • $\begingroup$ Thanks for the quick reply! Unfortunately, according to the task, I have to use Pollard's Rho Method on elliptic curves. $\endgroup$ – Gleb Ignatieff Apr 30 '17 at 11:42
  • $\begingroup$ @GlebIgnatieff: If you say so. But it makes no sense. $\endgroup$ – TonyK Apr 30 '17 at 14:27
  • $\begingroup$ Well, I guess there is some misunderstanding between me and my teacher... $\endgroup$ – Gleb Ignatieff Apr 30 '17 at 16:22

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.