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?

Improve this question

3 Answers 3

Reset to default
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.

Improve this answer
1
  • 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
    Commented Nov 1, 2015 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.

Improve this answer
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.

Improve this answer
4
  • Lamonte - if you want to know about the leading zero probability, that would likely be better served over on Crypto Stack Exchange
    – Rory Alsop ♦
    Commented Jul 19, 2015 at 17:35
  • @RoryAlsop Will ask there ;)
    – makerofthings7
    Commented Jul 19, 2015 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 ♦
    Commented Jul 19, 2015 at 18:07
  • Found it, the leading zero occurs 1/256 times crypto.stackexchange.com/a/26648/371
    – makerofthings7
    Commented Jul 19, 2015 at 18:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .