Set Subgroup Order to Higher Value

This section provides a tutorial example on how to set the subgroup order a value greater than the order of the entire group, like 2 times of the modulo, to ensure correct result of scalar multiplications.

If you want to perform the scalar multiplication using the "*" operator with tinyec Python library, you must update the subgroup order, n, to a value greater than the order of the entire group, like 2 times of the modulo. This is a safe value based on the Hasse's Theorem.

For example, we can find all points in the subgroup of a given point using a loop of scalar multiplications:

>>> import tinyec.ec as ec

>>> s = ec.SubGroup(p=97,g=(0,0),n=1,h=1)
>>> c = ec.Curve(a=2,b=3,field=s,name='p97a2b3')

>>> s.n = 2*97
>>> print(s)
Subgroup => generator (0, 0), order: 194, cofactor: 1 on Field => prime 97

>>> p = ec.Point(curve=c,x=3,y=6)
>>> print(p)
(3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)

>>> z = ec.Inf(c)   # represents the infinite point on the curve
>>> r = p
>>> for i in range(0,97):
...     i += 1
...     r = i * p   # scalar multiplication operation
...     print(r)
...     if (r == z):
...        break
... ^Z

(3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)
(80, 10) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)
(80, 87) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)
(3, 91) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)
Inf on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)

It works!

But if you set the subgroup order, n, to lower number like 3, you will get incorrect result:

   i * p = (i mod n) * P

Here is an example:

>>> s.n = 3
>>> print(s)
Subgroup => generator (0, 0), order: 3, cofactor: 1 on Field => prime 97

>>> p = ec.Point(curve=c,x=3,y=6)

>>> print(p)
(3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)

>>> z = ec.Inf(c)   # represents the infinite point on the curve
>>> r = p
>>> for i in range(0,97):
...     i += 1
...     r = i * p   # scalar multiplication operation
...     print(r)
...     if (r == z):
...        break
... ^Z

(3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)
(80, 10) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)
Inf on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)

As you can see, 3*p returns "Inf", which is incorrect. This is because of the reduction step in tinyec code: 3*p = (3%n)*p = (3%3)*p = 0*p.

So setting the subgroup order, n, to a higher value will avoid this problem.

Note that if you are using other methods on the ec.SubGroup object, you must:

Last update: 2019.

Table of Contents

 About This Book

 Geometric Introduction to Elliptic Curves

 Algebraic Introduction to Elliptic Curves

 Abelian Group and Elliptic Curves

 Discrete Logarithm Problem (DLP)

 Finite Fields

 Generators and Cyclic Subgroups

 Reduced Elliptic Curve Groups

 Elliptic Curve Subgroups

tinyec - Python Library for ECC

 What Is tinyec

 Download and Install tinyec

 Build New Curves with tinyec

 Perform Point Addition with tinyec

 Find Subgroup with Point Addition

Set Subgroup Order to Higher Value

 EC (Elliptic Curve) Key Pair

 ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

 ECDSA (Elliptic Curve Digital Signature Algorithm)

 ECES (Elliptic Curve Encryption Scheme)

 Terminology

 References

 Full Version in PDF/EPUB