Este folosirea unui cofactor pentru a găsi un punct de bază doar din motive de performanță?

Pentru criptografia cu curbă eliptică, procedura de găsire a unui punct de bază care generează un subgrup cu ordine $n$ este:

1. Calculați comanda $N$ a curbei eliptice (folosind cea a lui Schoof)
2. Alege $n$. $n$ trebuie să fie prim și un divizor al $N$
3. Calculați cofactor $h = \frac{N}{n}$
4. Alegeți un punct aleatoriu $P$ pe curbă
5. Calcula $G = hP$
6. Dacă $G$ este 0, apoi reveniți la pasul 4. În caz contrar, ați găsit un generator cu comandă $n$ și cofactor $h$

Sursă

Scopul cofactorului este aici doar de a crește eficiența în găsirea unui subgrup mare?

Presupun că dacă nu ai folosit un co-factor și ai încercat să calculezi în forță brută dacă punctul aleatoriu, $P$, a fost un generator pentru un subgrup de dimensiune $n$ ar trebui să faci $n$ iterații, ceea ce ar fi imposibil pe computerele moderne. Dar, vreau să confirm.

Editați | ×: Ultimul meu paragraf este greșit, deoarece putem folosi pătratul repetat pentru a calcula $G = nP$

Acesta este un rezultat empiric pentru a completa răspunsul lui Poncho;

Luați Curve25519 care are un cofactor $8$ ca ordin $n$ a factorilor de grup ca

$\small{n = 2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989}$

• $h = 8 $
• $q = n/8$

Folosim SageMath și SageMath element_aleatoriu funcţie în care poate returna elementul de identitate $\mathcal{O}$ a curbei ( probabilitatea de a-l obține este neglijabilă) , pe Curve25519 $\mathcal{O} = (0:1:0)$ pe forma Weierstrass.

timpul de import

def randomBasePointByCofactor(E,identity,cofactor):
    
    s = timp.timp()
    ci = 0
    n = E.ordine()
    pentru i în interval (1,10000):
        P = E.element_aleatoriu()
        dacă cofactor*P != identitate:
            ci = ci +1
    e = timp.timp()
    print("timp scurs pe randomBasePointByCofactor", e-s)
    întoarcere (ci)
        
def randomBasePointByOrder(E,identity,cofactor):
    
    s = timp.timp()
    ci = 0
    n = Integer(E.order() / cofactor)
    pentru i în interval (1,10000):
        P = E.element_aleatoriu()
        dacă n*P == identitate:
            ci = ci +1

    e = timp.timp()
    print("timp scurs pe randomBasePointByOrder", e-s)
    întoarcere (ci)    

p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
K = GF(p)
A = K(0x76d06)
B = K(0x01)
E = Curbă eliptică(K, ((3 - A^2)/(3 * B^2), (2 * A^3 - 9 * A)/(27 * B^3)))

IP = E((0,1,0))
Legat = 10000

print(" numărul de generatoare găsite =" , randomBasePointByCofactor(E,IP,8), "/", Bound)

print(" numărul de generatoare găsite =", randomBasePointByOrder(E,IP,8),"/", Bound)

O mostră de rezultat este

timpul scurs pe randomBasePointByCofactor 1.9164307117462158
 numărul de generatoare găsite = 9999 / 10000
timpul scurs pe randomBasePointByOrder 64.77565383911133
 numărul de generatoare găsite = 1267 / 10000

Prin urmare

• metoda cofactorului este mai rapidă de ~32 de ori mai rapidă în experimente.

  Putem explica acest lucru în termeni simpli ca; $8$ necesită 4 dubleri și 1 adăugare, în timp ce $n$ necesită 251 de dubleri și 125 de adăugare cu naiv dublu-și-algoritm. Acest lucru oferă de aproximativ 75 de ori mai multe calcule dacă presupunem că dublarea și adunările au aceeași viteză pe care nu o au.

• metoda cofactorului produce mai mulți generatori decât metoda ordinului, deoarece $1/8$ a elementelor aleatorii din $8\cdot q$ cade în primul mare $q$ a Curbei25519.

Prin urmare, metoda cofactorului este de preferat.