You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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?
The text was updated successfully, but these errors were encountered:
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)
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?
The text was updated successfully, but these errors were encountered: