Editing RSA cryptosystem (section)

===Importance of strong random number generation===
A cryptographically strong [[random number generator]], which has been properly seeded with adequate entropy, must be used to generate the primes {{mvar|p}} and {{mvar|q}}. An analysis comparing millions of public keys gathered from the Internet was carried out in early 2012 by [[Arjen Klaas Lenstra|Arjen K.&nbsp;Lenstra]], James P.&nbsp;Hughes, Maxime Augier, Joppe W.&nbsp;Bos, Thorsten Kleinjung and Christophe Wachter. They were able to factor 0.2% of the keys using only Euclid's algorithm.<ref>{{cite web|title=Flaw Found in an Online Encryption Method |url=https://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html |newspaper=[[The New York Times]] |date=February 14, 2012 |first=John |last=Markoff }}</ref><ref>{{cite web |title=Ron was wrong, Whit is right |url=http://eprint.iacr.org/2012/064.pdf |year=2012 |last1=Lenstra |first1=Arjen K. |last2=Hughes |first2=James P. |last3=Augier |first3=Maxime |last4=Bos |first4=Joppe W. |last5=Kleinjung |first5=Thorsten |last6=Wachter |first6=Christophe }}</ref>{{self published inline|date=December 2023|reason=This paper is not from a journal and may not have been peer-reviewed}}

They exploited a weakness unique to cryptosystems based on integer factorization. If {{math|1=''n'' = ''pq''}} is one public key, and {{math|1=''n''′ = ''p''′''q''′}} is another, then if by chance {{math|1=''p'' = ''p''′}} (but {{mvar|q}} is not equal to {{mvar|q}}'), then a simple computation of {{math|1=gcd(''n'', ''n''′) = ''p''}} factors both {{mvar|n}} and {{mvar|n}}', totally compromising both keys. Lenstra et al. note that this problem can be minimized by using a strong random seed of bit length twice the intended security level, or by employing a deterministic function to choose {{mvar|q}} given {{mvar|p}}, instead of choosing {{mvar|p}} and {{mvar|q}} independently.

[[Nadia Heninger]] was part of a group that did a similar experiment. They used an idea of [[Daniel J.&nbsp;Bernstein]] to compute the GCD of each RSA key {{mvar|n}} against the product of all the other keys {{mvar|n}}' they had found (a 729-million-digit number), instead of computing each {{math|gcd(''n'', ''n''′)}} separately, thereby achieving a very significant speedup, since after one large division, the GCD problem is of normal size.

Heninger says in her blog that the bad keys occurred almost entirely in embedded applications, including "firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones" from more than 30 manufacturers. Heninger explains that the one-shared-prime problem uncovered by the two groups results from situations where the pseudorandom number generator is poorly seeded initially, and then is reseeded between the generation of the first and second primes. Using seeds of sufficiently high entropy obtained from key stroke timings or electronic diode noise or [[atmospheric noise]] from a radio receiver tuned between stations should solve the problem.<ref>{{Cite web | url=https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs | title=New research: There's no need to panic over factorable keys–just mind your Ps and Qs | date=February 15, 2012 | website=Freedom to Tinker | first=Nadia | last=Heninger}}</ref>

Strong random number generation is important throughout every phase of public-key cryptography. For instance, if a weak generator is used for the symmetric keys that are being distributed by RSA, then an eavesdropper could bypass RSA and guess the symmetric keys directly.