How ROCA get the polynomial used with coppersmith

Question

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?

Answer 1

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.

Answer 2

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$.