Why were primes which are $1$ modulo $4$ considered to be weak for use in RSA cryptography (http://en.wikipedia.org/wiki/Blum_integer)? Was there a time it was considered there could be an efficient algorithm if these primes be utilized (if so, then what exact reasons were these)?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Your question is answered entirely by the "History" section of the Wikipedia article you link to. $\endgroup$– David RicherbyCommented Apr 4, 2015 at 9:17
-
$\begingroup$ It only states "Before modern factoring algorithms, such as MPQS and NFS, were developed, it was thought to be useful to select Blum integers as RSA moduli. This is no longer regarded as a useful precaution, since MPQS and NFS are able to factor Blum integers with the same ease as RSA moduli constructed from randomly selected primes".. does not say prehistory. $\endgroup$– TurboCommented Apr 4, 2015 at 9:31
-
$\begingroup$ It tells you that older factoring algorithms factored products of non-Blum primes faster than products of Blum primes. $\endgroup$– David RicherbyCommented Apr 4, 2015 at 9:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
They're not weak for use with RSA. You don't cite where you got that misconception from, so it's hard for me to respond or identify the source of your confusion -- but you have a faulty premise. Given that the premise is false, the question evaporates.
For instance, see Wikipedia: https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Key_generation. The description of the key generation algorithm has no mention of choosing $p$ or $q$ to be 1 mod 4.
-
$\begingroup$ From the wikipedia page linked in the question, it seems that one was previously advised to avoid primes congruent to 1, mod 4 because older factoring algorithms are slower on products of primes congruent to 3, mod 4. So the question isn't actually based on a false premise (especially since, after you posted your answer, it was edited to put the premise in the past tense). $\endgroup$ Commented Apr 4, 2015 at 11:27