Cum să decideți dacă un punct de pe o curbă eliptică aparține unui grup generat de un generator g?

Răspunsul depinde cu adevărat de curbele eliptice criptografice pe care le cunoaștem!

1. EC criptografic de ordin prim: Deoarece ordinea subgrupului generat de un element trebuie să împartă ordinea, atunci există grupul complet și grupul de $\mathcal{O}$ de ordine $1$ ( Curbele P NIST Curbele P-192, P-224, P-256, P-384, P-521) au ordinea principală listată în NIST.FIPS.186-4 si luat din Sec1).

2. EC criptografic cu un factor mic: În Criptografie, curbele au ordine mare pentru a fi sigure și trebuie să alegem elementul de bază din cel mai mare subgrup.Acest lucru se datorează

   1. Protejând de Algoritmul Pohlig-Hellman care reduce timpul la cel mai mare factor și este foarte eficient atunci când comanda este netedă, adică toți factorii sunt mici.

   2. Pentru a avea un echivalent Montogmery birațional al curbei ca Curve25519 cu cofactor $8$ și Ed448-Blocuri de aur cu cofactor $4$. În acest caz, avem comenzi pentru subgrupuri precum; $2,4,8,p,2p,4p,8p$ (pentru Curve25519)^*

      Pentru a vedea că un punct $G$ este de ordine $2$ sau $p$ este usor, verifica $2[G]$ sau $[p]G$, dacă rezultatul este identitatea, atunci se află în acest grup. Ei dar sunt și în subgrupul care conține subgrupurile. Există elemente în subgrupul de ordine 2p$ dar nu în subgrupul de ordine $2$ sau $p$. Verifica $[2]G$ și $[p]G$ dacă nu sunt identitate ci $[2p]G$ este atunci este pe subgrupul de ordine 2p$.

      The grupul Klein este cel mai mic grup care are două subgrupe de ordinul 2, este izomorf la $\mathbb Z_2 \times \mathbb Z_2$. Acest lucru poate ajuta la înțelegerea faptului că cele două subgrupuri diferite pot avea aceeași ordine.

      The Curbele NIST B au cofactor 2, iar curbele K au 4, și sunt luate din Sec2.

3. Twist of the Criptographic EC: Răsucirea curbelor binecunoscute nu are un factor pătratic mare, se aplică același lucru ca și în cazul 2.

4. Curba aleatorie: Nu am idee despre dimensiunea așteptată a factorilor curbelor generate aleatoriu (văzut unele lucrări). Putem avea o curbă cu un ordin astfel încât să aibă un factor mare de ordin 2 sau mai mult. În acest caz, $[p]G$ nu va dezvălui apartenența la subgrup. Pentru a o rezolva trebuie să găsim un generator pentru fiecare dintre subgrupuri și să încercăm să rezolvăm DLog.

5. Factorizarea ordinii grupului nu este cunoscută: În acest caz, avem un problema de decizie subgrup (după cum se spune în celălalt răspuns)

   Dat $(n, G, G1, e)$ și un element $x \în G$, ieşire $1$ dacă ordinul de $x$ este $q_1$ și ieșire $0$ in caz contrar; Adică fără a cunoaște factorizarea ordinii de grup $n$, decide dacă un element $x$ se află într-un subgrup de $G$. Ne referim la această problemă ca problema de decizie subgrup

   Deși această problemă stabilește rezultate interesante în contextul său, aceasta nu are legătură cu curbele eliptice utilizate în ECDH, EdDSA, etc. În curbele eliptice, toți parametrii sunt publici. Chiar dacă nu oferiți factorizarea ordinului curbei (nu este clar cum vă veți vinde curba comunității), puteți lua în considerare 829 de biți ( 512-bit a atins un ego de aproximativ 20 de ani).

   Dacă luați în considerare curbele în ordine foarte mare, putem spune că nu există prea multă semnificație a ordinii curbei mai mare de 512 biți (chiar 256), deoarece odată ce algoritmul lui Shor este setat în computerul cuantic criptografic pentru curbele de 256 de biți, este o chestiune de timp cercetătorii îl vor rupe pe celălalt. Acest lucru se poate vedea din tabelul de Lucrarea lui Proos și Zalks

ECC post-cuantic, pe de altă parte, folosește săritura pe izogenii în loc de DH și această lucrare oferă o introducere bună pentru oricine dorește să învețe.

• Schimb de chei de izogenie supersingulară pentru începători, Craig Costello, 2019. ( Bine ați revenit curbe supersingulare!)

În cele din urmă, singurele cazuri problematice nu sunt curbele criptografice.

^* Acolo am folosit Teorema Lagrange despre teoria grupurilor;

• Dacă $H$ este un subgrup al unui grup $G$ atunci $ord(H) \mid ord(G)$

Ar trebui să rețineți că am folosit inversul teoremei, dacă $x|org(G)$ atunci există un subgrup de ordine $x$. Acest lucru nu este întotdeauna adevărat și grup alternant de gradul 4 $A_4$ este cel mai mic exemplu.