Tôi hiện đang cố gắng thực hiện thử thách tiền điện tử 62, phá vỡ ECDSA với nonce thiên vị, với sự trợ giúp của hai liên kết đó (1 2) mô tả chính xác cuộc tấn công. Tuy nhiên, sau khoảng 15 giờ, tôi vẫn không thể làm cho nó hoạt động và tôi hoàn toàn không biết mình đã mắc lỗi ở đâu.
Đây là cách tôi đã làm (sử dụng Python 3.6):
Đầu tiên, để tạo các chữ ký có nonce bị lỗi (tôi đã lấy cùng một mô hình với mô hình mà các liên kết đó sử dụng, vì vậy 8 bit LSB bằng 0):
nhập khẩu ecdsa
từ nhập ngẫu nhiên randint
gen = ecdsa.SECP256k1.generator
thứ tự = gen.order()
d = randint(1, thứ tự)
quán rượu = ecdsa.ecdsa.Public_key(gen, gen*d)
riêng tư = ecdsa.ecdsa.Private_key(pub, d)
R = []
S = []
cho tôi trong phạm vi (100):
nonce = randint(1, thứ tự)
nonce ^= (nonce & 0xff)
đã ký = priv.sign(h, nonce)
R.append(đã ký.r)
S.append(đã ký.s)
sau đó là cuộc tấn công thực tế, khá ngắn: chúng tôi tính toán một vài số, xây dựng ma trận với chúng, gọi thuật toán LLL và chúng tôi sẽ tìm thấy giá trị trong cơ sở rút gọn -d*ct ngay bên cạnh một cu một, theo các liên kết:
Xây dựng ma trận:
h = 1337
N_CHỮ KÝ = 100
M = [[0 cho i trong phạm vi(N_SIGNATURE + 2)] cho j trong phạm vi(N_SIGNATURE + 2)]
cho tôi trong phạm vi (N_SIGNATURE):
M[i][i] = thứ tự
ct = gmpy2.invert(256, order) # 2**l với l = bit đã biết
cu = lệnh * ct
M[-2][-2] = int(ct)
M[-1][-1] = int(cu)
cho tôi trong phạm vi (N_SIGNATURE):
M[-2][i] = int(R[i] * gmpy2.invert(S[i] * 256, đơn hàng)) % đơn hàng # t_i
M[-1][i] = int( -h * gmpy2.invert(S[i] * 256, order)) % order # u_i
Sử dụng rất hiệu quả fplll lib (phần này hơi phức tạp và sẽ được viết lại bằng Sage, nhưng nó hoạt động. Ở đây, tôi chủ yếu thực hiện định dạng trên ma trận để nó có thể được nhập vào cho fplll và tôi chuyển đổi đầu ra trở lại thành ma trận):
str_M = str(M).replace(",", "")
os.system("echo " + str_M + " | fplll -a lll -m Certified -f mpfr > result.txt")
new_matrix = [[0 cho i trong phạm vi(N_SIGNATURE+2)] cho j trong phạm vi(N_SIGNATURE+2)]
với open("result.txt", "r") dưới dạng myfile:
nội dung = myfile.read()
nội dung = content.replace("[", "").replace("]", "").replace("\n", "").split(" ")
nội dung = nội dung[:-1] # có một dòng trống ở cuối
khẳng định (len (nội dung) == pow (N_SIGNATURE + 2, 2))
tôi = 0
j = 0
cho v trong nội dung:
new_matrix[i][j] = int(v)
j += 1
nếu j == N_SIGNATURE + 2:
j = 0
tôi += 1
Bắt d:
cho hàng trong new_matrix:
nếu (hàng [-1] == cu):
d2 = (-row[-2] * gmpy2.invert(ct, order)) % đơn hàng
nếu (d2 == d):
print("Đã khôi phục khóa bí mật")
Tuy nhiên, cho dù tôi có điều chỉnh bao nhiêu biến số và thử bao nhiêu thứ đi chăng nữa, tôi vẫn không thể đạt được kết quả. Tôi cũng đã thử quét toàn bộ ma trận thay vì các phần tử cuối cùng nhưng không thành công. Có phải tôi đã mắc một sai lầm ngớ ngẩn mà tôi không để ý hay có điều gì đó khá sai trong mã của tôi?
Lưu ý: dòng sau trong liên kết 2:
Tôi quên đề cập đến: bạn sẽ muốn viết triển khai của mình để hoạt động trên các vectơ của các số hữu tỉ. Nếu bạn có phao có độ chính xác vô hạn, chúng cũng sẽ hoạt động.
thu hút sự chú ý của tôi, nhưng mpfr đối số của fplll phải phù hợp với những gì cần thiết ở đây.Và trong trường hợp không được, tôi cũng đã thử sử dụng ma trận Sage được xác định trên QQ, nhưng nó không hoạt động tốt hơn.
