0
$\begingroup$

In the case of an Elliptic curve over a GF(p) which has order n and multiplicative group of n-1 elements, does multiplication of an element of a subgroup of order q where q is a divisor of n-1 with a scalar s obey the cyclic property, or plainly put does an element e member of subgroup q when multiplied with s stay in the subgroup?

Ok an update and the clarification, my colleague has put forth the claim that given the Nist256r1 curve, which has a prime number of elements (points), the number of valid integers/scalars that equals order n-1 can be factored into smaller subgroups, and if an element of that subgroup was used as the private key, part of a DH key, any subsequent multiplication of the resulting EC point would still remain in the subgroup bounded by the choice of private key. To me this sounds like mixing different groups but as I explained not a maths guy. So to restate the question: Is what he is claiming reasonable since that would constitute changing of the order of the calculated EC point.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ If an ECC has order $n$ then the order of the subgroups must divide $n$. Also, the standard terminology is point addition. Your question, as of currently, is not clear. $\endgroup$
    – kelalaka
    Commented Jan 31 at 20:05
  • 1
    $\begingroup$ If you are asking, let $n$ be the order of the ECC group where $q$ is a divisor of the order, and let $e \in <P>$ where $P$ is a subgroup with order $q$ ( existance is not guaranteed) the adding $e$ itself $k$ times $[k]e \in <P>$ $\endgroup$
    – kelalaka
    Commented Jan 31 at 20:10
  • 1
    $\begingroup$ "an Elliptic curve over a GF(p) which has order n and multiplicative grouo on n-1 elements"; I have problems parsing this. When we talk about $\mathbb{Z}/p$, there are addition and multiplication operations defined, and we can define a group ($\mathbb{Z}_p^*$) which has (if $p$ is prime) $p-1$ elements (this happens because there is one element of $\mathbb{Z}/p$, namely 0, which is not a member of $\mathbb{Z}_p^*$). Nothing similar happens with elliptic curves; there is only one operation (elliptic curve addition), and so we don't use up with a group with $n-1$ elements. $\endgroup$
    – poncho
    Commented Jan 31 at 20:11
  • 1
    $\begingroup$ On the other hand, to answer the question in the title "does multiplying a subgroup element (by an integer) make it leave the subgrouop", no it doesn't. Subgroups are closed; that is, if $A$, and $B$ are members of the subgroup, so is $A+B$. Hence, $nA = A + A + ... + A$ is also in the subgroup. $\endgroup$
    – poncho
    Commented Jan 31 at 20:22
  • $\begingroup$ Thank you for the answers kelalaka and poncho, I will try to clarify the question. I was refering to the claim in the answer to this question bitcoin.stackexchange.com/questions/114570/… $\endgroup$
    – immigrantswede
    Commented Jan 31 at 20:38

1 Answer 1

Reset to default
1
$\begingroup$

Ok an update and the clarification, my colleague has put forth the claim that given the Nist256r1 curve, which has a prime number of elements (points), the number of valid integers/scalars that equals order n-1 can be factored into smaller subgroups

Your colleague is wrong. As mentioned in the comments, the size of any subgroup is always a divisor of the size of the full group. Nist256r1 (Secp256r1) has a prime number of points, and since the only divisors of a prime is the prime itself and one, the only subgroups that exist are the full curve (with $n$ points) and the subgroup that consists only of the point-at-infinity (with 1 point). There are no other possibilities.

I believe that your colleague is getting confused between $\mathbb{Z}_p^*$, which does have $p-1$ elements (assuming $p$ is prime), and so always (for $p>3$) has proper subgroups, and elliptic curves, which has $n$ elements (for some $n$ close to $p$ for prime curves, but need not be $p-1$). To oversimplify, the elliptic curve replaces the $p-1$ by $n$, and hence you don't need to subtract one again.

Is what he is claiming reasonable since that would constitute changing of the order of the calculated EC point.

No, it is not reasonable; for the Secp256r1 curve, all points (except for the point at infinity) have order $n$. And, if $P$ is not the point at infinity, then $aP$ can be any point on the curve (with the appropriate value for $a$).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you Poncho this ahould settle the discussion $\endgroup$
    – immigrantswede
    Commented Feb 1 at 15:29
  • $\begingroup$ The linked Q is about bitcoin which uses secp256k1 not secp256r1=(X9)prime256v1=(NIST)P-256. But all SECG-and-X9 $F_p$ curves have prime order so the reasoning still applies. $\endgroup$
    – dave_thompson_085
    Commented Feb 2 at 1:35

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.