ECDSA questions

[jl2012]

I am completely new to this area so my questions may be very stupid.



To calculate P+Q, one has to draw a line going through P and Q, and look for the intersection with the elliptic curve (R). Flip the y-value of R and the solution is P+Q.

So it is trivial to get the value of R if P+Q is known. If P is also known, one can draw a line going through R and P, and the intersection with the curve will be Q.

The whole process seems reversible. What's wrong with my interpretation?

-------------

My second question is related to bitcoin

From wikipedia:

In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. However, this attack can be considered invalid against ECDSA because it is Sony who failed to implement valid signature(s). That is, the attack was made possible because Sony failed to generate a new random k for each signature.

I suppose bitcoin is not vulnerable to this attack? When I try to sign a transaction for multiple times, I find that the signatures are different. Is it related to this vulnerability?

[1714582817]

1714582817

[1714582817]

1714582817

[1714582817]

1714582817

[1714582817]

1714582817

[freeloader247]

My second question is related to bitcoin

From wikipedia:

In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. However, this attack can be considered invalid against ECDSA because it is Sony who failed to implement valid signature(s). That is, the attack was made possible because Sony failed to generate a new random k for each signature.

I suppose bitcoin is not vulnerable to this attack? When I try to sign a transaction for multiple times, I find that the signatures are different. Is it related to this vulnerability?

Not sure if this is what you mean, meant but Sony vulnerability came from them using the same "random" number every time they signed anything.
http://images.eurogamer.net/articles//a/1/3/1/3/9/2/5/equation2.jpg.jpg

[fpgaminer]

So it is trivial to get the value of R if P+Q is known. If P is also known, one can draw a line going through R and P, and the intersection with the curve will be Q.

The reverse of addition is subtraction.  So what you have described is Elliptic Curve subtraction.  However, EC subtraction won't help you break ECC (Elliptic Curve Cryptography).  Here's why:

In ECDSA, we generate key pairs.  A private key, which must be kept secret, and a public key which can be shared.  Given a private key d_a (a 256-bit integer), we calculate a corresponding public key (Q) like so:

Code:

Q = d_a * G

Where G is the Generator for whatever elliptic curve you're in (it's a special Elliptic Curve Point, which more or less means "1").  Note that G is a point on an elliptic curve, and d_a is an integer.  This is scalar multiplication on an EC point.  You can look up the math for that, but it's basically just binary multiplication where all additions are EC additions.

Long story made short, if one wants to break ECDSA, one merely needs to find an efficient way to recover d_a, given only Q (and of course G).  Currently, no one has found an efficient way to reverse this scalar multiplication in an EC field.

As you can see, being able to subtract in an Elliptic Curve field does not help you recover d_a.

I suppose bitcoin is not vulnerable to this attack? When I try to sign a transaction for multiple times, I find that the signatures are different. Is it related to this vulnerability?

As the quote mentions, Sony failed to implement ECDSA correctly.  One of the basic rules of cryptography is, if you implement the algorithm incorrectly, get ready for a world of pain.  Sony got a world of pain.

The Satoshi Bitcoin client is not vulnerable to the attack fail0verflow performed on the PS3, because the Satoshi Bitcoin client will always use a new, random k when generating signatures.

[Zeilap]

The points on an elliptic curve can be added (via the construction you describe) and similarly can be subtracted as you've worked out. By repeated addition, you get multiplication of a point by an integer.
The curve that is used in Bitcoin has the property that from a single point G, (for generator point) by repeatedly adding it to itself you get every point (with integer coordinates) on the elliptic curve.

In elliptic curve cryptography a private key, k, is simply an integer, and the public key is the point you get by adding G to itself k times. Given a general point on the curve, there is no known way to get back to the number k without simply trying every one until you get lucky.

The recovery of the Sony keys was because of a flaw in their implementation of the signing algorithm. The algorithm requires a random number which should be different every time something is signed. Sony used the same number every time and this allowed the private key to be recovered (though of course it took a long time before anyone realized that they were always using the same number). The signature is dependent on the random number, so repeatedly signing the same message should give a different signature every time.

[jl2012]

Q = d_a * G = G + G + G ........  + G (repeated for d_a times)

With a known Q (public key) and G, one could calculate Q - G - G - G....... until the solution equals to G, and deduces the value of d_a (private key). Is this correct? Is this impractical because this would take very long time to subtract that many G?

[Zeilap]

Yes and yes.

[fpgaminer]

Is this impractical because this would take very long time to subtract that many G?

To be specific, d_a is a random 256-bit number.  That means, on average, you would need to subtract G 57,896,044,618,658,097,711,785,492,504,343,953,926,634,992,332,820,282,019,728,792,003,956,564,819,968 times

To put that into perspective, modern CPUs run at 4GHz on the high-end.  If a CPU could add/subtract G once per cycle (far, far, far from possible), it would take that CPU, on average, 458,967,882,885,100,343,351,927,103,186,389,792,036,363,143,176,213,549,750,513 years to find the private key.  Or, you could just have that many CPUs churning for a year.

[jl2012]

Very interesting! Thanks a lot for your replies!

[Mike Hearn]

I feel the explanation is a little incomplete - it's clear why you cannot use point subtraction to find the answer because you need too many, but then that just leads to the question of why the initial multiplication (G+G+G+G+....) is tractable and the reverse operation isn't.

The reason is that there is an efficient way to double a point (2G * 2 == G+G+G+G). In a graphical sense you take the tangent line of the point and find where it intersects the curve. In a finite field you cannot really calculate the tangent in the high-school sense using the tan() function but there is an equation to do the equivalent.

So now it should become clear that given a point P multiplied by some number, say 5, we can double the point (2P), double it again (4P) and add a point to get 5P.

To efficiently calculate Q = d_a * G, you need to break it up into doubles and adds, the simplest algorithm is appropriately enough called "double-and-add" which is log2(d_a) - tractable! There are other better methods though, see here:

http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

One of them even uses point subtraction.