0
$\begingroup$

Given a curve with points over GF(p), a subgroup of prime order q and a co-factor h.

How do I calculate the size of q which is also the modulus?

I was thinking q = p/h

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Run Schoof's algorithm on the curve parameters to find $qh$, and divide by $h$.

The size $p$ of the coordinate field is only required, by Hasse's theorem, to be near $qh$, within a factor of a square root: $|qh - (p + 1)| \leq 2 \sqrt p$. Consequently, $p/h$ may be near $q$ but is not equal to $q$ except in anomalous curves in which ECDLP is easily solved by additive transfers as described by Smart (preprint), Araki–Satoh, and Semaev (the ‘Smart-ASS’ attack).

For example, Curve25519's coordinate field is $\operatorname{GF}(2^{255} - 19)$, and its order $2^{255} + 221938542218978828286815502327069187944 = qh$ where $q = 2^{252} + 27742317777372353535851937790883648493$ and $h = 8$.

$\endgroup$
7
  • $\begingroup$ Thanks for the answer. Could you explain why I cannot just divide by the co-factor? $\endgroup$ Apr 26, 2019 at 20:12
  • $\begingroup$ @WeCanBeFriends: divide what by the cofactor? You need to know the number of points on the curve (and while it'll be close to $p$, it won't be exactly $p$) $\endgroup$
    – poncho
    Apr 26, 2019 at 20:21
  • $\begingroup$ Oh, I was referring to do p/h . TBC I have the order of the basefield p already $\endgroup$ Apr 26, 2019 at 20:33
  • $\begingroup$ @poncho To rephrase, given a group p, how do I find the largest subgroup? $\endgroup$ Apr 26, 2019 at 20:46
  • 1
    $\begingroup$ @WeCanBeFriends: do you mean the order of an elliptic curve based on $GF(p)$; no, in general, it wouldn't (but again, it would be close). Do you mean the order of the multiplicative group $\mathbb{Z}_p^*$? No, that'd be $p-1$. Do you mean the order of the additive group $\mathbb{Z}_p^+$? Yes, that would be (however, that group isn't typically used in cryptography, as things like the 'discrete log' problem (modular division) is easy $\endgroup$
    – poncho
    Apr 26, 2019 at 21:25

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.