1
$\begingroup$

I am trying to implement Coppersmith's attack to find small roots of an example bivariate polynomial.

$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$

In this example, the results should be $x = 2$ and $y = 8$ (obviously you could brute force it, but that's besides the point).

For univariate polynomials, Coppersmith's attack is implemented via the .small_roots() function. However, it is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage. Is there any workaround code / method that will allow for small root finding of multivariate polynomials?

Relevant papers:

http://honors.cs.umd.edu/reports/lowexprsa.pdf

http://www.jscoron.fr/publications/bivariate.pdf

Thanks, and your time and effort are greatly appreciated.

Improve this question
$\endgroup$
3
  • $\begingroup$ How is this related to RSA? Are you having some sort of unknown padding, hence the second variable? If your question is purely about "how to use Sage to do..." then I think you'll find more help on SO. $\endgroup$
    – Lery
    Commented Jun 30, 2017 at 22:54
  • 1
    $\begingroup$ A further search led me to this very interesting paper, which I added to my "to read" list (the ever-growing one), and which seems to explain in details how one can do what you're trying to do. And it even happens to have been implemented for PlaidCTF using Sage. $\endgroup$
    – Lery
    Commented Jun 30, 2017 at 23:11
  • 1
    $\begingroup$ Thanks for your comment. Looks like there's no easy way around the issue. I'll have to read more before I attempt to figure out what's going on in that code. $\endgroup$
    – user3089196
    Commented Jul 1, 2017 at 2:32

1 Answer 1

Reset to default
2
$\begingroup$

If you calculate modulo $8$, your polynomial becomes constant: $f(x, y) = 1-N \pmod{8}$

So something is wrong about what you are trying to do!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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