**EC Cryptography Tutorials - Herong's Tutorial Examples** - v1.03, by 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.

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)