Passa al contenuto principale

12. Appendici

Appendice A. Lavori correlati​

L'idea di eseguire l'hash verso curve ellittiche risale a [BJ02], [OKS00] e [ADKR07]; si veda [S05] per un'ampia rassegna. Una delle prime descrizioni formali di un tale algoritmo è il metodo "try-and-increment" (noto anche come "hunt-and-peck") di [BJ02]. I punti della curva vengono campionati generando un input casuale, calcolando la corrispondente coordinata x e risolvendo l'equazione della curva per la coordinata y. Poiché questo metodo richiede un numero variabile di tentativi, i tempi di esecuzione dipendono dai valori segreti e non sono in tempo costante. Inoltre, il metodo può fallire, ed è difficile da analizzare dal punto di vista della sicurezza. Di conseguenza, il presente documento NON specifica alcun metodo di campionamento per rifiuto.

Un approccio successivo di [AFQTZ14] tenta di evitare la natura non in tempo costante del campionamento per rifiuto generando il punto di curve ellittiche direttamente dagli elementi di un campo finito. Tuttavia, le curve trattate in [AFQTZ14] hanno un piccolo grado di non quadraticità, il che significa che i punti generati sono facilmente distinguibili dai punti casuali.

Il presente documento trae spunto da [H15], [KR17], [FFSTV13], [BLS01], [W09] e [Icart09]. In particolare, [H15] e [KR17] forniscono un'analisi completa per il caso della curva Elligator 2 su curve Montgomery. L'algoritmo Elligator 2 è dovuto a [BHKL13]. La presente specifica è strettamente correlata a [S15], che fornisce una trattazione formale delle proprietà di indifferenziabilità dei mapping in questo documento, e che è un prerequisito della presente specifica. L'analisi di [S15] si applica a curve con cofattore 1; il lavoro successivo di [LBB19] amplia tale analisi al caso a cofattore generico. Il presente documento unifica tutti questi approcci in un singolo quadro.

I mapping in questo documento sono inoltre correlati agli algoritmi di crittografia basati sull'identità (IBE) di [BF01] e [S05], che utilizzano una funzione di hash verso punti di curva ellittica per associare un identificatore a un punto su una curva ellittica. Invece di utilizzare il metodo di campionamento per rifiuto, questi lavori utilizzano funzioni di hash deterministiche. [S05] fornisce una trattazione formale di questo problema e dei suoi requisiti di sicurezza. Più recentemente, [LBB19] generalizza e migliora tali risultati.

Infine, [CK11] propone una famiglia di funzioni hash su curve ellittiche che non utilizzano il mapping indifferenziabile; invece, fa affidamento sull'applicazione ripetuta di una funzione di hash e sulla moltiplicazione scalare per garantire la correttezza. Il presente documento non adotta questo approccio perché utilizza un mapping non in tempo costante e richiede la moltiplicazione scalare di un punto casuale su una curva ellittica.

Appendice B. Hashing verso ristretto255​

ristretto255 [ristretto255-decaf448] fornisce un gruppo di ordine primo basato sulla curva edwards25519 [RFC7748]. Questa sezione descrive hash_to_ristretto255, che implementa una codifica con random oracle verso questo gruppo avente una distribuzione di output uniforme (Sezione 2.2.3) e le stesse proprietà di sicurezza e la stessa interfaccia della funzione hash_to_curve (Sezione 3).

L'API ristretto255 definisce una mappa unidirezionale ([ristretto255-decaf448], Sezione 5.3.2); questa sezione si riferisce a tale mappa come ristretto255_map.

La funzione hash_to_ristretto255 DEVE essere istanziata con una funzione expand_message che soddisfi i requisiti dati nella Sezione 5.3. Inoltre, DEVE utilizzare un tag di separazione dei domini costruito come descritto nella Sezione 3.1, e tutte le raccomandazioni di separazione dei domini della Sezione 10.7 si applicano quando si implementano protocolli che utilizzano hash_to_ristretto255.

hash_to_ristretto255(msg)

Parametri:
- DST, un tag di separazione dei domini (vedi discussione sopra).
- expand_message, una funzione che espande una stringa di byte e
  un tag di separazione dei domini in una stringa di byte
  uniformemente casuale (vedi discussione sopra).
- ristretto255_map, la mappa unidirezionale dall'API ristretto255.

Input: msg, una stringa di byte di lunghezza arbitraria.
Output: P, un elemento del gruppo ristretto255.

Passi:
1. uniform_bytes = expand_message(msg, DST, 64)
2. P = ristretto255_map(uniform_bytes)
3. return P

Poiché hash_to_ristretto255 non è una suite di hash-to-curve, non ha un Suite ID. Se è necessario un identificatore simile, DEVE essere costruito seguendo le linee guida della Sezione 8.10, con i seguenti parametri:

  • CURVE_ID: "ristretto255"
  • HASH_ID: come descritto nella Sezione 8.10
  • MAP_ID: "R255MAP"
  • ENC_VAR: "RO"

Ad esempio, se expand_message è expand_message_xmd con SHA-512, l'identificatore RICHIESTO è:

ristretto255_XMD:SHA-512_R255MAP_RO_

Appendice C. Hashing verso decaf448​

In modo simile a ristretto255, decaf448 [ristretto255-decaf448] fornisce un gruppo di ordine primo basato sulla curva curve448 [RFC7748]. Questa sezione descrive hash_to_decaf448, che implementa una codifica con random oracle verso questo gruppo avente una distribuzione di output uniforme (Sezione 2.2.3) e le stesse proprietà di sicurezza e la stessa interfaccia della funzione hash_to_curve (Sezione 3).

L'API decaf448 definisce una mappa unidirezionale ([ristretto255-decaf448], Sezione 5.3.4); questa sezione si riferisce a tale mappa come decaf448_map.

La funzione hash_to_decaf448 DEVE essere istanziata con una funzione expand_message che soddisfi i requisiti dati nella Sezione 5.3. Inoltre, DEVE utilizzare un tag di separazione dei domini costruito come descritto nella Sezione 3.1, e tutte le raccomandazioni di separazione dei domini della Sezione 10.7 si applicano quando si implementano protocolli che utilizzano hash_to_decaf448.

hash_to_decaf448(msg)

Parametri:
- DST, un tag di separazione dei domini (vedi discussione sopra).
- expand_message, una funzione che espande una stringa di byte e
  un tag di separazione dei domini in una stringa di byte
  uniformemente casuale (vedi discussione sopra).
- decaf448_map, la mappa unidirezionale dall'API decaf448.

Input: msg, una stringa di byte di lunghezza arbitraria.
Output: P, un elemento del gruppo decaf448.

Passi:
1. uniform_bytes = expand_message(msg, DST, 112)
2. P = decaf448_map(uniform_bytes)
3. return P

Poiché hash_to_decaf448 non è una suite di hash-to-curve, non ha un Suite ID. Se è necessario un identificatore simile, DEVE essere costruito seguendo le linee guida della Sezione 8.10, con i seguenti parametri:

  • CURVE_ID: "decaf448"
  • HASH_ID: come descritto nella Sezione 8.10
  • MAP_ID: "D448MAP"
  • ENC_VAR: "RO"

Ad esempio, se expand_message è expand_message_xof con SHAKE256, l'identificatore RICHIESTO è:

decaf448_XOF:SHAKE256_D448MAP_RO_

Appendice D. Mappe razionali​

Questa sezione fornisce mappe razionali che possono essere utilizzate quando si esegue l'hash verso curve twisted Edwards o Montgomery.

Data una curva twisted Edwards, l'Appendice D.1 mostra come derivare una curva Montgomery corrispondente e come mappare da tale curva alla curva twisted Edwards. Questa mappa può essere utilizzata quando si esegue l'hash verso curve twisted Edwards come descritto nella Sezione 6.8.

Data una curva Montgomery, l'Appendice D.2 mostra come derivare una curva Weierstraß corrispondente e come mappare da tale curva alla curva Montgomery. Questa mappa può essere utilizzata per eseguire l'hash verso curve Montgomery o twisted Edwards tramite il metodo Shallue-van de Woestijne (Sezione 6.6.1) o il metodo Simplified SWU (Sezione 6.6.2), come segue:

  • Per le curve Montgomery, si mappa prima alla curva Weierstraß, quindi si converte in coordinate Montgomery tramite la mappa.
  • Per le curve twisted Edwards, si compone la mappa da Weierstraß a Montgomery con la mappa da Montgomery a twisted Edwards (Appendice D.1) per ottenere una curva Weierstraß e una mappa verso la curva twisted Edwards target. Si mappa verso questa curva Weierstraß, quindi si converte in coordinate Edwards tramite la mappa.

D.1. Mappa generica da Montgomery a Twisted Edwards​

Questa sezione fornisce una mappa birazionale generica tra curve twisted Edwards e curve Montgomery.

La mappa in questa sezione è una versione semplificata della mappa data in [BBJLP08], Teorema 3.2. Nello specifico, la mappa di questa sezione gestisce i casi eccezionali in modo semplificato, orientato all'hash verso il sottogruppo di ordine primo di una curva twisted Edwards.

La curva twisted Edwards

a * v^2 + w^2 = 1 + d * v^2 * w^2

è birazionalmente equivalente alla curva Montgomery

K * t^2 = s^3 + J * s^2 + s

che ha la forma richiesta dal mapping Elligator 2 della Sezione 6.7.1. I coefficienti della curva Montgomery sono

  • J = 2 * (a + d) / (a - d)
  • K = 4 / (a - d)

La mappa razionale dal punto (s, t) sulla curva Montgomery di cui sopra al punto (v, w) sulla curva twisted Edwards è data da

  • v = s / t
  • w = (s - 1) / (s + 1)

Questa mappa non è definita quando t == 0 o s == -1, cioè quando il denominatore di una delle funzioni razionali sopra è zero. Le implementazioni DEVONO rilevare i casi eccezionali e restituire il valore (v, w) = (0, 1), che è il punto identità su tutte le curve twisted Edwards.

La seguente implementazione straight-line della mappa razionale sopra gestisce i casi eccezionali.

monty_to_edw_generic(s, t)

Input: (s, t), un punto sulla curva K * t^2 = s^3 + J * s^2 + s.
Output: (v, w), un punto su una curva twisted Edwards equivalente.

Passi:
1. tv1 = s + 1
2. tv2 = tv1 * t        # (s + 1) * t
3. tv2 = inv0(tv2)      # 1 / ((s + 1) * t)
4.   v = tv2 * tv1      # 1 / t
5.   v = v * s          # s / t
6.   w = tv2 * t        # 1 / (s + 1)
7. tv1 = s - 1
8.   w = w * tv1        # (s - 1) / (s + 1)
9.   e = tv2 == 0
10.  w = CMOV(w, 1, e)  # gestisce il caso eccezionale
11. return (v, w)

Per completezza, forniamo anche le relazioni inverse. (Si noti che questa mappa non è richiesta quando si esegue l'hash verso curve twisted Edwards.) I coefficienti della curva twisted Edwards corrispondente alla curva Montgomery di cui sopra sono

  • a = (J + 2) / K
  • d = (J - 2) / K

La mappa razionale dal punto (v, w) sulla curva twisted Edwards al punto (s, t) sulla curva Montgomery è data da

  • s = (1 + w) / (1 - w)
  • t = (1 + w) / (v * (1 - w))

La mappa non è definita quando v == 0 o w == 1. Quando l'obiettivo è mappare nel sottogruppo di ordine primo della curva Montgomery, è sufficiente restituire il punto identità sulla curva Montgomery nei casi eccezionali.

D.2. Mappa da Weierstraß a Montgomery​

La mappa razionale dal punto (s, t) sulla curva Montgomery

K * t^2 = s^3 + J * s^2 + s

al punto (x, y) sulla curva Weierstraß equivalente

y^2 = x^3 + A * x + B

è data da

  • A = (3 - J^2) / (3 * K^2)
  • B = (2 * J^3 - 9 * J) / (27 * K^3)
  • x = (3 * s + J) / (3 * K)
  • y = t / K

La mappa inversa, dal punto (x, y) al punto (s, t), è data da

  • s = (3 * K * x - J) / 3
  • t = y * K

Appendice E. Mappe di isogenia per le suite​

Questa sezione specifica le mappe di isogenia per le suite secp256k1 e BLS12-381 elencate nella Sezione 8.

Queste mappe sono espresse in coordinate affini. Wahby e Boneh ([WB19], Sezione 4.3) mostrano come valutare queste mappe in un sistema di coordinate proiettive (Appendice G.1), il che evita inversioni modulari.

Si faccia riferimento a [hash2curve-repo] per uno script Sage [SAGE] che costruisce queste isogenie.

E.1. Mappa di 3-isogenia per secp256k1​

Questa sezione specifica la mappa di isogenia per la suite secp256k1 elencata nella Sezione 8.7.

La mappa di 3-isogenia da (x', y') su E' a (x, y) su E è data dalle seguenti funzioni razionali:

  • x = x_num / x_den, dove

    • x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + k_(1,0)
    • x_den = x'^2 + k_(2,1) * x' + k_(2,0)

  • y = y' * y_num / y_den, dove

    • y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + k_(3,0)
    • y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)

Le costanti utilizzate per calcolare x_num sono le seguenti:

  • k_(1,0) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
  • k_(1,1) = 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581
  • k_(1,2) = 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262
  • k_(1,3) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c

Le costanti utilizzate per calcolare x_den sono le seguenti:

  • k_(2,0) = 0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b745781eb49b
  • k_(2,1) = 0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56612a8c6d14

Le costanti utilizzate per calcolare y_num sono le seguenti:

  • k_(3,0) = 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
note

Gli allegati rimanenti a partire dall'Appendice E.2 (Appendici E.2, E.3, F, G, H, I, J e K) contengono una grande quantità di costanti esadecimali, codice di implementazione in forma straight-line, script per la generazione di parametri e vettori di test. Si tratta di contenuti costituiti puramente da codice e dati: il vantaggio di una traduzione è limitato, mentre il rischio di errori di trascrizione è molto elevato. Per garantire la correttezza, tale contenuto non viene riprodotto qui; si forniscono invece direttamente i collegamenti al testo originale:

Testo originale completo: https://www.rfc-editor.org/rfc/rfc9380.html

Ultimo aggiornamento il