Join Log in
Score:3
avatar Crypto

RSA: Is it a security risk if an attacker knows the length of the values of P and Q?

in flag
slickboy

Is it a security risk - or perhaps, how big of a security risk is it - if an attacker knows the length of the values of P and Q used when deriving a value for the parameter N in the RSA encryption algorithm?

I've been doing some reading on implementations of RSA and I see that some require P and Q to be the same length, while others have a minimum length for P or Q - so with this in mind, it is probably worth asking if there is a minimum length that P or Q must be when using RSA (in practice)?

1594
0 + 0
rsa
kelalaka avatar
in flag
kelalaka
No. The biggest risk is the bad randomness [The GCD strikes back to RSA in 2019 - Good randomness is the only solution?](https://crypto.stackexchange.com/q/76757/18298) and Fermat factoring if the primes are close. Minimum length is about guaranteeing that you have a prime larger than min so that you have, let say, 2048-bit RSA. And, It is easy to generate a random prime in every interval.
0
Reply
Score:14
Gilles 'SO- stop being evil' avatar Crypto
cn flag
Gilles 'SO- stop being evil'

It is not a security risk at all for the length of $P$ and $Q$ to be known. In fact, the length of $P$ and $Q$ is usually known, because most standards require $P$ and $Q$ to have the same length and for the public modulus $N = P \cdot Q$ to have double the length (which excludes values of $P$ and $Q$ which are both $n$-bit number whose product is between $2^{2n-2}$ and $2^{2n-1}$).

So if you know that $2^{2n-1} < N < 2^{2n}$ and the key was generated by a typical implementation, then $2^{n-1} < P < 2^n$ and $2^{n-1} < Q < 2^n$. In fact, some implementations even force the two leading bits of the primes to be 1, i.e. $3 \cdot 2^{n-2} < P,Q < 2^n$, which guarantees that $N \ge 2^{2n-1}$ and doesn't reduce the private key space significantly.

An RSA key can only be as strong as the smallest prime, so it doesn't really make sense for the primes to have different sizes. Having a prime larger than the other makes the computation slower without improving security.

You can see the minimum key lengths for RSA (“factoring modulus”) recommended by some authorities on keylength.com. Divide by two to get the size of the two primes.

0 + 0
Chrᴉz remembers Monica avatar
us flag
Chrᴉz remembers Monica
_...typical implementation, then 2n−1<P<2n and 2n−1<P<2n...._ Shouldn't it be 2n-1<Q<2n once?
1
Reply
Steve Cox avatar
ro flag
Steve Cox
_Having a prime larger than the other makes the computation slower without improving security_ Well one of the primes better be smaller than the other, and if they're too close there's a [simple attack](https://math.stackexchange.com/questions/3754984/explain-why-we-should-not-choose-primes-p-and-q-that-are-too-close-together-to-f) that undermines the system. Might help to clarify that you're just talking about bit-length, the primes should be well separated.
2
Reply
Score:7
poncho avatar Crypto
my flag
poncho

Gilles answered your first question, so I'll address your second:

it is probably worth asking if there is a minimum length that P or Q must be when using RSA (in practice)?

Yes; there are factorization algorithms that take time based on the shortest factor, and which work considerably faster than trial factorization. The best one is the Elliptic Curve Method (ECM); using it, someone found a 276 bit factor of a large composite ($7^{337}+1$); hence, it would be considered wise to make sure that the smaller factor is considerably larger than that.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.