3 ms·
The whole point of the long keys is the search space, isn’t it? If the leading bit has to be 1 then effectively you have a 2047 bit key either way. 1 followed b
by hinkley 6y ago
The whole point of the long keys is the search space, isn’t it? If the leading bit has to be 1 then effectively you have a 2047 bit key either way. 1 followed by 2047 random-looking bits.
- anyfoo 6y agoIf you want to do it that way, it's much less than 2047 bits for RSA, though. Also compare with AES keys for example, which can be much shorter while still being harder to crack.
- sp332 6y agoAccording to Table 2 (page 67) of this NIST report, 2048-bit RSA only has about 112 bits of entropy anyway. https://csrc.nist.gov/publications/detail/sp/800-57-part-1/rev-5/final https://csrc.nist.gov/publications/detail/sp/800-57-part-1/r...
- bmurray7jhu 6y agoAn 2048 bit RSA key has 112 bits of security, but not necessarily 2048 bits of entropy. RSA 2048 only has about ~112 bits of security because there are faster-than-brute-force algorithms for integer factorization. A 2048 bit RSA key is generated from two 1024 bit primes. Let's assume we randomly choose each prime from the range 2^1023 to 2^1024. Per the Prime Number Theorem, there are ~ N / ln (N) primes below N. That means that there are 2^1024 / (1024 ln 2) - 2^1023 / (1023 ln 2) ≈ 1.3e305 1024-bit primes. It follows that a 1024 bit prime has ~1023 bits of entropy and that a 2048 bit RSA key has ~2022 bits of entropy.
- labawi 6y ago2048 bit RSA can have at most ~2022 bits of entropy. It can and often does have much less¹, depending on how the keys were generated (debian). That may or may not be an issue, depending on the resulting distribution of keys, i.e. how usable is the information that only a teeny fraction of keys are possible (Infineon). ¹ Entropy interpreted as the number of possible, roughly equal-likelihood outcomes.
- wrs 6y agoNot being a random key, it’s not precisely a “search space”, but to your point, from the article: “the difficulty of factoring 2047-bit keys is only marginally lower than that for full 2048-bits”.