In preparation for this post, I’ve read several research papers, a book, listened to 4 university lectures, idled away hours on IRC, developed elliptic curve libraries in 2 seperate languages, and built my own elliptic curve graphing framework. Elliptic curve cryuptography is hard to wrap your head around. As one of the fundamental crypto systems making Bitcoin a “crypto”-currency, I really wanted to understand the underlying technical aspects which make this form of cryptography secure. This post is an attempt to demystify the elliptic curve digital signing algorithm which underlies bitcoin’s psuedo-anonymous identity system.

Explain like I’m 5 (or thereabouts)

Imagine a classroom of elementary school children who know multiplication but have not yet learned division. At the beginning of the year, the teacher proclaims “My special number is 5”. One morning, the message “Twas always thus and always thus will be” – signed “Teacher - 8” appears on the chalkboard. How do the students know this message came from the teacher and not some movie-quote-loving fraudster? They multiply the teacher’s “special number” - 5 - by the “signature number” - 8 - and if they get the number of characters in the message (40 characters), they deem the signature valid, and are confidant that the message actually came from the teacher. Oblivious to the magic of division, students are unable to produce a valid signature for any arbitrary message, and because the signature is based on the length of the message, the students can’t serruptitously change the message.

This is fundamentally how the elliptic curve digital signature algorithm works; the knower of the private key is endowed with the power of division, while public key holders are restricted to multiplication, which lets them check whether a signature is valid.

Why does Bitcoin need digital signatures?

Alice sends 2 bitcoins to Bob’s public bitcoin address (1Bob4ddr355). If Bob sends these 2 bitcoins to Charley (1Char4ddr355), he broadcasts a message stating “1Bob4ddr355 sends 2 BTC to 1Char4ddr355”. The Bitcoin system must ensure that Bob and only Bob can broadcast this message; if anyone can broadcast a transaction spending Bob’s bitcoin, or alter Bob’s message in anyway, then Bitcoin breaks irreparably.

Public Key Cryptography to the Rescue

Bob needs:

• a private key - sequence of numbers that only Bob knows
• a public key - another sequence of numbers that Bob can share with anyone
• a message to be signed

Because it’s impossible to create Signature _{“This is a message”, Bob} without Bob’s private key, we can be certain that Bob and only Bob digitally signed a message when his public key verifies a signature.

Several mathematical techniques can be used to build such a system, but the current “cutting edge” technology in terms of efficiency and security is elliptic curve cryptography.

What are Elliptic Curves?

Not to be confused with an “ellipse,” elliptic curves look like:

We need the ability to add 2 points on this curve; which works as follows.

What happens if we want to add a point to itself? We can’t draw a line between a point and itself, so we slightly modify the above operation.

Using a bit of algebra and calculus, we can derive the following equations to easily add or double points without the necessity of graphs. The equations themselves aren’t very interesting; they’re here to show that point addition and doubling are trivially calculated by computers.

Point addition and point doubling gives us:

Let’s say we want to figure out “9 * Point A”….how might we do that?

One way to do this:

• 2 * Point A = Point 2A
• Point 2A + Point A = Point 3A
• Point 3A + Point A = Point 4A
• Point 4A + Point A = Point 5A
• Point 5A + Point A = Point 6A
• Point 6A + Point A = Point 7A
• Point 7A + Point A = Point 8A
• Point 8A + Point A = Point 9A ... our answer.

An easier way: (called the “divide and conquer method”)

• 2 * Point A = Point 2A
• 2 * Point 2A = Point 4A
• 2 * Point 4A = Point 8A
• Point 8A + Point A = Point 9A ... our answer.

Using the divide and conquer method, we compute the product in only 4 steps, instead of 9. As the multiplier increases in size, the time saved using the divide and conquer method increases exponentially: calculating 1,000 * G takes only 10 steps and 10,000 * G takes 14 steps (bitcoin uses numbers on the order of 10⁷⁷, which take about 250 steps to compute). This trick is very important in making elliptic curve cryptography actually work, and is the basis of the public key pair (more on that later).

A problem

Computers hate decimal places, and the preceeding equations produce numbers with decimals. Some decimals are irrational (they go on forever…like 1.4142135623…), and computers don’t have the infinite space required to store all these digits. They can make approximations, but when rounding produces equations that ask if 5.9999999 = 6, what’s the computer to do?

Two relatively esoteric mathematical concepts called “finite fields” and “modular arithmetic” help us solve this problem.

If you can tell time, you already understand some modular arithmetic. If it’s 21:00 (9:00pm), and you must wake up for work in 11 hours, you will set your alarm for 8:00; not 32:00. When the clock resets at 24:00, we continue counting from 0:00. This concept, known as “taking the modulus”, lets us transform fractions and decimals into whole numbers.

This technique of transforming fractions into integers is used to eliminate all decimals from the above mathematical equations, making our computer very happy.

Elliptic Curves over Finite Fields

When translating our beloved elliptic curves onto finite fields, graphing all points on the curve becomes a difficult problem. In order to enumerate all points, we add an initial point, called the “generator point” to itself many times.

An elliptic curve with modulus 29 (upper limit is 29) looks like:

Some peculiar things that you might notice:

• Graph is symmetric about the line y = 14.5. Like our continuous graphs, each point has a complement on the same x coordinate.
• Not every x coordinate has a point (look at x = 10….there are no points)

We’re only able to show all points because the modulus is very small. When using a much bigger modulus, such as the one bitcoin uses, creating a “full graph” of all points is impossible.

Using our trusty equations from above and a convoluted graphing system which wraps around the axes, we can see that our point doubling operator still works properly.

The Key to Elliptic Curves

We’re now ready to discuss public and private keys:

Some intersting things arise from this arrangement:

• If the private key is very large, it’s easy to compute the public key using the divide and conquer method, but very difficult for an attacker to brute force.
• Unlike the public key, the private key is just a number. We’re able to perform “normal” math operations on it to build out the digital signature system (we can easily divide, multiply, etc.)
• The public key, an elliptic curve point, is restricted to the addition and doubling operations that we’ve discussed (there is no division of points)

We now have a system fairly similiar to the elementary school classroom scenario above.

The Digital Signature Algorithm

The signer creates 3 points:

1. Message Point: Convert the message to a number (by taking it’s hash), and multiply this number by the generator point
         (Message Point) = Message Hash * G
2. Random Point: We pick a point at random
         (Random Point) = Random Number * G
3. Random-Public Key Point: We multiply the x-coordinate of the random point by the public key, (remember, the random point’s x coordinate is an integer)
         (PK-Random Point) = Random Point X-Coordinate * (Public Key)

The signer creates a special pathway to the “Random Point” by way of both the “Message Point” and the “PK-Random Point”. We must compute a signature factor such that

The signer then gives the random point and the signature factor to the verifier, who checks whether the signature factor recreates the special pathway to the random point by way of the “Message Point” and “PK-Random Point.”

This is secure because:

• Creating a signature factor that verifies with a given public key is impossible to create without the knowledge of the public key’s generator.
• The signature factor is also used in conjunction with the message hash, so if the message ever changes, the signature factor will no longer be useful in recreating the “pathway” to the given random point. As stated above, creating a new signature factor to work with a modified message is out of the question.

Hopefully the following example can help illuminate this process further (although, admittedly, it’s a bit hard to conceptualize). Notice when the verifier changes any of the parameters, the signature is no longer valid.

Bitcoin Numbers

To ground all this in reality, here are some real numbers taken directly from bitcoin itself (bitcoin uses the sicp256k1 curve, which has it’s own paramers and generator point).

Generator Point: Remember, this is the same for everyone. All other points are children of this base point.
      x: 55066263022277343669578718895168534326250603453777594175500187360389116729240 (10^76)
      y: 32670510020758816978083085130507043184471273380659243275938904335757337482424 (10^76)

Order: The number of possible points on the curve. There’s a nifty formula which calculates this (I have no idea why it works, but it does)
      115792089237316195423570985008687907852837564279074904382605163141518161494337 (10^77)

Private Key:
      23695310554196047209792918797392416191148132060917476866274911959533140016553

Public Key:
      x: 39874617776630327813190058413816560767734954098998567043224950074533143699292
      y: 83115399533222200534442050051826386603242609920409430626876080623730665355556

Signature:
      r: 25282362915497655056329512917121654088602539327808216077267936411779996643728
      s: 39257440409490934652644589859771879805788241064351461738307073788061051966857

These are truly gargantuan numbers - the number of possible points on the elliptic curve is fairly close to the number of atoms in the observable universe. A human body contains 7,000,000,000,000,000,000,000,000,000 atoms. Think about how insignificant in size we are compared to the entire earth, which is insignificant compared to the sun, which is only 1 of hundreds of billions in a single galaxy, of which there are hundreds of billions in the universe. Computers are fast, but not fast enough to visit even a small fraction of those points. It’s just impossible. It’s amazing that such security is possible so quickly and accessibly (a phone can do these calculations in fractions of a second); full acollades go out to the brilliant cryptographers, mathematicians, and computer scientists behind the elliptic curve technology.

Key Take-aways

• An elliptic curve is nothing more than: Point = Multiplier * Public Generator Point
• Private key is the multiplier, public key is the point
• Given the point, it’s impossible to get the multiplier
• You can do addition, subtraction, multiplication, and division with the multiplier (private key); but can only do addition and multiplication with the point (public key)
• Creating a signature requires division (needs the private key), but verifying the signature only needs addition and multiplication (can be done with public key)

Special Thanks to the following resources which helped me out immensely:

• Understanding Cryptography - by Cristof Paar
• Elliptic Curves Number Theory and Cryptography - by Lawrence Washington
• Intro to Cryptography and Data Security - Ruhr University Lectures
• Flot Javascript Plotting Library
• Ruby ECDSA | github.com