Why are secp256k1 privateKeys not always 32 bytes in nodejs?

Question

I was generating a lot of secp256k1 keys using node's crypto module when I ran into a problem that some generated private keys were not always 32bytes in length. I wrote a test script and it shows clearly that that happens quite often.

What is the reason for that and is there a fix or do I have to check for length and then regenerate until I get 32 bytes?

This is the test script for reproducing the issue:

const { createECDH, ECDH } = require("crypto");

const privateLens = {};
const publicLens = {};

for(let i = 0; i < 10000; i++){
    const ecdh = createECDH("secp256k1");
    ecdh.generateKeys();
    const privateKey = ecdh.getPrivateKey("hex");
    const publicKey = ecdh.getPublicKey("hex");

    privateLens[privateKey.length+""] = (privateLens[privateKey.length+""] || 0) + 1;
    publicLens[publicKey.length+""] = (publicLens[publicKey.length+""] || 0) + 1;

}

console.log(privateLens);
console.log(publicLens);

The output (of multiple runs) looks like this:

% node test.js
{ '62': 32, '64': 9968 }
{ '130': 10000 }
% node test.js
{ '62': 40, '64': 9960 }
{ '130': 10000 }
% node test.js
{ '62': 39, '64': 9961 }
{ '130': 10000 }

I just don't get it... if I encode it in base64 its always the same length, but decoding that back to a buffer shows 31 bytes for some keys again.

Thanks, any insights are highly appreciated!

Answer 1

For EC cryptography the key is not fully random over the bytes, it's a random number in the range [1, N) where N is the order of the curve. Now generally the number generated will be in the same ballpark as the 256 bit order. This is especially true since N has been (deliberately) chosen to be very close to 2^256, i.e. the high order bits are all set to 1 for secp256k1.

However, about once in 256, the first bits are still all set to zero for the chosen private key s. That means that it takes 31 or fewer bytes instead of 32 bytes. Once in 65536 it will be even 30 bytes instead of 32, etc. And once in somewhere over 4 billion times (short scale) it will even use 29 bytes.

Base64 uses one character for 6 bits excluding overhead. However generally it just encodes blocks of 3 bytes to 4 characters at a time (possibly including padding with = characters). That means that 32 bytes will take ceil(32 / 3) * 4 = 44 bytes. Now since ceil(31 / 3) * 4 = 44 you won't notice anything. However, once in 65536 times you'll get ceil(30 / 3) * 4 = 40. After that going to 36 characters becomes extremely unlikely (although not negligibly small cryptographically speaking, "just" once in 2^48 times - there are lotteries that do worse I suppose)...

So no, you don't have to regenerate the keys - for the algorithm they are perfectly valid after all. For private keys you don't generally have much compatibility requirements, however generally you'd try and encode such keys to a static size (32 bytes, possibly using 00 valued bytes at the left). Re-encoding them as statically sized keys might be a good idea...