Finding Small Roots of Multivariate Polynomial Modulo an Integer

asked 2017-06-29 22:30:13 -0500

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I am trying to apply Coppersmith's attack to find small roots of an example polynomial

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

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 the above polynomial, and others of the same form?

In this example, the results should be $x = 2$ and $y = 8$.

Relevant papers:

http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)

http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)

Thanks, and your time and effort are greatly appreciated.

edit retag flag offensive close merge delete

Comments

Is your example really representative of your needs? Because in the example you provide, there are two features that allow you to compute the roots efficiently:

  • You look for roots modulo $8$: With two variables taking $8$ different values each, you can use a brute force algorithm and test the $64$ pairs $(x,y)$.

    • You can first reduce your equation modulo $8$: Here you get $f(x,y) = 1 - N$, so your equation has eitger no solution or an infinity of them, depending on whether $N \equiv 1\mod 8$.
B r u n o gravatar imageB r u n o ( 2017-06-30 07:58:30 -0500 )edit

I edited the OP a bit. Unfortunately I don't have enough Karma to create clickable hyperlinks, but I put some relevant papers in the description. The first paper is where the example came from, and it uses the Coppersmith method described in the second link to obtain those roots. For univariate polynomials, Coppersmith's attack is already implemented via the .small_roots() method. However, this is not the case for multivariate polynomials, where I get a NotImplementedError. As such, I was asking to see if there was a potential workaround.

Sanguinius gravatar imageSanguinius ( 2017-06-30 08:16:14 -0500 )edit

If you work modulo 8, your polynomial f is constant, right ?

tmonteil gravatar imagetmonteil ( 2017-06-30 08:26:15 -0500 )edit

I believe so. However, the objective is to find $x$ and $y$ such that $(8x+7)(8y+7)−N \pmod{8} = 0$.

$x = 2$ and $y = 8$ are thus roots of the polynomial. The goal of this problem is to find small integer zeroes of bivariate polynomials modulo a given integer via Lattice Basis Reduction (as shown here: https://en.wikipedia.org/wiki/Coppersmith_method (https://en.wikipedia.org/wiki/Coppers...)).

In the context of the RSA cryptosystem, $(8x+7)$ and $8y+7& would be the prime factors of the modulus N.

Sanguinius gravatar imageSanguinius ( 2017-06-30 09:21:46 -0500 )edit

The posted link http://honors.cs.umd.edu/reports/lowexprsa.pdf gives us an other story. Citing it "Actually Theorem 2 all together isn’t very fun, but it does provide the framework to produce a corollary that is immensely helpful..." and this Cor can be simply understood in a simple case. Let $N = pq= 2017\cdot 2027=4088459< 2^{24}$. We want the two (prime) factors. Fix $r=64\ge 2^{24/4}$. Assume we know $p_0=33$, the rest of $p$ modulo $r$. Then $q_0=43$ is... We search integer solutions for $$ (64x+33)(64y+43) = 4088459\ .$$ And of course integer not modulo $64$, since we arranged it is so while computing $q_0$ !

And here we can start the brute force search.

dan_fulea gravatar imagedan_fulea ( 2017-06-30 10:55:51 -0500 )edit