Topic: Elliptic Curve Cryptography Basics - How It Works (Read 366 times)
...
The inverse of this equation is called discrete logarithm, which is log cb mod m = e
...
The inverse of this equation is called discrete logarithm, which is log cb mod m = e
...
A minor typo in the notation. No need for a reply. It should be:
Quote
...
The inverse of this equation is called discrete logarithm, which is logb c mod m = e
...
The inverse of this equation is called discrete logarithm, which is logb c mod m = e
...
Bump! Here I'm going to collect my notes about point addition and multiplication in one place.
How To Do Point Addition / Point Multiplication By Hand?
We'll start with the two basic operations, point addition and point multiplication, and show graphical examples of how these operations work on the curve as well. Subtraction and Division can be implemented as point addition by a negative number and point multiplication by a modular inverse respectively.
Point Addition
Basically:
- (Ax,Ay) and (Bx,By) are your input points
- Lambda (green) is an expression made out of the A and B coordinates that basically refers to the slope of the line made by drawing a line between point A and point B
The result of the point addition is (lambda2 - Ax - Bx, lambda*(Ax - Cx) - Ay) and this will always be the intersection between the curve, and the line formed by A and B.
Note: three points will touch the curve, two of them are A and B, the third is the sum of them.
Note: If either of the points are 0 then the result is the other point. If both of them are 0 then the result is 0. If one of the points is the negative of the other then the result is 0.
Here Q is added to P to give the result R:
Image source: https://medium.com/asecuritysite-when-bob-met-alice/adding-points-in-elliptic-curve-cryptography-a1f0a1bce638
So graphically, once you find the point that lies on the same line as the two points your adding, you mirror it over the X axis to get the final resulting point. The reason you do this is because the point on the line is actually the negative of the result, and it's necessary that this point be negative to satisfy the relation "P + Q - R = 0", so the "R" on the line is negative and it cancels out the P and Q. In my words: "you draw a line that crosses both of these points, and find the third point that intersects the line, and flip it over the x-axis. There will always be a third intersecting point, because the curve is cubic."
Point Doubling (i.e. multiplication)
Point doubling is basically when you add a point P to itself. The normal point addition method cannot be used, because it only works when the two points are different. However, the two operators refer to the same point so a different method is needed.
from a previous post I made about the subject: "When you add a point to itself, you take the tangent line of the point, and find the other point on the curve this line intersects, and then "flip" that point across the x-axis (this is possible because elliptic curves are symmetrical across the x-axis). This new point is P + P, or 2P."
This procedure can be used to repeatedly produce the doubles of these points such as 4G, 8G, 16G and so on. In each case you take the result of the previous doubling and inset it as operands of the next doubling operation.
Here is a graph that demonstrates P + P = 2P = R:
Image source: https://hackernoon.com/elliptic-curve-crypto-point-doubling-b98508d40a88
Although the relationship is not immediately clear from the graph, since you're technically adding P to P, it balances out the -R in this graph as well.
Now it's possible to combine the two processes of point addition and point doubling to multiply arbitrary numbers, otherwise known as point multiplication. You can implement point multiplication as a series of point doubles and point additions.
I talked a lot about how the points on each side of the relation balance each other out. This is called collinearality, or, all points lie on the same line. This mathematical concept means that these points all add up to zero.
It's also the reason why adding a point to it's negative, like -R to R, will give you zero, because the line formed becomes vertical, indicating there is no such point on the curve to satisfy the relation (the point "0" means "no such point on the curve". It is also sometimes called "point at infinity"). This also explains why adding the point "0" to a point gives you the same point. Any line formed from "0" to another point will only include two points, and thus the result is taken as the non-null point. In this way "0" acts as an identity operator.
Algorithms
Below I post-conventional algorithms used to calculate point addition, point double, and point multiplication respectively in pseudocode.
The first one handles both point addition and point doubling (addition of a point to itself):
The second one implements point multiplication using the Montgomery ladder algorithm, which runs in a fixed amount of time and thus is not vulnerable to most side-channel attacks.
How To Do Point Addition / Point Multiplication By Hand?
We'll start with the two basic operations, point addition and point multiplication, and show graphical examples of how these operations work on the curve as well. Subtraction and Division can be implemented as point addition by a negative number and point multiplication by a modular inverse respectively.
Point Addition
To get G*2 (I am assuming this is the value you are trying to compute, correct me if I'm wrong), you have to add G + G.
There is an algorithm for doing this point doubling C = B*2 by hand. First, take lambda = (3Bx2 + a)/(2By) , where (Bx, By) are the coordinates of the point B you are trying to double, and a is a parameter whose value is given along with the type of curve you are using. Since you are using the secp256k1 curve, a = 0.
So for the secp256k1 this expression becomes lambda = (3Bx2)/(2By) (I'm using red to color x coordinates and blue to color y coordinates).
Next you compute Cx = lambda2 -2Bx, then you compute Cy = lambda*(Bx - Cx) - By . And this is how you get coordinates (Cx, Cy) of the point C = B*2.
The algorithm for doing point addition is so similar I might as well include it here too. To get C = A + B, where A != B (in other words A and B must not be the same point. If that's the case, use point doubling instead):
- lambda = (By - Ay)/(Bx - Ax) (Note: no a term, even if the curve is not secp256k1!)
- Cx = lambda2 - Ax - Bx
- Cy = lambda*(Ax - Cx) - Ay
There is an algorithm for doing this point doubling C = B*2 by hand. First, take lambda = (3Bx2 + a)/(2By) , where (Bx, By) are the coordinates of the point B you are trying to double, and a is a parameter whose value is given along with the type of curve you are using. Since you are using the secp256k1 curve, a = 0.
So for the secp256k1 this expression becomes lambda = (3Bx2)/(2By) (I'm using red to color x coordinates and blue to color y coordinates).
Next you compute Cx = lambda2 -2Bx, then you compute Cy = lambda*(Bx - Cx) - By . And this is how you get coordinates (Cx, Cy) of the point C = B*2.
The algorithm for doing point addition is so similar I might as well include it here too. To get C = A + B, where A != B (in other words A and B must not be the same point. If that's the case, use point doubling instead):
- lambda = (By - Ay)/(Bx - Ax) (Note: no a term, even if the curve is not secp256k1!)
- Cx = lambda2 - Ax - Bx
- Cy = lambda*(Ax - Cx) - Ay
Basically:
- (Ax,Ay) and (Bx,By) are your input points
- Lambda (green) is an expression made out of the A and B coordinates that basically refers to the slope of the line made by drawing a line between point A and point B
The result of the point addition is (lambda2 - Ax - Bx, lambda*(Ax - Cx) - Ay) and this will always be the intersection between the curve, and the line formed by A and B.
Note: three points will touch the curve, two of them are A and B, the third is the sum of them.
Note: If either of the points are 0 then the result is the other point. If both of them are 0 then the result is 0. If one of the points is the negative of the other then the result is 0.
Here Q is added to P to give the result R:
Image source: https://medium.com/asecuritysite-when-bob-met-alice/adding-points-in-elliptic-curve-cryptography-a1f0a1bce638
So graphically, once you find the point that lies on the same line as the two points your adding, you mirror it over the X axis to get the final resulting point. The reason you do this is because the point on the line is actually the negative of the result, and it's necessary that this point be negative to satisfy the relation "P + Q - R = 0", so the "R" on the line is negative and it cancels out the P and Q. In my words: "you draw a line that crosses both of these points, and find the third point that intersects the line, and flip it over the x-axis. There will always be a third intersecting point, because the curve is cubic."
Point Doubling (i.e. multiplication)
Point doubling is basically when you add a point P to itself. The normal point addition method cannot be used, because it only works when the two points are different. However, the two operators refer to the same point so a different method is needed.
from a previous post I made about the subject: "When you add a point to itself, you take the tangent line of the point, and find the other point on the curve this line intersects, and then "flip" that point across the x-axis (this is possible because elliptic curves are symmetrical across the x-axis). This new point is P + P, or 2P."
This procedure can be used to repeatedly produce the doubles of these points such as 4G, 8G, 16G and so on. In each case you take the result of the previous doubling and inset it as operands of the next doubling operation.
Here is a graph that demonstrates P + P = 2P = R:
Image source: https://hackernoon.com/elliptic-curve-crypto-point-doubling-b98508d40a88
Although the relationship is not immediately clear from the graph, since you're technically adding P to P, it balances out the -R in this graph as well.
Now it's possible to combine the two processes of point addition and point doubling to multiply arbitrary numbers, otherwise known as point multiplication. You can implement point multiplication as a series of point doubles and point additions.
I talked a lot about how the points on each side of the relation balance each other out. This is called collinearality, or, all points lie on the same line. This mathematical concept means that these points all add up to zero.
It's also the reason why adding a point to it's negative, like -R to R, will give you zero, because the line formed becomes vertical, indicating there is no such point on the curve to satisfy the relation (the point "0" means "no such point on the curve". It is also sometimes called "point at infinity"). This also explains why adding the point "0" to a point gives you the same point. Any line formed from "0" to another point will only include two points, and thus the result is taken as the non-null point. In this way "0" acts as an identity operator.
When you "flip" a point, you are changing its sign. Flipping the point a second time changes it's sign back just like in conventional arithmetic.
The commutative property holds because it doesn't matter which wya you add Q + P or P + Q; the line is the same. And the associative property also holds because it doesn't matter which points you add first before others, you will ultimately arrive at the same point.
The commutative property holds because it doesn't matter which wya you add Q + P or P + Q; the line is the same. And the associative property also holds because it doesn't matter which points you add first before others, you will ultimately arrive at the same point.
Algorithms
Below I post-conventional algorithms used to calculate point addition, point double, and point multiplication respectively in pseudocode.
The first one handles both point addition and point doubling (addition of a point to itself):
Code:
if (x1,y1) == O
result = (x2,y2)
else if (x2,y2) == O
result = (x1,y1)
else if (x2,y2) == (x1,y1)**(-1)
result = O
if (x2,y2) == (x1,y1):
# Point doubling: 2P
lambda = (3 * x1**2) * (2*y1)**-1
else:
# Point addition: P+Q
lambda = (y2 - y1)*(x2 - x1)**-1
x3 = lambda**2 - x1 - x2
y3 = lambda*(x1 - x3) - y1
The second one implements point multiplication using the Montgomery ladder algorithm, which runs in a fixed amount of time and thus is not vulnerable to most side-channel attacks.
Code:
R0 ← 0
R1 ← P
for i from m downto 0 do
if di = 0 then
R1 ← point_add(R0, R1)
R0 ← point_double(R0)
else
R0 ← point_add(R0, R1)
R1 ← point_double(R1)
return R0
In light of new information connecting the discrete logarithm and its parameters to the numbers representing the public, private and secret keys, I have updated the topic with new information pertaining to that.
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.
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:
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.
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.
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:
Code:
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.
Jump to: