I have a problem which require lattice attack at some point to reduce work load but for most of use lattices are hard to understand. I have: k1 = (k0+x1)*const +1 k2 = (k1+x2)*const +1 k3 = (k2+x3)*const +1 k4 = (k3+x4)*const +1 All these equations are mod 2^32. Known parts are: LSB(k0) = 0x59 LSB(k1) = 0x32 LSB(k2) = 0x89 LSB(k3) = 0x45 LSB(k4) = 0x61 x1 = 0xe4 x2 = 0xb6 x3 = 0xeb x4 = 0x9b const = 0x08088405 invconst = 0xd94fa8cd Where LSB means Last Significant Byte and i understood the layout of the matrix when attacking ECDSA with biased nonces but the layout of the matrix here is what kills me. I cannot break the equation into a lattice problem but i have read Stern's Attack on truncated LCG using lattice but the code is a bit more complex. I know where to put 2^32 in the matrix ( it goes diagonally) but what about the known parts of K. I have read that, to find a Shortest Vector we need the good basis, but how do i go about getting basis from equation. Continue reading...
