Passa al contenuto principale

3. Codifica di stringhe di byte su curve ellittiche

Questa sezione presenta un quadro generale e un'interfaccia per la codifica di stringhe di byte in punti su una curva ellittica. Le costruzioni di questa sezione si basano su tre funzioni di base:

  • La funzione hash_to_field esegue l'hash di stringhe di byte di lunghezza arbitraria in un elenco di uno o più elementi di un campo finito F; la sua implementazione è definita nella Sezione 5.
hash_to_field(msg, count)

Input:
- msg, una stringa di byte contenente il messaggio da sottoporre a hash.
- count, il numero di elementi di F da emettere.

Output:
- (u_0, ..., u_(count - 1)), un elenco di elementi del campo.

Passi: definiti nella Sezione 5.
  • La funzione map_to_curve calcola un punto sulla curva ellittica E a partire da un elemento del campo finito F su cui E è definita. La Sezione 6 descrive i mapping per una gamma di famiglie di curve.
map_to_curve(u)

Input: u, un elemento del campo F.
Output: Q, un punto sulla curva ellittica E.
Passi: definiti nella Sezione 6.
  • La funzione clear_cofactor invia qualsiasi punto sulla curva E al sottogruppo G di E. La Sezione 7 descrive i metodi per eseguire questa operazione.
clear_cofactor(Q)

Input: Q, un punto sulla curva ellittica E.
Output: P, un punto in G.
Passi: definiti nella Sezione 7.

Le due codifiche (Sezione 2.2.2) definite in questa sezione hanno la stessa interfaccia e sono entrambe codifiche con random oracle (Sezione 2.2.3). Entrambe sono implementate come composizione delle tre funzioni di base sopra. La differenza tra le due è che i loro output sono campionati da distribuzioni diverse:

  • encode_to_curve è una codifica non uniforme da stringhe di byte a punti in G. Cioè, la distribuzione del suo output non è uniformemente casuale in G: l'insieme degli output possibili di encode_to_curve è solo una frazione dei punti in G, e alcuni punti di questo insieme hanno una probabilità maggiore di essere emessi rispetto ad altri. La Sezione 10.4 fornisce una definizione più precisa della distribuzione di output di encode_to_curve.
encode_to_curve(msg)

Input: msg, una stringa di byte di lunghezza arbitraria.
Output: P, un punto in G.

Passi:
1. u = hash_to_field(msg, 1)
2. Q = map_to_curve(u[0])
3. P = clear_cofactor(Q)
4. return P
  • hash_to_curve è una codifica uniforme da stringhe di byte a punti in G. Cioè, la distribuzione del suo output è statisticamente vicina all'uniforme in G.

Questa funzione è adatta alla maggior parte delle applicazioni che richiedono un random oracle che restituisca punti in G, quando istanziata con una qualsiasi delle funzioni map_to_curve descritte nella Sezione 6. Si veda la Sezione 10.1 per ulteriori discussioni.

hash_to_curve(msg)

Input: msg, una stringa di byte di lunghezza arbitraria.
Output: P, un punto in G.

Passi:
1. u = hash_to_field(msg, 2)
2. Q0 = map_to_curve(u[0])
3. Q1 = map_to_curve(u[1])
4. R = Q0 + Q1              # Somma di punti
5. P = clear_cofactor(R)
6. return P

Ciascuna suite di hash-to-curve della Sezione 8 istanzia una di queste funzioni di codifica per una specifica curva ellittica.

3.1. Requisiti di separazione dei domini​

Tutti gli usi delle funzioni di codifica definite in questo documento DEVONO includere la separazione dei domini (Sezione 2.2.5) per evitare interferenze con altri usi di funzionalità simili.

Le applicazioni che istanziano più istanze indipendenti di hash_to_curve o di encode_to_curve DEVONO imporre la separazione dei domini tra tali istanze. Questo requisito si applica sia nel caso di più istanze rivolte alla stessa curva sia nel caso di più istanze rivolte a curve diverse. (Ciò è dovuto al fatto che la primitiva interna hash_to_field (Sezione 5) richiede la separazione dei domini per garantire output indipendenti.)

La separazione dei domini è imposta tramite un tag di separazione dei domini (DST), che è una stringa di byte costruita secondo i seguenti requisiti:

  1. I tag DEVONO essere forniti come parametro DST a hash_to_field, come descritto nella Sezione 5.

  2. I tag DEVONO avere lunghezza diversa da zero. È RACCOMANDATA una lunghezza minima di 16 byte per ridurre la probabilità di collisioni con altre applicazioni.

  3. I tag DOVREBBERO iniziare con una stringa di identificazione fissa e univoca per l'applicazione.

  4. I tag DOVREBBERO includere un numero di versione.

  5. Per le applicazioni che definiscono più ciphersuite, il tag di ciascuna ciphersuite DEVE essere diverso. A tal fine, è RACCOMANDATO includere un identificatore di ciphersuite in ciascun tag.

  6. Per le applicazioni che utilizzano più codifiche, verso la stessa curva o curve diverse, ciascuna codifica DEVE utilizzare un tag diverso. A tal fine, è RACCOMANDATO includere il Suite ID (Sezione 8) della codifica nel tag di separazione dei domini. Per codifiche indipendenti basate sulla stessa suite, ciascun tag DOVREBBE inoltre includere un identificatore distinto, ad esempio "ENC1" e "ENC2".

Come esempio, si consideri un'applicazione fittizia di nome Quux che definisce diverse ciphersuite, ciascuna per una curva diversa. Una scelta ragionevole di tag è "QUUX-V-CS-", dove e sono numeri a due cifre che indicano rispettivamente la versione e la ciphersuite, e è il Suite ID della codifica utilizzata nella ciphersuite .

Come altro esempio, si consideri un'applicazione fittizia di nome Baz che richiede due random oracle indipendenti sulla stessa curva. Scelte ragionevoli di tag per questi oracle sono rispettivamente "BAZ-V-CS--ENC1" e "BAZ-V-CS--ENC2", dove , e sono come sopra descritto.

I tag di esempio riportati sopra si assumono essere stringhe di byte codificate in ASCII senza terminazione null, che è il formato RACCOMANDATO. Possono essere utilizzate altre codifiche, ma in tutti i casi la codifica come sequenza di byte DEVE essere specificata in modo non ambiguo.

Ultimo aggiornamento il