Pe o curbă eliptică este posibil ca din $P$ să putem spune dacă $a$ este reziduu pătratic modulo $N$?

Imaginează-ți că, Pe o schemă de criptare cu curbă eliptică, unde $P=a\ori G$, Bob își împărtășește cheia publică $P$ cu Eva (diavolul care vrea să afle secrete pe care nu trebuie să le facă). Bob a dezvăluit, de asemenea, un indiciu despre $a$ accidental. Indiciul poate fi unul sau o combinație de elemente din următoarea listă:

1. Numarul $a$ este un întreg IMPAR/PAR.
2. Numarul $a$ este MAI MARE/MAI MICI decât jumătate din ordinul grupului $N/2$.
3. Numarul $a$ are $x$ biți semnificativi când sunt scrise ca binar. (Acolo $x$ este numărul de biți din $a$, de exemplu dacă $a=152=10011000$ atunci $x=8$
4. Numarul $a$ este RESIDUE/NON-RESIDUE patratică modulo $N$.

Intrebarea 1:

Cunoașterea unui astfel de indiciu va fi considerată o slăbiciune semnificativă pentru cheia publică a lui Bob, astfel încât să spunem că nu mai este sigur să o folosim?

Intrebarea 2:

Indiciile menționate mai sus sunt foarte puține informații despre $a$ Presupun. Am dreptate? Ce se întâmplă dacă le putem dezvălui pentru toate punctele de pe curbă folosind un algoritm magic?

Știu că, pentru itemii 1-3, cunoașterea unui algoritm general care pentru orice dat $P=a\ori G$ ne poate spune sigur că $a$ este IMPAR/PAR sau $a$ este MAI MARE/MAI MICI decât $N/2$ sau $a$ are $x$ biții vor sparge complet securitatea Elliptic Curves și prin care va fi posibil să se recupereze $a$ din $P$.

Dar cum rămâne cu articolul 4? Adică dacă cineva poate descoperi un algoritm prin care se poate determina asta pentru orice dat $P$, $a$ este sau nu un reziduu patratic modulo $N$, vor putea ei să recupereze complet $a$ și rupe schema criptografică?

Ce se întâmplă dacă algoritmul poate spune și rădăcina pătrată a $a$ modulo $N$?

Actualizare 1:

Aceste întrebări au apărut când studiam riscurile ca baza de date cu chei private să fie parțial compromisă. Asta se întâmplă dacă un atacator știe indicii ale cheilor noastre private.

Impactul asupra securității de la 1 și 2 poate fi considerat ca nesemnificativ. Să presupunem că aveți securitate de 256 de biți, asta înseamnă $2^{256}$ diferite chei din care să alegeți. Dacă știți că cheia este ciudată, aceasta se reduce la $2^{255}$ chei diferite. Pentru 2 este similar.

A ști câte uni și zerouri există poate fi considerat un risc semnificativ. Să presupunem că aveți o cheie de 256 de biți care conține un 1. Au rămas doar 256 de chei posibile. Aceasta duce la întrebarea câte permutări există. Pentru numerele binare cu o lungime dată X și un număr dat dacă cele N, acest lucru duce la numere de cheie, care pot fi calculate folosind:

$$ numărul\ de\ taste=\frac{(X!)}{ (N! * (X-N)!)} $$

În cel mai bun caz, acest lucru are ca rezultat $\aproximativ 2^{252}$ chei posibile, pentru 128 de chei. Dar pentru un număr diferit de acestea, acest lucru se înrăutățește doar. Timing Attacks încearcă adesea să afle câte diferite și câte zerouri există (sau chiar încearcă să găsească unele). Aceste atacuri sunt adesea o problemă serioasă. Unele dintre aceste atacuri au încercat să ghicească 1 de pornire a tastelor curbe eliptice, deoarece unii algoritmi vechi aveau timp de calcul diferit în funcție de poziția primului 1. Acest lucru nu trebuie să fie un risc, de ex. 1 este primul sau al doilea bit. Dar dacă cel de conducere era pe poziție $i$ securitatea ar scădea la $2^{256-i}$. Depinde de $i$ acest lucru poate fi un risc semnificativ, mai ales dacă cheile sunt alese complet la întâmplare. Cu siguranță nu vrei aceste riscuri.

Pentru 4 nu sunt sigur. Voi edita asta, dacă găsesc un răspuns bun.