**EC Cryptography Tutorials - Herong's Tutorial Examples** - Version 1.00, by Dr. Herong Yang

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:

- Make sure the generator (or base point), g, is on the curve.
- n is the true value of order of the subgroup generated from g.
- h is the true value of cofactor of the subgroup generated from g.

Last update: 2019.

Table of Contents

Geometric Introduction to Elliptic Curves

Algebraic Introduction to Elliptic Curves

Abelian Group and Elliptic Curves

Discrete Logarithm Problem (DLP)

Generators and Cyclic Subgroups

►tinyec - Python Library for ECC

Perform Point Addition with tinyec

Find Subgroup with Point Addition

►Set Subgroup Order to Higher Value

ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

ECDSA (Elliptic Curve Digital Signature Algorithm)