Help with elliptic curve experiments in SageMath

Question

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.

Answer 1

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.

answer to comments.

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.