Inspired by webtricks'
topic about elliptic curve cryptography, I decided to write my own as well. This is intended to be a supplement to his guide. The difference between his and my topics is that this topic serves as a general introduction to ECC and not just the parts that relate to bitcoin. The goal of writing this guide is so you don't need to understand advanced mathematics to learn about elliptic curve cryptography.
As you can tell from the name, Elliptic Curve Cryptography creates keys from the equation of elliptic curves. In an ellipse,
a is the length of the x-side and
b is the length of the y-side, however elliptic curves aren't ellipses, and these variables don't represent lengths of anything; I just mentioned them to make the meaning of the variables
a and
b clearer.
a and
b both equaling 0 does not make an elliptic curve. This is the equation of an elliptic curve:
In fact, any
a and
b which make this expression zero isn't an elliptical curve either.
No combination of positive integers, or (0, 1) or (1, 0) make the above equal to zero. All this means is that they form a valid elliptical curve.
Here are a few graphs of elliptic curves I got from wikipedia. They are plotted x vs y, y being the vertical axis of course. Also different
a and
b values are listed. None of these curves have "loops" or "corners" except for the
a,
b = 0, 0 graph which has a corner, but like I said that is not an elliptic curve:
Next before I cover elliptic curve cryptography you need to know what two mathematical terms mean and I'll try to explain them in a simple way. The first term is a
field which is just a list/array/set of numbers. A finite field, also called a galois field, is a finite list of integers (it cannot be a list of decimal numbers because there are infinitely many decimal numbers between two integers). The
field of an elliptic curve is a field (list) of numbers that
a and
b are allowed to be. They might be the same number.
Selecting all the rearrangements of two numbers, which includes selecting the same number twice, and using each pair of numbers as
a and
b parameters makes a list of curves, like the diagram above. That diagram used two fields,
a in [-2, -1, 0, 1] and
b in [-1, 0, 1, 2] but in practical use, the parameters use one and the same field and the field is a sequential list of integers from 0 to a large integer.
The second term is the
characteristic of a field which is the number that is designated to have the properties of the number 0. An example is when you have a field of integer moduli (integer remainders) like [0 (a real zero), 1, 2, 0 (three), 1 (four), 2 (five), 0 (six), 1 (seven), ...] (modulus 3 in this example) then 3 and its multiples behave like the number zero. In other words a field can have numbers between 1 and some integer n (0 is excluded from the field, as it would make a degenerate equation), with n+1 being the characteristic of the field. It is quicker to refer to a field with characteristic
p as
Zp. Z is just a symbol that represents this, and not a number. The mathematical definition of characteristic involves ring addition and ring multiplication but to keep this topic simple I will not describe those here. Webtricks did a good job explaining those so read his topic if you want to know more about them.
Very important: It's only possible for a characteristic to be
zero or a prime number. A composite number modulus like 6 also has a smaller, prime modulus (3 and 2). Because modulus by 1 makes all numbers zero, and modulus by zero is undefined (and number theory only ever deals with positive integers and zero), such fields are technically characteristic 0.
ECC Theory
To start, a field must be used that is not characteristic 2, 3 or other small numbers as there are ways to solve the below equation,
discrete logarithm, for those characteristics. The security of ECC depends on the inability to find solutions to the discrete logarithm problem.
Then parameters
a and
b are selected from the field and plugged in to the elliptic curve equation at the top. Then a point on the elliptic curve is any
x value along with its corresponding
y value (they could represent intermediate secrets), which unlike
a and
b are
not restricted to integers (in a field) for cryptographic purposes, and could be any pair of decimal numbers as long as it's on the curve. But as far as cryptographic algorithms go, the variables
a and
b represent private and public keys respectively. Extremely large numbers can represent public and private keys. That's why it's important that the characteristic and number of elements in the field be extremely large.
There are two types of fields used in cryptography, those with a power of 2 number of elements, and those with a prime number of elements. The fields with a power of 2 number of elements are sect163k1, sect233k1, sect283k1, sect409k1 and sect571k1. The fields with a prime number of elements are secp192k1, secp224k1, secp256k1, secp384k1 and secp521k1.
Now just like in webtrick's guide, there are predefined parameters for
x,
y, the characteristic and the number of elements in the field used. There is no point in listing the parameters for all these here because all of them rely on the same numerical problem to be computationally unsolvable, which is described below.
Suppose you have numbers
b,
e and
m and you want to find
be mod
m =
c, mod being the modulus operation. This problem is called
modular exponentiation. It is relatively easy to calculate the value of
c using the above equation, this is some pseudocode from wikipedia that will do the trick:
function modular_exponentiation(base, exponent, modulus) is
if modulus = 1 then
return 0
c := 1
for e_prime = 0 to exponent-1 do
c := (c * base) mod modulus
return c
Here's a (wikipedia) example of modular exponentiation using the above function and
b = 4,
e = 13, and
m = 497:
e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
e′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
e′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
e′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
e′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
e′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
e′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
e′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
e′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
e′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
e′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
e′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.
So, this function terminates with the answer
c = 445. Now in a cryptographic use case instead of assigning arbitrary numbers to
b,
e and
m, we usually have a large number representing the public key to
b, a large number representing the private key as
e and the characteristic, which is a number corresponding to one of the NIST or SEC standard curves as
m, which results in
c becoming an intermediate secret value which could either be used as a digital signature or for encrypting other data.
The inverse of this equation is called
discrete logarithm, which is log
bc mod
m =
e and is computationally difficult to solve. Essentially you are taking the intermediate secret, the characteristic and the public key "base" number and attempt to find the exponent representing the private key that creates the same intermediate secret as the modular exponentiation function above. Yet this is exactly what attackers need to do to break elliptic curve cryptography.
Two examples of ECC use
Elliptic curve cryptography is used to create signatures, such as the ones in bitcoin, using
Elliptic Curve Digital Signature Algorithm (ECDSA). The advantage of ECDSA over conventional DSA is that relatively fewer bits are needed for an ECDSA public key to have the same security as a larger DSA public key. For example, 160-bit ECDSA keys has about the same strength as a 1024-bit DSA key.
The second use is in several messaging programs like Skype, Signal, WhatsApp and Facebook Messenger, powered by
Elliptic-curve Diffie–Hellman (ECDH). This is a special algorithm that uses ECC for two people to independently create the same secret key using different public/private keys without transmitting the secret over the internet. It has a non-ECC version aptly called
Diffie–Hellman. This is what you hear people call "end-to-end encryption" but if you google that term it would give you technical details unfortunately, so it's always good to know what people are referring to when they use words like that.
