ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 05 Jul 2017 11:09:52 +0200Finding Small Roots of Multivariate Polynomial Modulo an Integerhttps://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/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://www.jscoron.fr/publications/bivariate.pdf
Thanks, and your time and effort are greatly appreciated.Fri, 30 Jun 2017 05:30:13 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/Comment by B r u n o for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38142#post-id-38142Is 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$.Fri, 30 Jun 2017 14:58:30 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38142#post-id-38142Comment by Sanguinius for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38143#post-id-38143I 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.Fri, 30 Jun 2017 15:16:14 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38143#post-id-38143Comment by tmonteil for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38144#post-id-38144If you work modulo 8, your polynomial f is constant, right ?Fri, 30 Jun 2017 15:26:15 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38144#post-id-38144Comment by Sanguinius for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38145#post-id-38145I 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).
In the context of the RSA cryptosystem, $(8x+7)$ and $8y+7& would be the prime factors of the modulus N.Fri, 30 Jun 2017 16:21:46 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38145#post-id-38145Comment by dan_fulea for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38147#post-id-38147The posted link [http://honors.cs.umd.edu/reports/lowexprsa.pdf](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.Fri, 30 Jun 2017 17:55:51 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38147#post-id-38147Comment by dan_fulea for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38149#post-id-38149On page 7 of the *loc. cit.* we have the following example:
$$ ƒ(x,y) = (8x + 7)(8y + 7) – 1633 \ .$$
We are searching a solution by checking all $(x,y)$ with either $x$ OR (not AND as specified in the source) $y$ between $0$ and $M=\sqrt{1633}/8$. Sage is doing this quickly:
sage: f(x,y) = (8*x+7)*(8*y+7)-1633
sage: M = int( sqrt(1633) / 8 )
sage: M
5
sage: for x in range(1,M):
....: if 1633 % (8*x+7) == 0:
....: print "Divisor %s for x=%s" % ( 8*x+7, x )
....:
Divisor 23 for x=2
(And if the rest $7$ would be different for the factor $(8y+?)$, a loop for this factor has to be started, too.)Fri, 30 Jun 2017 19:30:45 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38149#post-id-38149Comment by Sanguinius for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38150#post-id-38150Yes that's correct, but the problem is that you need an algorithm that works for numbers of much larger magnitude. RSA primes are usually at least 1024 bits, so you're looking at a number in the magnitude of $2^{1024}$. Brute force simply will not work for such a scenario. Coppersmith's attack is supposed to run in polynomial time, not exponential, hence why it's so powerful.Fri, 30 Jun 2017 20:13:55 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38150#post-id-38150Comment by dan_fulea for <p>I am trying to apply Coppersmith's attack to find small roots of an example polynomial </p>
<p>$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$</p>
<p>For univariate polynomials, Coppersmith's attack is implemented via the <code>.small_roots()</code> 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? </p>
<p>In this example, the results should be $x = 2$ and $y = 8$.</p>
<p>Relevant papers:</p>
<p>http://honors.cs.umd.edu/reports/lowexprsa.pdf (http://honors.cs.umd.edu/reports/lowe...)</p>
<p>http://www.jscoron.fr/publications/bivariate.pdf (http://www.jscoron.fr/publications/bi...)</p>
<p>Thanks, and your time and effort are greatly appreciated.</p>
https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38183#post-id-38183It was really not simple to find the point that hurts, and in a comment there is not so much place to also solve all questions in a realistic scenario.
So the comment "Yes, but..." is frustating. (First things first. If these are done, then we can insert the but-points at a second point after restating the question for them.)
Please edit the question, so that it makes sense, then put the right focus in it.
(The cited source also needs a brute force search at some point. It is hard to fix all details and frames in an answer, the question has to fix it. The question was not "explain the algoritm, the subtle points of it, and implement it in sage, giving also a realistic example"... This is too much for a hobby.)Wed, 05 Jul 2017 11:09:52 +0200https://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/?comment=38183#post-id-38183