Leading 00 in RSA public/private key file

Question

I found these following values ALWAYS have the leading 00 in public/private key,

public key: modulus

private key: modulus, p,q, d mod (p-1), d mod (q-1), coefficient

e.g., modulus

0007:    02 81 81                               ; INTEGER (81 Bytes)
000a:    |  00   <= the leading 00
000b:    |  da ff 24 57 07 8a 4c b8  63 79 79 ff 55 27 10 15
001b:    |  0f 6c ab 0e 17 dc 05 1a  d3 4f 85 77 6c a6 89 37
002b:    |  8c 83 11 3d 5e 11 15 4b  34 5e 5c dd fd 3f a6 dc
003b:    |  6e 3e ff 97 be 5b 49 2a  78 10 f1 bf 80 d6 09 36
004b:    |  34 bd 99 5f 40 d6 1c 41  8d 3a d8 75 b9 53 b2 40
005b:    |  fb e6 97 72 31 f7 bf 81  5e 75 04 e7 35 0d 98 3b
006b:    |  54 83 3f 9d e8 66 3b e6  2f c9 63 98 63 9f d7 88
007b:    |  99 85 75 d1 21 24 e9 1a  9e 3c da 41 7e 92 5f f1 

Could someone tell me why RSA public/private key need the leading 00 ?

Answer 1

You are looking at the ASN.1 encoding of private (and public) keys; the 00 values you see are an artifact of how ASN.1 encodes integers.

ASN.1 is a method for describing data structures, and has ways to represents all sorts of data types. It wasn't designed with public keys (or cryptography) in mind; it was intended for more general use, initially telecommunications. When it encodes an integer, it has the ability to represent a negative integer.

When we use the BER encoding rules for ASN.1 (which is how ASN.1 are usually encoded in practice), here is how it may represent an integer:

<Tag> <Length> <Value of the integer>

where:

• <Tag>: 02 is the magic value for "this is an integer"

• <Length>: 81 81 is a variable sized length field that says how many bytes are in the binary value

• <Value of the integer>: 00 da ff ... 5f f1 is the binary encoded integer value, in signed big endian form

This is called a Tag-Length-Value encoding or TLV in short.

Now, the rules say that if the most significant bit of the <Value of the integer> field is a 1, the encoded integer is negative (using two's-complement encoding); if it is 0 then the integer is positive (or zero).

Here are the implications of that; if we were to encode the modulus you state as a 256 byte binary value, we would have the binary value as da ff 24 ... 5f f1. However, if we were to use that as the representation, the decoder would look at the most significant bit of the first byte (da), see that the most significant bit is 1, and interpret that as a negative integer.

In this case, it is required to encode this as a 257 byte binary value, and have the binary value include a leading 0, that is, as 00 da ff 24 ... 5f f1. In this case, the decoder would look at the most significant bit of the first byte (00 in this case), see that the most significant bit is 0, and interpret that as a positive integer. And, since adding a leading zero doesn't change the represented value, the decoded integer would be the one we want.

This happens whenever the encoded integer is a multiple of 8 bits in length.

We typically select RSA modulus sizes which are powers of two or small multiples thereof (1024, 1536, 2048, 3072, etc), and so this typically happens there.

And, when we select the primes, we typically split the primes evenly. For example, when we generate a 2048-bit RSA key, we would typically select two 1024 bit primes; these primes are hence typically multiples of 8 bits in length. And at least one, usually both, must be towards the higher end of the noninclusive range $(2^{1023}, 2^{1024})$ to ensure $n$ is over $2^{2047}$.

The other CRT parameters ($d \bmod p-1$, $d \bmod q-1$, $q^{-1} \bmod p$) are for practical purposes random numbers up to nearly $p$ or $q$, so given the typical values for $p$ and $q$ above, roughly 1/3 of the time these are the same number of bits (1024) and need the extra 00, roughly 2/3 of the time they are 1 to 7 bits smaller and need the same number of octets but no extra 00 or 8 bits smaller and need one less octet for the magnitude plus the 00, and roughly 1/400 of the time they are small enough to need fewer octets.

This rule about an 'extra' 00 applies to both BER and DER, a commonly used subset of BER; see 8.3.2 in X.690. BER gives a choice to include 'redundant' information while DER does not; DER only allows one well defined encoding for a specific type and value combination.

One case where the 00 is typically not included is the public exponent $e$. The most common value for that is 65537, or 01 00 01 in binary. The leading bit here is 0, and so a leading 00 byte is not required; hence the typical encoding for this exponent is 02 03 01 00 01.

Answer 2

I have seen this before in Java. Java's BigInteger class requires and generates binary data as signed little-endian. If the high bit of the first byte is set, the whole number is interpreted as negative.

In order to represent a 1024-bit number in which bit 1023 is set, it's therefore needed to add a 00 byte to the beginning, because otherwise, it'd be interpreted as negative.