4

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?

4

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

enter image description here

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.

  • Your last statement claiming that in most cases d will be much smaller than 4096 bits is incorrect. d will be approximately uniformly distributed over the range from 1 to φ(n), and φ(n) is not much smaller than n. So on average d will be close to n/2, which means if n is 4096 bits d will be around 4095 bits. – kasperd Nov 1 '15 at 11:05
0

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.

0

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.

  • Lamonte - if you want to know about the leading zero probability, that would likely be better served over on Crypto Stack Exchange – Rory Alsop Jul 19 '15 at 17:35
  • @RoryAlsop Will ask there ;) – goodguys_activate Jul 19 '15 at 18:05
  • 1
    Cool. Our typical rule of thumb is that if it is the maths or theory then Crypto should have it. Implementation is on topic here. – Rory Alsop Jul 19 '15 at 18:07
  • Found it, the leading zero occurs 1/256 times crypto.stackexchange.com/a/26648/371 – goodguys_activate Jul 19 '15 at 18:08

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.