CODEWITHSUNDEEP
node.jscryptographyelliptic-curvediffie-hellman
undefined7887
undefined7887

Reputation: 111

ECDH private key size

I know that key sizes in ECDH depend on size of Elliptic Curve.

If it is a 256-bit curve (secp256k1), keys will be:

Public: 32 bytes * 2 + 1 = 65 (uncompressed)
Private: 32 bytes

384-bit curve (secp384r1):

Public: 48 bytes * 2 + 1= 97 (uncompressed)
Private: 48 bytes

But with 521-bit curve (secp521r1) situation is very strange:

Public: 66 bytes * 2 + 1 = 133 (uncompressed)
Private: 66 bytes or 65 bytes.

I used node.js crypto module to generate this keys.

Why private key value of 521-bit curve is variable?

Upvotes: 4

Views: 4464

Answers (1)

Maarten Bodewes
Maarten Bodewes

Reputation: 93958

The private key of the other curves are variable as well, but they are less likely to exhibit this variance when it comes to encoding to bytes.

The public key is encoded as two statically sized integers, prefixed with the uncompressed point indicator 04. The size is identical to the key size in bytes.

The private key doesn't really have an pre-established encoding. It is a single random value (or vector) within the range 1..N-1 where N is the order of the curve. Now if you encode this value as a variable sized unsigned number then usually it will be the same size as the key in bytes. However, it may by chance be one byte smaller, or two, or three or more. Of course, the chance that it is much smaller is pretty low.

Now the 521 bit key is a bit strange that the first, most significant byte of the order doesn't start with a bit set to 1; it only has the least significant bit set to 1. This means that there is a much higher chance that the most significant byte of the private value (usually called s) is a byte shorter.

The exact chance of course depends on the full value of the order:

01FF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
     FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFA
     51868783 BF2F966B 7FCC0148 F709A5D0
     3BB5C9B8 899C47AE BB6FB71E 91386409

but as you may guess it is pretty close to 1 out of 2 because there are many bits set to 1 afterwards. The chance that two bytes are missing is of course 1 out of 512, and three bytes 1 out of 131072 (etc.).

Note that ECDSA signature sizes may fluctuate as well. The X9.42 signature scheme uses two DER encoded signed integers. The fact that they are signed may introduces a byte set all to zeros if the most significant bit of the most significant byte is set to 1, otherwise the value would be interpreted as being negative. The fact that it consists of two numbers, r and s, and that the size of DER encoding is also dependent of the size of the encoded integers makes the size of the full encoding rather hard to predict.

Another less common (flat) encoding of an ECDSA signature uses the same statically sized integers as the public key, in which case it is just twice the size of the order N in bytes.

ECDH doesn't have this issue. Commonly the shared secret is the statically encoded X coordinate of the point that is the result of the ECDH calculation - or at least a value that is derived from it using a Key Derivation Function (KDF).

Upvotes: 3

Related Questions