Voi descrie trucul Shamir standard adaptat contextului Verificarea semnăturii ECDSA. Renunțând la unii indici, partea costisitoare din punct de vedere computațional este calculul
$$u\cdot G+v\cdot Q$$
Unde $u$ și $v$ sunt (presupunem, strict pozitive) numere întregi, $G$ și $Q$ sunt puncte de curbă eliptică și $+$ este adăugarea de puncte (pe care pentru simplificare o consider o cutie neagră, a cărui execuție domină costul de calcul). Amintiți-vă că prin definiție, $$u\cdot G=\underbrace{G+G+\ldots+G+G}_{u\text{ termeni}}$$
Ei bine, rețineți $\mathbin\|u\mathbin\|$ pentru numărul de biți în întreg $u$, acesta este $\left\lfloor\log_2(u)+1\right\rfloor$; la fel pt $\mathbin\|v\mathbin\|$.
Un mod comun de a calcula $u\cdot G$ este să
- a stabilit $R:=G$
- pentru un pic $b$ copiat din reprezentarea binară a $u$, începând cu index $\mathbin\|u\mathbin\|-1$ (primul bit din dreapta celui din stânga $1$ bit) până la $0$ (partea cea mai dreaptă)
- a stabilit $R:=R+R$
- dacă $b=1$, a stabilit $R:=R+G$
Modul de bază de a calcula $u\cdot G+v\cdot Q$ ar fi să calculez $u\cdot G$, atunci $v\cdot Q$ prin aceeași metodă, apoi adăugați cele două rezultate. Trucul lui Shamir se îmbunătățește în acest sens:
- a stabilit $H:=G+Q$
- dacă $\mathbin\|u\mathbin\|>\mathbin\|v\mathbin\|$, a stabilit $R:=G$;
- altfel dacă $\mathbin\|u\mathbin\|<\mathbin\|v\mathbin\|$, a stabilit $R:=Q$;
- altfel (adica daca $\mathbin\|u\mathbin\|=\mathbin\|v\mathbin\|$ ), a stabilit $R:=H$;
- pentru un pic $b$ (resp. $c$) copiat din reprezentarea binară a $u$ (resp. $v$), cu reprezentările lui $u$ sau $v$ adăugată la stânga cu zerouri după cum este necesar, la index de la $\max(\mathbin\|u\mathbin\|,\mathbin\|v\mathbin\|)-1$ până la $0$
- a stabilit $R:=R+R$
- dacă $b=1$ și $c=0$, a stabilit $R:=R+G$
- (altfel) dacă $b=0$ și $c=1$, a stabilit $R:=R+Q$
- (altfel) dacă $b=1$ și $c=1$, a stabilit $R:=R+H$
Această afirmație este aproape echivalentă cu cea dată în acest raspuns sub denumirea de truc Strauss-Shamir (când cunosc trucul ca al lui Shamir). Varianta pe care o dau evită nevoia de a cunoaște grupul neutru, dar necesită $\max(u,v)>0$.
Corectitudinea înmulțirii standard a punctelor și trucul lui Shamir pot fi dovedite în mod formal prin inducție.
Pentru mare aleatorie $u$ și $v$ de $k$ biți, algoritmul naiv de calculat $u\cdot G+v\cdot Q$ performeaza in medie $\aproximativ 3k$ adaosuri de puncte, trucul lui Shamir reduce asta la $\aproximativ 1,75k$, cum ar fi cu 42% mai puțin (costul beneficiu este mai mic, în mare parte din cauza dublarii punctelor $R:=R+R$ este cel mai rapid tip de adunare de puncte și cel care este cel mai mic). Sunt posibile îmbunătățiri suplimentare, de ex. gruparea biților cu doi sau puțin mai mulți, poate cu „fereastra glisante” când $b=0=c$.
Observați că, în contextul verificării semnăturii, $u$, $v$, $G$ și $Q$ toate sunt publice, astfel că canalele secundare (timing, power draw, emisie, cache…) nu reprezintă o problemă de securitate, deoarece sunt în generarea semnăturii.
Nu cunosc trucul Strauss-Shamir al întrebării altă referință, dar bănuiți vag că se îmbunătățește în continuare acest lucru prin efectuarea uneori de scădere în loc de adunare și/sau este mai compatibil cu o tehnică de accelerare a adunării de puncte.
