Algorithm for elliptic curve point compression

Question

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.

For ECDH you don't actually need point compression. In many cases it's sufficient to only use a single coordinate in the first place. — CodesInChaos
@CodesInChaos Can you explain that a little bit more ? or perhaps do you have a reference ? Thanks. — Ian Purton
Looks like he mixed together result of calculation and storage of public keys. In most standards x coordinate of resulting ECDH point is used as source for shared secret. — Nickolay Olshevsky

Adria Adria · Accepted Answer · 2015-05-25T05:06:50

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()
    };
}

Algorithm for elliptic curve point compression

5 Answers