Is it possible to say that the most significant bit of an RSA private exponent is always 1? Wouldn't that weaken the key strength by exactly that one bit?

I refer to the paper "Timing Attack: What can be achieved by a powerful adversary?", p. 2, footnote 2.

  • 6
    $\begingroup$ Note: the most significant bit of any number is 1. Otherwise it wouldn't be the most significant bit. $\endgroup$ – SEJPM Nov 28 '15 at 20:53
  • $\begingroup$ Correct. Nevertheless, if I say I am using a 64-bit key, the size is fixed and my MSB is the bit at index 63. Can't that bit be zero? $\endgroup$ – pafodie Nov 28 '15 at 21:01
  • 1
    $\begingroup$ @pafodie There is a subtle difference between numbers and bit strings. Bit strings might have either 0 or 1 at the most significant index. All positive non-zero numbers will always have 1 in the most significant bit. $\endgroup$ – Henrick Hellström Nov 28 '15 at 21:09
  • 2
    $\begingroup$ If you have a random 64-bit string, the bit #63 is set with probability 1/2. For RSA we usually set the highest bit to achieve the claimed key length and prevent in any case against small key attacks. $\endgroup$ – SEJPM Nov 28 '15 at 21:12
  • 1
    $\begingroup$ @pafodie, it's still unclear what you mean by "RSA private key". The private exponent $d$ does not necessarily have MSB set (when looked at as the same size number as the totient or the modulus). $\endgroup$ – otus Nov 28 '15 at 21:28

No, in the end the private exponent $d$ is just a number within $0..N$ where $N$ is the modulus. It depends on $N$ what the chance is that the first bit is one, but in more likely to be valued $0$ than $1$ (given that it is well distributed, you would expect it to be $0$ around $\frac23$ of the time). If you generate enough private keys you'll even see private exponents that start with a few leading bytes that are completely zero'ed out (!). That's not a problem cryptographically speaking, it just shows that the entire key space is utilized.

So the private exponent $d$ doesn't always start with a $1$ when you consider the most significant bit of the modulus. The fact that the modulus is strictly less than $2^{keylength}$ does matter ever so slightly though. But as RSA requires exponential sized keys to achieve a certain security level, that should not worry you overly much (1 partial bit out of 1024 for the absolute minimum key size is completely negligible). Even if the private exponent would always have a 1 at the most significant position then the same logic applies; it would not have any significant impact on security.

I'm assuming a calculation with a preset/precalculated RSA public exponent, which is most often used in practice. If PKCS#1 conformant calculations are used then the most significant bit of $d$ is always $0$.

As I'm not that good in statistics, my computer has calculated that the first bit is probably 0 about 69 percent of the time and the first byte is zero 0.54 percent of the time, slightly higher than you would probably expect. And yes, I did generate 21171 keys starting with at least two zero bytes.

| improve this answer | |
  • 2
    $\begingroup$ Number within $[0, \varphi(N)]$, really, but yes. $\endgroup$ – otus Nov 29 '15 at 12:28
  • 3
    $\begingroup$ If we compute $d$ as $e^{-1}\bmod(\operatorname{lcm}(p-1,q-1))$, which is PKCS#1 conformant; and, as in the answer, consider $d$ as a bitstring of the same length as the shortest bitstring coding $N$; then the most significant bit of $d$ is always 0. $\endgroup$ – fgrieu Nov 29 '15 at 12:28
  • $\begingroup$ I had to make the edit because the random number generator is now seriously deprived of entropy :P $\endgroup$ – Maarten Bodewes Nov 29 '15 at 17:40

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.