Passa al contenuto principale

4. Funzioni di utilità

Gli algoritmi di 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 di curva ellittica (addizione di punti e moltiplicazione scalare).

Per ragioni di sicurezza, le implementazioni di queste funzioni DOVREBBERO essere in tempo costante: in breve, ciò significa che i tempi di esecuzione e i pattern di accesso alla memoria NON DOVREBBERO dipendere dai valori di input segreti, valori intermedi o output. Per tali implementazioni in tempo costante, anche tutte le operazioni aritmetiche, i confronti e le assegnazioni DEVONO essere implementati in tempo costante. La Sezione 10.3 discute brevemente i problemi di sicurezza in tempo costante.

Indicazioni sull'implementazione di operazioni a basso livello (in tempo costante o meno) vanno oltre lo scopo di questo documento; i lettori dovrebbero consultare i riferimenti standard [MOV96] [CFADLNV05].

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

  • AND, OR, NOT e XOR sono gli operatori logici bitwise standard. Per le implementazioni in tempo costante, NON DEVONO essere utilizzati operatori con corto circuito (short-circuit).

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

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

In certi campi di estensione, is_square può essere calcolata in tempo costante più rapidamente rispetto all'esponenziazione sopra. [AR13] e [S85] descrivono metodi ottimizzati per i campi di estensione. L'Appendice I.5 fornisce un metodo straight-line ottimizzato per GF(p^2).

  • sqrt(x): L'operazione sqrt è una funzione multivalore, cioè esistono due radici di x nel campo F ogni volta che x è un quadrato (eccetto quando x = 0). Per mantenere la compatibilità tra le implementazioni pur lasciando libertà agli implementatori per le ottimizzazioni, questo documento non richiede che sqrt() restituisca un valore particolare. Invece, 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 algoritmo deterministico particolare 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 se e solo se x è "negativo". (In altre parole, questa funzione considera sempre 0 come positivo.) La Sezione 4.1 definisce questa funzione e ne discute l'implementazione.

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

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

Si noti che per input 0, l'output è 0 come richiesto. Certi campi possono consentire metodi di inversione più rapidi; una discussione dettagliata di tali metodi va oltre lo scopo di questo documento.

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

  • a || b: denota 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 a partire 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 bitwise 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 è applicato solo a input di uguale lunghezza.

4.1. La funzione sgn0​

Questa sezione definisce un'implementazione generica di sgn0 applicabile 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; si veda la Sezione 8 per maggiori informazioni su questa base, e 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 (vedi sopra).
- m, il grado di estensione di F, m >= 1 (vedi sopra).

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

Passi:
1. sign = 0
2. zero = 1
3. for i in (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 operatori logici con corto circuito
7.   zero = zero AND zero_i
8. return sign

Quando m == 1, sgn0 può essere significativamente semplificata:

sgn0_m_eq_1(x)

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

Passi:
1. return x mod 2

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

sgn0_m_eq_2(x)

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

Passi:
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 operatori logici con corto circuito
5. return s
Ultimo aggiornamento il