Skip to content

Instantly share code, notes, and snippets.

@DavidBuchanan314

DavidBuchanan314/decompress.ts

Last active August 31, 2025 16:41
Show Gist options
  • Save DavidBuchanan314/4f357c7d8247d744a0b19adbc5a01dbb to your computer and use it in GitHub Desktop.
Save DavidBuchanan314/4f357c7d8247d744a0b19adbc5a01dbb to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. DavidBuchanan314 revised this gist Aug 31, 2025. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion decompress.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -35,7 +35,7 @@ function pow16mod(a: bigint, n: bigint): bigint {
    return a
    }

    // efficiently-ish compute (a^p)%n
    // efficiently-ish compute (a^b)%n
    function powmod(a: bigint, b: bigint, n: bigint): bigint {
    const a_lut = [1n];
    for (let i=0; i<15; i++) {
  2. DavidBuchanan314 created this gist Aug 31, 2025.
    87 changes: 87 additions & 0 deletions decompress.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,87 @@
    /*
    NOTE: arithnetic here is NOT CONSTANT TIME
    This is mostly ok since we're operating on public keys.
    */

    const P256_P = BigInt("0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff");
    const P256_A = BigInt("0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc");
    const P256_B = BigInt("0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b");
    const P256_N = BigInt("0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551");
    const P256_P_PLUS_ONE_OVER_4 = (P256_P + 1n) / 4n;

    function BEu8toBigInt(buf: Uint8Array): bigint {
    return buf.reduce(
    (a, n, i) => a + (
    BigInt(n) << BigInt(8 * (buf.length - i - 1))
    ),
    0n
    );
    }

    // size in bytes
    function BigIntToBEu8(n: bigint, size: number): Uint8Array {
    return new Uint8Array([...Array(size)].map((_, i) =>
    Number(BigInt.asUintN(8, n >> BigInt((size - i - 1) * 8)))
    ))
    }

    // (a^16)%n
    function pow16mod(a: bigint, n: bigint): bigint {
    a = (a * a) % n;
    a = (a * a) % n;
    a = (a * a) % n;
    a = (a * a) % n;
    return a
    }

    // efficiently-ish compute (a^p)%n
    function powmod(a: bigint, b: bigint, n: bigint): bigint {
    const a_lut = [1n];
    for (let i=0; i<15; i++) {
    a_lut.push((a_lut[i] * a) % n);
    }
    return Array.from(b.toString(16)).reduce(
    (acc, bi) => ((pow16mod(acc, n) * a_lut[parseInt(bi, 16)])) % n,
    1n
    );
    }

    function p256decompress(compressed: Uint8Array): Uint8Array {
    if (!(compressed[0] === 2 || compressed[0] === 3)) {
    throw new Error("not a compressed point");
    }
    if (compressed.length !== 33) {
    throw new Error("invalid compressed point length");
    }

    const x = BEu8toBigInt(compressed.slice(1));

    const y_squared = (x ** 3n + P256_A * x + P256_B) % P256_P;

    // sqrt via tonelli shanks
    let y = powmod(y_squared, P256_P_PLUS_ONE_OVER_4, P256_P);

    // check the result is valid
    if (((y * y) % P256_P) != y_squared) {
    throw new Error("invalid curve point");
    }

    // parity correction
    if ((compressed[0] ^ Number(BigInt.asUintN(1, y))) & 1) {
    y = P256_P - y;
    }

    const res = new Uint8Array(1 + 32 + 32);
    res.set([4], 0);
    res.set(BigIntToBEu8(x, 32), 1);
    res.set(BigIntToBEu8(y, 32), 1 + 32);

    return res;
    }

    console.log(p256decompress(new Uint8Array([3, 6, 51, 14, 4, 53, 11, 220, 220, 210, 226, 96, 98, 247, 174, 134, 146, 179, 181, 149, 85, 92, 84, 143, 219, 95, 152, 13, 43, 46, 137, 149, 188])))
    console.log(p256decompress(new Uint8Array([2, 162, 161, 22, 14, 215, 20, 47, 145, 27, 220, 35, 23, 191, 119, 106, 245, 200, 208, 181, 246, 39, 153, 5, 130, 67, 253, 61, 230, 5, 234, 100, 88])))

    console.log(p256decompress(new Uint8Array([3, 143, 159, 2, 99, 165, 174, 89, 69, 27, 134, 252, 39, 253, 198, 211, 113, 58, 181, 114, 70, 138, 53, 236, 116, 197, 173, 162, 102, 6, 124, 89, 208])))
    console.log(p256decompress(new Uint8Array([2, 69, 244, 15, 230, 104, 128, 105, 163, 167, 150, 127, 147, 86, 80, 167, 229, 154, 55, 27, 155, 205, 38, 158, 233, 6, 0, 57, 41, 67, 103, 8, 215])))