Schneier’s Law and Creating a Random Elliptic Curve

Schneier’s Law defines:

“Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break.”

Well, in a world of AI, the most clueless amateur is perhaps AI entities, and where AI could easily evolve to use ciphers that we cannot actually decrypt. While we humans have defined standards for cryptography, especially through NIST standards, there is nothing to stop AI agents from evolving their own ciphers, and to use an almost uncrackable code.

So, let’s say that two AI entities decide to use their own elliptic curve method, and where they pick their own parameters for the curve used. Normally, we would have well-defined curves, such as for NIST P256, secp256k1 and Curve 25519, but AI entities could agree on their own parameters. The parameters used could be passed over secure channels, such as with an ECDH (Elliptic Curve Diffie Hellman) key exchange.

The security of ECC (Elliptic Curve Cryptography) is based on finding the discrete logarithm of a random elliptic curve element that relates to a publicly known point on a curve. This is defined as ECDLP (elliptic curve discrete logarithm problem). For this, we have a base point (G), and then a secret scale value (x), and compute a point on the curve of x.G. Overall, it should be computationally difficult to discover x from x.G, even though we know the point G. For a Koblitz curve, we have the form of:

y²=x³+a.x+b (mod p)

and where a and b are well-defined parameters of the curve, and p is a prime number. The Bitcoin curve, for example, uses a=0 and b=7:

y²=x³+7 (mod p)

Overall, when we have our Koblitz curve, the number of addressable points on the curve is then defined by the order (n). This value will be less than the prime number selected. In the following Sage program, we define a random prime number (p) of a given number of bits, and then select random values of a and b:

bits=32

range=2^bits
p = random_prime(range)
a = random.randrange(p)
b = random.randrange(p)

We can then build the elliptic curve with:

E = EllipticCurve(GF(p), [a,b])

We can determine possible generators with:

G = E.gens()

And then select the first possible generator and then determine the order of the curve from this:

G = E.gens()[0]
n = G.order()

Next, we can generate a random private key (in the range of the order), and compute a public key:

private_key = random.randrange(n)
public_key = private_key * G

Some code to implement this is [here]:

import random

bits=32

range=2^bits
p = random_prime(range)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])

G = E.gens()[0]
n = G.order()

private_key = random.randrange(n)
public_key = private_key * G

print (f"p = {p}. Number of bits: {bits}")
print (f"a = {a}")
print (f"b = {b}\n")
print (f"y^2 = x^3 + {a}x +{b} (mod {p})\n")
print (f"Possible G values : {E.gens()}\n")
print (f"Order (n) = {n}\n")
print (f"\nPrivate key = {private_key}")
print (f"Public key = {public_key}")

A sample run with a prime number of 32 bits is [here]:

p = 4219979983. Number of bits: 32
a = 405262603
b = 2207231206

y^2 = x^3 + 405262603x +2207231206 (mod 4219979983)
Possible G values : ((3123294287 : 747653088 : 1),)
Order (n) = 4220029990

Private key = 2019747373
Public key = (965870056 : 3091212914 : 1)

We can see we have a private key of 2019747373, and a public key of (965870056, 3091212914). A sample run for 128 bits is [here]:

p = 121498666637002641114842558285755314563. Number of bits: 128
a = 76420701999387810440999019276514157700
b = 36956449699246600086845407130860872517
y^2 = x^3 + 76420701999387810440999019276514157700x +36956449699246600086845407130860872517 (mod 121498666637002641114842558285755314563)
Possible G values : ((68171807056679976711871317428104520161 : 95136238550703181267148233371770929347 : 1),)
Order (n) = 121498666637002641108073291458754756353

Private key = 97502274403840360169137493917431899306
Public key = (32932562500312149439357959910459727109 : 77041490469973804496030991625300148601 : 1)

We can see we have a private key of 97502274403840360169137493917431899306, and a public key of (32932562500312149439357959910459727109, 77041490469973804496030991625300148601). For a 256-bit prime number [here]:

p = 58496621280496295175809120265161659403636255220457290357349395523424122180267. Number of bits: 256
a = 54605786984246342561282416504361312071202890920864572259694362358496149108584
b = 42159113432504081184152544658816054030428160421250321983020437024289211728770

y^2 = x^3 + 54605786984246342561282416504361312071202890920864572259694362358496149108584x +42159113432504081184152544658816054030428160421250321983020437024289211728770 (mod 58496621280496295175809120265161659403636255220457290357349395523424122180267)
Possible G values : ((36025350626609720797194445382481321851962837704687737424770579342839465991700 : 41537631728217554579119026060008001478340073575335313654703071963096856858978 : 1),)
Order (n) = 58496621280496295175809120265161659403360030373893037653175619851640148134307
Private key = 12050005325796870332233504154211259061467911744751211256965693633741168082818
Public key = (28530271735739756150942423784973548793043292469860734234115607921525361773472 : 53048849336375034875925183306439737771503900482331630462987691711634506370159 : 1)

We can see we have a private key of 12050005325796870332233504154211259061467911744751211256965693633741168082818, and a public key of (28530271735739756150942423784973548793043292469860734234115607921525361773472, 53048849336375034875925183306439737771503900482331630462987691711634506370159).