Print Page - question about ECDSA

Title: question about ECDSA
Post by: Topazan on December 16, 2013, 07:23:52 AM

Recently, I decided that I needed to better understand what goes on in the backend of cryptocurrency. I've slowly been trying to teach myself to comprehend the various backend protocols.

However, I'm a little confused about this (https://en.bitcoin.it/wiki/Secp256k1). From my understanding, the "base point" G should be a point, with both an x and a y value. However, it's given there as a single value, with a compressed and uncompressed form. The linked pdf doesn't seem to elaborate on this. What does this number mean, and how do you derive the x and y of the base point from it?

Thanks in advance.

Title: Re: question about ECDSA
Post by: Topazan on December 16, 2013, 08:10:53 AM

Ah, here we go. I found this in bitaddress.org's source code.

Code:

ec.CurveFp.prototype.decodePointHex = function (s) {
                var firstByte = parseInt(s.substr(0, 2), 16);
                switch (firstByte) { // first byte
                        case 0:
                                return this.infinity;
                        case 2: // compressed
                        case 3: // compressed
                                var yTilde = firstByte & 1;
                                var xHex = s.substr(2, s.length - 2);
                                var X1 = new BigInteger(xHex, 16);
                                return this.decompressPoint(yTilde, X1);
                        case 4: // uncompressed
                        case 6: // hybrid
                        case 7: // hybrid
                                var len = (s.length - 2) / 2;
                                var xHex = s.substr(2, len);
                                var yHex = s.substr(len + 2, len);

                                return new ec.PointFp(this,
                                        this.fromBigInteger(new BigInteger(xHex, 16)),
                                        this.fromBigInteger(new BigInteger(yHex, 16)));

                        default: // unsupported
                                return null;
                }
        };

So, I guess that answers that.

Title: Re: question about ECDSA
Post by: bluemeanie1 on December 16, 2013, 10:23:03 PM

Quote from: Topazan on December 16, 2013, 07:23:52 AM

An EC curve point is compressed by abbreviating the way the Y coordinate is expressed. There are really only two possible values of Y for any X, thus we only need to indicate if it is either positive or negative(1 bit).

while this isn't exactly a standard, more of a convention, typically you take the first byte off(the 0x04 in the uncompressed point) and then the remaining data is two 32 byte integers. As you can see from the example there in your link, in the compressed format, only the X coordinate of G is fully expressed.

Title: Re: question about ECDSA
Post by: kjj on December 16, 2013, 11:06:12 PM


G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 
G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Red - encoding marker. 04 = x then y. 02 = x only, y has even parity. 03 = x only, y has odd parity
Green - X
Blue - Y

Title: Re: question about ECDSA
Post by: Topazan on December 17, 2013, 02:51:04 AM

Thanks both of you.

So:

X=79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Y=483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Is this correct?

Title: Re: question about ECDSA
Post by: bluemeanie1 on December 17, 2013, 06:25:42 PM

Quote from: Topazan on December 17, 2013, 02:51:04 AM

Thanks both of you.

So:

X=79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Y=483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Is this correct?

that does look correct.

this image can help you understand point compression better, this is an elliptic curve:

http://cdn.arstechnica.net/wp-content/uploads/2013/10/elliptic-curve-crypt-image00.png

note that the vertical line intersects the curve at only 2 points. If you study the curve, you will see that this is true for any vertical line. This if we know the X(the position of the vertical line) then we've narrowed it down to two Y points that are perfect mirror images of each other on the X axis. Thus we only need to express the positive or negative component. This also suggests that the ECDSA algo could probably be refactored into simpler math terms, but as of now this is the best we have(that is fully proven).

Title: Re: question about ECDSA
Post by: Topazan on December 18, 2013, 04:26:37 AM

Thanks, that helps.

Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: Topazan on December 16, 2013, 07:23:52 AM