4. Funzioni di utilità

Gli algoritmi in questo documento utilizzano le funzioni di utilità descritte di seguito, oltre alle operazioni aritmetiche standard (addizione, moltiplicazione, riduzione modulare, ecc.) e alle operazioni sui punti delle curve ellittiche (addizione di punti e moltiplicazione scalare).

Per sicurezza, le implementazioni di queste funzioni DOVREBBERO essere a tempo costante: in breve, ciò significa che il tempo di esecuzione e i modelli di accesso alla memoria NON DOVREBBERO dipendere dai valori degli input segreti, dai valori intermedi o dagli output. Per tali implementazioni a tempo costante, tutte le operazioni aritmetiche, i confronti e le assegnazioni DEVONO essere implementati a tempo costante. La Sezione 10.3 tratta brevemente le questioni di sicurezza relative al tempo costante.

I consigli sull'implementazione delle operazioni di basso livello (a tempo costante o meno) esulano dallo scopo di questo documento; i lettori dovrebbero consultare i documenti di riferimento standard [MOV96] [CFADLNV05].

• CMOV(a, b, c): se c è falso, CMOV restituisce a; altrimenti restituisce b. Per le implementazioni a tempo costante, questa operazione deve essere eseguita in un tempo indipendente dal valore di c.

• AND, OR, NOT e XOR sono operatori logici bit a bit standard. Per le implementazioni a tempo costante, gli operatori di cortocircuito DEVONO essere evitati.

• is_square(x): questa funzione restituisce Vero ogni volta che il valore x è un quadrato nel campo F. Tramite il criterio di Eulero, questa funzione può essere calcolata a tempo costante come:

  is_square(x) := { Vero, se x^((q - 1) / 2) è 0 o 1 in F; { Falso, altrimenti.

  In alcuni campi di estensione, is_square può essere calcolato a tempo costante più rapidamente rispetto all'elevamento a potenza sopra indicato. [AR13] e [S85] descrivono metodi ottimizzati per i campi di estensione. L'Appendice I.5 fornisce un metodo ottimizzato per GF(p^2).

• sqrt(x): l'operazione sqrt è una funzione multivalore, nel senso che esistono due radici di x nel campo F ogni volta che x è un quadrato (tranne quando x = 0). Per mantenere la compatibilità tra le implementazioni lasciando agli implementatori spazio per le ottimizzazioni, questo documento non richiede che sqrt() restituisca un valore particolare. Al contrario, come spiegato nella Sezione 6.4, qualsiasi funzione che chiama sqrt specifica anche come determinare la radice corretta.

  Il modo preferito per calcolare le radici quadrate è fissare un particolare algoritmo deterministico per F. Forniamo diversi algoritmi nell'Appendice I.

• sgn0(x): questa funzione restituisce 0 o 1 indicando il "segno" di x, dove sgn0(x) == 1 esattamente quando x è "negativo". (In altre parole, questa funzione considera sempre 0 come positivo). La Sezione 4.1 definisce questa funzione e tratta la sua implementazione.

• inv0(x): questa funzione restituisce l'inverso moltiplicativo di x in F, esteso a tutto F fissando inv0(0) == 0. Un modo semplice per implementare inv0 a tempo costante è calcolare:

  inv0(x) := x^(q - 2).

  Si noti che sull'input 0, l'output è 0 come richiesto. Alcuni campi possono consentire metodi di inversione più veloci; una discussione dettagliata di tali metodi esula dallo scopo di questo documento.

• I2OSP e OS2IP: queste funzioni vengono utilizzate per convertire una stringa di byte da e verso un intero non negativo come descritto in [RFC8017]. (Si noti che queste funzioni operano su stringhe di byte in ordine big-endian).

• a || b: indica la concatenazione delle stringhe di byte a e b. Ad esempio, "ABC" || "DEF" == "ABCDEF".

• substr(str, sbegin, slen): per una stringa di byte str, questa funzione restituisce la sottostringa di slen byte che inizia dalla posizione sbegin; le posizioni sono indicizzate a partire da zero. Ad esempio, substr("ABCDEFG", 2, 3) == "CDE".

• len(str): per una stringa di byte str, questa funzione restituisce la lunghezza di str in byte. Ad esempio, len("ABC") == 3.

• strxor(str1, str2): per le stringhe di byte str1 e str2, strxor(str1, str2) restituisce lo XOR bit a bit delle due stringhe. Ad esempio, strxor("abc", "XYZ") == "9;9" (le stringhe in questo esempio sono letterali ASCII, ma strxor è definito per stringhe di byte arbitrarie). In questo documento, strxor viene applicato solo a input di pari lunghezza.

4.1. La funzione sgn0

Questa sezione definisce un'implementazione sgn0 generica che si applica a qualsiasi campo F = GF(p^m). Fornisce inoltre implementazioni semplificate per i casi F = GF(p) e F = GF(p^2).

La definizione della funzione sgn0 per i campi di estensione si basa sulla base polinomiale o sulla rappresentazione vettoriale degli elementi del campo e itera sull'intera rappresentazione vettoriale dell'elemento di input. Di conseguenza, sgn0 dipende dal polinomio primitivo utilizzato per definire la base polinomiale; vedere la Sezione 8 per ulteriori informazioni su questa base e vedere la Sezione 2.1 per una discussione sulla rappresentazione degli elementi dei campi di estensione come vettori.

sgn0(x)

Parametri:

• F, un campo finito di caratteristica p e ordine q = p^m.
• p, la caratteristica di F (vedere immediatamente sopra).
• m, il grado di estensione di F, m >= 1 (vedere immediatamente sopra).

Input: x, un elemento di F. Output: 0 o 1.

Passaggi:

1. sign = 0
2. zero = 1
3. per i che va da 1, 2, ..., m:
4. sign_i = x_i mod 2
5. zero_i = x_i == 0
6. sign = sign OR (zero AND sign_i) # Evitare operazioni logiche di cortocircuito
7. zero = zero AND zero_i
8. ritorna sign

Quando m == 1, sgn0 può essere notevolmente semplificato:

sgn0_m_eq_1(x)

Input: x, un elemento di GF(p). Output: 0 o 1.

Passaggi:

1. ritorna x mod 2

Il caso m == 2 è solo leggermente più complicato:

sgn0_m_eq_2(x)

Input: x, un elemento di GF(p^2). Output: 0 o 1.

Passaggi:

1. sign_0 = x_0 mod 2
2. zero_0 = x_0 == 0
3. sign_1 = x_1 mod 2
4. s = sign_0 OR (zero_0 AND sign_1) # Evitare operazioni logiche di cortocircuito
5. ritorna s