2. Contesto
Quella che segue è una breve definizione delle curve ellittiche, con enfasi sui parametri importanti e sulla loro relazione con l'hashing su curve. Per ulteriori riferimenti sulle curve ellittiche, consultare [CFADLNV05] o [W08].
2.1. Curve ellittiche
Sia F il campo finito GF(q) di caratteristica prima p > 3. (Questo documento non considera le 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. Questo documento scrive gli elementi dei campi di estensione in una base di elementi primitivi o polinomiale, cioè nella forma di un vettore di m elementi di GF(p) scritti in ordine crescente di grado. Le voci 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 alcune scelte possono risultare in un'implementazione più efficiente; questo documento non fa alcuna ipotesi particolare sulla scelta della base.)
Una curva ellittica E è specificata da un'equazione a due variabili e un campo finito F. Un'equazione di curva ellittica assume una delle diverse forme standard, incluse (ma non limitate a) Weierstrass, Montgomery ed Edwards.
La curva E induce un gruppo algebrico di ordine n, il che significa che il gruppo ha n elementi distinti. (Questo documento utilizza la notazione additiva per l'operazione di gruppo della curva ellittica.) Gli elementi di un gruppo di curve ellittiche sono punti di 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 all'infinito o punto identità, che funge da elemento identità per l'operazione di gruppo. Su alcune curve (incluse le curve di Weierstrass e Montgomery), il punto identità non può essere rappresentato come una coppia di coordinate (x, y).
Per motivi di sicurezza, le applicazioni crittografiche delle curve ellittiche generalmente richiedono l'uso di un (sotto-)gruppo di ordine primo. Sia G un 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 "cancellare il cofattore". 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 ogni algoritmo presentato, questo 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 #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 un campo F. |
| n | Numero di punti sulla curva ellittica E. | n = h * r, per h e r definiti di seguito. |
| G | Un sottogruppo di ordine primo dei punti su E. | G è un gruppo di destinazione a cui vengono codificate le stringhe di byte. |
| r | Ordine di G. | r è un fattore primo di n (di solito, il più grande 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 i termini importanti utilizzati in tutto il documento.
2.2.1. Mappature
Una mappatura è 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 una mappatura può produrre su tutti i possibili input può essere solo un sottoinsieme dei punti di una curva ellittica (cioè, la mappatura potrebbe non essere suriettiva). Inoltre, una mappatura può produrre lo stesso punto per due o più input distinti (cioè, la mappatura potrebbe non essere iniettiva). Ad esempio, si consideri una mappatura da F a una curva ellittica con n punti: se il numero di elementi di F non è uguale a n, allora questa mappatura non può essere biiettiva (cioè sia iniettiva che suriettiva), poiché la mappatura è definita come deterministica.
Le mappature possono anche essere invertibili, il che significa che esiste un algoritmo efficiente che, per qualsiasi punto P prodotto dalla mappatura, produce un x in F tale che l'applicazione della mappatura a x produce P. Alcune delle mappature fornite nella Sezione 6 sono invertibili, ma questo documento non tratta degli algoritmi di inversione.
2.2.2. Codifiche
Le codifiche sono strettamente correlate alle mappature. Come una mappatura, una codifica è una funzione che produce un punto su una curva ellittica. A differenza di una mappatura, tuttavia, l'input di una codifica è una stringa di byte di lunghezza arbitraria.
Questo documento costruisce codifiche deterministiche componendo una funzione di hash Hf con una mappatura deterministica. In particolare, Hf prende in input una stringa arbitraria e produce un elemento di F. La mappatura deterministica prende questo elemento in input e produce un punto su una curva ellittica E definita su F. Poiché Hf prende stringhe di byte di lunghezza arbitraria in input, non può essere iniettiva: l'insieme degli input è più grande dell'insieme degli output, quindi devono esserci input distinti che danno lo stesso output (cioè, devono esserci collisioni). Pertanto, qualsiasi codifica costruita da Hf non è nemmeno iniettiva.
Come le mappature, le codifiche possono essere invertibili, il che significa che esiste un algoritmo efficiente che, per qualsiasi punto P prodotto dalla codifica, produce una stringa s tale che l'applicazione della codifica a s produce P. Tuttavia, l'istanziazione di Hf utilizzata da tutte le codifiche specificate in questo documento (Sezione 5) non è invertibile; quindi, queste codifiche non sono nemmeno invertibili.
In alcune applicazioni di hashing su curve ellittiche, è importante che le codifiche non rivelino informazioni attraverso canali laterali. [VR20] è un esempio di questo tipo di perdita che porta a una vulnerabilità di sicurezza. Vedere la Sezione 10.3 per ulteriori dettagli.
2.2.3. Codifiche random oracle
Una codifica random oracle soddisfa una proprietà forte: può essere dimostrata indifferenziabile da un random oracle [MRH04] sotto un'ipotesi appropriata.
Le due costruzioni descritte nella Sezione 3 sono indifferenziabili dai random oracle [MRH04] quando istanziate seguendo i consigli di questo documento. Le costruzioni differiscono nelle loro distribuzioni di output: una fornisce un punto casuale uniforme sulla curva, l'altra fornisce un punto campionato da una distribuzione non uniforme.
Una codifica random oracle con una distribuzione di output uniforme è adatta per l'uso in molti protocolli crittografici la cui sicurezza è dimostrata nel modello del random oracle. Vedere la Sezione 10.1 per ulteriori dettagli.
2.2.4. Serializzazione
Una procedura correlata alla codifica è la conversione di un punto di curva ellittica in una stringa di bit. Questo è chiamato serializzazione, ed è generalmente utilizzato per memorizzare o trasmettere punti in modo compatto. L'operazione inversa, 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 è diversa dalla codifica per il fatto che solo alcune stringhe (cioè quelle prodotte dalla procedura di serializzazione) possono essere deserializzate. Al contrario, questo documento riguarda le codifiche di stringhe arbitrarie in punti di curve ellittiche. Questo documento non copre la serializzazione o la deserializzazione.
2.2.5. Separazione di dominio
I protocolli crittografici la cui sicurezza è dimostrata nel modello del random oracle sono spesso analizzati sotto l'ipotesi che il random oracle risponda solo alle query associate a quel protocollo (incluse le query effettuate da avversari) [BR93]. In pratica, questa ipotesi non è valida se due protocolli utilizzano la stessa funzione per istanziare il random oracle. Concretamente, si considerino 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 entrambi i protocolli potrebbe essere invalidata.
Un modo comune per affrontare questo problema è chiamato separazione di dominio, che consente a un singolo random oracle di simulare più oracle indipendenti. Questo si ottiene assicurandosi che ogni oracle simulato veda query distinte da quelle viste da tutti gli altri oracle simulati. Ad esempio, per simulare due oracle RO1 e RO2 da un singolo oracle 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 di dominio (DST); 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 oracle indipendenti.
In generale, la separazione di dominio richiede di definire una codifica iniettiva distinta per ogni oracle simulato. Nell'esempio sopra, "RO1" e "RO2" hanno la stessa lunghezza e quindi soddisfano questo requisito quando utilizzati come prefissi. Gli algoritmi specificati in questo documento adottano un approccio diverso per garantire l'iniettività; vedere le Sezioni 5.3 e 10.7 per ulteriori dettagli.