OpenSSL prime generation

Recently, I have noticed that openssl always gives numbers which have '1' in upper two bits. It always begins with 0xC or higher values (0xD, 0xE, 0xF). It doesn't give primes that starting with 0xB, 0xC, 0xA, 0x9 or 0x8. Common thing among those values is that their bit before msb is '0'.

I have an assumption about that situation. In RSA key generation, we need p and q values as primes and they needed to be multiplied to obtain n (modulus). There is a possibility that n can be $$(p.bit\_length\ x \ 2) - 1$$. For example; if we want to have 1024 bit key generation, we get 512 bit p and q values. However, their multiplication might be 1023 bit value and I guess, it is something not desired. Hence, openssl doesn't give this chance by setting two msb bits as '1'.

I can't find any docs or any piece of code to proof my theory. What do you think ?

• That's pretty much the case. There are other ways to make sure that $p \times q$ is a 2048 bit value; however just making the upper two bits of $p, q$ both 1 certainly is simple. Jun 5, 2023 at 17:20
• Is there any security issue to set upper two bits '1', and can you explain me other ways, please Jun 5, 2023 at 17:21
• No security issues; if the attack could factor by guessing those two bits, RSA would essentially be broken anyways. As for an alternative, one common one is selecting $p, q$ from the range $[1/\sqrt{2} \cdot 2^{1024}, 2^{1024}]$. A tad more work, but it is a bit more esthetic (if you care about such things), Jun 5, 2023 at 17:25

1 Answer

openssl always gives numbers which have '1' in upper two bits. It always begins with 0xC or higher values (0xD, 0xE, 0xF).

I observe otherwise. On my first attempt, openssl genra made me a key with the first byte of $$p$$ equal to 0xB8. I'm using the version in Mint 21.1 Vera, such that openssl version outputs OpenSSL 3.0.2 15 Mar 2022 (Library: OpenSSL 3.0.2 15 Mar 2022).

OpenSSL tries to obey the standard practice, codified in X9.31-1998 then FIPS 186-2 and later (see the current FIPS 186-5), that for $$k$$-bit public modulus the primes $$p$$ and $$q$$ should be in the interval $$(2^{(k-1)/2},2^{k/2})$$.

There is no security issue to this. It would also be secure to use the slightly smaller interval $$(3\cdot 2^{k/2-2},2^{k/2})$$ proposed in the question (for $$k$$ multiple of 2 or 8 depending on the question's formulation).