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.
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.
