6
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ You should not be using 1024 bit keys anymore. Check keylength.com for more current sizes. $\endgroup$ – Maarten Bodewes Nov 18 '15 at 10:35
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @MattElson: values don't have 'first bytes', representations of values do. So, what format (representation) of public/private key were you looking at? $\endgroup$ – poncho Nov 17 '15 at 15:28
  • $\begingroup$ According to my example, 00 is the first byte of modulus. $\endgroup$ – Matt Elson Nov 17 '15 at 15:35
  • $\begingroup$ @MattElson: so, where did you get your example from? $\endgroup$ – poncho Nov 17 '15 at 15:38
  • $\begingroup$ Since this is complete and mostly great already, proposed edit on two substantial points and some minor fixes; dispose as you wish. $\endgroup$ – dave_thompson_085 Nov 18 '15 at 0:36
  • $\begingroup$ Minor note: you would often also see a 00 byte in front of the value if you encode a value as an ASN.1 BIT STRING instead of INTEGER. In that case the 00 is the number of bits of padding; as most values are encoded in bytes, not bits, the padding is usually 0. Rather different reason, same result. $\endgroup$ – Maarten Bodewes Nov 18 '15 at 10:18
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ BigInteger can construct from big-endian signed two's-complement byte[], OR magnitude-only byte[] with separate signum, OR String of digits in decimal or any sensible radix; and can convert back to all of those except the second. $\endgroup$ – dave_thompson_085 Nov 18 '15 at 0:44
  • $\begingroup$ @Myria new BigInteger(1, byte[] modulus) would solve that. You are right about the encoding though, that always returns a signed representation which is a major pain which should be solved asap by Oracle (because of the overhead of the intermediate byte array, one of the drawbacks of not having pointer arithmetic / immutable arrays). Still, a -1 because this is indeed an ASN.1 issue as poncho already explained in his answer. $\endgroup$ – Maarten Bodewes Nov 18 '15 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.