OpenSSL prime generation

Sukru

6/5/24, 5:15 PM

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 ?

1 + 3

prime-numbers

key-generation

poncho

6/5/24, 5:20 PM

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.

Sukru

6/5/24, 5:21 PM

Is there any security issue to set upper two bits '1', and can you explain me other ways, please

poncho

6/5/24, 5:25 PM

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),

Score:2

Crypto

fgrieu

6/5/24, 5:55 PM

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

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: OpenSSL prime generation

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.