The Mighty Base Point (G) in Elliptic Curve Cryptography — And What’s An Order?
Your online security is highly dependent on a simple point on a curve — the base point, G. Every time you make a connection to the Web, you and the server are using the magical point to create a secret key which only you and server know. This is the basic mechanics of the Elliptic Curve Diffie Hellman method (ECDH), and its usage of the base point (G).
You might think that the Diffie-Hellman method is cool, and that RSA has a neat backdoor method, but it is when you discover elliptic curve cryptography that you really see the beauty of cryptography. Much of our original public key and key exchange methods were based on the discrete logarithm method of:
Y=g^x (mod p)
and where we have a base of g and a prime number of p. The value of g needs to be selected carefully so that it maximises the number of possible mapping of x to Y, and where every one of these has a mapping back. If you are interested, when we pick the right value of g and p, the total number of mappings from x to Y will be p-1. This value is known as the order of the mapping. So that:
Y = 7^x (mod 997)
will have an order of 996 (as 7 is a safe generator for 997 [here]). But what about elliptic curves? Well, they have a base point G on the curve, and then we create 2.G, 3.G and so on. For our private key, we can have a scale of priv, and then the public key will be priv.G (and which is basically add G for priv number of times). So does it matter which base point we use? So, just like in discrete logs, the answer is YES!.
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 also 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 curveWe 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. We can check this with Sage:
a = 2
b = 3
p = 97
E = EllipticCurve(GF(p), [0,0,0,a,b])
print(E)
print(E.abelian_group())
card = E.cardinality()
print("cardinality =",card)
factor(card)
G = E(3,91)
print("Generator order q=", G.order())This gives:
Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 97
Additive abelian group isomorphic to Z/50 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 97
cardinality = 100
Generator order q= 5Now 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 curveAnd 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.
We can again compute with Sage:
a = 2
b = 3
p = 97
E = EllipticCurve(GF(p), [0,0,0,a,b])
print(E)
print(E.abelian_group())
card = E.cardinality()
print("cardinality =",card)
factor(card)
G = E(1,54)
print("Generator order q=", G.order())and which gives:
Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 97
Additive abelian group isomorphic to Z/50 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 97
cardinality = 100
Generator order q= 50One thing should be noticed, in that we have two possible x points for every reachable x co-ordinate.
Here is some code [here]:
# https://asecuritysite.com/encryption/ecc_points_mult
import sys
import libnum
a=0
b=7
p=37 # prime number
n=10 # number of points to show
x=3 # starting point
# y^2 = x^3 + ax + b (mod p)
print("a=",a)
print("b=",b)
print("p=",p)
print("n=",n)
print("x-point=",x)
if (n>20): n=20
z=(x**3 + a*x +b) % p
if (libnum.has_sqrtmod(z,{p:1} )):
y=next(libnum.sqrtmod(z,{p:1}))
print("P\t(%d,%d)" % (x,y), end=' ')
if ((y**2 % p) == ((x**3+a*x+b) %p)): print(" \tPoint is on curve")
else:
print(" \tPoint is not on curve")
sys.exit()
s=((3*x**2)+a) * libnum.invmod(2*y,p)
x1=(s**2-2*x) % p
y1=((s*(x-x1))-y) % p
x3=x1
y3=y1
x2=0
y2=0
counter=1
for i in range(2, n+1):
counter=counter+1
if (counter>n): sys.exit()
print("%dP\t(%d,%d)" % (counter,x1,y1), end=' ')
if ((y1**2 % p) == ((x1**3+a*x1+b) %p)): print(" \tPoint is on curve")
rtn=libnum.invmod(x1-x,p)
if (rtn==0):
print("%dP=0" % (counter+1))
counter=counter+2
s=((3*x**2)+a) * libnum.invmod(2*y,p)
x1=(s**2-2*x) % p
y1=((s*(x-x1))-y) % p
print("%dP\t(%d,%d)" % (counter,x,y), end=' ')
if ((y**2 % p) == ((x**3+a*x+b) %p)): print(" \tPoint is on curve")
else:
s=(y1-y)* rtn
x2=(s**2-x1-x) % p
y2=((s*(x1-x2)-y1)) % p
x1=x2
y1=y2So, 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 (y²=x³+7 mod p), we have a base point and prime number of:
x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FIf we try in Sage:
a = 0
b = 7
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
E = EllipticCurve(GF(p), [0,0,0,a,b])
print(E)
print(E.abelian_group())
card = E.cardinality()
print("cardinality =",card)
factor(card)
G = E(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
print("Generator order q=", G.order())and the run gives us:
Elliptic Curve defined by y² = x³ + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
Additive abelian group isomorphic to Z/115792089237316195423570985008687907852837564279074904382605163141518161494337 embedded in Abelian group of points on Elliptic Curve defined by y² = x³ + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
cardinality = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Generator order q= 115792089237316195423570985008687907852837564279074904382605163141518161494337we can convert this to hex in Python with:
hex(115792089237316195423570985008687907852837564279074904382605163141518161494337)
'0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'The value of N will thus give us our core security levels, and will define the number of possible values before we cycle.
