Introduction: Understanding How ECDSA Protects Your Data.
Everyone has probably heard of ECDSA in one form or another. Some people will better recognize it when I say "Digital signature", and some people will just have no idea what I'm talking about.
I once tried to understand how ECDSA works, but it's hard to figure it out because most reference documents online are insufficient. They are either too basic -- they only explain the basics of the algorithm and you're left wondering "how does it actually work?" -- or they are too advanced and completely skip over the basics which they assume you should already know. So you're struggling between "how does it really work" and "How did we get here?". So if you don't have a degree in Mathematics or Cryptography, but still want to understand how it actually works (other than "magic happens, and the signature is verified"), you're out of luck because there is no "ECDSA for newbies" anywhere.
I decided to research ECDSA to better understand how it can protect my data and to understand how secure it actually is. After doing a lot of research and finally figuring it out, I decided to write an explanation of how ECDSA works, what the algorithm is, how a digital signature can be verified and how it's impossible to forge such a signature. Understanding all of that isn't trivial but I tried to explain the best I can while assuming as little as possible on the reader's knowledge and hopefully anyone can understand it now.
Step 1: What Is ECDSA?
ECDSA stands for “Elliptic Curve Digital Signature Algorithm”, it’s used to create a digital signature of data (a file for example) in order to allow you to verify its authenticity without compromising its security. Think of it like a real signature, you can recognize someone’s signature, but you can’t forge it without others knowing. The difference however between an ECDSA signature and a real signature is that it's simply impossible to forge the ECDSA signature.
You shouldn't confuse ECDSA with AES (Advanced Encryption Standard) which is to encrypt the data. ECDSA does not encrypt or prevent someone from seeing or accessing your data, what it protects against though is making sure that the data was not tampered with.
Two words are worth noting here in "ECDSA" and that's "Curve" and "Algorithm" because it means that ECDSA is basically all about mathematics.. so I think it’s important to start by saying : “hey kids, don’t slack off at school, listen to your teachers, that stuff might be useful for you some day!” But these maths are fairly complicated, so while I’ll try to vulgarize it and make it understandable for non technical people, you will still probably need some knowledge in mathematics to understand it properly. I will do this in two parts, one that is a sort of high level explanation about how it works, and another where I dig deeper into its inner workings to complete your understanding. Note however that while I understand ECDSA fairly well now, I'm not an expert on the matter (my document here was however reviewed by someone who wrote a thesis about ECDSA and approved it as being accurate).
Step 2: Understanding the Basics
So the principle is simple, you have a mathematical equation which draws a curve on a graph, and you choose a random point on that curve and consider that your point of origin. Then you generate a random number, this is your private key, you do some magical mathematical equation using that random number and that “point of origin” and you get a second point on the curve, that’s your public key.
When you want to sign a file, you will use this private key (the random number) with a hash of the file (a unique number to represent the file) into a magical equation and that will give you your signature. The signature itself is divided into two parts, called R and S. In order to verify that the signature is correct, you only need the public key (that point on the curve that was generated using the private key) and you put that into another magical equation with one part of the signature (S), and if it was signed correctly using the the private key, it will give you the other part of the signature (R). So to make it short, a signature consists of two numbers, R and S, and you use a private key to generate R and S, and if a mathematical equation using the public key and S gives you R, then the signature is valid. There is no way to know the private key or to create a signature using only the public key.
Step 3: Why Use ECDSA?
Ok, you now know the basics.. you probably didn't understand much, it's all complicated, public key, private key, what's all that ? Don't worry, I'll get to it soon enough, but first, a little explanation on why we use ECDSA and where it can be useful.
Other than the obvious "I need to sign a contract/document", here's a very popular use case : let's take for example an application that doesn't want its data to be corrupted or modified by the users, like a game that only allows you to load official maps and prevents mods, or a phone or other kind of device that only allows you to install official applications.
In those case, the files (the apps, the game maps, the data) will be signed with the ECDSA signature, the public key will be bundled with the application/game/device and verifies the signature to make sure the data has not been modified, while the private key is kept under lock in a safe somewhere. Since you can verify the signature with the public key, but you can't create/forge a new signature with it, then the public key can be distributed with the application/game/device without any worries.
This is contrasted with the AES encryption system which allows you to encrypt the data but you will need the key to decrypt and such an application would need to bundle the key which defeats the purpose.
A good example is the Playstation 3 console which was broken wide open and all its files can be decrypted and all the keys within the PS3 files can be extracted but the one thing that remains to be broken on it is an ECDSA signature which prevents anyone from making applications run on the latest firmwares.
Step 4: Basic Mathematics and Binary
Alright, now for the more in depth understanding, I suggest you take an aspirin right now as this might hurt!
Let’s start with the basics (which may be boring for people who know about it, but is mandatory for those who don’t) : ECDSA uses only integer mathematics, there are no floating points (this means possible values are 1, 2, 3, etc.. but not 1.5, 2.5, etc..), also, the range of the numbers is bound by how many bits are used in the signature (more bits means higher numbers, means more security as it becomes harder to ‘guess’ the critical numbers used in the equation), as you should know, computers use ‘bits’ to represent data, a bit is a ‘digit’ in binary notation (0 and 1) and 8 bits represent one byte. Every time you add one bit, the maximum number that can be represented doubles, with 4 bits you can represent values 0 to 15 (for a total of 16 possible values), with 5 bits, you can represent 32 values, with 6 bits, you can represent 64 values, etc.. one byte (8 bits) can represent 256 values, and 32 bits can represent 4294967296 values (4 Giga).. Usually ECDSA will use 160 bits total, so that makes… well, a very huge number with 49 digits in it…
Another mathematical construct you need to know is the modulus, which can be simplified by saying it's the rest of a division of integers. So for example, x mod 10 means the rest of the division of x by 10, which will always be a number between 0 and 9, so 142 mod 10 gives 2 for example. Another example, would be x mod 2which gives 0 for even numbers and 1 for odd numbers.
Step 5: The Hash
ECDSA is used with a SHA1cryptographic hash of the message to sign (the file). A hash is simply another mathematical equation that you apply on every byte of data which will give you a number that is unique to your data. Like for example, the sum of the values of all bytes may be considered a very dumb hash function. So if anything changes in the message (the file) then the hash will be completely different. In the case of the SHA1 hash algorithm, it will always be 20 bytes (160 bits). It’s very useful in order to validate that a file has not been modified or corrupted, you get the 20 bytes hash for a file of any size, and you can easily recalculate that hash to make sure it matches. What ECDSA signs is actually that hash, so if the data changes, the hash changes, and the signature isn’t valid anymore.
Let's use an example to make it easier to understand. We'll use the simplest (and dumbest) hash function possible in which we make the sum of all the data and use a modulus 10 on the result.
First of all, you must understand that all data will be interpreted as a number. A text file is a series of bytes, which, as we explained earlier represents 8 bits, meaning it can represent a number between 0 and 255. So if we take each byte as a number and add each byte of the file, then we do a modulus by 10 of the result, we'll end up with a number between 0 and 9 as the resulting hash. We'll always get the same hash for the same data, and if you change a byte in the file, the result may be different. Of course, you'll also understand that it would be very easy to change the file in order to get the same hash since there are only 10 possibilities (0 to 9), then there is a one in 10 chances of getting the same hash by changing the content of the file.
That's where SHA1 comes into play, the SHA1 algorithm is much much more complex than our simple "modulus 10" hash function, it will give an extremely huge number (160 bits, so a number with 49 digits in decimal) and it has the particularity to change radically if a single bit of data is modified from the file.
This makes SHA1 a very good hashing algorithm that is unpredictable which is very secure and with very little chances of getting a 'collision' (when two different files have the same hash) and makes it practically impossible to forge data to get a specific hash.
Step 6: The ECDSA Equation
Now, how does it work? Well Elliptic Curve cryptography is based on an equation of the form :
y^2 = (x^3 + a * x + b) mod p
First thing you notice is that there is a modulo and that the ‘y‘ is squared (don't forget this is the equation of a curve on a graph). This means that for any x coordinate (don't forget as well that we're only working with integers), you will have two values of y and that the curve is symmetric on the X axis. The modulo is a prime number and makes sure that all the values are within our range of 160 bits and it allows the use of “modular square root” and “modular multiplicative inverse” mathematics which make calculating stuff easier. Since we have a modulo (p) , it means that the possible values of y^2 are between 0 and p-1, which gives us p total possible values. However, since we are dealing with integers, only a smaller subset of those values will be a “perfect square” (the square value of two integers), which gives us N possible points on the curve where N < p (N being the number of perfect squares between 0 and p). You're following me so far? :)
Since each x will yield two points (positive and negative values of the square-root of y^2), this means that there are N/2 possible ‘x‘ coordinates that are valid and that give a point on the curve. So this elliptic curve has a finite number of points on it, and it’s all because of the integer calculations and the modulus.
Ouff, that was hard! Let's summarize before we move on. The ECDSA equation gives us a curve with a finite number of valid points on it (N) because the Y axis is bound by the modulus (p) and needs to be a perfect square (y^2) with a symmetry on the X axis. We have a total of N/2 possible, valid x coordinates without forgetting that N < p.
Step 7: Point Addition
Another thing you need to know about Elliptic curves, is the notion of “point addition“. It is defined as adding one point P to another point Q will lead to a point S such that if you draw a line from P to Q, it will intersect the curve on a third point R which is the negative value of S (remember that the curve is symmetric on the X axis). In this case, we define R = -S to represent the symmetrical point of R on the X axis.This is easier to illustrate with an image, so look at the above image.
So you can see a curve of the form y^2 = x^3 + ax + b (where a = -4 and b = 0), which is symmetric on the X axis, and where P+Q is the symmetrical point through X of the point R which is the third intersection of a line going from P to Q.
Step 8: Point Multiplication
In the same manner, if you do P + P, it will be the symmetrical point of R which is the intersection of the line that is a tangent to the point P.. And P + P + P is the addition between the resulting point of P+P with the point P since P + P + P can be written as (P+P) + P.. This defines the “point multiplication” where k*P is the addition of the point P to itself k times… Look at the two images above for examples of the point multiplication.
Here, you can see two elliptic curves, and a point P from which you draw the tangent, it intersects the curve with a third point, and its symmetric point is 2P, then from there, you draw a line from 2P and P and it will intersect the curve, and the symmetrical point is 3P. etc… you can keep doing that for the point multiplication. You can also already guess why you need to take the symmetric point of R when doing the addition, otherwise, multiple additions of the same point will always give the same line and the same three intersections.
Step 9: The Trap Door Function!
One particularity of this point multiplication is that if you have a point R = k*P, where you know R and you know P, there is no way to find out what the value of ‘k‘ is. Since there is no point subtraction or point division, you cannot just resolve k = R/P. Also, since you could be doing millions of point additions, you will just end up on another point on the curve, and you’d have no way of knowing “how” you got there. You can’t reverse this operation, and you can’t find the value ‘k‘ which was multiplied with your point P to give you the resulting point R.
This thing where you can’t find the multiplicand even when you know the original and destination points is the whole basis of the security behind the ECDSA algorithm, and the principle is called a “trap door function“.
Step 10: The ECDSA Algorithm
Now that we’ve handled the “basics”, let’s talk about the actual ECDSA signature algorithm.
For ECDSA, you first need to know your curve parameters, those are a, b, p, N and G. You already know that ‘a‘ and ‘b‘ are the parameters of the curve function (y^2 = x^3 + ax + b), that ‘p‘ is the prime modulus, and that ‘N‘ is the number of points of the curve, but there is also ‘G‘ that is needed for ECDSA, and it represents a ‘reference point’ or a point of origin if you prefer. The reference point could be any point on the curve.
Those curve parameters are important and without knowing them, you obviously can’t sign or verify a signature. Yes, verifying a signature isn’t just about knowing the public key, you also need to know the curve parameters for which this public key is derived from. The NIST (National Institute of Standards and Technology) and SECG (Standards for Efficient Cryptography Group) offer pre-made and standardized curve parameters which are known to be secure and efficient.
So first of all, you will have a private and a public key.. the private key is a random number (of 160 bits too) that is generated, and the public key is a point on the curve generated from the point multiplication of G with the private key. We set ‘dA‘ as the private key (random number) and ‘Qa‘ as the public key (a point), so we have : Qa = dA * G (where G is the point of reference in the curve parameters).
Step 11: Creating a Signature
So how do you sign a file/message ?
First, you need to know that the signature is 40 bytes and is represented by two values of 20 bytes each, the first one is called R and the second one is called S.. so the pair (R, S) together is your ECDSA signature.. now here’s how you can create those two values in order to sign a file.. first you must generate a random value ‘k‘ (of 20 byes), and use point multiplication to calculate the point P=k*G. That point’s x value will represent ‘R‘. Since the point on the curve P is represented by its (x, y) coordinates (each being 20 bytes long), you only need the ‘x‘ value (20 bytes) for the signature, and that value will be called ‘R‘. Now all you need is the ‘S‘ value.
To calculate S, you must make a SHA1 hash of the message, this gives you a 20 bytes value that you will consider as a very huge integer number and we’ll call it ‘z‘. Now you can calculate S using the equation :
S = k^-1 (z + dA * R) mod p
Note here the k^-1 which is the ‘modular multiplicative inverse‘ of k… it’s basically the inverse of k, but since we are dealing with integer numbers, then that’s not possible, so it’s a number such that (k^-1 * k ) mod p is equal to 1. And again, I remind you that k is the random number used to generate R, z is the hash of the message to sign, dA is the private key and R is the x coordinate of k*G (where G is the point of origin of the curve parameters).
Step 12: Verifying the Signature
Now that you have your signature, you want to verify it, it’s also quite simple, and you only need the public key (and curve parameters of course) to do that. You use this equation to calculate a point P :
P = S^-1*z*G + S^-1 * R * Qa
If the x coordinate of the point P is equal to R, that means that the signature is valid, otherwise it’s not.
Pretty simple, huh? now let’s see why and how… and this is going to require some mathematics to verify :
We have :
P = S^-1*z*G + S^-1 * R *Qa
but Qa = dA*G, so:
P = S^-1*z*G + S^-1 * R * dA*G = S^-1 (z + dA* R) * G
But the x coordinate of P must match R and R is the x coordinate of k * G, which means that :
k*G = S^-1 (z + dA * R) *G
we can simplify by removing G which gives us :
k = S^-1(z + dA * R)
by inverting k and S, we get :
S = k^-1 (z + dA *R)
and that is the equation used to generate the signature.. so it matches, and that is the reason why you can verify the signature with that first equation above.
Step 13: The Security of ECDSA
You can note that you need both ‘k‘ (random number) and ‘dA‘ (the private key) in order to calculate S, but you only need R and Qa (public key) to verify the signature. And since R=k*G and Qa = dA*G and because of the trap door function in the ECDSA point multiplication (explained in step 9), we cannot calculate dA or k from knowing Qa and R, this makes the ECDSA algorithm secure, there is no way of finding the private keys, and there is no way of faking a signature without knowing the private key.
Step 14: The Importance of a Random K
Let's discuss now how and why the ECDSA signatures that Sony used in the Playstation 3 were faulty and how it allowed hackers to gain access to the PS3's ECDSA private key.
So you remember the equations needed to generate a signature.. R = k*G and S= k^-1(z + dA*R) mod p.. well this equation’s strength is in the fact that you have one equation with two unknowns (k and dA) so there is no way to determine either one of those.
However, the security of the algorithm is based on its implementation and it’s important to make sure that ‘k‘ is randomly generated and that there is no way that someone can guess, calculate, or use a timing attack or any other type of attack in order to find the random value ‘k‘. But Sony made a huge mistake in their implementation, they used the same value for ‘k‘ everywhere, which means that if you have two signatures, both with the same k, then they will both have the same R value, and it means that you can calculate k using two S signatures of two files with hashes z and z’ and signatures S and S’ respectively :
S – S’ = k^-1 (z + dA*R) – k^-1 (z’ + da*R) = k^-1 (z + da*R – z’ -dA*R) = k^-1 (z – z’)
So : k = (z – z’) / (S – S’)
Once you know k, then the equation for S becomes one equation with one unknown and is then easily resolved for dA :
dA = (S*k – z) / R
Once you know the private key dA, you can now sign your files and the PS3 will recognize it as an authentic file signed by Sony. This is why it’s important to make sure that the random number used for generating the signature is actually “cryptographically random”. This is also the reason why it is impossible to have a custom firmware above 3.56, simply because since the 3.56 version, Sony have fixed their ECDSA algorithm implementation and used new keys for which it is now impossible to find the private key..
Another example of this issue is when some bitcoin clients used a non-cryptographically random number generator (on some browsers and on some Android clients) which caused them to sign their transactions with the same 'k' value, and malicious people were able to find the private key of their bitcoin wallet and steal their funds.
This shows the importance of using a truly random number every time you make a signature, as you will expose the private key if the R value of the (R, S) signature pair is the same on two different signatures.
A good joke about this is shown in xkcd comic 221 (see image above) which became the go-to image to illustrate this issue. The image was often re-used whenever such an implementation error of the algorithm happened.
The ECDSA algorithm is very secure for which it is impossible to find the private key... as long as the implementation is done correctly of course. If there was a way to find the private key, then the security of every computer, website, system may be compromised since a lot of systems are relying on ECDSA for their security, and it is impossible to crack.
Step 15: Conclusion
Finally! I hope this makes the whole algorithm clearer to many of you.. I know that this is still very complicated and hard to understand. I usually try to make things easy to understand for non technical people, but this algorithm is too complex to be able to explain in any simpler terms.
But if you are a developer or a mathematician or someone interested in learning about this because you want to help or simple gain knowledge, then I’m sure that this contains enough information for you to get started or to at least understand the concept behind this unknown beast called “ECDSA”.
That being said, I’d like to thank a few people who helped me understand all of this, one particularly who wishes to remain anonymous, as well as the many wikipedia pages I linked to throughout this article, and Avi Kak thanks to his paper explaining the mathematics behind ECDSA, and from which I have taken those graph images aboves.
P.s: In this instructable, I used ’160 bits’ in my text to talk about the ECDSA signature because that’s what is usually used as it matches the SHA1 hash size of 160 bits (20 bytes) and that’s what the PS3 security uses, but the algorithm itself can be used with any size of numbers. There may be other inaccuracies in this article, but like I said, I’m not an expert and this was dumbed down as much as possible whichout removing any information about the algorithm.