Understanding Elliptic Curve Cryptography

It’s getting tough but you can not avoid this modern cryptography technology called elliptic curve cryptography (ECC).

The basic expression looks as simple as below.

y²=x³+ax+b

When plotted, they look like below for different a and b values.
Thanks, Wolfram Alpha!

Then, we define additions, subtractions and multiplications of points on the curve. There are many good resources on this so I won’t explain it by myself.

When using the expression for cryptography, real numbers are not suitable to handle because weird things happen with floating point numbers.
Also, we introduce finite field with modulo. Thus we are limiting the numbers to integers with a certain range.
For modulo operations, additions, subtractions and multiplications are preserved. For example, (a + b) mod p = (a mod p) + (b mod p).
For divisions, we need to introduce an inverse of modulo.
When x = (1/a) mod p, then x is defined as a number which satisfies (a mod p) * (x mod p) = 1. The x can be found using Fermat’s little theorem which gives x = a^p-2 mod p.

When a = 0 and b = 7 (the third plot in the above) and p = 23, I scanned all the points which are on the elliptic curve. This no more looks like “a curve”.

As I said, operations on finite field preserve the equality relationship. Thus, when addition and multiplication is applied on a point on finite field, the new point is still on the curve. I just wanted to make sure this so I tested it with a Python script.

The next thing I did was to test my Python implementation with the real-world number where p is reasonably big for cryptographic purpose.
First I created a private and public key using the elliptic curve defined in secp256k1 which is used for Bitcoin, where a = 0, b = 7. (The same one used in the above.)
Key generation is done using openssl command as below.

openssl ecparam -genkey -name secp256k1 -out ec_key.pem -param_enc explicit

The PEM file looks like this.

-----BEGIN EC PARAMETERS-----
MIHgAgEBMCwGByqGSM49AQECIQD////////////////////////////////////+
///8LzBEBCAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQgAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAcEQQR5vmZ++dy7rFWgYpXOhwsHApv8
2y3OKNlZ8oFbFvgXmEg62ncmo8RlXaT7/A4RCKj9F7RIpoVUGZxH0I/7ENS4AiEA
/////////////////////rqu3OavSKA7v9JejNA2QUECAQE=
-----END EC PARAMETERS-----
-----BEGIN EC PRIVATE KEY-----
MIIBUQIBAQQgotDE7fMaK6IxQL6oBdDgsrRVeWVKAweTkgMEoa38V+2ggeMwgeAC
AQEwLAYHKoZIzj0BAQIhAP////////////////////////////////////7///wv
MEQEIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABCAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAABwRBBHm+Zn753LusVaBilc6HCwcCm/zbLc4o
2VnygVsW+BeYSDradyajxGVdpPv8DhEIqP0XtEimhVQZnEfQj/sQ1LgCIQD/////
///////////////+uq7c5q9IoDu/0l6M0DZBQQIBAaFEA0IABB0ykweOtX2G9WjA
KK1msjy1ecNE1GYbTlnVbNu9jT7bDSMQeh+AO60sSg4e1zlHsqsYwFn4iy4ERvEQ
0T4W2pE=
-----END EC PRIVATE KEY-----

To see exactly what kind parameters and values we have, we can convert it with command,

openssl ec -in ec_key.pem -noout -text  

This gives

read EC key
Private-Key: (256 bit)
priv:
    a2:d0:c4:ed:f3:1a:2b:a2:31:40:be:a8:05:d0:e0:
    b2:b4:55:79:65:4a:03:07:93:92:03:04:a1:ad:fc:
    57:ed
pub:
    04:1d:32:93:07:8e:b5:7d:86:f5:68:c0:28:ad:66:
    b2:3c:b5:79:c3:44:d4:66:1b:4e:59:d5:6c:db:bd:
    8d:3e:db:0d:23:10:7a:1f:80:3b:ad:2c:4a:0e:1e:
    d7:39:47:b2:ab:18:c0:59:f8:8b:2e:04:46:f1:10:
    d1:3e:16:da:91
Field Type: prime-field
Prime:
    00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:ff:
    ff:fc:2f
A:    0
B:    7 (0x7)
Generator (uncompressed):
    04:79:be:66:7e:f9:dc:bb:ac:55:a0:62:95:ce:87:
    0b:07:02:9b:fc:db:2d:ce:28:d9:59:f2:81:5b:16:
    f8:17:98:48:3a:da:77:26:a3:c4:65:5d:a4:fb:fc:
    0e:11:08:a8:fd:17:b4:48:a6:85:54:19:9c:47:d0:
    8f:fb:10:d4:b8
Order: 
    00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:fe:ba:ae:dc:e6:af:48:a0:3b:bf:d2:5e:8c:d0:
    36:41:41
Cofactor:  1 (0x1)

All the necessary parameters are here. Generator and pub (public key) each represents a point on the curve. They have x and y coordinates concatenated with a prefix (0x04). Generator is a base point on the curve which is specific to the curve (in this case secp256k1) and Order is how many points are on the curve.

Prime is a prime number used in modulo operation for the finite field, mentioned as p in the above plot examples.

The private key is generated just as a random number smaller than Order and the public key is the point generated by

Public_key = Generator * Private_key

I confirmed this with my code. The multiplication here is done as defined for elliptic curves on finite field, not a simple vector multiplication.

The security of the elliptic curve relies on the fact that it is practically impossible to guess the private key out of the public key and Generator.

All experiments in this article can be reviewed in my python code on Google Colab.
Also, I am learning ECC and other cryptography with books “暗号と認証 しくみと理論がしっかりわかる教科書” and “Software Design magazine, issue of March, 2022“. These materials are very helpful and some of my python code is from them.