What kind of special numbers are not suitable as RSA keys?

Begoña Garcia

10/20/23, 11:26 AM

I have read that some integers are not appropriate to be chosen as the modulus in an RSA cryptosystem. Some of these numbers are those that, given a modulus $n=pq$, then $p-1$ or $q-1$ do not have large factors. This is due to the fact that there are factorization algorithms that allow this type of modulus to be factored efficiently.

My question is, what other types of integers are not suitable to be used as a modulus and why?

Edit:

Other kind of numbers not suitable as RSA modulus:

p+1 and q+1 without big factors: kelalaka highlights the use of the Williams p+1 algorithm.
p and q with close values: kelalaka highlights the use of Fermat's factorization method.

0 + 8

cryptanalysis

factoring

kelalaka

10/20/23, 11:32 AM

Probably the Q duplicates this [Is it reasonable to assure that p-1 and q-1 aren't smooth?](https://crypto.stackexchange.com/q/1151/18298) and this [Williams' p+1 in tandem with Pollard's p−1?](https://crypto.stackexchange.com/q/59788/18298) and this [Finding strong primes](https://crypto.stackexchange.com/q/22554/18298) and finally this [Generation of strong primes](https://crypto.stackexchange.com/q/20548/18298)

kelalaka

10/20/23, 11:36 AM

It is edited in 2000, and it is old. Check the links that I've provided to you to see.

Begoña Garcia

10/20/23, 11:39 AM

Thanks @kelalaka, it seems that due to Williams p+1 we also have to worry about large factors at p+1 and q+1, which is very interesting. But I think my question remains open. What other kinds of numbers do we have to worry about?

kelalaka

10/20/23, 11:43 AM

[close primes due to Fermat's factoring](https://crypto.stackexchange.com/questions/102252/is-fermats-factorization-method-used-in-any-practical-application)

Begoña Garcia

10/20/23, 11:53 AM

Thans again kelalaka, i've edited the question. Let's see if anyone knows of other cases.

fgrieu

10/20/23, 12:00 PM

@kelalaka: yes the HAC is old, but it's still excellent for what it covers, and can't be construed as stating that strong primes matter in RSA. On the contrary, section 4.4.2 states _"it is now believed that strong primes offer little protection beyond that offered by random primes"_.

kelalaka

10/20/23, 1:51 PM

@fgrieu I don't agree that, some parts needs to be updated. I wish they updated to be content or released the $\LaTeX$ code on github etc. so that it is still as reliable as 15 years ago.

kelalaka

10/20/23, 1:52 PM

Of cource, if you want to read you can read [20 years of RSA](https://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html) paper from Dan Boneh.

Elon Musk

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

EN: What kind of special numbers are not suitable as RSA keys?

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.