Another ecdsa question (zinv in bitaddress.org)

[Topazan]

So, at the moment I'm trying to reverse engineer the bitaddress.org source code to improve my own understanding of cryptography and bitcoin specifically.

I was following along with this wikipedia page on elliptic curve point multiplication.

However, I'm a little confused by bitaddress.org's variable "zinv".  Related to it is the variable "z".  The wikipedia page doesn't seem to have anything like that, and I'd like to know what it is and what it does.

Also, I'd be willing to pay someone who can answer questions like these to tutor me privately, so I don't have to keep coming to these forums with my questions.

[1714098943]

1714098943

[1714098943]

1714098943

[1714098943]

1714098943

[1714098943]

1714098943

[Topazan]

For easy reference, let me quote the relevant section of the code:

Code:

ec.PointFp = function (curve, x, y, z, compressed) {
                this.curve = curve;
                this.x = x;
                this.y = y;
                // Projective coordinates: either zinv == null or z * zinv == 1
                // z and zinv are just BigIntegers, not fieldElements
                if (z == null) {
                        this.z = BigInteger.ONE;
                }
                else {
                        this.z = z;
                }
                this.zinv = null;
                // compression flag
                this.compressed = !!compressed;
        };

        ec.PointFp.prototype.getX = function () {
                if (this.zinv == null) {
                        this.zinv = this.z.modInverse(this.curve.q);
                }
                var r = this.x.toBigInteger().multiply(this.zinv);
                this.curve.reduce(r);
                return this.curve.fromBigInteger(r);
        };

        ec.PointFp.prototype.getY = function () {
                if (this.zinv == null) {
                        this.zinv = this.z.modInverse(this.curve.q);
                }
                var r = this.y.toBigInteger().multiply(this.zinv);
                this.curve.reduce(r);
                return this.curve.fromBigInteger(r);
        };

        ec.PointFp.prototype.equals = function (other) {
                if (other == this) return true;
                if (this.isInfinity()) return other.isInfinity();
                if (other.isInfinity()) return this.isInfinity();
                var u, v;
                // u = Y2 * Z1 - Y1 * Z2
                u = other.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(other.z)).mod(this.curve.q);
                if (!u.equals(BigInteger.ZERO)) return false;
                // v = X2 * Z1 - X1 * Z2
                v = other.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(other.z)).mod(this.curve.q);
                return v.equals(BigInteger.ZERO);
        };

        ec.PointFp.prototype.isInfinity = function () {
                if ((this.x == null) && (this.y == null)) return true;
                return this.z.equals(BigInteger.ZERO) && !this.y.toBigInteger().equals(BigInteger.ZERO);
        };

        ec.PointFp.prototype.negate = function () {
                return new ec.PointFp(this.curve, this.x, this.y.negate(), this.z);
        };

        ec.PointFp.prototype.add = function (b) {
                if (this.isInfinity()) return b;
                if (b.isInfinity()) return this;

                // u = Y2 * Z1 - Y1 * Z2
                var u = b.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(b.z)).mod(this.curve.q);
                // v = X2 * Z1 - X1 * Z2
                var v = b.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(b.z)).mod(this.curve.q);


                if (BigInteger.ZERO.equals(v)) {
                        if (BigInteger.ZERO.equals(u)) {
                                return this.twice(); // this == b, so double
                        }
                        return this.curve.getInfinity(); // this = -b, so infinity
                }

                var THREE = new BigInteger("3");
                var x1 = this.x.toBigInteger();
                var y1 = this.y.toBigInteger();
                var x2 = b.x.toBigInteger();
                var y2 = b.y.toBigInteger();

                var v2 = v.square();
                var v3 = v2.multiply(v);
                var x1v2 = x1.multiply(v2);
                var zu2 = u.square().multiply(this.z);

                // x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
                var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.q);
                // y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
                var y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.curve.q);
                // z3 = v^3 * z1 * z2
                var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.q);

                return new ec.PointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
        };

        ec.PointFp.prototype.twice = function () {
                if (this.isInfinity()) return this;
                if (this.y.toBigInteger().signum() == 0) return this.curve.getInfinity();

                // TODO: optimized handling of constants
                var THREE = new BigInteger("3");
                var x1 = this.x.toBigInteger();
                var y1 = this.y.toBigInteger();

                var y1z1 = y1.multiply(this.z);
                var y1sqz1 = y1z1.multiply(y1).mod(this.curve.q);
                var a = this.curve.a.toBigInteger();

                // w = 3 * x1^2 + a * z1^2
                var w = x1.square().multiply(THREE);
                if (!BigInteger.ZERO.equals(a)) {
                        w = w.add(this.z.square().multiply(a));
                }
                w = w.mod(this.curve.q);
                //this.curve.reduce(w);
                // x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
                var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.q);
                // y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
                var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.square().multiply(w)).mod(this.curve.q);
                // z3 = 8 * (y1 * z1)^3
                var z3 = y1z1.square().multiply(y1z1).shiftLeft(3).mod(this.curve.q);

                return new ec.PointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
        };

        // Simple NAF (Non-Adjacent Form) multiplication algorithm
        // TODO: modularize the multiplication algorithm
        ec.PointFp.prototype.multiply = function (k) {
                if (this.isInfinity()) return this;
                if (k.signum() == 0) return this.curve.getInfinity();

                var e = k;
                var h = e.multiply(new BigInteger("3"));

                var neg = this.negate();
                var R = this;

                var i;
                for (i = h.bitLength() - 2; i > 0; --i) {
                        R = R.twice();

                        var hBit = h.testBit(i);
                        var eBit = e.testBit(i);

                        if (hBit != eBit) {
                                R = R.add(hBit ? this : neg);
                        }
                }

                return R;
        };

        // Compute this*j + x*k (simultaneous multiplication)
        ec.PointFp.prototype.multiplyTwo = function (j, x, k) {
                var i;
                if (j.bitLength() > k.bitLength())
                        i = j.bitLength() - 1;
                else
                        i = k.bitLength() - 1;

                var R = this.curve.getInfinity();
                var both = this.add(x);
                while (i >= 0) {
                        R = R.twice();
                        if (j.testBit(i)) {
                                if (k.testBit(i)) {
                                        R = R.add(both);
                                }
                                else {
                                        R = R.add(this);
                                }
                        }
                        else {
                                if (k.testBit(i)) {
                                        R = R.add(x);
                                }
                        }
                        --i;
                }

                return R;
        };

        // patched by bitaddress.org and Casascius for use with Bitcoin.ECKey
        // patched by coretechs to support compressed public keys
        ec.PointFp.prototype.getEncoded = function (compressed) {
                var x = this.getX().toBigInteger();
                var y = this.getY().toBigInteger();
                var len = 32; // integerToBytes will zero pad if integer is less than 32 bytes. 32 bytes length is required by the Bitcoin protocol.
                var enc = ec.integerToBytes(x, len);

                // when compressed prepend byte depending if y point is even or odd
                if (compressed) {
                        if (y.isEven()) {
                                enc.unshift(0x02);
                        }
                        else {
                                enc.unshift(0x03);
                        }
                }
                else {
                        enc.unshift(0x04);
                        enc = enc.concat(ec.integerToBytes(y, len)); // uncompressed public key appends the bytes of the y point
                }
                return enc;
        };

        ec.PointFp.decodeFrom = function (curve, enc) {
                var type = enc[0];
                var dataLen = enc.length - 1;

                // Extract x and y as byte arrays
                var xBa = enc.slice(1, 1 + dataLen / 2);
                var yBa = enc.slice(1 + dataLen / 2, 1 + dataLen);

                // Prepend zero byte to prevent interpretation as negative integer
                xBa.unshift(0);
                yBa.unshift(0);

                // Convert to BigIntegers
                var x = new BigInteger(xBa);
                var y = new BigInteger(yBa);

                // Return point
                return new ec.PointFp(curve, curve.fromBigInteger(x), curve.fromBigInteger(y));
        };

        ec.PointFp.prototype.add2D = function (b) {
                if (this.isInfinity()) return b;
                if (b.isInfinity()) return this;

                if (this.x.equals(b.x)) {
                        if (this.y.equals(b.y)) {
                                // this = b, i.e. this must be doubled
                                return this.twice();
                        }
                        // this = -b, i.e. the result is the point at infinity
                        return this.curve.getInfinity();
                }

                var x_x = b.x.subtract(this.x);
                var y_y = b.y.subtract(this.y);
                var gamma = y_y.divide(x_x);

                var x3 = gamma.square().subtract(this.x).subtract(b.x);
                var y3 = gamma.multiply(this.x.subtract(x3)).subtract(this.y);

                return new ec.PointFp(this.curve, x3, y3);
        };

        ec.PointFp.prototype.twice2D = function () {
                if (this.isInfinity()) return this;
                if (this.y.toBigInteger().signum() == 0) {
                        // if y1 == 0, then (x1, y1) == (x1, -y1)
                        // and hence this = -this and thus 2(x1, y1) == infinity
                        return this.curve.getInfinity();
                }

                var TWO = this.curve.fromBigInteger(BigInteger.valueOf(2));
                var THREE = this.curve.fromBigInteger(BigInteger.valueOf(3));
                var gamma = this.x.square().multiply(THREE).add(this.curve.a).divide(this.y.multiply(TWO));

                var x3 = gamma.square().subtract(this.x.multiply(TWO));
                var y3 = gamma.multiply(this.x.subtract(x3)).subtract(this.y);

                return new ec.PointFp(this.curve, x3, y3);
        };

        ec.PointFp.prototype.multiply2D = function (k) {
                if (this.isInfinity()) return this;
                if (k.signum() == 0) return this.curve.getInfinity();

                var e = k;
                var h = e.multiply(new BigInteger("3"));

                var neg = this.negate();
                var R = this;

                var i;
                for (i = h.bitLength() - 2; i > 0; --i) {
                        R = R.twice();

                        var hBit = h.testBit(i);
                        var eBit = e.testBit(i);

                        if (hBit != eBit) {
                                R = R.add2D(hBit ? this : neg);
                        }
                }

                return R;
        };

        ec.PointFp.prototype.isOnCurve = function () {
                var x = this.getX().toBigInteger();
                var y = this.getY().toBigInteger();
                var a = this.curve.getA().toBigInteger();
                var b = this.curve.getB().toBigInteger();
                var n = this.curve.getQ();
                var lhs = y.multiply(y).mod(n);
                var rhs = x.multiply(x).multiply(x).add(a.multiply(x)).add(b).mod(n);
                return lhs.equals(rhs);
        };

        ec.PointFp.prototype.toString = function () {
                return '(' + this.getX().toBigInteger().toString() + ',' + this.getY().toBigInteger().toString() + ')';
        };

        /**
        * Validate an elliptic curve point.
        *
        * See SEC 1, section 3.2.2.1: Elliptic Curve Public Key Validation Primitive
        */
        ec.PointFp.prototype.validate = function () {
                var n = this.curve.getQ();

                // Check Q != O
                if (this.isInfinity()) {
                        throw new Error("Point is at infinity.");
                }

                // Check coordinate bounds
                var x = this.getX().toBigInteger();
                var y = this.getY().toBigInteger();
                if (x.compareTo(BigInteger.ONE) < 0 || x.compareTo(n.subtract(BigInteger.ONE)) > 0) {
                        throw new Error('x coordinate out of bounds');
                }
                if (y.compareTo(BigInteger.ONE) < 0 || y.compareTo(n.subtract(BigInteger.ONE)) > 0) {
                        throw new Error('y coordinate out of bounds');
                }

                // Check y^2 = x^3 + ax + b (mod n)
                if (!this.isOnCurve()) {
                        throw new Error("Point is not on the curve.");
                }

                // Check nQ = 0 (Q is a scalar multiple of G)
                if (this.multiply(n).isInfinity()) {
                        // TODO: This check doesn't work - fix.
                        throw new Error("Point is not a scalar multiple of G.");
                }

                return true;
        };

[deepceleron]

You can also examine "### Elliptic Curve functions" in:
https://github.com/vbuterin/pybitcointools/blob/master/pybitcointools/main.py

[altoz]

zinv is the modulo inverse of z.

That is, z * zinv = 1 (identity element)

I believe you do this to get the actual modulo inverse

zinv = z ^ (p-2) mod p

You can find information on this here: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

[Topazan]

Thanks for the answers.

zinv is the modulo inverse of z.

I can see that from the code.  But what's z and why do we need its modulo inverse?  Neither value is mentioned in the wikipedia.

zinv = z ^ (p-2) mod p

Thanks, I'll make a note of that.

[kjj]

uh...

You will gain no insight into bitcoin or the cryptography it uses by studying any given efficient multiply implementation.  Your time would be much better spent treating the EC math libraries as black boxes until much later.

[Topazan]

What will I understand much later that will help me understand this?

I don't know, I just feel like being a self-taught developer I miss out on a lot of theory and mathematics that would really help my projects.  I kind of wanted to do this "right".

So, is what you're saying that bitaddress uses a different multiply implementation than the wiki article?  I kind of suspected that was the case.

All I want to do in the short term is get to the point where I can generate public addresses from private keys without relying on a library.

[Topazan]

You can also examine "### Elliptic Curve functions" in:
https://github.com/vbuterin/pybitcointools/blob/master/pybitcointools/main.py

This is awesome, thanks.