suppose i have two equations: $$ (m)^{3} \bmod n = c_{0}$$ $$(m + 2^{k}r + d) \bmod n = c_{1}$$ The values($c_{0}, c_{1}, k, d$) are known. I wanted to retrieve r (ofc $|r| < n^{\frac{1}{9}})$ Using resultant on equations gives me equation of 9 degree.: $$w(x) = x^{9} + 3(c_{1} - c_{0})x^{6} + (3c_{0}^{2} + 21c_{0}c_{1} + 3c{1}^{2})x^{3} + (c_{1} - c_{0})^3 \bmod n = 0$$ , where x is $2^{k}r + d$ (as usual with coppersmith method). After substitute x with $2^{k}r + d$ and change polynomial to monic i have polynomial of 9 degree w(r).

My question is that: How can i use coppersmith attack? I tried sagemath small_root() but it dosnt return r(it return it only in special case when d = 0, and polynomial of 9 can be cast to polynomial of 3- bc it have only nonzero coefficient on $ r^3, r^6, r^9 $. Can my goal be achieved by changing implementation of small_root or by other mathematic transformation?


N = 55555
R = Zmod(N)
P.<x> = PolynomialRing( R, implementation='NTL' )

for k in range(1,5):
f     = (x-7)^k*(x-5)*(x-43)*(x-273)    # 7, 43, 273 are here for making 2 a root
d     = f.degree()
roots = [ r for r in R if f(r) == R(0) ]
info  = ( str(roots) if len(roots)<10
          else str(roots[:10]) + ( '... (totally %s roots)' % len(roots) ) )
print "k=%s" % k
print "          ROOTS: %s" % info
print "    SMALL ROOTS: %s" % f.small_roots()

Code above doesnt return 2 even if it meet condition for Coppersmith's method.


Coppersmith's method, parameterized by $\epsilon$, finds all roots $\le \frac{1}{2} n^{\beta^2/\delta - \epsilon}$ to a polynomial $f(x)$ of degree $\delta$ modulo an unknown factor of $n$ of size $\ge n^\beta$. In your case, $\beta = 1$ and $\delta = \{4,5,6,7\}$.

Sage defaults $\epsilon = \beta/8$, which in your case would be $0.125$. However, $55555^{1^2/\{4,5,6,7\} - 0.125}$ is, respectively, $\{1.96, 1.13, 0.79, 0.61\}$. Only the first (almost) respects the bound. But if you tweak small_roots with an appropriate $\epsilon$, e.g., f.small_roots(epsilon=0.02), you should get more satisfactory answers.

| improve this answer | |

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.