Ask Your Question

Sanguinius's profile - activity

2021-04-29 21:37:17 +0100 received badge  Notable Question (source)
2020-10-11 20:02:33 +0100 received badge  Famous Question (source)
2018-12-11 17:16:02 +0100 received badge  Notable Question (source)
2018-12-11 17:15:35 +0100 received badge  Popular Question (source)
2018-04-26 17:03:05 +0100 received badge  Popular Question (source)
2017-06-30 20:13:55 +0100 commented question Finding Small Roots of Multivariate Polynomial Modulo an Integer

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

2017-06-30 16:21:46 +0100 commented question Finding Small Roots of Multivariate Polynomial Modulo an Integer

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.

2017-06-30 15:16:14 +0100 commented question Finding Small Roots of Multivariate Polynomial Modulo an Integer

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.

2017-06-30 13:58:07 +0100 received badge  Editor (source)
2017-06-30 11:36:07 +0100 asked a question 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://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.

2017-06-30 11:36:07 +0100 asked a question Finding Small Roots of Multivariate Polynomials 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) \pmod{8}$

It is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage. However, is there a workaround code / method that will allow for small root finding of the above polynomial, and others of the same form?

Thanks, and your time and effort are greatly appreciated.