Picking a Base Point in ECC

Picking a Base Point in ECC

In ECC, we have an equation of y²=x³+ax+b (mod p). This gives us points on an elliptic curve. For a=2, b=3 and p=97, we get [here]:

(1,54) (1,43) (3,91) (3,6) (4,47) (4,50) (10,76) (10,21) (11,17) (11,80) (12,94) (12,3) (17,87) (17,10) (20,34) (20,63) (21,73) (21,24) (22,92) (22,5) (23,73) (23,24) (24,95) (24,2) (25,35) (25,62) (27,7) (27,90) (28,34) (28,63) (29,54) (29,43) (32,7) (32,90) (37,22) (37,75) (38,7) (38,90) (39,91) (39,6) (44,77) (44,20) (46,72) (46,25) (47,79) (47,18) (49,34) (49,63) (50,19) (50,78) (52,68) (52,29) (53,73) (53,24) (54,85) (54,12) (55,91) (55,6) (56,89) (56,8) (59,65) (59,32) (65,65) (65,32) (67,54) (67,43) (70,65) (70,32) (73,83) (73,14) (74,77) (74,20) (76,77) (76,20) (80,87) (80,10) (83,74) (83,23) (84,37) (84,60) (85,26) (85,71) (86,69) (86,28) (87,27) (87,70) (88,41) (88,56) (91,39) (91,58) (92,81) (92,16) (95,66) (95,31) (97,87) (97,10)

You can check with (1,54), as 54² (mod 97) is 6, and 1³+2 x 1 + 3 (mod 97) is 6. For (3,91), we have 91² (mod 97) and which is 36, and 3³ + 2 x 3 + 3 (mod 97) is 36. There is no solution for x=2, and x=5.

A basic plot is [here]:

For public key encryption we must create a base point (G), and then add it n times (to get nG). The value of nG will be our public key, and the value of n will be our private key. But how do we choose a base point? Let’s try (3,91) [here]:

a= 2
b= 3
p= 97
n= 18
x-point= 3
P (3,91) Point is on curve
2P (80,87) Point is on curve
3P (80,10) Point is on curve
4P (3,6) Point is on curve
5P=0
6P (3,91) Point is on curve
7P (80,87) Point is on curve
8P (80,10) Point is on curve
9P (3,6) Point is on curve
10P=0
11P (3,91) Point is on curve
12P (80,87) Point is on curve
13P (80,10) Point is on curve
14P (3,6) Point is on curve
15P=0
16P (3,91) Point is on curve
17P (80,87) Point is on curve
18P (80,10) Point is on curve

We can see that this is a bad base point, as it will cycle. We define the order of this point (N) as N=5. We define this as the subgroup generated by P has 5 points. Now let’s try a base point of (1,54) [here]:

a= 2
b= 3
p= 97
n= 18
x-point= 1
P (1,54) Point is on curve
2P (92,81) Point is on curve
3P (0,87) Point is on curve
4P (21,24) Point is on curve
5P (53,24) Point is on curve
6P (65,65) Point is on curve
7P (85,71) Point is on curve
8P (46,72) Point is on curve
9P (23,73) Point is on curve
10P (3,6) Point is on curve
11P (87,70) Point is on curve
12P (52,29) Point is on curve
13P (47,18) Point is on curve
14P (74,20) Point is on curve
15P (88,41) Point is on curve
16P (32,90) Point is on curve
17P (17,87) Point is on curve
18P (95,31) Point is on curve

And we can see that (1,54) makes a much better base point, as it does not cycle for the range of n values that we have chosen. In fact, in this case, subgroup generated by P has 50 points.

Here is some code:

So, in real-life, when we select a base point, we make sure that it has a high order value, so that it does not cycle. For SEPC256k1, we have a base point and prime number of:

x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
    y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

The order is:

N = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

The value of N will thus give us our core security levels, and will define the number of possible values before we cycle.