Set Subgroup Order to Higher Value

Python Tutorials - Herong's Tutorial Examples

∟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)