Why and What is ECDSA

 Referenced from 

  • Instruct-able workshops
  • others 

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.

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.

Why use ECDSA

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.


Mathematics and Binary

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.


Hash


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 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.


ECDSA Equation

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 (equation of a curve on a graph). This means for any x coordinate (only integers), we will have 2 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. Since we have modulo(p), it means that thee possible values of y^2 are between 0 and p-1, which gives us p total possible values Since we are dealing with integers, only a smaller subset of those values will be perfect square, which gives us N possible points on the curve where N<p (N being the perfect squares between 0 and p).

Since each x will yield two points(+ve and -ve values of the square-root of y^2) means that there are N/2 possible x coordinates that are valid and that give a point on the curve.

To summarize, the ECDSA equation gives us a curve with the finite number of valid points on it (N) because the Y axis is bound by thee modulus (p) and needs to be perfect square (y^2) with a symmetry on the X axis.

ECDSA Algorithm

For ECDSA, We need to know our curve parameters, those are a,b,p,N and G. We already know 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. The reference point can be any point on the curve.

Those curve parameters are important and without knowing them, we cannot sign or verify a signature. Verifying a signature isn't just about knowing the public key, you also need to know the curve parameters for which the public key is derived from. 

Key pairs, private key and public key, the private key is a random number 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 and Qa as the public key(a point), so we will have Qa = dA * G (where G is the point of reference in the curve parameters.

Creating a Signature

The signature consists of 2 values or pair (R,S), the pair together is called ECDSA signature. Now first generate a random number k, and use point multiplication to calculate P=k*G, where P is the curve point (x,y). The points x value will represent R, we only need x value for the signature, and that value will be called R. Now all we need is the S value.

To calculate S, we must make SHA-2 hash of the message, this gives us some bytes value that we will consider as a very huge integer and call it z. Now we can calculate S using the equation:

S=k^-1(z+dA*R)mod p

k^-1 which is modular multiplication inverse of k. So k is the random number 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.

Verifying the Signature

To verify a signature we only need public key and the curve parameters. We use the 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, else it is not. Lets dig in to the equation :

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

So x coordinate pf P must match R and R is the x coordinate of k*G, which gives

k*G = S^-1(z+dA*R)*G = k = S^-1(z+dA*R)

so inverting k and S we get,

S = k^-1(z+dA*R)

and that is the equation is used to generate the signature, so it matches and that is the reason we can verify the signature using the first equation.


Security of ECDSA

Since we need dA and k to create a signature S and we only need R and Qa to verify the signature S. And since R=k*G and Qa=dA*G and because of the trap door function in the ECDSA point multiplication, we cannot calculate dA and k from knowing Qa and R, this makes the ECDSA secure.