We are currently trying to reproduce the implementation of the ROCA-Paper. Therefore we calculated $M'$ from $M$ and $Order_M'$ from $Order_M$ to reduce the search space, but when we hand these values to the coppersmith algorithm as described in Algorithm 1 of the paper, this algorithm does not find any roots.vIt only finds "potential" roots, which are fractional numbers and result in float numbers between $0$ and $1$.

These Roots have the form:

  • 7903163834028830451137438186485015861/17304344567133368654502628603056098610,
  • 213501605850162343745788742125935233/17304344567133368654502628603056098610, ...

Our Implementation can be found on Github

Does anybody have an idea, why the coppersmith algorithm does not return correct roots?


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} \bmod N)(65537^{a'}\bmod M), $$ so when you put $\mathrm{result} = f(\mathrm{root[0]})$, you do not get $p$ or a multiple of $p$, so the gcd makes no sense (and if ever you get a gcd greater than 1, you may have a factor of $N$).

I suggest that if root[0] is an integer, put it in roots and return that. That's what I did and it works fine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.