2. Background (Cenni preliminari)
2.1. Curve ellittiche
Quanto segue è una breve definizione di curve ellittiche, con particolare attenzione ai parametri importanti e alla loro relazione con l'hashing su curve. Per ulteriori riferimenti sulle curve ellittiche, consultare [CFADLNV05] o [W08].
Sia F il campo finito GF(q) di caratteristica prima p > 3. (Il presente documento non considera curve ellittiche su campi di caratteristica 2 o 3.) Nella maggior parte dei casi, F è un campo primo, quindi q = p. Altrimenti, F è un campo di estensione, quindi q = p^m per un intero m > 1. Il presente documento scrive gli elementi dei campi di estensione in una base di elementi primitivi o polinomiale, ovvero come un vettore di m elementi di GF(p) scritti in ordine crescente per grado. Le entrate di questo vettore sono indicizzate in ordine crescente a partire da 1, cioè x = (x_1, x_2, ..., x_m). Ad esempio, se q = p^2 e la base di elementi primitivi è (1, I), allora x = (a, b) corrisponde all'elemento a + b * I, dove x_1 = a e x_2 = b. (Si noti che tutte le scelte di base sono isomorfe, ma certe scelte possono portare a un'implementazione più efficiente; il presente documento non fa alcuna particolare ipotesi sulla scelta della base.)
Una curva ellittica E è specificata da un'equazione in due variabili e da un campo finito F. Un'equazione di curva ellittica assume una delle diverse forme standard, che includono (ma non si limitano a) Weierstraß, Montgomery ed Edwards.
La curva E induce un gruppo algebrico di ordine n, il che significa che il gruppo ha n elementi distinti. (Il presente documento utilizza la notazione additiva per l'operazione di gruppo della curva ellittica.) Gli elementi di un gruppo di curva ellittica sono punti con coordinate affini (x, y) che soddisfano l'equazione della curva, dove x e y sono elementi di F. Inoltre, tutti i gruppi di curve ellittiche hanno un elemento distinto, il punto identità, che funge da elemento neutro per l'operazione di gruppo. Su alcune curve (incluse le curve Weierstraß e Montgomery), il punto identità non può essere rappresentato come coppia di coordinate (x, y).
Per ragioni di sicurezza, le applicazioni crittografiche delle curve ellittiche richiedono generalmente l'uso di un sottogruppo di ordine primo. Sia G tale sottogruppo della curva di ordine primo r, dove n = h * r. In questa equazione, h è un intero chiamato cofattore. Un algoritmo che prende in input un punto arbitrario sulla curva E e produce in output un punto nel sottogruppo G di E è detto "azzerare il cofattore" (clear the cofactor). Tali algoritmi sono discussi nella Sezione 7.
Alcuni algoritmi di hash-to-curve limitano la forma dell'equazione della curva, la caratteristica del campo o i parametri della curva. Per ciascun algoritmo presentato, il presente documento elenca le restrizioni pertinenti.
La tabella seguente riassume le quantità rilevanti per l'hashing su curve:
| Simbolo | Significato | Rilevanza |
|---|---|---|
| F,q,p | Un campo finito F di caratteristica p e con #F = q = p^m. | Per campi primi, q = p; altrimenti, q = p^m e m>1. |
| E | Curva ellittica. | E è specificata da un'equazione e da un campo F. |
| n | Numero di punti sulla curva ellittica E. | n = h * r, con h e r definiti di seguito. |
| G | Un sottogruppo di ordine primo dei punti su E. | G è un gruppo di destinazione in cui le stringhe di byte vengono codificate. |
| r | Ordine di G. | r è un fattore primo di n (solitamente, il maggiore di tali fattori). |
| h | Cofattore, h >= 1. | h è un intero che soddisfa n = h * r. |
Tabella 1: Riepilogo dei simboli e delle loro definizioni
2.2. Terminologia
In questa sezione definiamo termini importanti utilizzati in tutto il documento.
2.2.1. Mapping (Applicazioni)
Un mapping è una funzione deterministica da un elemento del campo F a un punto su una curva ellittica E definita su F.
In generale, l'insieme di tutti i punti che un mapping può produrre su tutti gli input possibili può essere solo un sottoinsieme dei punti di una curva ellittica (cioè, il mapping potrebbe non essere suriettivo). Inoltre, un mapping può emettere lo stesso punto per due o più input distinti (cioè, il mapping potrebbe non essere iniettivo). Ad esempio, consideriamo un mapping da F a una curva ellittica avente n punti: se il numero di elementi di F non è uguale a n, allora questo mapping non può essere biiettivo (cioè, sia iniettivo sia suriettivo), poiché il mapping è definito come deterministico.
I mapping possono anche essere invertibili, nel senso che esiste un algoritmo efficiente che, per ogni punto P emesso dal mapping, emette un x in F tale che applicando il mapping a x si ottenga P. Alcuni dei mapping forniti nella Sezione 6 sono invertibili, ma il presente documento non discute gli algoritmi di inversione.
2.2.2. Codifiche (Encodings)
Le codifiche sono strettamente correlate ai mapping. Come un mapping, una codifica è una funzione che emette un punto su una curva ellittica. A differenza di un mapping, tuttavia, l'input di una codifica è una stringa di byte di lunghezza arbitraria.
Il presente documento costruisce codifiche deterministiche componendo una funzione di hash Hf con un mapping deterministico. In particolare, Hf prende in input una stringa arbitraria ed emette un elemento di F. Il mapping deterministico prende quell'elemento in input ed emette un punto su una curva ellittica E definita su F. Poiché Hf prende in input stringhe di byte di lunghezza arbitraria, non può essere iniettiva: l'insieme degli input è più grande dell'insieme degli output, quindi devono esistere input distinti che danno lo stesso output (cioè, devono esserci collisioni). Pertanto, qualsiasi codifica costruita a partire da Hf non è anch'essa iniettiva.
Come i mapping, le codifiche possono essere invertibili, nel senso che esiste un algoritmo efficiente che, per ogni punto P emesso dalla codifica, emette una stringa s tale che applicando la codifica a s si ottenga P. Tuttavia, l'istanziazione di Hf utilizzata da tutte le codifiche specificate in questo documento (Sezione 5) non è invertibile; pertanto, tali codifiche non sono anch'esse invertibili.
In alcune applicazioni dell'hashing su curve ellittiche, è importante che le codifiche non rivelino informazioni attraverso canali laterali. [VR20] è un esempio di questa tipologia di perdita che porta a una vulnerabilità di sicurezza. Si veda la Sezione 10.3 per ulteriori discussioni.
2.2.3. Codifiche con oracle casuale (Random Oracle Encodings)
Una codifica con random oracle soddisfa una proprietà forte: può essere dimostrata indifferenziabile da un random oracle [MRH04] sotto opportune ipotesi.
Entrambe le costruzioni descritte nella Sezione 3 sono indifferenziabili da random oracle [MRH04] quando istanziate seguendo le linee guida di questo documento. Le costruzioni differiscono nelle loro distribuzioni di output: una fornisce un punto uniformemente casuale sulla curva, l'altra fornisce un punto campionato da una distribuzione non uniforme.
Una codifica con random oracle avente distribuzione di output uniforme è adatta per l'uso in molti protocolli crittografici dimostrati sicuri nel modello dell'oracolo casuale. Si veda la Sezione 10.1 per ulteriori discussioni.
2.2.4. Serializzazione
Una procedura correlata alla codifica è la conversione di un punto di curva ellittica in una stringa di bit. Questa operazione è chiamata serializzazione ed è tipicamente utilizzata per memorizzare o trasmettere in modo compatto i punti. L'operazione inversa, la deserializzazione, converte una stringa di bit in un punto di curva ellittica. Ad esempio, [SEC1] e [p1363a] forniscono metodi standard per la serializzazione e la deserializzazione.
La deserializzazione differisce dalla codifica per il fatto che solo alcune stringhe (ovvero, quelle emesse dalla procedura di serializzazione) possono essere deserializzate. Al contrario, il presente documento riguarda le codifiche da stringhe arbitrarie a punti di curva ellittica. Il presente documento non tratta la serializzazione né la deserializzazione.
2.2.5. Separazione dei domini (Domain Separation)
I protocolli crittografici dimostrati sicuri nel modello dell'oracolo casuale sono spesso analizzati sotto l'ipotesi che l'oracolo casuale risponda solo a query associate a quel protocollo (incluse le query effettuate dagli avversari) [BR93]. Nella pratica, questa ipotesi non vale se due protocolli utilizzano la stessa funzione per istanziare l'oracolo casuale. Concretamente, consideriamo i protocolli P1 e P2 che interrogano un random oracle RO: se P1 e P2 interrogano entrambi RO sullo stesso valore x, l'analisi di sicurezza di uno o di entrambi i protocolli potrebbe essere invalidata.
Un modo comune di affrontare questo problema è chiamato separazione dei domini (domain separation), che consente a un singolo random oracle di simulare più oracoli indipendenti. Ciò è realizzato garantendo che ciascun oracolo simulato veda query distinte da quelle viste da tutti gli altri oracoli simulati. Ad esempio, per simulare due oracoli RO1 e RO2 dato un singolo oracolo RO, si potrebbe definire
RO1(x) := RO("RO1" || x)
RO2(x) := RO("RO2" || x)
dove || è l'operatore di concatenazione. In questo esempio, "RO1" e "RO2" sono chiamati tag di separazione dei domini (DST, domain separation tags); essi garantiscono che le query a RO1 e RO2 non possano risultare in query identiche a RO, il che significa che è sicuro trattare RO1 e RO2 come oracoli indipendenti.
In generale, la separazione dei domini richiede di definire una codifica iniettiva distinta per ciascun oracolo simulato. Nell'esempio sopra, "RO1" e "RO2" hanno la stessa lunghezza e soddisfano pertanto questo requisito quando usati come prefissi. Gli algoritmi specificati in questo documento adottano un approccio diverso per garantire l'iniettività; si vedano le Sezioni 5.3 e 10.7 per ulteriori dettagli.