In this note, the manufacturer of a RSA key generation gizmo vulnerable to the new ROCA attack (see second section) explains that

it is common practice to employ acceleration algorithms in order to generate key pairs, especially if time resources are sparse. (We) also utilizes such an acceleration algorithm in time-restricted cases, called “Fast Prime”. This algorithm is software-based..

The foundations of “Fast Prime” date back to the year 2000. Its use started around ten years later after thorough reviews. As a sub-part of one cryptographic software library which is supplied to customers as a basis for their own development, this software function was certified by the BSI (Federal Office for Information Security) in Germany. No mathematical weaknesses were known, nor have been discovered during the certification processes.

What is “Fast Prime” and where was it suggested?

A source about the ROCA vulnerability/attack targeting some RSA keys generated using “Fast Prime” is this pre-anouncement (updated link), and this short Java code testing a public modulus $N$ for vulnerability. Essentially this tests a number of relations of the form $N^2\bmod11=1$, $N^3\bmod37=1$, $N^6\bmod97=1$ (where the modulus is a small prime $r$ and the exponent divides $r-1$ ), and conclude that if a number of such tests pass, then the key likely is vulnerable. This article also seems well informed and has interesting tidbits, including alleged identification of an affected software library, which has a certification report and a security target lite (that is, sanitized for public consumption); but I found nothing revealing.

For random public modulus $N$ with no small divisor, the whole published ROCA test (be it in Java, Python, or C#) has probability $1/238878720\approx2^{-27.8}$ to hold (thus low odds of false positive when few keys are tested), and is equivalent to: $$\begin{align} N^{2}&\bmod11&&=1&&\wedge\\ N^{6}&\bmod13&&=1&&\wedge\\ N^{8}&\bmod17&&=1&&\wedge\\ N^{9}&\bmod19&&=1&&\wedge\\ N^{3}&\bmod37&&=1&&\wedge\\ N^{26}&\bmod53&&=1&&\wedge\\ N^{20}&\bmod61&&=1&&\wedge\\ N^{35}&\bmod71&&=1&&\wedge\\ N^{24}&\bmod73&&=1&&\wedge\\ N^{13}&\bmod79&&=1&&\wedge\\ N^{6}&\bmod97&&=1&&\wedge\\ N^{51}&\bmod103&&=1&&\wedge\\ N^{53}&\bmod107&&=1&&\wedge\\ N^{54}&\bmod109&&=1&&\wedge\\ N^{42}&\bmod127&&=1&&\wedge\\ N^{50}&\bmod151&&=1&&\wedge\\ N^{78}&\bmod157&&=1 \end{align} $$

Note: the exponent for $N$ in each condition $\bmod p_i$ turns out to be the order of $2^{16}+1\bmod p_i$ in $\mathbb Z_{p_i}^*$, for reasons explained below. I have omitted the other small primes $p_i\le167$ included in the ROCCA test, because for these $2^{16}+1\bmod p_i$ is a generator and the order is $p_i-1$ , thus any $N$ without trivial divisor pass the corresponding test $N^{p_i-1}\bmod p_i=1$ .

Update: the Roca paper (or a preprint thereof) is now online: Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas; The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli.

Paraphrasing that, the factors making the attack possible (presumably, those generated by “Fast Prime” ) all are of the form $$p=k\;M+(65537^a\bmod M) \text{ where } M=P_n\#=\prod_{i=1}^n p_i$$ with $p_i$ is the $i^\text{th}$ prime. The integer $n$ is chosen according to the desired size of $p$ : $n=39$ ( $p_n=167$ ) for $256\dots480$-bit $p$ ; $n=71$ ( $p_n=353$ ) for $496\dots976$-bit $p$ ; $n=126$ ( $p_n=701$ ) for $992\dots1968$-bit $p$ ; $n=225$ ( $p_n=1427$ ) for $1984\dots2048$-bit $p$ .

It follows that any public moduli made from such primes verifies $\exists a, 1\le i\le n\implies N\equiv65537^a\pmod{p_i}$.