code problem in coppersmith.sage

[swLai]

Thanks for sharing the work!

I have a little question about the code at line 99 in coppersmith.sage, which represents the formulae at page 9 below in (Wong, 2015).

I mean, in (Wong, 2015), g_ij = x^j * N^i * f^(m-i), but the code here is composed as g_ij = x^j * modulus^(m-i) * f^i... Would the results be different if I change the code here?

[mimoo]

honestly, I wrote this such a long time ago that I don't know. But it used to work so I wouldn't change things around :)

[swLai]

That makes sense, since LLL will always manifest the same shortest vector in a given lattice space as long as the original setup basis achieved certain conditions. So, the case here just gave an excellent example: Even though we did not take the suggested formulae, we can still get correct results as long as B is full rank, etc. ——— Another question is that, code line 131 states that, the wanted root should make the result achieve: gcd(result, modulus) >= N^beta.

That makes me interpret it as: b should be greater than or equal to N^beta (b is subject to beta)

Since beta=1 in this experiment, b must represent the modulus,N, due to Coppersmith’s statement: b|N.

[The questions is: Does gcd(result, modulus) still represent b when beta < 1 ?]

Not sure am I wrong or not, but my opinion is that: To accommodate all possibilities, beta should, alternatively, be subject to b, which gives a sense of how to choose proper beta in order to produce X, m, t, epsilon.

For example, since b|N, b has to be p, q or N. And, in general RSA system, p, q ~ N^(1/2), we can choose beta based on this: b ~ N^(1/2) >= N^beta —-> beta \in (0, 1/2]

And, the condition is: gcd(result, N) = gcd(kb, N) != 1 (b and N are not relative prime, then the root is a correct one)