4

As I understand things so far, the ECDSA scheme used by Bitcoin uses a group G generated by a point on the elliptic curve y^2 = x^2 + 7.

Now G is a cyclic group of finite order n and is, hence, isomorphic to the additive group Z/nZ.

My question is: why not work within Z/nZ directly then? I am assuming there are certain security benefits of using G but I am lacking the general overview to understand why.

Improve this question

1 Answer 1

Reset to default
2

(Disclaimer: this is not my field.)

Let g be the chosen generator and n its (prime) order. In the ECDSA algorithm, these are publicly known. It is true that g generates a cyclic (abelian) group isomorphic to Z/nZ.

Now a private key consists of an integer k, and the corresponding public key is the group element h = kg. (I use additive notation since we are in an abelian group, so kg = g+g+...+g (k times)). If we were actually working in Z/nZ, it would be trivial to recover k from h: just divide h by g (mod n) using the Euclidean algorithm. Then we would have no security at all.

The point, as I understand it, is that in the elliptic curve group, there is no known efficient way to "divide". And while there certainly exist isomorphisms from <g> to Z/nZ (map g to any element of Z/nZ you like), the inverse of such an isomorphism is not trivial to compute.

Improve this answer
5
  • Interesting. A follow up question now would be why is this isomorphism hard to find? I.e is there a provable reason or just social consensus that people were not able to find it?
    – Jernej
    Commented May 26, 2019 at 15:06
  • 2
    Now you're beyond the limits of my knowledge. You might find more experts at crypto.stackexchange.com.
    – Nate Eldredge
    Commented May 26, 2019 at 15:08
  • 1
    @Jernej The reason is simply that people have tried and failed to find an algorithm for the discrete logarithm (given group elements A and B, find x such that xA=B). This is essentially true for all cryptography: people find a hard problem to base things on, and hope that problem gets attention from people trying to break it.
    – Pieter Wuille
    Commented May 26, 2019 at 17:17
  • @PieterWuille So essentially saying that finding the said group isomorphism is equivalent to the discrete log problem?
    – Jernej
    Commented May 26, 2019 at 18:50
  • 3
    Yes, the ismorphism from G to Z/nZ is exactly f(h) = DL(h wrt g).
    – Pieter Wuille
    Commented May 26, 2019 at 18:51

Your Answer

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

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