How ROCA get the polynomial used with coppersmith

I'm trying to understand the ROCA attack on RSA from Matus Nemec et al. but I'm stuck on how they goes from the constraint they have expressed has: $$f(x) = x ∗ M' + (65537^{a'} \mod M') \pmod p$$

To the real polynomial they feed to Coppersmith: $$f(x) = x + (M'^{-1} \mod N) * (65537^{a'} \mod M') \pmod N$$

Specifically how we can go from a polynomial on $\Bbb{Z}/p\Bbb{Z}$ to a polynomial on $\Bbb{Z}/N\Bbb{Z}$ ?

If we try with some real values and we don't use $M'$ but keep $M$: M = P_{39}\# \\ a = 1675986788854043070, k = 26617369843\\ \begin{align} p = & k * M + (65537^a\mod M) \\ = & 256311276376047921060658369130455899807 \\ & 39897944295144398331573049960294370089 \end{align}

$q$ computed in the same way:

\begin{align} q = & 143831813798290446194046706419144504095 \\ & 59736324729154061604353910339692872653 \end{align}

$k$ is obviously a root for

$f(x) = x ∗ M + (65537^{a} \mod M) \pmod p$

but, as far as I understand it's not for

$f(x) = x + (M^{-1} \mod N) * (65537^{a} \mod M) \pmod N$

With: \begin{align} M^{-1} \mod N = & 352742121330634029642965446346501378229514125041483823729 \\ & 9285302994689783984115678100687263685016509742529377 \\ & 76329363423355363257168553996151098868709524 \end{align}

Where am I wrong on this?

• Take a look at theorems 5 and 6 in Alexander May's PhD thesis. You need the conditions (1) $p^k$ divides $f(x)$ and (2) $|f(x)| < p^k$ to get that $x$ is a root. Condition (2) you obtain by viewing $f(x)$ as a scalar product of a vector containing the coefficients of the polynomial $f$ and a vector containing the powers of $x$. – j.p. May 28 '18 at 5:58
• Sorry, my $k$ doesn't have to do with your $k$. – j.p. May 28 '18 at 19:37

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 residue class $M \cdot x + (65537^a \bmod M)$. This is explicitly accomplished by the Coppersmith/Howgrave-Graham method, as long as the appropriate restrictions are respected.

However, Coppersmith's method to find such roots traditionally expects a monic polynomial as input. So, to make it monic we simply divide it by the coefficient associated with $x$, that is, $M$: $$g(x) = \frac{1}{M}f(x) = x + \frac{65537^a \bmod M}{M} \bmod N\,.$$ The roots of $g(x)$ are the same as $f(x)$; to see this decompose the polynomial into its factorization: $$f(x) = (x - \alpha_0)(x - \alpha_1)\dots(x - \alpha_n)\,,$$ $$g(x) = \frac{1}{M}(x - \alpha_0)(x - \alpha_1)\dots(x - \alpha_n)\,,$$ and notice that both have the same roots $\alpha_i$. The Coppersmith method finds the appropriate root modulo a factor of $N$ once you guess the correct $a$.

[*]: The ROCA paper uses alternative $M'$ there, but this is irrelevant here.

• I thought the constraint was $f(x) = M \cdot x + (65537^a \mod M) \mod p$ and not $f(x) = M \cdot x + (65537^a \mod M) \mod N$. – needle Aug 3 '18 at 14:15
• It is more convenient to use the Alexander May (§3.2) formulation of Coppersmith's method, which explicitly finds a small root of $f(x)$ modulo an unknown factor of $N$, i.e., $p$. – Samuel Neves Aug 7 '18 at 9:55

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 (we can do that because $p$ divides $N$), and then we can check if we still have $f(k) \equiv 0 \bmod p$:

\begin{array}{rcll} f(k) & \equiv & k + (M^{-1} \bmod N)(65537^{a} \bmod M) & \mod p \\ & \equiv & k + (M^{-1} \bmod N)(-kM) & \mod p \\ & \equiv & k - k & \mod p \\ & \equiv & 0 & \mod p. \end{array}

On the second line because $p=kM+(65537^a\bmod M)$ so $(65537^a\bmod M) \equiv -kM \bmod p$, and the third line because $M(M^{-1} \bmod N) \equiv 1 \bmod p$.