What’s The Order in ECC?

I love using elliptic curve cryptography (ECC), but there’s one little parameter of the curve that’s not so easy to explain … the order…
Photo by Fabian Quintero on Unsplash

What’s The Order in ECC?

I love using elliptic curve cryptography (ECC), but there’s one little parameter of the curve that’s not so easy to explain … the order (n). Let me first give you a bluffers guide to ECC …

  • We have a curve y²=x³+ax+b (mod p), and where a and b define the curve and p is a prime number. An example is where a=0 and b=7, and which gives y²=x³+7 (mod p).
  • We select a base point of the curve (G) and then make all the operations in relation to this.
  • First, we generate a random number for our private key (a), and then we calculate xG (mod p), and which is the point G, added x times (with the mod p operation). The value of a is the private key, and xG (mod p) is the public key.

All fine up to now? And so we have p, a, b, and G:

EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

curve = EllipticCurve(
    'secp256k1',
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    # Subgroup cofactor.
    h=1,
)

But we have one more parameter: n. This is the order of the curve, and defines the maximum number of points on the curve. So, although we have a possible p values from the prime number, not all the points will exist. The number of actual points is then defined by n. Thus the value of x can only go from 0 to (n-1).

Now let’s illustrate where the order is used. In this case we will use secp256k1, and ECDH (Elliptic Curve Diffie Hellman). With this we select a base x co-ordinate point of G, and then Bob and Alice generate random values and determine their public keys. Alice generates a, and Bob generates b. Alice’s public key will be:

A=aG (mod p)

and Bob’s public key becomes:

B=bG (mod p)

The exchange their values and Alice multiplies by the value received from Bob by a, and Bob multiplies the value he receives from Alice by b. They should then end up with the same value, and which should be:

K=abG (mod p)

So here is a basic Python program to implement [here]:

from secp256k1 import curve,scalar_mult
import random
print("Basepoint:\t", curve.g)
aliceSecretKey  = random.randrange(1, curve.n)
alicePublicKey = scalar_mult(aliceSecretKey, curve.g)
bobSecretKey  = random.randrange(1, curve.n)
bobPublicKey = scalar_mult(bobSecretKey, curve.g)
print("Alice\'s secret key:\t", aliceSecretKey)
print("Alice\'s public key:\t", alicePublicKey)
print("Bob\'s secret key:\t", bobSecretKey)
print("Bob\'s public key:\t", bobPublicKey)
print("==========================")
sharedSecret1 = scalar_mult(bobSecretKey, alicePublicKey)
sharedSecret2 = scalar_mult(aliceSecretKey, bobPublicKey)
print("==========================")
print("Alice\'s shared key:\t", sharedSecret1)
print("Bob\'s shared key:\t", sharedSecret2)
print("\n==========================")
print("abG: \t", (sharedSecret1[0]))
res=(aliceSecretKey*bobSecretKey) % curve.n
res=scalar_mult(res, curve.g)
print("(ab)G \t", (res[0]))

In this case, the highlighted text is showing a test where we calculate (ab) and then use this as a scalar. But because we only have n points on the curve, we must perform a “(mod n)” operation of the multiplication of a and b. A sample run shows that this works [here]:

Basepoint:   (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
Alice's secret key:  4343994315440782507420089117650409135767624159733852799554305098867261718156
Alice's public key:  (78297706197955729350667779391386441808284296051751165431039294303456744675395, 53026595987980089952057873560627991776900908823460698813038262338893485972970)
Bob's secret key:    65170588075519180455552204289336723056354524029876452054263255971647918539276
Bob's public key:    (95103350695611509758480650883534725116254969214790126410271490073854292336714, 104926054008673271728343434701453979994709138304414019234704185907996583773111)
==========================
==========================
Alice's shared key:  (115660414424092852739774689410671739462086977293256206809544563743959327999239, 32139619968824126694502263965253429226345100195006162372388222594743027172750)
Bob's shared key:    (115660414424092852739774689410671739462086977293256206809544563743959327999239, 32139619968824126694502263965253429226345100195006162372388222594743027172750)

==========================
abG:     115660414424092852739774689410671739462086977293256206809544563743959327999239
(ab)G    115660414424092852739774689410671739462086977293256206809544563743959327999239

And now, let’s take a more complex example. In this case, we will implement ECDH with a long term key pair for Bob and Alice:

With this, we select a base x co-ordinate point of G, and then Bob and Alice generate random values and determine their public keys. Alice generates a long-term private key of a, and Bob generates a long term private key of b. Alice’s long public key will be:

A_pub=aG (mod p)

and Bob’s long-term public key becomes:

B_pub=bG (mod p)

Alice will store Bob’s long-term key, and Bob will store Alice’s long-term key, and they will use these to compute the shared key for each session. For a new session, Bob generates a random private key value of b and Alice generates a random private key of a. Alice will then share a public key by and multiplying Bob’s long term public key by a and x :

Ashare=axB_pub=axbG (mod p)

And Bob takes Alice’s public key and multiplies by b and y:

Bshare=byA_pub=byaG (mod p)

The exchange their values and Alice multiplies by the value received from Bob by y, and Bob multiplies the value he receives from Alice by x. They should then end up with the same value, and which should be:

Akey=yaxbG (mod p)=abxyG (mod p)

and:

Bkey=xbyaG(mod p)=abxyG(mod p)

and which are the same values. So here is a basic Python program to implement using secp256k1 [here]:

from secp256k1 import curve,scalar_mult
import random
print("Basepoint:\t", curve.g)
a  = random.randrange(1, curve.n)
a_pub = scalar_mult(a, curve.g)
b = random.randrange(1, curve.n)
b_pub = scalar_mult(b, curve.g)
x  = random.randrange(1, curve.n)
xG = scalar_mult(x, curve.g)
y  = random.randrange(1, curve.n)
yG = scalar_mult(y, curve.g)

Bob_send = scalar_mult(y, a_pub) # (y) aG
Bob_send = scalar_mult(b, Bob_send) # (yb) aG

Alice_send = scalar_mult(x, b_pub) # (x) bG
Alice_send = scalar_mult(a, Alice_send) # (xa) bG

k_a = scalar_mult(x, Bob_send) # x (yb) aG
k_b = scalar_mult(y, Alice_send) # y ( xa) bG
print("\nAlice\'s secret key (a):\t", a)
print("Alice\'s public key:\t", a_pub)
print("\nBob\'s secret key (b):\t", b)
print("Bob\'s public key:\t", b_pub)
print("==========================")
print("\nAlice\'s session secret key (a):\t", x)
print("Alice\'s  session public key:\t", Alice_send)
print("\nBob\'s  session secret key (b):\t", y)
print("Bob\'s  session public key:\t", Bob_send)
print("\n==========================")
print("Alice\'s shared key:\t", k_a)
print("Bob\'s shared key:\t", k_b)
print("\n==========================")
print("abxyG: \t", (k_a[0])) # Just the x co-ordinate for the share
res=(a*b*x*y) % curve.n
res=scalar_mult(res, curve.g)
print("(abxy)G \t", (res[0]))

We can see here, that we check that (abxy) G is the same as the two calculated shared keys, and we see that they are the same [here]:

Basepoint:	 (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

Alice's secret key (a):	 36174920093024219696392156306003690242162474822404603858328924369879994168253
Alice's public key:	 (3572052161433792509600267342175648279192831386679223652914158021842810378840, 1235342631816766697094392548458428723477445557255525298350020407132367900897)

Bob's secret key (b):	 53509219924942155473162132152965201264615451398261194516027329249696669422222
Bob's public key:	 (15951408455209101037028429025972391744911835080809580141193677976899118413256, 6918895901651896086852059768371461579836056836786554642802706405760362636912)
==========================

Alice's session secret key (a):	 19766948269856779597330086441495512536515020866159834941668545441640224511995
Alice's  session public key:	 (72881623455733425619419705518220198066934991645428615027845183524295615871810, 83079200979961930241312957420210934573778128130262102744709021398140045287701)

Bob's  session secret key (b):	 76683091699302157013559881564648733094848619480308123637466457796185861338661
Bob's  session public key:	 (105694093852805773400411449889793866681555137517498926232436098077797554053548, 85006669603370824884600453389007789822283341602358778688845638680397707853560)

==========================
Alice's shared key:	 (10748270688032665893452586036769175734536800018568665430743809582413501276795, 12838609976384858037993587302595420945433979446657814746572600295057624743669)
Bob's shared key:	 (10748270688032665893452586036769175734536800018568665430743809582413501276795, 12838609976384858037993587302595420945433979446657814746572600295057624743669)

==========================
abG: 	 10748270688032665893452586036769175734536800018568665430743809582413501276795
(abxy)G 	 10748270688032665893452586036769175734536800018568665430743809582413501276795

And, that’s it! That where the order is needed.