2

One thing which I am wondering for a long time and to which I did not find an answer after doing a web search and hope to find an answer here.

When we construct the elliptic curve over a prime field why do we actually select a cyclic subgroup instead of taking the entire group of the elliptic curve?

On a side note the thing that confuses me most about this choice: We know that the cyclic subgroup of prime order p is isomorphic to Z/pZ and finding the isomorphism would mean solving the discrete log.

Switching to a cyclic group seems actually rather like making the problem easier in comparison to staying with the full elliptic curve.

Improve this question
2
  • 1
    You may get better answers on Crypto.SE.
    – Nate Eldredge
    Commented Feb 22, 2019 at 19:32
  • ah that is a good idea. I will repost it there if no answer comes in here (:
    – Rene Pickhardt
    Commented Feb 22, 2019 at 19:50

1 Answer 1

Reset to default
3

The security of the discrete logarithm problem in a group is only as hard as that of the largest prime subgroup.

Because of this, there is no security gain from working in the larger group. However; it's worse. If you're working in the larger group you must make sure to not accidentally ending up in a (much smaller) subgroup when multiplying.

Improve this answer
5
  • first part of your answer I understand and makes sense. For the second part I have an add on question: When choosing a random element in the large group is there an obvious way to know if it lies in the largest subgroup or a smaller one? (Obviously I could use this element as a generator and start to compute powers to see the order of the subgroup it generates. But I guess that would only work fast in small groups which are the insecure ones? Or is that exactly the reason? )
    – Rene Pickhardt
    Commented Feb 22, 2019 at 20:07
  • 1
    In a finite group, every subgroup has a size that divides the suoergroup's size. So it suffices to try multiplying your group element with every (n/p), where n is the supergroup's size, and p is every prime divisor of n, and checking you don't end up with 0 (the point at infinity).
    – Pieter Wuille
    Commented Feb 22, 2019 at 20:12
  • would still need to know the prime factors of n but yeah I see why it makes sense to just take a large (or the largest) cyclic subgroup. thanks a lot!
    – Rene Pickhardt
    Commented Feb 22, 2019 at 22:17
  • 1
    Finding the prime factors of a 256-bit number is trivial.
    – Pieter Wuille
    Commented Feb 22, 2019 at 22:33
  • Oh, a small note: in elliptic curves, the largest prime subgroup is chosen to work with (which is always cyclic). However, there exist cyclic groups whose size is not a prime. In fact, a large portion of EC groups are cyclic, even the ones who are not prime.
    – Pieter Wuille
    Commented Feb 23, 2019 at 12:37

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.