Nsryjdtyk

I'm using Javascript to generate elliptic curves for use in a cryptographic messaging app based on this example code http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html

The public keys will be quite large and I know it's possible to compress them, but I've been unable to find a Javascript or outline algorithm to do this. Here's an article http://nmav.gnutls.org/2012/01/do-we-need-elliptic-curve-point.html that outlines the maths.

I imagine they'll be increased interest in a JavaScript elliptic curve point compression solution, with WebCrypto support filtering into browsers.

I'll use the NIST curves as the example, because these the ones I had to deal with when importing a compressed public key into WebCrypto.

Curves and their primes

NIST P-256 (secp256r1) 2^256 - 2^224 + 2^192 + 2^96 - 1

NIST P-384 (secp384r1) 2^384 - 2^128 - 2^96 + 2^32 - 1

NIST P-521 (secp521r1) 2^521 - 1

These prime numbers all satisfy the equation, p mod 4 === 3

What this means is you can skip the somewhat complex general purpose Tonelli-Shanks algorithm, and use a simple identity to find the square roots.

First, the compression part of 'point compression' is very simple. Record the sign of Y, then discard the value of Y.

/**

 * Point compress elliptic curve key

 * @param {Uint8Array} x component

 * @param {Uint8Array} y component

 * @return {Uint8Array} Compressed representation

 */

function ECPointCompress( x, y )

{

    const out = new Uint8Array( x.length + 1 );



    out[0] = 2 + ( y[ y.length-1 ] & 1 );

    out.set( x, 1 );



    return out;

}

Decompression involves looking up the square root, then correcting depending on the Y parity bit.
This function depends on a JavaScript big integer library which exposes the following functions: add, sub, multiply, pow, modPow.

// Consts for P256 curve. Adjust accordingly

const two = new bigInt(2),

// 115792089210356248762697446949407573530086143415290314195533631308867097853951

prime = two.pow(256).sub( two.pow(224) ).add( two.pow(192) ).add( two.pow(96) ).sub(1),

b = new bigInt( '41058363725152142129326129780047268409114441015993725554835256314039467401291' ),

// Pre-computed value, or literal

pIdent = prime.add(1).divide(4); // 28948022302589062190674361737351893382521535853822578548883407827216774463488





/**

 * Point decompress NIST curve

 * @param {Uint8Array} Compressed representation

 * @return {Object} Explicit x & y

 */

function ECPointDecompress( comp )

{

    const signY = comp[0] - 2, // This value must be 2 or 3. 4 indicates an uncompressed key, and anything else is invalid.

    x = comp.subarray(1),

    // Import x into bigInt library

    xBig = new bigInt( x );



    // y^2 = x^3 - 3x + b

    var yBig = xBig.pow(3).sub( xBig.multiply(3) ).add( b ).modPow( pIdent, prime );



    // If the parity doesn't match it's the *other* root

    if( yBig.mod(2) !== signY )

    {

        // y = prime - y

        yBig = prime.sub( yBig );

    }



    return {

        x: x,

        y: yBig.toUint8Array()

    };

}

It would be difficult to patent a methematical formula alone. The use of a quadratic equation y = sqrt(x^3+ax+b) can't be patented, and if it is, cannot be protected. One can certainly claim prior art from Diophantes (200-298 AD). and the work around Hall conjecture (circa 1971) about the smallest absolute difference betwwen a square and a cube |y^2 - x^3| being rarely less than x. Rewrite it y^2 - x^3 = ax-b with x < b/a and remark that solutions in modular groups would help reduce the amount of brute force search in integers.

What is patented is the bit which helps to figure out the sign of y. This bit can be used to discriminate the largest of the solution from (y and M-y), or the positive solution from (y, -y), depending the standards you look at.

But since the patent has been accepted, you need to seek a legal advice.

As a reputable cryptographer well versed in the skills of the art Dr. Dan Bernstein points judiciously ( http://cr.yp.to/ecdh/patents.html ), the idea of recomputing y from x is mentioned in Miller 1986 as a triviality to reduce the footprint of elliptic curves points in memory-based systems.

A lawyer specialized in patent claims could help you to assess if the patent still applies if you do not use a normal basis as a representation of the point coordinates, or in the case of ecc in gf(p), or if you do not use a bit to recode the compressed value of y, e.g. when choosing the randomness k, P1(x1,y1) and computing P2(x2,y2) = [k]P1 until tr(y1) == tr(y2) removes the ambiguity (a little bit CPU costly, but why not ?).

Alternatively, you can point that the resolution of the quadratic formula is evidently more costly than the few bits saved on a communication channels and this patent is not useful at all, and even damaging for the environment by suggesting the replacement of 6 picowatts of transmission costs by 2 miliwatts of CPU costs (To be acceptable, a patent submission must be new, non-trivial and useful). Then you find a crooked lawyer preferably in California and for sure, there will be a local judge to award you a few $billions for the damages caused to the environment, for the distress caused to your programming skills and to your wallet considering the resulting delays in the release of your valuable application.

Else, as suggested in another post, you go for a licensing solution.

If your application is for the US government, you need another lawyer to assess if this patent and the way you plan to use it is already part of the licences purchased by NSA in the context of the "Suite B" of algorithms, in which case the license could already be payed for by the people of the US.

Compression of elliptic curve points is patented by Certicom, so you should not use it without the license, generally.

Update: Certicom's patent was expired in 2014, according to the comment by denis bider below.

Code for converting bitcoin compressed public key (ECDSA public key) to an 65 bytes of an uncompressed public key, using secp256k1 curve consts, with javascript big integer library latest version 1.6.36, and it can work with hex string directly

const bigInt = require("big-integer");



function pad_with_zeroes(number, length) {

    var retval = '' + number;

    while (retval.length < length) {

        retval = '0' + retval;

    }

    return retval;

}



// Consts for secp256k1 curve. Adjust accordingly

// https://en.bitcoin.it/wiki/Secp256k1

const prime = new bigInt('fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f', 16),

pIdent = prime.add(1).divide(4);



/**

 * Point decompress secp256k1 curve

 * @param {string} Compressed representation in hex string

 * @return {string} Uncompressed representation in hex string

 */

function ECPointDecompress( comp ) {

    var signY = new Number(comp[1]) - 2;

    var x = new bigInt(comp.substring(2), 16);

    // y mod p = +-(x^3 + 7)^((p+1)/4) mod p

    var y = x.modPow(3, prime).add(7).mod(prime).modPow( pIdent, prime );

    // If the parity doesn't match it's the *other* root

    if( y.mod(2).toJSNumber() !== signY ) {

        // y = prime - y

        y = prime.subtract( y );

    }

    return '04' + pad_with_zeroes(x.toString(16), 64) + pad_with_zeroes(y.toString(16), 64);

}

Example with private key: 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641

ECPointDecompress('0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267')

returns: '0414fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267be5645686309c6e6736dbd93940707cc9143d3cf29f1b877ff340e2cb2d259cf'

code for ECPointDecompress above from @Adria is unfortunately outdated, it is using a very old version of JavaScript big integer library

I rewrite ECPointDecompress with big integer library latest version 1.6.36, and it can work with hex string directly, do not need to use Uint8Array:

const bigInt = require("big-integer");



// Consts for P256 curve. Adjust accordingly

const two = new bigInt(2),

// 115792089210356248762697446949407573530086143415290314195533631308867097853951

prime = two.pow(256).subtract( two.pow(224) ).add( two.pow(192) ).add( two.pow(96) ).subtract(1),

b = new bigInt( '41058363725152142129326129780047268409114441015993725554835256314039467401291' ),

// Pre-computed value, or literal

// 28948022302589062190674361737351893382521535853822578548883407827216774463488

pIdent = prime.add(1).divide(4);



function pad_with_zeroes(number, length) {

    var retval = '' + number;

    while (retval.length < length) {

        retval = '0' + retval;

    }

    return retval;

}



/**

 * Point decompress NIST curve

 * @param {string} Compressed representation in hex string

 * @return {string} Uncompressed representation in hex string

 */

function ECPointDecompress( comp ) {

    var signY = new Number(comp[1]) - 2;

    var x = new bigInt(comp.substring(2), 16);

    // y^2 = x^3 - 3x + b

    var y = x.pow(3).subtract( x.multiply(3) ).add( b ).modPow( pIdent, prime );

    // If the parity doesn't match it's the *other* root

    if( y.mod(2).toJSNumber() !== signY ) {

        // y = prime - y

        y = prime.subtract( y );

    }

    return '04' + pad_with_zeroes(x.toString(16), 64) + pad_with_zeroes(y.toString(16), 64);

}

This can be used to convert compressed public key (ECDSA public key) to an 65 bytes of an uncompressed public key, but note that bitcoin's compressed public key is created using secp256k1 curve, which is different to the curve that we used in this code: NIST P-256 (secp256r1) 2^256 - 2^224 + 2^192 + 2^96 - 1

Therefore, above code can not be used to convert bitcoin's compressed public key, looking for converter of bitcoin compressed public key with secp256k1 curve consts, refer to https://stackoverflow.com/a/53480175/5630352

Examples:

ECPointDecompress('030ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca4593')

returns: '040ce2995c738e2320a5dea2df51b99d88bc5dd38356ba72e51ecc0ca660ca45936215a67f6e3fa1d72f6ef46aa2b7481991427b8764ff90447c6215d8dc931773'

ECPointDecompress('0267bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e')

returns: '0467bc6cae41a4579cda2556818bc942a38321cad961028bc74459f36ddca71e0e7c52f0e9f82bd1b2ba81935ba125cb1030d1ade1bd0306b3579a951418b858e8'