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]:
print(str(k))
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?