# Help with elliptic curve experiments in SageMath

This question may be quite basic but I'm learning about applied cryptography and abstract math isn't my strongest point.

I was just hoping for a little help to confirm a couple of things and help me figure out more about the mathematical underpinnings of elliptic curve cryptography. I believe understanding the math means understanding the technology.

I'm using curve25519 as an experimental playground in SageMath.

Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949


Assumption I made: The cyclic subgroup: Q=2^252 + 27742317777372353535851937790883648493 is generated by using the base point G, generation means adding G to itself over and over. From G+G to G+G 2^252+27742317777372353535851937790883648493 times. Is this all it means to generate a subgroup?

Findings: I noticed that G*0 and G*Q+1 both produce the point (0 : 1 : 0), is this expected?

I've also learned about the co-factor of an elliptic curve, for curve25519 I understand that for cryptographic use a point must lie in the subgroup Q defined above and as such will have a co-factor for 8.

Thus, points that lie in other subgroups of the curve 2Q, 4Q, 8Q are not valid for cryptographic use because (Assumption):

1) We don't use these subgroups as they aren't prime.

2) All private keys (scalars k) must be multiples of 8 to ensure we are inside subgroup of order Q.

So generating some random points, took a while until I got one that is generated by G, and as such has a valid order of 8:

sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
4
sage: ec.order()/ec.random_point().order()
2
sage: ec.order()/ec.random_point().order()
2
sage: ec.order()/ec.random_point().order()
2
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
1
sage: ec.order()/ec.random_point().order()
8 <-- valid order


So my two questions are:

• Am I correct so far in my learnings?

• Is there a SageMath function I can use to check if a random point belongs to the subgroup generated by G (and as such would be a usable cryptographic public key point)?

Thank you for helping me learn.

Your notation is not standard. $$G *G$$ is not an elliptic curve operation. We have additive group operation on points $$P+Q$$ and scalar multiplication defined as below;

$$[a]P = \overbrace{P+\cdots+P}^{{a\hbox{ - }times}}$$ and $$P+\mathcal{O} = \mathcal{O} + P = \mathcal{O}$$ for any point $$P$$ on the curve and $$\mathcal{O}$$ is the point at the infinity or the identity element of the group.

Assuming that the order of the subgroup generated by $$G$$ is $$q$$ than $$[0]G = \mathcal{O}$$ and $$[q]G = \mathcal{O}$$

The subgroups $$2Q$$, $$4Q$$, and $$8Q$$ are not interesting since they are not providing additional security due to The Pohlig-Helman algorithm. Also, while generating a random element, you may fall into the trap by selecting the small subgroup like your method. There are safer methods.

You can generate random elements by using a good random source like /dev/urandom

• One way by using random scalar;

1. Choose a generator point $$P$$
2. Get random integer between $$0 < k < \text{Order of the Group}$$
3. Calculate $$R = [k]P$$ by a fast scalar multiplication.
• another way is rejective sampling the $$x$$ coordinate.

1. Select random $$x$$ coordinate
2. Calculate $$y^2 = x^3 + 486662*x^2 + x$$
3. If $$y$$ is a quaratic redisude than choose $$y$$ or $$-y$$ else return step 1.

1) is it normal that G*0 and G*q produce 0:1:0?

Note $$[0]G = \mathcal{O}$$ is normal and $$[q]G = \mathcal{O}$$ if the order divides $$q$$

2) Is there a SageMath function I can use to check if a random point belongs to the subgroup generated by G?

P.order()


3) the 2^252 subgroup is formed by adding G to itself q times right?

if the $$G$$ is generator, yes.

• upvoted, thanks for the reply, to clarify: 1) is it normal that G*0 and G*q produce 0:1:0? 2) Is there a SageMath function I can use to check if a random point belongs to the subgroup generated by G? 3) the @2^252 subgroup is formed by adding G to itself q times right? Nov 21, 2019 at 19:04
• @Woodstock see the update. Nov 21, 2019 at 19:12
• thank you, so for a curve, if G.order = q then G*q == 0:1:0? Nov 21, 2019 at 19:19
• thank you, I think I'm finally starting to understand this stuff. Nov 21, 2019 at 19:22
• $[2^{252}]G$ as in the top of the answer add $G$ itself $2^{252}$-times Nov 21, 2019 at 19:47