When generating a 4096 bit RSA key pair, do both the private and the public key always have exactly 4096 bits, thus do not start with a 0 in binary representation?
As a preliminary, in RSA the public key is the pair
(N, e) and the private key is
d. Like it has been stated, the bit size of the modulus
N is what the 4096 refers to.
N only makes up part of the public key, along with
e. There is no requirement for what bit size
e is. The only requirement for secure encryption in RSA is that exponentiating the message
m to the
eth power "wraps the modulus", i.e.
m^e > N. So in practice values of
e as small as 3 (2 bits) have been used. The most common current value for
e is 65537 (17 bits) in fact most SSL certs that you see have this value e.g. google.com
The bit size of
d, the private key, is not set and can vary greatly as it is simply the multiplicative inverse of
e in the group
phi(N) where phi is the totient function. In most cases it will be much smaller than 4096 bits.
4096 refers to the modulus of n. The public key and the private key should be of "similar" bit length in order to provide the intended security. Choosing a significantly smaller value for either p or q allows for the factorization of n(i.e. through brute forcing) and can thus be used to retrieve the secret key.
Consequently, it is necessary for both parameters to have the mentioned length.
Expect Zeros to occur in the MSB or LSB of the BigInteger. (either end of the binary output)
I've written RSA code in C# and had to account for a leading zero in BouncyCastle BigInteger and .NET Big Integer. What is interesting about the two libraries is that one is Big Endian, the other Little Endian.