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 you have read our privacy policy.