vanilla fix {\huge Do Gaps Between Primes Affect RSA Keys?} A possible contributing factor to the recent discovery of weaknesses in RSA keys en-masse \vspace{.5in} Arjen Lenstra is one of the top computational number theorists in the world, especially on the state-of-the-art in integer factoring. For example, he helped create the best general factorization method known to date—the number field sieve—see here for a previous discussion. Also he was one of the authors of the great paper that introduced the LLL lattice algorithm, which was joint work with one of his brothers, Hendrik Lenstra, and also with Lászlò Lovász. Today we want to add some potential considerations to the discussion of Lenstra’s recent paper on why RSA public keys deployed in practice are sometimes breakable. Ken and I do not know whether they actually apply, but there are some reasonable questions to ask, and a tie-in to general questions in number theory. The paper is joint work with James Hughes, Maxime Augie, Joppe Bos, Thorsten Kleinjung, and Christophe Wachter, and bears the title, “Ron was wrong, Whit was right.” Here Ron refers to Ron Rivest and Whit refers to Whitfield Diffie. Rivest is the “R” in RSA, of course, and Diffie is the Diffie in the Diffie-Hellman protocol. The former uses two primes and the latter uses one prime. The message is that crypto-systems that use one prime may be better than ones that use two primes—because the latter allow two users unwittingly to share one prime in a way that endangers both their systems. Here is how. Testing…-3 -1 AQ ${AQ}$ QA ${QA}$ xY ${xY}$ Yx ${Yx}$ xYx ${xYx}$ YxY ${YxY}$ Testing…-3 1 Ap ${Ap}$ pA ${pA}$ pAp ${pAp}$ ApA ${ApA}$ Testing…-3 2 k. ${k.}$ 0.5 ${0.5}$ 5.0 ${5.0}$ X,Y ${X,Y}$ Testing… a’ ${a'}$ b’ ${b'}$ c’ ${c'}$ d’ ${d'}$ e’ ${e'}$ f’ ${f'}$ g’ ${g'}$ h’ ${h'}$ i’ ${i'}$ j’ ${j'}$ k’ ${k'}$ l’ ${l'}$ m’ ${m'}$ n’ ${n'}$ o’ ${o'}$ p’ ${p'}$ q’ ${q'}$ r’ ${r'}$ s’ ${s'}$ t’ ${t'}$ u’ ${u'}$ v’ ${v'}$ w’ ${w'}$ x’ ${x'}$ y’ ${y'}$ z’ ${z'}$ Testing… A’ ${A'}$ B’ ${B'}$ C’ ${C'}$ D’ ${D'}$ E’ ${E'}$ F’ ${F'}$ G’ ${G'}$ H’ ${H'}$ I’ ${I'}$ J’ ${J'}$ K’ ${K'}$ L’ ${L'}$ M’ ${M'}$ N’ ${N'}$ Np’ ${Np'}$ N,p’ ${N,p'}$ O’ ${O'}$ P’ ${P'}$ Q’ ${Q'}$ R’ ${R'}$ S’ ${S'}$ T’ ${T'}$ U’ ${U'}$ V’ ${V'}$ W’ ${W'}$ X’ ${X'}$ Y’ ${Y'}$ Z’ ${Z'}$ Testing… hello 0 ${0}$ hello 1 ${1}$ hello 2 ${2}$ hello 3 ${3}$ hello 4 ${4}$ hello 5 ${5}$ hello 6 ${6}$ hello 7 ${7}$ hello 8 ${8}$ hello 9 ${9}$ Testing… a ${a}$ b ${b}$ c ${c}$ d ${d}$ e ${e}$ f ${f}$ g ${g}$ h ${h}$ i ${i}$ j ${j}$ k ${k}$ l ${l}$ m ${m}$ n ${n}$ o ${o}$ p ${p}$ q ${q}$ pq ${pq}$ p,q ${p,q}$ r ${r}$ s ${s}$ t ${t}$ u ${u}$ v ${v}$ w ${w}$ x ${x}$ y ${y}$ z ${z}$ Testing… A ${A}$ B ${B}$ C ${C}$ D ${D}$ E ${E}$ F ${F}$ G ${G}$ H ${H}$ I ${I}$ J ${J}$ K ${K}$ L ${L}$ M ${M}$ N ${N}$ O ${O}$ P ${P}$ Q ${Q}$ R ${R}$ S ${S}$ T ${T}$ U ${U}$ V ${V}$ W ${W}$ X ${X}$ Y ${Y}$ Z ${Z}$ Testing… A^n ${A^n}$ Q^n ${Q^n}$ A^A ${A^A}$ Q^Q ${Q^Q}$ 2^n ${2^n}$ n^2 ${n^2}$ p^2 ${p^2}$ 2^p ${2^p}$ Testing… 2p ${2p}$ 4x ${4x}$ 2.123x ${2.123x}$ 2.123p ${2.123p}$ Testing… x0 ${x0}$ x1 ${x1}$ x2 ${x2}$ x3 ${x3}$ x4 ${x4}$ x5 ${x5}$ x6 ${x6}$ x7 ${x7}$ x8 ${x8}$ x9 ${x9}$ Testing… 0.1234 ${0.1234}$ 1.235 ${1.235}$ 1234.1234 ${1234.1234}$ 1235.1235 ${1235.1235}$ Testing… -0.1234 ${-0.1234}$ -1.235 ${-1.235}$ -1234.1234 ${-1234.1234}$ -1235.1235 ${-1235.1235}$ Testing… 1^2 ${1^2}$ 4^4 ${4^4}$ 1234.1234^2 ${1234.1234^2}$ 1234.1234^1234.1234 ${1234.1234^{1234.1234}}$ 1235.1235 ${1235.1235}$ Testing… -1^2 ${-1^2}$ -4^4 ${-4^4}$ -1234.1234^2 ${-1234.1234^2}$ -1234.1234^1234.1234 ${-1234.1234^{1234.1234}}$ -1235.1235 ${-1235.1235}$ Testing… hello 0 ${0}$ hello 1 ${1}$ hello 2 ${2}$ hello 3 ${3}$ hello 4 ${4}$ hello 5 ${5}$ hello 6 ${6}$ hello 7 ${7}$ hello 8 ${8}$ hello 9 ${9}$ 1>2 ${1>2}$ 1,2 ${1,2}$ Testing… = ${=}$ – ${-}$ + ${+}$ ‘ ${'}$ * ${*}$ / ${/}$ . ${.}$ , ${,}$ ! ${!}$ ? ${?}$ : ${:}$ > ${>}$ < ${<}$ Testing… x+y ${x+y}$ x-y ${x-y}$ x^2 ${x^2}$ x_2 ${x_2}$ x^2_2 ${x^2_2}$ 1+x ${1+x}$ 1+y ${1+y}$ 1-x ${1-x}$ 1-y ${1-y}$ Testing… x^x ${x^x}$ x^A ${x^A}$ A^x ${A^x}$ A^A ${A^A}$ Testing… x^x ${x^x}$ x^A^A ${x^A^A}$ x^A ${x^A}$ A^x ${A^x}$ A^A ${A^A}$ Testing… p ${+p}$ ${p}$ ${pA}$ Testing… xj ${xj}$ xi ${xi}$ f ${f}$ af ${af}$ ag ${ag}$ xt ${xt}$ Testing… x0 ${x0}$ x1 ${x1}$ x2 ${x2}$ x3 ${x3}$ x4 ${x4}$ x5 ${x5}$ x6 ${x6}$ xa7 ${xa7}$ x8 ${x8}$ x9 ${x9}$ Testing… x> ${x>}$ x< ${x<}$ x! ${x!}$ x? ${x?}$ x^2 ${x^2}$ x_2 ${x_2}$ x^x ${x^x}$ x_x ${x_x}$ x, ${x,}$ x. ${x.}$ x: ${x:}$ x/ ${x/}$ Testing… xA ${x\mathbb{A}}$ xQ ${x\mathbb{Q}}$ xA ${x\mathcal{A}}$ xQ ${x\mathcal{Q}}$ xA ${x\mathbf{A}}$ xQ ${x\mathbf{Q}}$ Testing… x= ${x=}$ Testing… ${x\alpha}$ ${x\theta}$ ${x\tau}$ ${x\beta}$ ${x\vartheta}$ ${x\pi}$ ${x\upsilon}$ ${x\gamma}$ ${x\gamma}$ ${x\varpi}$ ${x\phi}$ ${x\delta}$ ${x\kappa}$ ${x\rho}$ ${x\varphi}$ ${x\epsilon}$ ${x\lambda}$ ${x\varrho}$ ${x\chi}$ ${x\varepsilon}$ ${x\mu}$ ${x\sigma}$ ${x\psi}$ ${x\zeta}$ ${x\nu}$ ${x\varsigma}$ ${x\omega}$ ${x\eta}$ ${x\xi}$ ${x\Gamma}$ ${x\Lambda}$ ${x\Sigma}$ ${x\Psi}$ ${x\Delta}$ ${x\Xi}$ ${x\Upsilon}$ ${x\Omega}$ ${x\Theta}$ ${x\Pi}$ ${x\Phi}$ Testing… ${x\pm}$ ${x\cap}$ ${x\diamond}$ ${x\oplus}$ ${x\mp}$ ${x\cup}$ ${x\bigtriangleup}$ ${x\ominus}$ ${x\times}$ ${x\uplus}$ ${x\bigtriangledown}$ ${x\otimes}$ ${x\div}$ ${x\sqcap}$ ${x\triangleleft}$ ${x\oslash}$ ${x\ast}$ ${x\sqcup}$ ${x\triangleright}$ ${x\odot}$ ${x\star}$ ${x\vee}$ ${x\bigcirc}$ ${x\circ}$ ${x\wedge}$ ${x\dagger}$ ${x\bullet}$ ${x\setminus}$ ${x\ddagger}$ ${x\cdot}$ ${x\wr}$ ${x\amalg}$ ${x+}$ ${x-}$ Testing… ${x\leq}$ ${x\geq}$ ${x\equiv}$ ${x\models}$ ${x\prec}$ ${x\succ}$ ${x\sim}$ ${x\perp}$ ${x\preceq}$ ${x\succeq}$ ${x\simeq}$ ${x\mid}$ ${x\ll}$ ${x\gg}$ ${x\asymp}$ ${x\parallel}$ ${x\subset}$ ${x\supset}$ ${x\approx}$ ${x\bowtie}$ ${x\subseteq}$ ${x\supseteq}$ ${x\cong}$ ${x\neq}$ ${x\smile}$ ${x\sqsubseteq}$ ${x\sqsupseteq}$ ${x\doteq}$ ${x\frown}$ ${x\in}$ ${x\ni}$ ${x\propto}$ ${x=}$ ${x\vdash}$ ${x\dashv}$ ${x<}$ ${x>}$ ${x:}$ Testing… ${x,}$ ${x;}$ ${x\colon}$ ${x\ldotp}$ Testing… ${x\prime}$ ${x\forall}$ ${x\infty}$ ${x\emptyset}$ ${x\exists}$ ${x\nabla}$ ${x\neg}$ ${x\backslash}$ Testing… ${x\arccos}$ ${x\arcsin}$ ${x\arctan}$ ${x\arg}$ ${x\cos}$ ${x\cosh}$ ${x\cot}$ ${x\coth}$ ${x\csc}$ ${x\deg}$ ${x\det}$ ${x\dim}$ ${x\exp}$ ${x\gcd}$ ${x\hom}$ ${x\inf}$ ${x\ker}$ ${x\lg}$ ${x\lim}$ ${x\liminf}$ ${x\limsup}$ ${x\ln}$ ${x\log}$ ${x\max}$ ${x\min}$ ${x\Pr}$ ${x\sec}$ ${x\sin}$ ${x\sinh}$ ${x\sup}$ ${x\tan}$ ${x\tanh}$ Testing… ${x(}$ ${x)}$ ${x[}$ ${x]}$ ${x\{}$ ${x\}}$ ${x\lfloor}$ ${x\langle}$ ${x\rfloor}$ ${x\rangle}$ ${x\lceil}$ ${x\rceil}$ Testing… ${x\leftarrow}$ ${x\longleftarrow}$ ${x\uparrow}$ ${x\Leftarrow}$ ${x\Longleftarrow}$ ${x\Uparrow}$ ${x\rightarrow}$ ${x\longrightarrow}$ ${x\downarrow}$ ${x\Rightarrow}$ ${x\Longrightarrow}$ ${x\Downarrow}$ ${x\leftrightarrow}$ ${x\longleftrightarrow}$ ${x\updownarrow}$ ${x\Leftrightarrow}$ ${x\Longleftrightarrow}$ ${x\Updownarrow}$ ${x\mapsto}$ ${x\longmapsto}$ ${x\nearrow}$ ${x\hookleftarrow}$ ${x\hookrightarrow}$ ${x\searrow}$ ${x\leftharpoonup}$ ${x\rightharpoonup}$ ${x\swarrow}$ ${x\leftharpoondown}$ ${x\rightharpoondown}$ ${x\nwarrow}$ ${x\rightleftharpoons}$ Testing… considerations to the discussion of ${A}$ considerations to the discussion of ${B}$ considerations to the discussion of ${Y}$ considerations to the discussion of ${y}$ considerations to the discussion of ${1+2}$ considerations to the discussion of ${1-2}$ considerations to the discussion of ${p, X}$ considerations to the discussion of ${p, x}$ considerations to the discussion of ${p^2}$ considerations to the discussion of ${p_2}$ considerations to the discussion of ${x}$ considerations to the discussion of ${y}$ considerations to the discussion of. Testing… xO ${xO}$ xA’ ${xA'}$ Testing… x^x${x^x}$ x_x${x_x}$ The Factoring Idea Perhaps there is one fundamental idea in factoring, an idea that goes back at least to Pierre de Fermat. Suppose that ${N=pq}$ where ${p,q}$ are primes. The approach is to try to factor ${N}$ by constructing another number ${M}$ so that the greatest common divisor (gcd) of ${N}$ and ${M}$ is equal to either ${p}$ or to ${q}$. There is good and bad news with this method. The good news is if you can find such an ${M}$ then ${N}$ is easy to factor. Just compute the value of ${ \gcd(N,M)}$ by Euclid’s algorithm and ${p}$ or ${q}$ will pop out. Since the gcd algorithm is quite efficient, this runs fast even if ${N}$ and ${M}$ are very large numbers. Thanks are due to Euclid, although the first proof that this algorithm runs fast is due to Gabriel Lamé in 1844. Perhaps this is one of the first algorithm analysis results. The bad news is, where does ${M}$ come from? Fermat’s idea was to try and find ${x}$ and ${y}$ so that $\displaystyle N = x^{2} - y^{2},$ and then use ${x+y}$ and ${x-y}$ as potential values of ${M}$. Note that this succeeds provided ${x+y}$ is not equal to ${N}$. The difficulty is that finding such a pair of integers ${x}$ and ${y}$ is still hard, but there are tricks that can be used to make the search for them more efficient. In any event, the search for values of ${M}$ that will work is one of the achievements of modern computational number theory. There are a variety of more and more powerful methods that attempt to find an ${M}$. If there was a way to always find ${M}$ efficiently, then of course factoring would be easy. Even Peter Shor’s quantum factoring algorithm uses the power of quantum circuits to find such an ${M}$. Attacks on RSA Let’s turn to the recent attack on RSA. Recall RSA relies on having an ${N=pq}$, where ${p}$ and ${q}$ are secret primes that are not public. The value of ${N}$ is public, but the primes are secret and will remain so provided factoring is hard. Lenstra’s paper used a clever idea, an idea that probably has been around, but still a clever idea: instead of working hard to try and find an ${M}$ that will help factor ${N}$, just use values that public. Use ${N'}$ from other public keys—basically play the RSA system against itself. If ${N'}$ and ${N}$ share a prime, ${\gcd(N,N')}$ finds it—bingo. This is really neat because these values ${N'}$ are available, there are a lot of them, and there are reasons to believe they could be useful. The empirical result found in the paper is that using these ${N'}$ values as the ${M}$‘s works quite well. The paper summarizes the result by ending with a riff on a quotation commonly attributed to Josef Stalin: Factoring one 1024-bit RSA modulus would be historic. Factoring 12,720 such moduli is a statistic. The original quotation is, “When one dies, it is a tragedy. When a million die, it is a statistic.” According to this wiki the quotation came from a 1981 Russian biography of Stalin that was used by an American historian, but it probably originates in a 1932 essay on the nature of jokes in France. Attacks on Lenstra Lenstra put two extra charges into his broadside: having the story appear in the New York Times on the same Valentine’s Day as the paper’s e-print date, and the title “Ron was wrong, Whit was right.” A great title to get noticed, but not the best for search engines in the future—jump forward ten years and imagine saying, “I recall a paper that showed a problem with RSA, I forget the title.” Right afterward there were attacks not on the results, but on their meaning and on the bearer of the news—Lenstra. I personally find this pushback to be unscientific and unwarranted. The paper shows that a small fraction of the RSA keys are easy to break, 0.2%, while 99.8% are okay. But Lenstra and his team have been attacked that this observation is picayune—if only a small percent fail, what is the concern? This line strikes me as unfair, unreasonable, and wrong: cryptography here is predicated on the chance of total failure being negligible. I regard the following statement as wrongheaded insofar as it is seen to disclaim resposibility for considerations that should be on RSA’s watch as a security firm: RSA said Thursday in a statement. “Our analysis confirms to us that the data does not point to a flaw in the algorithm, but instead points to the importance of proper implementation, especially regarding the exploding number of embedded devices that are connected to the Internet today.” One Prime vs. Two Primes The nub of the argument is whether Lenstra’s contention that relying on two primes is innately more dangerous than one is fair. There is no obvious counterpart to the GCD trick for systems that use one prime. Note that two primes are required for RSA, and this is why the GCD method could even work. Clearly the facts speak for themselves: many RSA keys were broken. I do not accept that “only” a small percent were compromised. This reminds of the scene in Dr. Strangelove where a US bomber has ignored orders to return to base and is on the way to attack the USSR and likely start WW III: President Merkin Muffley: General Turgidson! When you instituted the human reliability tests, you *assured* me there was *no* possibility of such a thing *ever* occurring! General “Buck” Turgidson: Well, I, uh, don’t think it’s quite fair to condemn a whole program because of a single slip-up, sir. How about tens of thousands of “slip-ups”? The argument then moves on to ask, what is the root cause, and what can be done to avoid these problems? The paper does not identify a main culprit, and the answers might truly emerge only from sifting how millions of RSA certificates were created—acts of checking that the authors disclaim for reasons of both security and time-intensiveness. We don’t have a main culprit either, but rather an observation about the scenery. One Way (Not) to Pick Primes We wish to draw attention to one aspect of generating primes, and ask whether it may be interacting with more-salient problems found in the generation of keys, especially by smaller “consumer” devices. For more on the salient problems, see this excellent post by Nadia Heninger pointing to another in-depth study, this Y-Combinator thread, and this Secret Blogging Seminar note, among many good sources. We make an educated guess that many implementers start with ${r}$ and ${s}$ initialized correctly. Then they perform something like the following key loop—we will consider different ways to change ${r}$ later: $\displaystyle \text{while } gcd(e,r-1) > 1 \text{ or } r \not\equiv 3 \bmod 4 \text{ or } \textsf{primetest}(r) = no''$ $\displaystyle \; \; \; r \leftarrow r+4;$ This strategy of picking a random place and then starting a search from that place yields extremely biased primes. Whether this matters may depend on implementation details discussed below, but potentially it could have three ramifications: It could explain some, if not all, the lost entropy in the key generation that Lenstra found. It could suggest a method that could break many more keys. Searching for primes with “extra” security properties, such as so-called safe primes and/or strong primes, could make the bias problem worse not better. Why This Could Be Bad To understand the bias, let’s recall an old problem from Martin Gardner’s first book of mathematical recreations from his Scientific American columns. A young man reaches a subway platform at a random moment each Saturday afternoon. Brooklyn and Bronx trains arrive equally often—[each regularly] every 10 minutes. Yet on the average he goes to Brooklyn nine times out of ten. Why? The answer is that while uptown trains to the Bronx may dutifully arrive on the :00, :10, thru :50 every hour, downtown trains to Brooklyn could be coming at :09, :19, ${\dots}$, :59. The downtown trains have a lead interval that is nine times as great, and hence captures nine times as many random moments of arrival. The distribution of primes is much more uneven than that of the trains, and some primes may have lead intervals that are vastly larger than average. Call such primes leaders. By the Prime Number Theorem, the average density of primes between a given ${n}$ and ${2n}$ will be about ${1/\ln n}$, but it was a nontrivial theorem even to show there is at least one prime in that range. If the first prime ${p > n}$ were to come a fifth of the way into that range, and we’re searching for primes with the same number of bits as ${n}$, then one-fifth of the random starting points ${r}$ will yield the same prime, ${p}$. Then about two-fifths of the ${N = pq}$ values chosen this way would include this same ${p}$, and all pairs of them would cough up ${p}$ by the GCD trick. Of course saying ${1/5}$ is a huge exaggeration. For sufficiently large ${n}$ there is always a prime between ${n}$ and ${n + n^c}$, where ${c = 0.525}$ is known to work. Some conjectures push ${c}$ essentially down to ${0.5}$, perhaps with dependence on the Riemann Hypothesis. There is even a much stronger conjecture by Harald Cramér in 1936 that the gaps are ${O(\log n)^2}$ not ${n^c}$, and numerical evidence has so far supported this out to about ${10^{18}}$. Whether this makes the problem go away is where we get into concrete details. Do Gaps in Primes Show Up? We can do one quick calculation to argue the gap issue should not matter, even with the bigger gap values ${n^c}$. Suppose we are picking random 512-bit primes, and use one 64-bit random seed to select a starting point ${n}$ between ${2^{512}}$ and ${2^{513}}$. If we space the starting points equally, then they are ${2^{448}}$ apart. Meanwhile the largest gaps are no more than ${2^{512*0.525} < 2^{269}}$. Thus no gap has two random points—it is not close—so we should be dealing from a pool of fully ${2^{64}}$ distinct primes. Of course such a pool is not observed in the Lenstra and Heninger-et-al. studies. Ironically, using more randomness, say 512 bits of randomness, with the above simple search strategy puts bias from multiple selection of leader primes on the table. However, as opined by numerous commenters on the above studies, we are evidently dealing with a problem of insufficient randomness and systematic bias, such as tending to use the same pseudo-random generators and seeds. Then does the bias toward leader primes show up? In one sense, of course it should—completely apart from the issue of multiple selection, leader primes are more likely to be chosen by any form of the above loop with ${r \leftarrow r+4}$. For the relatively small number of primes ${p}$ that were “outed” by the GCD calculations in the studies, we can feasible compute the distance to the adjacent primes lower and higher, and simply ask: Are the distances to the nearest neighbors of the primes ${p}$ caught in the studies significantly greater than the expectation of ${\ln n}$? Same question for gaps to the nearest “strong” and/or “safe” prime. As we said a positive answer may not mean much—we would expect it anyway—but perhaps the magnitude of the gaps may shed light on why certain ${p}$ recurred so often. It is also possible to compare them with the non-shared primes ${q}$ giving ${N = pq}$. We might like to compare them with the ${p',q'}$ for keys ${N'}$ that were not caught, but of course this should be infeasible for various reasons. We would also like to know whether systematic repetition of generators and/or seeds tended to “bite” more on leader primes. One way to evade the literal problem of gaps is to use ${r \leftarrow f(r)}$ for some other update function ${f}$ besides ${r+4}$ or ${r-4}$. However, this may merely shuffle the gap issue without improving it. What happens to the gaps between primes under single-cycle permutations of ${\mathbb{N}}$? Of course we can create permutations with arbitrarily large gaps by defining ${f}$ to alternate between long even-number and long odd-number stretches upon iteration, but does this happen for any truly simple ones? $\displaystyle §$ In any event, a safer solution that avoids the gap problem is easy to describe: generate a new random seed ${s'}$ each time and use ${r \leftarrow f(r,s')}$ or just ${r \leftarrow f(s')}$ on each iteration. We stop only when ${r}$ itself is a prime, not doing a search at all. Then all primes in the chosen range are a-priori equally likely. There is no bias, and there should essentially be no duplication. Whether this would solve any tangible portion of the phenomenon of duplication of RSA primes that is actually out there, however, is problematic. Open Problems Does our question about gaps neighboring the primes ${p}$ that were found in the GCD computations have a ready answer? Is it relevant? (We might call a simple-minded question whose relevance is also part of the question a “Pipsqueak.”) What happens to gaps between prime numbers when iterating low-complexity functions ${f}$ other than adding ${2}$ or ${4}$? {\huge Do Gaps Between Primes Affect RSA Keys?} A possible contributing factor to the recent discovery of weaknesses in RSA keys en-masse \vspace{.5in} Arjen Lenstra is one of the top computational number theorists in the world, especially on the state-of-the-art in integer factoring. For example, he helped create the best general factorization method known to date—the number field sieve—see here for a previous discussion. Also he was one of the authors of the great paper that introduced the LLL lattice algorithm, which was joint work with one of his brothers, Hendrik Lenstra, and also with Lászlò Lovász. Today we want to add some potential considerations to the discussion of Lenstra’s recent paper on why RSA public keys deployed in practice are sometimes breakable. Ken and I do not know whether they actually apply, but there are some reasonable questions to ask, and a tie-in to general questions in number theory. The paper is joint work with James Hughes, Maxime Augie, Joppe Bos, Thorsten Kleinjung, and Christophe Wachter, and bears the title, “Ron was wrong, Whit was right.” Here Ron refers to Ron Rivest and Whit refers to Whitfield Diffie. Rivest is the “R” in RSA, of course, and Diffie is the Diffie in the Diffie-Hellman protocol. The former uses two primes and the latter uses one prime. The message is that crypto-systems that use one prime may be better than ones that use two primes—because the latter allow two users unwittingly to share one prime in a way that endangers both their systems. Here is how. Testing…-3 -1 AQ ${AQ}$ QA ${QA}$ xY ${xY}$ Yx ${Yx}$ xYx ${xYx}$ YxY ${YxY}$ Testing…-3 1 Ap ${Ap}$ pA ${pA}$ pAp ${pAp}$ ApA ${ApA}$ Testing…-3 2 k. ${k.}$ 0.5 ${0.5}$ 5.0 ${5.0}$ X,Y ${X,Y}$ Testing… a’ ${a'}$ b’ ${b'}$ c’ ${c'}$ d’ ${d'}$ e’ ${e'}$ f’ ${f'}$ g’ ${g'}$ h’ ${h'}$ i’ ${i'}$ j’ ${j'}$ k’ ${k'}$ l’ ${l'}$ m’ ${m'}$ n’ ${n'}$ o’ ${o'}$ p’ ${p'}$ q’ ${q'}$ r’ ${r'}$ s’ ${s'}$ t’ ${t'}$ u’ ${u'}$ v’ ${v'}$ w’ ${w'}$ x’ ${x'}$ y’ ${y'}$ z’ ${z'}$ Testing… A’ ${A'}$ B’ ${B'}$ C’ ${C'}$ D’ ${D'}$ E’ ${E'}$ F’ ${F'}$ G’ ${G'}$ H’ ${H'}$ I’ ${I'}$ J’ ${J'}$ K’ ${K'}$ L’ ${L'}$ M’ ${M'}$ N’ ${N'}$ Np’ ${Np'}$ N,p’ ${N,p'}$ O’ ${O'}$ P’ ${P'}$ Q’ ${Q'}$ R’ ${R'}$ S’ ${S'}$ T’ ${T'}$ U’ ${U'}$ V’ ${V'}$ W’ ${W'}$ X’ ${X'}$ Y’ ${Y'}$ Z’ ${Z'}$ Testing… hello 0 ${0}$ hello 1 ${1}$ hello 2 ${2}$ hello 3 ${3}$ hello 4 ${4}$ hello 5 ${5}$ hello 6 ${6}$ hello 7 ${7}$ hello 8 ${8}$ hello 9 ${9}$ Testing… a ${a}$ b ${b}$ c ${c}$ d ${d}$ e ${e}$ f ${f}$ g ${g}$ h ${h}$ i ${i}$ j ${j}$ k ${k}$ l ${l}$ m ${m}$ n ${n}$ o ${o}$ p ${p}$ q ${q}$ pq ${pq}$ p,q ${p,q}$ r ${r}$ s ${s}$ t ${t}$ u ${u}$ v ${v}$ w ${w}$ x ${x}$ y ${y}$ z ${z}$ Testing… A ${A}$ B ${B}$ C ${C}$ D ${D}$ E ${E}$ F ${F}$ G ${G}$ H ${H}$ I ${I}$ J ${J}$ K ${K}$ L ${L}$ M ${M}$ N ${N}$ O ${O}$ P ${P}$ Q ${Q}$ R ${R}$ S ${S}$ T ${T}$ U ${U}$ V ${V}$ W ${W}$ X ${X}$ Y ${Y}$ Z ${Z}$ Testing… A^n ${A^n}$ Q^n ${Q^n}$ A^A ${A^A}$ Q^Q ${Q^Q}$ 2^n ${2^n}$ n^2 ${n^2}$ p^2 ${p^2}$ 2^p ${2^p}$ Testing… 2p ${2p}$ 4x ${4x}$ 2.123x ${2.123x}$ 2.123p ${2.123p}$ Testing… x0 ${x0}$ x1 ${x1}$ x2 ${x2}$ x3 ${x3}$ x4 ${x4}$ x5 ${x5}$ x6 ${x6}$ x7 ${x7}$ x8 ${x8}$ x9 ${x9}$ Testing… 0.1234 ${0.1234}$ 1.235 ${1.235}$ 1234.1234 ${1234.1234}$ 1235.1235 ${1235.1235}$ Testing… -0.1234 ${-0.1234}$ -1.235 ${-1.235}$ -1234.1234 ${-1234.1234}$ -1235.1235 ${-1235.1235}$ Testing… 1^2 ${1^2}$ 4^4 ${4^4}$ 1234.1234^2 ${1234.1234^2}$ 1234.1234^1234.1234 ${1234.1234^{1234.1234}}$ 1235.1235 ${1235.1235}$ Testing… -1^2 ${-1^2}$ -4^4 ${-4^4}$ -1234.1234^2 ${-1234.1234^2}$ -1234.1234^1234.1234 ${-1234.1234^{1234.1234}}$ -1235.1235 ${-1235.1235}$ Testing… hello 0 ${0}$ hello 1 ${1}$ hello 2 ${2}$ hello 3 ${3}$ hello 4 ${4}$ hello 5 ${5}$ hello 6 ${6}$ hello 7 ${7}$ hello 8 ${8}$ hello 9 ${9}$ 1>2 ${1>2}$ 1,2 ${1,2}$ Testing… = ${=}$ – ${-}$ + ${+}$ ‘ ${'}$ * ${*}$ / ${/}$ . ${.}$ , ${,}$ ! ${!}$ ? ${?}$ : ${:}$ > ${>}$ < ${<}$ Testing… x+y ${x+y}$ x-y ${x-y}$ x^2 ${x^2}$ x_2 ${x_2}$ x^2_2 ${x^2_2}$ 1+x ${1+x}$ 1+y ${1+y}$ 1-x ${1-x}$ 1-y ${1-y}$ Testing… x^x ${x^x}$ x^A ${x^A}$ A^x ${A^x}$ A^A ${A^A}$ Testing… x^x ${x^x}$ x^A^A ${x^A^A}$ x^A ${x^A}$ A^x ${A^x}$ A^A ${A^A}$ Testing… p ${+p}$ ${p}$ ${pA}$ Testing… xj ${xj}$ xi ${xi}$ f ${f}$ af ${af}$ ag ${ag}$ xt ${xt}$ Testing… x0 ${x0}$ x1 ${x1}$ x2 ${x2}$ x3 ${x3}$ x4 ${x4}$ x5 ${x5}$ x6 ${x6}$ xa7 ${xa7}$ x8 ${x8}$ x9 ${x9}$ Testing… x> ${x>}$ x< ${x<}$ x! ${x!}$ x? ${x?}$ x^2 ${x^2}$ x_2 ${x_2}$ x^x ${x^x}$ x_x ${x_x}$ x, ${x,}$ x. ${x.}$ x: ${x:}$ x/ ${x/}$ Testing… xA ${x\mathbb{A}}$ xQ ${x\mathbb{Q}}$ xA ${x\mathcal{A}}$ xQ ${x\mathcal{Q}}$ xA ${x\mathbf{A}}$ xQ ${x\mathbf{Q}}$ Testing… x= ${x=}$ Testing… ${x\alpha}$ ${x\theta}$ ${x\tau}$ ${x\beta}$ ${x\vartheta}$ ${x\pi}$ ${x\upsilon}$ ${x\gamma}$ ${x\gamma}$ ${x\varpi}$ ${x\phi}$ ${x\delta}$ ${x\kappa}$ ${x\rho}$ ${x\varphi}$ ${x\epsilon}$ ${x\lambda}$ ${x\varrho}$ ${x\chi}$ ${x\varepsilon}$ ${x\mu}$ ${x\sigma}$ ${x\psi}$ ${x\zeta}$ ${x\nu}$ ${x\varsigma}$ ${x\omega}$ ${x\eta}$ ${x\xi}$ ${x\Gamma}$ ${x\Lambda}$ ${x\Sigma}$ ${x\Psi}$ ${x\Delta}$ ${x\Xi}$ ${x\Upsilon}$ ${x\Omega}$ ${x\Theta}$ ${x\Pi}$ ${x\Phi}$ Testing… ${x\pm}$ ${x\cap}$ ${x\diamond}$ ${x\oplus}$ ${x\mp}$ ${x\cup}$ ${x\bigtriangleup}$ ${x\ominus}$ ${x\times}$ ${x\uplus}$ ${x\bigtriangledown}$ ${x\otimes}$ ${x\div}$ ${x\sqcap}$ ${x\triangleleft}$ ${x\oslash}$ ${x\ast}$ ${x\sqcup}$ ${x\triangleright}$ ${x\odot}$ ${x\star}$ ${x\vee}$ ${x\bigcirc}$ ${x\circ}$ ${x\wedge}$ ${x\dagger}$ ${x\bullet}$ ${x\setminus}$ ${x\ddagger}$ ${x\cdot}$ ${x\wr}$ ${x\amalg}$ ${x+}$ ${x-}$ Testing… ${x\leq}$ ${x\geq}$ ${x\equiv}$ ${x\models}$ ${x\prec}$ ${x\succ}$ ${x\sim}$ ${x\perp}$ ${x\preceq}$ ${x\succeq}$ ${x\simeq}$ ${x\mid}$ ${x\ll}$ ${x\gg}$ ${x\asymp}$ ${x\parallel}$ ${x\subset}$ ${x\supset}$ ${x\approx}$ ${x\bowtie}$ ${x\subseteq}$ ${x\supseteq}$ ${x\cong}$ ${x\neq}$ ${x\smile}$ ${x\sqsubseteq}$ ${x\sqsupseteq}$ ${x\doteq}$ ${x\frown}$ ${x\in}$ ${x\ni}$ ${x\propto}$ ${x=}$ ${x\vdash}$ ${x\dashv}$ ${x<}$ ${x>}$ ${x:}$ Testing… ${x,}$ ${x;}$ ${x\colon}$ ${x\ldotp}$ Testing… ${x\prime}$ ${x\forall}$ ${x\infty}$ ${x\emptyset}$ ${x\exists}$ ${x\nabla}$ ${x\neg}$ ${x\backslash}$ Testing… ${x\arccos}$ ${x\arcsin}$ ${x\arctan}$ ${x\arg}$ ${x\cos}$ ${x\cosh}$ ${x\cot}$ ${x\coth}$ ${x\csc}$ ${x\deg}$ ${x\det}$ ${x\dim}$ ${x\exp}$ ${x\gcd}$ ${x\hom}$ ${x\inf}$ ${x\ker}$ ${x\lg}$ ${x\lim}$ ${x\liminf}$ ${x\limsup}$ ${x\ln}$ ${x\log}$ ${x\max}$ ${x\min}$ ${x\Pr}$ ${x\sec}$ ${x\sin}$ ${x\sinh}$ ${x\sup}$ ${x\tan}$ ${x\tanh}$ Testing… ${x(}$ ${x)}$ ${x[}$ ${x]}$ ${x\{}$ ${x\}}$ ${x\lfloor}$ ${x\langle}$ ${x\rfloor}$ ${x\rangle}$ ${x\lceil}$ ${x\rceil}$ Testing… ${x\leftarrow}$ ${x\longleftarrow}$ ${x\uparrow}$ ${x\Leftarrow}$ ${x\Longleftarrow}$ ${x\Uparrow}$ ${x\rightarrow}$ ${x\longrightarrow}$ ${x\downarrow}$ ${x\Rightarrow}$ ${x\Longrightarrow}$ ${x\Downarrow}$ ${x\leftrightarrow}$ ${x\longleftrightarrow}$ ${x\updownarrow}$ ${x\Leftrightarrow}$ ${x\Longleftrightarrow}$ ${x\Updownarrow}$ ${x\mapsto}$ ${x\longmapsto}$ ${x\nearrow}$ ${x\hookleftarrow}$ ${x\hookrightarrow}$ ${x\searrow}$ ${x\leftharpoonup}$ ${x\rightharpoonup}$ ${x\swarrow}$ ${x\leftharpoondown}$ ${x\rightharpoondown}$ ${x\nwarrow}$ ${x\rightleftharpoons}$ Testing… considerations to the discussion of ${A}$ considerations to the discussion of ${B}$ considerations to the discussion of ${Y}$ considerations to the discussion of ${y}$ considerations to the discussion of ${1+2}$ considerations to the discussion of ${1-2}$ considerations to the discussion of ${p, X}$ considerations to the discussion of ${p, x}$ considerations to the discussion of ${p^2}$ considerations to the discussion of ${p_2}$ considerations to the discussion of ${x}$ considerations to the discussion of ${y}$ considerations to the discussion of. Testing… xO ${xO}$ xA’ ${xA'}$ Testing… x^x${x^x}$ x_x${x_x}$ The Factoring Idea Perhaps there is one fundamental idea in factoring, an idea that goes back at least to Pierre de Fermat. Suppose that ${N=pq}$ where ${p,q}$ are primes. The approach is to try to factor ${N}$ by constructing another number ${M}$ so that the greatest common divisor (gcd) of ${N}$ and ${M}$ is equal to either ${p}$ or to ${q}$. There is good and bad news with this method. The good news is if you can find such an ${M}$ then ${N}$ is easy to factor. Just compute the value of ${ \gcd(N,M)}$ by Euclid’s algorithm and ${p}$ or ${q}$ will pop out. Since the gcd algorithm is quite efficient, this runs fast even if ${N}$ and ${M}$ are very large numbers. Thanks are due to Euclid, although the first proof that this algorithm runs fast is due to Gabriel Lamé in 1844. Perhaps this is one of the first algorithm analysis results. The bad news is, where does ${M}$ come from? Fermat’s idea was to try and find ${x}$ and ${y}$ so that $\displaystyle N = x^{2} - y^{2},$ and then use ${x+y}$ and ${x-y}$ as potential values of ${M}$. Note that this succeeds provided ${x+y}$ is not equal to ${N}$. The difficulty is that finding such a pair of integers ${x}$ and ${y}$ is still hard, but there are tricks that can be used to make the search for them more efficient. In any event, the search for values of ${M}$ that will work is one of the achievements of modern computational number theory. There are a variety of more and more powerful methods that attempt to find an ${M}$. If there was a way to always find ${M}$ efficiently, then of course factoring would be easy. Even Peter Shor’s quantum factoring algorithm uses the power of quantum circuits to find such an ${M}$. Attacks on RSA Let’s turn to the recent attack on RSA. Recall RSA relies on having an ${N=pq}$, where ${p}$ and ${q}$ are secret primes that are not public. The value of ${N}$ is public, but the primes are secret and will remain so provided factoring is hard. Lenstra’s paper used a clever idea, an idea that probably has been around, but still a clever idea: instead of working hard to try and find an ${M}$ that will help factor ${N}$, just use values that public. Use ${N'}$ from other public keys—basically play the RSA system against itself. If ${N'}$ and ${N}$ share a prime, ${\gcd(N,N')}$ finds it—bingo. This is really neat because these values ${N'}$ are available, there are a lot of them, and there are reasons to believe they could be useful. The empirical result found in the paper is that using these ${N'}$ values as the ${M}$‘s works quite well. The paper summarizes the result by ending with a riff on a quotation commonly attributed to Josef Stalin: Factoring one 1024-bit RSA modulus would be historic. Factoring 12,720 such moduli is a statistic. The original quotation is, “When one dies, it is a tragedy. When a million die, it is a statistic.” According to this wiki the quotation came from a 1981 Russian biography of Stalin that was used by an American historian, but it probably originates in a 1932 essay on the nature of jokes in France. Attacks on Lenstra Lenstra put two extra charges into his broadside: having the story appear in the New York Times on the same Valentine’s Day as the paper’s e-print date, and the title “Ron was wrong, Whit was right.” A great title to get noticed, but not the best for search engines in the future—jump forward ten years and imagine saying, “I recall a paper that showed a problem with RSA, I forget the title.” Right afterward there were attacks not on the results, but on their meaning and on the bearer of the news—Lenstra. I personally find this pushback to be unscientific and unwarranted. The paper shows that a small fraction of the RSA keys are easy to break, 0.2%, while 99.8% are okay. But Lenstra and his team have been attacked that this observation is picayune—if only a small percent fail, what is the concern? This line strikes me as unfair, unreasonable, and wrong: cryptography here is predicated on the chance of total failure being negligible. I regard the following statement as wrongheaded insofar as it is seen to disclaim resposibility for considerations that should be on RSA’s watch as a security firm: RSA said Thursday in a statement. “Our analysis confirms to us that the data does not point to a flaw in the algorithm, but instead points to the importance of proper implementation, especially regarding the exploding number of embedded devices that are connected to the Internet today.” One Prime vs. Two Primes The nub of the argument is whether Lenstra’s contention that relying on two primes is innately more dangerous than one is fair. There is no obvious counterpart to the GCD trick for systems that use one prime. Note that two primes are required for RSA, and this is why the GCD method could even work. Clearly the facts speak for themselves: many RSA keys were broken. I do not accept that “only” a small percent were compromised. This reminds of the scene in Dr. Strangelove where a US bomber has ignored orders to return to base and is on the way to attack the USSR and likely start WW III: President Merkin Muffley: General Turgidson! When you instituted the human reliability tests, you *assured* me there was *no* possibility of such a thing *ever* occurring! General “Buck” Turgidson: Well, I, uh, don’t think it’s quite fair to condemn a whole program because of a single slip-up, sir. How about tens of thousands of “slip-ups”? The argument then moves on to ask, what is the root cause, and what can be done to avoid these problems? The paper does not identify a main culprit, and the answers might truly emerge only from sifting how millions of RSA certificates were created—acts of checking that the authors disclaim for reasons of both security and time-intensiveness. We don’t have a main culprit either, but rather an observation about the scenery. One Way (Not) to Pick Primes We wish to draw attention to one aspect of generating primes, and ask whether it may be interacting with more-salient problems found in the generation of keys, especially by smaller “consumer” devices. For more on the salient problems, see this excellent post by Nadia Heninger pointing to another in-depth study, this Y-Combinator thread, and this Secret Blogging Seminar note, among many good sources. We make an educated guess that many implementers start with ${r}$ and ${s}$ initialized correctly. Then they perform something like the following key loop—we will consider different ways to change ${r}$ later: $\displaystyle \text{while } gcd(e,r-1) > 1 \text{ or } r \not\equiv 3 \bmod 4 \text{ or } \textsf{primetest}(r) = no''$ $\displaystyle \; \; \; r \leftarrow r+4;$ This strategy of picking a random place and then starting a search from that place yields extremely biased primes. Whether this matters may depend on implementation details discussed below, but potentially it could have three ramifications: It could explain some, if not all, the lost entropy in the key generation that Lenstra found. It could suggest a method that could break many more keys. Searching for primes with “extra” security properties, such as so-called safe primes and/or strong primes, could make the bias problem worse not better. Why This Could Be Bad To understand the bias, let’s recall an old problem from Martin Gardner’s first book of mathematical recreations from his Scientific American columns. A young man reaches a subway platform at a random moment each Saturday afternoon. Brooklyn and Bronx trains arrive equally often—[each regularly] every 10 minutes. Yet on the average he goes to Brooklyn nine times out of ten. Why? The answer is that while uptown trains to the Bronx may dutifully arrive on the :00, :10, thru :50 every hour, downtown trains to Brooklyn could be coming at :09, :19, ${\dots}$, :59. The downtown trains have a lead interval that is nine times as great, and hence captures nine times as many random moments of arrival. The distribution of primes is much more uneven than that of the trains, and some primes may have lead intervals that are vastly larger than average. Call such primes leaders. By the Prime Number Theorem, the average density of primes between a given ${n}$ and ${2n}$ will be about ${1/\ln n}$, but it was a nontrivial theorem even to show there is at least one prime in that range. If the first prime ${p > n}$ were to come a fifth of the way into that range, and we’re searching for primes with the same number of bits as ${n}$, then one-fifth of the random starting points ${r}$ will yield the same prime, ${p}$. Then about two-fifths of the ${N = pq}$ values chosen this way would include this same ${p}$, and all pairs of them would cough up ${p}$ by the GCD trick. Of course saying ${1/5}$ is a huge exaggeration. For sufficiently large ${n}$ there is always a prime between ${n}$ and ${n + n^c}$, where ${c = 0.525}$ is known to work. Some conjectures push ${c}$ essentially down to ${0.5}$, perhaps with dependence on the Riemann Hypothesis. There is even a much stronger conjecture by Harald Cramér in 1936 that the gaps are ${O(\log n)^2}$ not ${n^c}$, and numerical evidence has so far supported this out to about ${10^{18}}$. Whether this makes the problem go away is where we get into concrete details. Do Gaps in Primes Show Up? We can do one quick calculation to argue the gap issue should not matter, even with the bigger gap values ${n^c}$. Suppose we are picking random 512-bit primes, and use one 64-bit random seed to select a starting point ${n}$ between ${2^{512}}$ and ${2^{513}}$. If we space the starting points equally, then they are ${2^{448}}$ apart. Meanwhile the largest gaps are no more than ${2^{512*0.525} < 2^{269}}$. Thus no gap has two random points—it is not close—so we should be dealing from a pool of fully ${2^{64}}$ distinct primes. Of course such a pool is not observed in the Lenstra and Heninger-et-al. studies. Ironically, using more randomness, say 512 bits of randomness, with the above simple search strategy puts bias from multiple selection of leader primes on the table. However, as opined by numerous commenters on the above studies, we are evidently dealing with a problem of insufficient randomness and systematic bias, such as tending to use the same pseudo-random generators and seeds. Then does the bias toward leader primes show up? In one sense, of course it should—completely apart from the issue of multiple selection, leader primes are more likely to be chosen by any form of the above loop with ${r \leftarrow r+4}$. For the relatively small number of primes ${p}$ that were “outed” by the GCD calculations in the studies, we can feasible compute the distance to the adjacent primes lower and higher, and simply ask: Are the distances to the nearest neighbors of the primes ${p}$ caught in the studies significantly greater than the expectation of ${\ln n}$? Same question for gaps to the nearest “strong” and/or “safe” prime. As we said a positive answer may not mean much—we would expect it anyway—but perhaps the magnitude of the gaps may shed light on why certain ${p}$ recurred so often. It is also possible to compare them with the non-shared primes ${q}$ giving ${N = pq}$. We might like to compare them with the ${p',q'}$ for keys ${N'}$ that were not caught, but of course this should be infeasible for various reasons. We would also like to know whether systematic repetition of generators and/or seeds tended to “bite” more on leader primes. One way to evade the literal problem of gaps is to use ${r \leftarrow f(r)}$ for some other update function ${f}$ besides ${r+4}$ or ${r-4}$. However, this may merely shuffle the gap issue without improving it. What happens to the gaps between primes under single-cycle permutations of ${\mathbb{N}}$? Of course we can create permutations with arbitrarily large gaps by defining ${f}$ to alternate between long even-number and long odd-number stretches upon iteration, but does this happen for any truly simple ones? $\displaystyle §$ In any event, a safer solution that avoids the gap problem is easy to describe: generate a new random seed ${s'}$ each time and use ${r \leftarrow f(r,s')}$ or just ${r \leftarrow f(s')}$ on each iteration. We stop only when ${r}$ itself is a prime, not doing a search at all. Then all primes in the chosen range are a-priori equally likely. There is no bias, and there should essentially be no duplication. Whether this would solve any tangible portion of the phenomenon of duplication of RSA primes that is actually out there, however, is problematic. Open Problems Does our question about gaps neighboring the primes ${p}$ that were found in the GCD computations have a ready answer? Is it relevant? (We might call a simple-minded question whose relevance is also part of the question a “Pipsqueak.”) What happens to gaps between prime numbers when iterating low-complexity functions ${f}$ other than adding ${2}$ or ${4}$?