Appendix A. Deterministic Generation (Generazione deterministica)

Appendix A. Deterministic Generation (Generazione deterministica)

Questa sezione specifica la procedura utilizzata per generare le curve sopra indicate; in particolare definisce come generare il parametro A della curva di Montgomery y^2 = x^3 + A*x^2 + x. Tale procedura è pensata per essere il più obiettiva possibile, in modo che sia chiaro che nessuna considerazione inopportuna ha influenzato la scelta della curva. L'ingresso di questo processo è p, il primo che definisce il campo sottostante. La dimensione di p determina il lavoro necessario per calcolare un logaritmo discreto nel gruppo della curva ellittica, e la scelta di un p preciso dipende da molte considerazioni implementative. Le prestazioni della curva saranno dominate da operazioni in GF(p), per cui scegliere con cura un valore che consenta riduzioni facili sull'architettura prevista è critico. Questo documento non tenta di esporre tutte queste considerazioni.

Il valore (A-2)/4 è usato in diverse formule aritmetiche sui punti della curva ellittica. Per semplicità e prestazioni, è utile che tale costante sia piccola, cioè scegliere A in modo che (A-2) sia un intero piccolo divisibile per quattro.

Per ciascuna curva a un dato livello di sicurezza:

1. La traccia di Frobenius NON DEVE essere in {0, 1} al fine di escludere gli attacchi descritti in [smart], [satoh] e [semaev], come in [brainpool] e [safecurves].

2. Grado MOV [reducing]: il grado di embedding DEVE essere maggiore di (order - 1) / 100, come in [brainpool] e [safecurves].

3. Discriminante CM: il discriminante D DEVE essere maggiore di 2^100, come in [safecurves].

A.1. p = 1 mod 4

Per primi congrui a 1 mod 4, i cofattori minimali della curva e della sua twist sono {4, 8} oppure {8, 4}. Si sceglie una curva con questi ultimi cofattori, in modo che gli algoritmi che tengono conto del cofattore non debbano preoccuparsi di verificare punti sulla twist, perché il cofattore della twist sarà il minore dei due.

Per generare la curva di Montgomery, si trova il valore A positivo minimale tale che A > 2 e (A-2) sia divisibile per quattro e i cofattori siano quelli desiderati. La funzione find1Mod4 nello script Sage seguente restituisce tale valore dato p:

def findCurve(prime, curveCofactor, twistCofactor):
    F = GF(prime)

    for A in xrange(3, int(1e9)):
        if (A-2) % 4 != 0:
          continue

        try:
          E = EllipticCurve(F, [0, A, 0, 1, 0])
        except:
          continue

        groupOrder = E.order()
        twistOrder = 2*(prime+1)-groupOrder

        if (groupOrder % curveCofactor == 0 and
            is_prime(groupOrder // curveCofactor) and
            twistOrder % twistCofactor == 0 and
            is_prime(twistOrder // twistCofactor)):
            return A

def find1Mod4(prime):
    assert((prime % 4) == 1)
    return findCurve(prime, 8, 4)

Generazione di una curva con p = 1 mod 4

A.2. p = 3 mod 4

Per un primo congruo a 3 mod 4, sia il cofattore della curva sia quello della twist possono essere 4, e ciò è minimale. Si sceglie pertanto la curva con tali cofattori e A positivo minimale tale che A > 2 e (A-2) sia divisibile per quattro. La funzione find3Mod4 nello script Sage seguente restituisce tale valore dato p:

def find3Mod4(prime):
    assert((prime % 4) == 3)
    return findCurve(prime, 4, 4)

Generazione di una curva con p = 3 mod 4

A.3. Base Points (Punti base)

Il punto base per una curva è il punto con valore u positivo minimale che appartiene al sottogruppo corretto. La funzione findBasepoint nello script Sage seguente restituisce tale valore dati p e A:

def findBasepoint(prime, A):
    F = GF(prime)
    E = EllipticCurve(F, [0, A, 0, 1, 0])

    for uInt in range(1, 1e3):
      u = F(uInt)
      v2 = u^3 + A*u^2 + u
      if not v2.is_square():
        continue
      v = v2.sqrt()

      point = E(u, v)
      pointOrder = point.order()
      if pointOrder > 8 and pointOrder.is_prime():
        return point

Generazione del punto base