Tag Info

In the ROCA paper the authors define an integer $M$ (which they call a primorial) as follows: $$M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n$$ Said another way, $M$ is the product of the first $n$ ...

This is a tentative guess at answering my own question. Perhaps the "Fast Prime" method alluded to in the question's citation is that of these two papers (the second polishing the first): [JPV2000]: ...

You are correct—you do want to find a small root of [*] $$ f(x) = M \cdot x + (65537^a \bmod M) \bmod N $$ modulo a divisor $p$ of $N$. In other words, you want to find a divisor of $N$ in the ...

A similar observation as yours was the starting point for the ROCA attack. In 2016, some of the authors of the ROCA attack (with other coauthors) had published a paper a USENIX about determining the ...

At the end of the function coppersmith_howgrave_univariate, you have if gcd(modulus, result) >= modulus ^ beta: You created $f$ as $$ f(x) = x + (M'^{-1} \...

One of the important part of the attack is to find $f$ such as $f(x) \equiv 0\bmod p$. First, you reduce $f(x)= x + (M^{-1} \bmod N) * (65537^{a} \bmod M)$ modulo $N$, to get a smaller coefficient (...