# Differences between the theory and implementation of a lattice attack against ECDSA

I know the theory of lattice attacks against ECDSA from Minerva. So, as far as I can understand, the lattice that they build is

$$L_M = \begin{bmatrix} 2^ln & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 2^ln & 0 & \cdots & 0 & 0 & 0 \\ 0 & 0 & 2^ln & \cdots & 0 & 0 & 0 \\ & \vdots & & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & 2^ln & 0 & 0 \\ 2^l t_1 & 2^l t_2 & 2^l t_3 & \cdots & 2^lt_d & 1 & 0 \\ 2^l u_1 & 2^l u_2 & 2^l u_3 & \cdots & 2^lu_d & 0 & n \end{bmatrix}$$

where $$t_i = s_i^{-1}r_i \mod n$$, $$u_i = -s^{-1}H(m_i) \mod n$$, $$l$$ is the nonce leakage in number of null most significant bits (for all signatures -- I'm aware that Minerva uses $$l_1, \dots l_d$$, but let's simplify and consider $$l_1 = \dots = l_d = l$$) and $$n$$ is the order of the group built over the elliptic curve used for ECDSA.

I found this repository online that uses a slightly different lattice:

$$L_R = \begin{bmatrix} 2^{l+1}n & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 2^{l+1}n & 0 & \cdots & 0 & 0 & 0 \\ 0 & 0 & 2^{l+1}n & \cdots & 0 & 0 & 0 \\ & \vdots & & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & 2^{l+1}n & 0 & 0 \\ 2^{l+1} t_1 & 2^{l+1} t_2 & 2^{l+1} t_3 & \cdots & 2^{l+1}t_d & 1 & 0 \\ 2^{l+1} u_1 & 2^{l+1} u_2 & 2^{l+1} u_3 & \cdots & 2^{l+1}u_d & 0 & n \end{bmatrix}$$

where all the quantities are defined like before, except for $$u_i = -(s_i^{-1} \mod n) \cdot H(m_i) + n$$. If I'm not mistaken, the $$l+1$$ and the $$+n$$ at the end of $$u_i$$ in this case are due to recentering. What I completely fail to understand is why $$u_i = -(s_i^{-1} \mod n) \cdot H(m_i) + n$$ and not $$u_i = -(s_i^{-1} \cdot H(m_i) \mod n) + n$$. If I change the relevant line of code from

2 * kbi * (- hash_i * inv(sigs[i].s, n_order) )  + n_order


to:

2 * kbi * (- hash_i * inv(sigs[i].s, n_order) ) % n_order  + n_order


(where kbi = 2**l) the code does not work anymore and it does not find any secret key where it worked perfectly before the change.

Any hints on a reason for this peculiar behavior?

• First of all, welcome to Cryptography. Sometimes we are all stupid. Please revert back to your question and answer this question yourself. This is better since if one searches this question may skip since there is no answer. If one can see there is an accepted answer, then they can consider that the problem is resolved. Oct 31, 2023 at 16:06

2 * kbi * (- hash_i * inv(sigs[i].s, n_order) ) % n_order  + n_order

reduces modulo n_order even 2*kbi. The actual line of code should be
2 * kbi * (- hash_i * inv(sigs[i].s, n_order) % n_order)  + n_order