Întrebare despre coeficientul ECDSA în atacul lattice

Actualizare: mi-am făcut ca atacul cu zăbrele să funcționeze în sfârșit. Întrucât motivul real este destul de complicat, decid să scriu un răspuns mai jos pentru a descrie cum a funcționat, astfel încât oricine cu o întrebare similară să se inspire din munca mea. Întrebarea nu este modificată.

Am studiat recent atacul latice. Am încercat să folosesc date de la TPM-FAIL pentru a mă ajuta să înțeleg acest atac și să încerc să implementez un atac folosind „metoda manuală” (există unele optimizări în scripturile de atac TPM-FAIL). Am avut câteva întrebări citind materialele pe care nu le-am putut înțelege. Va rog sa ma ajutati daca aveti vreo idee.

1. Formula semnăturii DSA poate fi în sfârșit transformată în următoarea ecuaţie:

   $k_i-s_i^{-1}r_id-s_i^{-1}H(m)\equiv 0 \pmod{n}$

   unde k este cheia efemeră, (r,s,) este perechea de semnături, d este cheie privată, H(m) este mesajul digest, ca de obicei... știi exercițiul.
   Atunci acesta poate fi transformat în formă de zăbrele. Ceva de genul următor ecuaţie:

   $k_i+A_id+B_i\equiv 0\pmod n$, Unde $A_i=-s_i^{-1}r_i$ și $B_i=-s_i^{-1}H(m)$

   Ce nu înțeleg este că, de ce trebuie să fie negativ? a încercat de fapt să modifice scriptul de atac furnizat în TPM-FAIL set de date și a constatat că eliminarea -1 din A_i și B_i va provoca atacul a eșuat. Dar putem rescrie prima ecuație ca:

   $s_i^{-1}r_id+s_i^{-1}H(m)\equiv k_i\pmod{n}$

   Conceptul de atac lattice ar trebui să rămână în continuare: Dacă lattice vectorul este mic, algoritmul de reducere a bazei ar trebui să genereze răspunsul. Ce am greșit?

2. Al doilea lucru este că am încercat să folosesc abordarea neoptimizată, rețeaua SVP este construită ca mai jos:

$\begin{bmatrix}n&&&&&\&n&&&&\&&\ddots&&&\&&&n&&\A_1&A_2&\dots&A_t&K/n&\ B_1&B_2&\dots&B_t&&K\end{bmatrix}$

Dar putem vedea clar că K/n va fi un număr fracționar care nu poate folosi metoda BKZ() sau LLL() în sagemath. Ceea ce înțeleg este că putem înmulți fiecare lucru din această matrice cu n, astfel încât totul din această matrice este întreg. După aplicarea BKZ() împărțim totul la n pentru a recupera rezultatul inițial: cheia privată ar trebui să fie în ultima coloană a primului rând. Cu toate acestea, nu am reușit să recuperez cheia privată. Chiar dacă am folosit 100 de semnături cu scurgeri de 8 biți. Este corectă abordarea mea?

Mulțumesc anticipat pentru ajutor!

Despre prima propoziție interogativă a întrebării:

de ce trebuie sa fie negativ?

citit literal și cu „ea” relativ la cantități $A_i$ și $B_i$.

Al doilea set de ecuații este într-adevăr (sau poate fi schimbat în) $k_i+{A_i}\,d+B_i\equiv0\pmod n$ Unde $A_i=-s_i^{-1}\,r_i\bmod n$ și $B_i=-s_i^{-1}\,H(m)\bmod n$. The $\bmod n$ sunt implicate. Prin urmare, în aceasta $A_i$ și $B_i$ sunt nenegative.

Asta prin definiția $\bmod$ operator:

• $x\bmod n$ este $z$ in raza de actiune $[0,n)$ cu $x\equiv z\pmod n$.
• $x^{-1}\bmod n$ este $z$ in raza de actiune $[0,n)$ cu $x\,z\equiv1\pmod n$
• $-x^{-1}\,y\bmod n$ este $z$ in raza de actiune $[0,n)$ cu $x\,z\equiv-y\pmod n$

Amintește-ți asta $x\equiv z\pmod n$ este definită în sensul că $x-z$ este un multiplu al $n$.

Putem rescrie prima ecuație ca $s_i^{-1}\,r_i+s_i^{-1}\,H(m)\equiv k_i\pmod n$. Conceptul de atac lattice ar trebui să fie valabil: dacă vectorul lattice este mic, algoritmul de reducere a bazei ar trebui să genereze răspunsul. Ce am greșit?

Presupun vag că problema este că codul de reducere a rețelei folosit vrea o intrare sub formă de matrice. Putem potrivi acest lucru prin rescrierea ecuației ca $s_i^{-1}\,r_i+s_i^{-1}\,H(m)+k'_i\equiv 0\pmod n$ cu $k'_i=n-k_i$. Dar amintiți-vă că atacul se învârte în jurul fezabilității selectării, printr-un atac de timp, a $i$ astfel încât $k_i$ este mic. Aceeași metodă de selecție nu va da puțin $k'_i$; și nu sunt sigur că o metodă potrivită este nici măcar posibilă.