5
$\begingroup$

Let $E$ be an elliptic curve defined over a finite field $F_q$ with prime order $n$ and $P,Q \in E$ and $k$ be private key such that $kP=Q$. Since $n$ is prime, $E$ is isomorphic to $Z_n$. Suppose $\psi$ be a map that $$\psi:E \to Z_n$$

Also, let $a,b\in Z_n$ such that $\psi(P)=a,\psi(Q)=b$. Then we have:

$$k=ba^{-1}$$

All recommended NIST elliptic curves(P-192,...,P-521,K-163,...) have prime orders.

Also When $\#E(F_p)=p$ we have polynomial time for computing such map. This is well known attack that is called anomalous curve attack.

What is the reason for confidence to them? Are computations speed enough?

Improve this question
$\endgroup$
4
  • $\begingroup$ Sorry, here's my fixed comment: While they are isomorphic the addition laws don't carry over. E.g. you could map $\psi:E \rightarrow \mathbb Z_n:x\cdot P\mapsto x$, but this wouldn't help you in finding the discrete logarithm. I think the relation you need would be birationally equivalent. And there's no such (efficiently calculatable) mapping (neither for birational equivalence nor for isomorphisms) known IIRC. And if there would be such a mapping, you could use GNFS against ECC completely destroying ECC as we know it. $\endgroup$
    – SEJPM
    Apr 27, 2016 at 21:15
  • $\begingroup$ @SEJPM, Your map $Q \mapsto k$, so we can break discrete logarithm. $\endgroup$
    – Meysam Ghahramani
    Apr 27, 2016 at 21:18
  • $\begingroup$ This is a theoretically valid mapping for which we just don't know how to calculate it. The thing is, we don't know any bijective mapping which is computable in polynomial time between $\mathbb Z_n$ and $E$ $\endgroup$
    – SEJPM
    Apr 27, 2016 at 21:23
  • $\begingroup$ @SEJPM Smells like an answer to me, if you combine the two comments. $\endgroup$
    – Maarten Bodewes ♦
    Apr 27, 2016 at 21:58

1 Answer 1

Reset to default
6
$\begingroup$

Yes, the attack you sketched out would work - in theory.

In practice, it's an efficient (computable in polynomial time) mapping $\psi:E\rightarrow\mathbb Z_n$ we're lacking. As for the unefficient mappings, $\psi:x\cdot P\mapsto x$ would be perfectly fine theoretically, but we don't know how to calculate it (it's the elliptic curve discrete logarithm problem, aka ECDLP).

Furthermore you might say: "well, we can construct an isomorphism in theory, so why don't we just map it somehow and apply the GNFS on $\mathbb Z_n$?" The problem is again, that we don't know an efficient mapping and even if we would, we would need one (for this attack) that preserves birational equivalence to transfer addition laws from one group to the other and if such a mapping would exist, people probably would have found it in ECC's 25 year(+) history.

Bottom line: The DLP isn't hard because of the elements you want to find, it is hard because of the element's representation.

Improve this answer
$\endgroup$

Your Answer

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

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