Ajută la spargerea ECDSA cu non-uri părtinitoare

În prezent încerc să fac Provocarea criptopalilor 62, rupând ECDSA cu non-uri părtinitoare, cu ajutorul acelor două legături (1 2) care descriu cu exactitate atacul. Cu toate acestea, după aproximativ 15 ore, încă nu pot să funcționeze și nu am absolut nicio idee unde am greșit.

Iată cum am făcut-o (folosind Python 3.6): În primul rând, pentru a genera semnăturile cu nonces defecte (am luat același model ca cel pe care îl folosesc acele linkuri, deci cei 8 biți LSB sunt zero):

import ecdsa
de la import aleatoriu randint

gen = ecdsa.SECP256k1.generator
ordine = gen.order()
d = randint(1, ordine)

pub = ecdsa.ecdsa.Public_key(gen, gen*d)
priv = ecdsa.ecdsa.Private_key(pub, d)

R = []
S = []

pentru i în interval (100):
    nonce = randint(1, ordine)
    nonce ^= (nonce și 0xff)
    semnat = priv.sign(h, nonce)
    R.apend(semnat.r)
    S.apend(semnat.s)

apoi atacul propriu-zis, care este destul de scurt: calculăm câteva numere, construim o matrice cu ele, apelăm algoritmul LLL și ar trebui să găsim în baza redusă valoarea -d*ct chiar lângă a cu unul, conform link-urilor:

Construirea matricei:

h = 1337
N_SIGNATURE = 100

M = [[0 pentru i în interval (N_SIGNATURE + 2)] pentru j în interval (N_SIGNATURE + 2)]

pentru i în interval (N_SIGNATURE):
    M[i][i] = ordin

ct = gmpy2.invert(256, ordine) # 2**l cu l = biți cunoscuți
cu = ordin * ct
M[-2][-2] = int(ct)
M[-1][-1] = int(cu)

pentru i în interval (N_SIGNATURE):
    M[-2][i] = int(R[i] * gmpy2.invert(S[i] * 256, ordine)) % ordine # t_i
    M[-1][i] = int( -h * gmpy2.invert(S[i] * 256, ordine)) % ordine # u_i

Folosind foarte eficient fplll lib (această parte este un pic neplăcută și va fi rescrisă folosind Sage, dar funcționează. Aici, fac în principal formatarea pe matrice, astfel încât să poată fi introdusă pentru fplll și convertesc rezultatul înapoi într-o matrice):

str_M = str(M).replace(",", "")
os.system("echo " + str_M + " | fplll -a lll -m dovedit -f mpfr > rezultat.txt")

matrice_nouă = [[0 pentru i în interval (N_SIGNATURE+2)] pentru j în interval (N_SIGNATURE+2)]

cu open("result.txt", "r") ca fișierul meu:
    conținut = myfile.read()
    contents = contents.replace("[", "").replace("]", "").replace("\n", "").split(" ")
    conținut = conținut[:-1] # există o linie goală la sfârșit

    assert(len(conținut) == pow(N_SIGNATURE + 2, 2))

    i = 0
    j = 0
    pentru v în conținut:
        matrice_nouă[i][j] = int(v)
        j += 1
        dacă j == N_SEMNATURĂ + 2:
            j = 0
            i += 1

Obținerea d:

pentru rândul din new_matrix:
    if(rând[-1] == cu):
        d2 = (-row[-2] * gmpy2.invert(ct, order)) % ordin
        
        dacă(d2 == d):
            print("Cheie secretă recuperată")

Cu toate acestea, indiferent câte variabile ajust și lucruri pe care le încerc, nu pot obține un rezultat. De asemenea, am încercat să scanez întreaga matrice în loc de ultimele elemente, fără succes. Am făcut o greșeală prostească pe care nu am observat-o sau este ceva destul de greșit în codul meu?

Notă: următorul rând din linkul 2:

Am uitat să menționez: veți dori să vă scrieți implementarea pentru a lucra pe vectori de raționali. Dacă aveți flotoare de precizie infinită, și acestea vor funcționa.

mi-a atras atenția, dar mpfr argumentul fplll ar trebui să se potrivească cu ceea ce este necesar aici.Și în caz că nu, am încercat și eu să folosesc o matrice Sage definită peste QQ, dar nu funcționează mai bine.