The basic idea behind one type of lattice attack to DSA and ECDSA scheme is to construct a system of congruences, and convert the hidden number problem into the nearest vector problem. if one of the solutions of the congruences is below a certain bound, the private key can be found by solving the closest vector. If the bound becomes larger, the size of solution within which the attack is effective can be broadened accordingly, thus reducing the level to construct such congruences. A new bound based on the oretical analysis and calculation was presented. The new bound was 6.92 times larger than the original one, reducing the level to launch an effective lattice attack significantly. This paper designed and implemented experiment to verify this new bound by collecting signatures from OpenSSL. The results show that under the new bound, the lattice attack only require solution vector’s elements’ 3 most significant bits to be known, compared with 6 most significant bits to be known before. For DSA, the success rate is about 80% with a lattice of size 350. For ECDSA, the success rate is about 97% with a lattice of size 260. Furthermore, by subtracting a base vector from the solution vector, the requirement of known bits can be reduced to just one, the difficulty to mount an attack can be reduced even further.
