OpenSSL generates 1032bits when I request 1024bits

When I enter the command-line openssl dhparam -text 1024 the resulting safe-prime is 1032 bits instead of 1024 bits. It seems like the 1st byte is always 0. Why is this?

Try this:

openssl genrsa | openssl rsa -text

Look at each of the fields; the primes, the exponents, all of them. Now try again, and again, and again. You'll notice some inconsistency as to whether an initial zero byte is present. Sometimes it is, sometimes it's not. The pattern is this: if the first bit of the first "real" byte is set -- that is, if the first hex character is less than 8 -- then there won't be an initial zero displayed (or stored), but if it's 8 or higher, then a zero byte will be prepended.

This makes it pretty clear that the problem they're solving is sign interpretation. With signed values, the first bit is the sign of the number; adding an initial zero removes any ambiguity.

To see what's actually stored (not displayed) look at this:

openssl genrsa | openssl asn1parse

You'll see that the while only 64 or 32 bytes are displayed, you'll see l= 33 or l= 65 indicating that one extra byte is actually stored. That's your initial zero byte you saw earlier.

As for 32-bit DH keys, look at this:

\$ openssl dhparam 32 -text
Generating DH parameters, 32 bit long safe prime, generator 2
This is going to take a long time

PKCS#3 DH Parameters: (32 bit)
prime: 2714658203 (0xa1ce659b)
generator: 2 (0x2)

So, that looks like only 4 bytes even though the initial bit is set. But let's look at the asn1parse:

0:d=0  hl=2 l=  10 cons: SEQUENCE
2:d=1  hl=2 l=   5 prim: INTEGER           :A1CE659B
9:d=1  hl=2 l=   1 prim: INTEGER           :02

So for this 32-bit prime, 5 bytes are stored even though you only saw 4 bytes displayed.

The reason you didn't see the zero byte this time is that since the stored value is only 32-bits, it can be displayed as a simple unsigned integer, and therefore OpenSSL's display library accordingly shows you the decimal value and the hex value in parens instead of just showing you a string of hex bytes separated by colons. But the initial zero is still there, as we saw in the asn1 output.

• Ok, that is indeed the more exhaustive answer. ;) – mkl Aug 5 '13 at 5:11
• @mki I prefer "exhausting". It took me nearly an hour to write, as I didn't actually know the answer when I started. – tylerl Aug 5 '13 at 5:30

You really get a 1024-bit prime: a 1024-bit prime is an integer whose value is greater than 21023 but lower than 21024. That's what OpenSSL returns you. However, when it comes to storing that integer into a file, some encoding convention must be used to turn that integer into bytes. OpenSSL uses ASN.1 with the DER (Distinguished Encoding Rules).

In ASN.1, the type is INTEGER, that is a generic integer value which could potentially be negative. The DER rules state that the INTEGER will encode as a tag (02, the standard tag for INTEGER) then a length (81 81, meaning "129": the value will be a sequence of 129 bytes), then the value itself, with big-endian signed interpretation. The important word here is "signed": since an INTEGER could be negative, but your prime is positive, its encoding must begin with a bit of value 0. If the prime was encoded over exactly 128 bytes, the first bit of the first byte would be a 1, and the INTEGER would be considered negative. Thus, an extra byte 00 is added (as per DER rules, the encoded must have minimal length provided that the first bit matches the expected sign, so only a single byte 00 may be added). The total length, with the header, is 132 bytes. The mathematical integer which is thus encoded is still a 1024-bit prime, not a 1032-bit or a 1056-bit integer.

If the highest bit in the 1024 bit value is set, a 0 byte is prepended because without that the number would be interpreted as a negative number.

• Really? We can't all just agree that key material is always unsigned? (though you're right of course) – tylerl Aug 5 '13 at 4:11
• Negative integers can not be prime. – Lucas Kauffman Aug 5 '13 at 4:18
• mkl, this doesn't seem to be what's occuring. OpenSLL always gives 32bits when passed 32. However, it also always gives 1032bits when passed 1024. – Mr. Smith Aug 5 '13 at 4:23
• @Mr.Smith have you checked the top bit in all your tests? – mkl Aug 5 '13 at 4:27
• @tylerl if such a prime shall eventually be used in a BER encoded ASN.1 structure integer, it is interpreted as signed. – mkl Aug 5 '13 at 4:30