I have read so many papers and posts about lattice attacks on ECDSA but none of them used an example of different MSB values for k but instead they all used fixed MSB. So here i am trying to understand it better, I have 3 nonce (k1,k2 and k3) with their distinct MSB but i do not know how to place them into a matrix.

Here is the code i am following:

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
A = 0
B = 7
F = GF(p)
E = EllipticCurve(F,[A,B])
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = E(Gx,Gy)
assert G.order() == n
SIGs =  []
B = 2**(256-128)
print("Constructing Two Rows of Lattice")
Mtilde = [B, 0]
Rtilde = [0, B/n]
for sig in SIGs:
    r,s,m = sig
    Mtilde += [inverse_mod(s,n)*m % n]
    Rtilde += [inverse_mod(s,n)*r % n]

# We redefine the arrays as matrixes
print("Building Matrixes")
Mtilde = matrix(QQ, 1, len(Mtilde), Mtilde)
Rtilde = matrix(QQ, 1, len(Rtilde), Rtilde)

# We contruct the diagonal submatrix with p entries
print("Constructing Diagonal submatrix...")
Pdiag = -n*identity_matrix(QQ, len(SIGs));

# We construct the lower left n x 2 zero block matrix
print("Constructing lower left n x 2 zero block matrix...")
Z = matrix(QQ, len(SIGs), 2, [0 for i in range(len(SIGs)*2)] )

# We construct the final matrix assembling all blocks
print("Constructing final matrix...")
M = block_matrix([[Z, Pdiag]])
M = block_matrix([[Mtilde], [Rtilde], [M]])

# We run the LLL algorithm
print("Running LLL...")
L = M.LLL()

for row in L.rows():
    for i in range(len(SIGs)):
        r,s,m = SIGs[i]
        solk = row[i+2]
        for k in [solk,-solk]:

I know that in the above, 0 in Mtilde =[B,0] is MSB for nonce but if i put my k1's MSB there then what about k2 and k3.

I hope i am making sense?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.