Appendici

Appendice A. Lavori correlati

Il problema della mappatura di stringhe di bit arbitrarie in punti di curve ellittiche è stato oggetto di ricerche sia pratiche che teoriche. Questa sezione descrive brevemente il contesto e i risultati della ricerca alla base delle raccomandazioni di questo documento. Questa sezione è fornita solo a scopo informativo.

Un metodo ingenuo ma generalmente non sicuro per mappare una stringa msg a un punto su una curva ellittica E con n punti consiste nel fissare prima un punto P che generi il gruppo della curva ellittica e una funzione di hash Hn dalle stringhe di bit agli interi minori di n; quindi calcolare Hn(msg) * P, dove l'operatore * rappresenta la moltiplicazione scalare. Il motivo per cui questo approccio non è sicuro è che il punto risultante ha una relazione di logaritmo discreto nota con P. Pertanto, tranne nei casi in cui questo metodo sia specificato dal protocollo, non deve essere utilizzato; farlo rischia di causare catastrofici fallimenti della sicurezza.

Boneh et al. [BLS01] descrivono un metodo di codifica chiamato MapToGroup, che funziona approssimativamente come segue: innanzitutto, utilizzare la stringa di input per inizializzare un generatore di numeri pseudocasuali, quindi utilizzare il generatore per produrre un valore x in F. Se x è la coordinata x di un punto sulla curva ellittica, produrre tale punto. Altrimenti, generare un nuovo valore x in F e riprovare. Poiché un valore casuale x in F ha una probabilità di circa 1/2 di corrispondere a un punto sulla curva, il numero di tentativi attesi è solo due. Tuttavia, il tempo di esecuzione di questo metodo, comunemente chiamato algoritmo probabilistico "try-and-increment", dipende dalla stringa di input. Pertanto, non è sicuro per l'uso in protocolli sensibili ai canali temporali laterali, come illustrato dall'attacco Dragonblood [VR20].

Schinzel e Skałba [SS04] introducono un metodo per la costruzione deterministica di punti di curve ellittiche, per una classe ristretta di curve e un numero molto ridotto di punti. Skałba [S05] generalizza questa costruzione a più curve e più punti su tali curve. Shallue e van de Woestijne [SW06] generalizzano e semplificano ulteriormente la costruzione di Skałba, producendo mappature concretamente efficienti verso una frazione costante dei punti su quasi tutte le curve. Fouque e Tibouchi [FT12] forniscono una parametrizzazione di questa mappatura per le curve Barreto-Naehrig pairing-friendly [BN05].

Ulas [U07] descrive una versione più semplice della mappatura Shallue-van de Woestijne, e Brier et al. [BCIMRT10] forniscono un'ulteriore semplificazione, chiamata dagli autori mappatura "SWU semplificata". Questa mappatura semplificata si applica solo ai campi con caratteristica p = 3 (mod 4); Wahby e Boneh [WB19] generalizzano ai campi di qualsiasi caratteristica e forniscono ulteriori ottimizzazioni.

Boneh e Franklin forniscono un algoritmo deterministico per la mappatura su alcune curve supersingolari su campi di caratteristica p = 2 (mod 3) [BF01]. Icart fornisce un altro algoritmo deterministico che mappa su qualsiasi curva su un campo di caratteristica p = 2 (mod 3) [Icart09]. Molte estensioni e generalizzazioni seguono questo lavoro, tra cui [FSV09], [FT10], [KLR10], [F11] e [CK11].

In seguito al lavoro di Farashahi [F11], Fouque et al. [FJT13] descrivono una mappatura su curve su campi di caratteristica p = 3 (mod 4) con un numero di punti divisibile per 4. Bernstein et al. [BHKL13] ottimizzano questa mappatura e descrivono una mappatura correlata chiamata "Elligator 2", che si applica a qualsiasi curva su un campo di caratteristica dispari con un punto di ordine 2. Ciò include Curve25519 e Curve448, entrambe curve raccomandate dal CFRG [RFC7748]. Bernstein et al. [BLMP19] estendono la mappatura Elligator 2 a una classe di curve supersingolari su campi di caratteristica p = 3 (mod 4).

Un avvertimento importante riguardo a tutte le funzioni di mappatura deterministiche sopra indicate è che nessuna di esse mappa sull'intera curva, bensì su una frazione dei punti. Ciò significa che non possono essere utilizzate direttamente per costruire un random oracle che produca punti sulla curva.

Brier et al. [BCIMRT10] forniscono due soluzioni a questo problema. La prima, che Brier et al. dimostrano applicarsi al metodo di Icart, calcola f(H0(msg)) + f(H1(msg)) per due diverse funzioni di hash H0 e H1 dalle stringhe di bit a F e una mappatura f da F alla curva ellittica E. La seconda, che si applica essenzialmente a tutte le mappature deterministiche ma è più costosa, calcola f(H0(msg)) + H2(msg) * P, dove P è un generatore del gruppo della curva ellittica, H2 è un hash dalle stringhe di bit agli interi modulo r, e r è l'ordine del gruppo della curva ellittica.

Farashahi et al. [FFSTV13] migliorano l'analisi del primo metodo, mostrando che si applica alla maggior parte delle mappature deterministiche. Tibouchi e Kim [TK17] perfezionano ulteriormente l'analisi e descrivono ulteriori ottimizzazioni.

In modo complementare al problema della mappatura delle stringhe di bit ai punti delle curve ellittiche, Bernstein et al. [BHKL13] studiano il problema della mappatura dei punti delle curve ellittiche a stringhe di bit uniformemente casuali, fornendo soluzioni per una classe di curve che include le curve di Montgomery e le curve di Edwards ritorte. Tibouchi [T14] e Aranha et al. [AFQTZ14] generalizzano questi risultati. Questo documento non tratta questo problema complementare.

Appendice B. Hashing su ristretto255

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

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

La funzione hash_to_ristretto255 DEVE essere istanziata con una funzione expand_message conforme ai requisiti forniti nella Sezione 5.3. Inoltre, DEVE utilizzare un tag di separazione di dominio costruito come descritto nella Sezione 3.1, e tutte le raccomandazioni di separazione di dominio fornite nella Sezione 10.7 si applicano quando si implementano protocolli che utilizzano hash_to_ristretto255.

hash_to_ristretto255(msg)

Parametri:

• DST, un tag di separazione di dominio (vedere la discussione sopra).
• expand_message, una funzione che espande una stringa di byte e un tag di separazione di dominio in una stringa di byte uniformemente casuale (vedere la discussione sopra).
• ristretto255_map, la mappatura unidirezionale dell'API ristretto255.

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

Passaggi:

1. uniform_bytes = expand_message(msg, DST, 64)
2. P = ristretto255_map(uniform_bytes)
3. ritorna P

Poiché hash_to_ristretto255 non è una suite hash-to-curve, non ha un ID suite. Se è richiesto un identificatore simile, DEVE essere costruito seguendo le linee guida nella 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 che utilizza SHA-512, l'identificatore RICHIESTO è:

ristretto255_XMD:SHA-512_R255MAP_RO_

Appendice C. Hashing su decaf448

Similmente a ristretto255, decaf448 [ristretto255-decaf448] fornisce un gruppo di ordine primo basato su curve448 [RFC7748]. Questa sezione descrive hash_to_decaf448, che implementa una codifica random oracle su questo gruppo con una distribuzione dell'output uniforme (Sezione 2.2.3) e le stesse proprietà di sicurezza e interfaccia della funzione hash_to_curve (Sezione 3).

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

La funzione hash_to_decaf448 DEVE essere istanziata con una funzione expand_message conforme ai requisiti forniti nella Sezione 5.3. Inoltre, DEVE utilizzare un tag di separazione di dominio costruito come descritto nella Sezione 3.1, e tutte le raccomandazioni di separazione di dominio fornite nella Sezione 10.7 si applicano quando si implementano protocolli che utilizzano hash_to_decaf448.

hash_to_decaf448(msg)

Parametri:

• DST, un tag di separazione di dominio (vedere la discussione sopra).
• expand_message, una funzione che espande una stringa di byte e un tag di separazione di dominio in una stringa di byte uniformemente casuale (vedere la discussione sopra).
• decaf448_map, la mappatura unidirezionale dell'API decaf448.

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

Passaggi:

1. uniform_bytes = expand_message(msg, DST, 112)
2. P = decaf448_map(uniform_bytes)
3. ritorna P

Poiché hash_to_decaf448 non è una suite hash-to-curve, non ha un ID suite. Se è richiesto un identificatore simile, DEVE essere costruito seguendo le linee guida nella 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 che utilizza SHAKE256, l'identificatore RICHIESTO è:

decaf448_XOF:SHAKE256_D448MAP_RO_

Appendice D. Mappe razionali

Questa sezione fornisce mappe razionali che possono essere utilizzate durante l'hashing verso curve di Edwards ritorte o di Montgomery.

Data una curva di Edwards ritorta, l'Appendice D.1 mostra come derivare una corrispondente curva di Montgomery e come mappare da tale curva alla curva di Edwards ritorta. Questa mappatura può essere utilizzata durante l'hashing verso curve di Edwards ritorte come descritto nella Sezione 6.8.

Data una curva di Montgomery, l'Appendice D.2 mostra come derivare una corrispondente curva di Weierstrass e come mappare da tale curva alla curva di Montgomery. Questa mappatura può essere utilizzata per l'hashing verso curve di Montgomery o di Edwards ritorte tramite il metodo Shallue-van de Woestijne (Sezione 6.6.1) o il metodo SWU semplificato (Sezione 6.6.2), come segue:

• Per le curve di Montgomery, mappare prima alla curva di Weierstrass, quindi convertire in coordinate di Montgomery tramite la mappatura.

• Per le curve di Edwards ritorte, comporre la mappatura da Weierstrass a Montgomery con la mappatura da Montgomery a Edwards ritorta (Appendice D.1) per ottenere una curva di Weierstrass e una mappatura alla curva di Edwards ritorta di destinazione. Mappare a questa curva di Weierstrass, quindi convertire in coordinate di Edwards tramite la mappatura.

D.1. Mappatura generica da Montgomery a Edwards ritorta

Questa sezione fornisce una mappa birazionalmente generica tra le curve di Edwards ritorte e le curve di Montgomery.

La mappa in questa sezione è una versione semplificata della mappa fornita in [BBJLP08], teorema 3.2. Nello specifico, la mappa in questa sezione gestisce i casi eccezionali in modo semplificato, orientato verso l'hashing nel sottogruppo di ordine primo di una curva di Edwards ritorta.

La curva di Edwards ritorta a * v^2 + w^2 = 1 + d * v^2 * w^2 è birazionalmente equivalente alla curva di Montgomery K * t^2 = s^3 + J * s^2 + s che ha la forma richiesta dalla mappatura Elligator 2 della Sezione 6.7.1. I coefficienti della curva di Montgomery sono:

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

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

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

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

La seguente procedura "straight-line" della mappatura razionale sopra indicata 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 di Edwards ritorta equivalente.

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) # gestire il caso eccezionale
11. ritorna (v, w)

Per completezza, forniamo anche le relazioni inverse. (Si noti che questa mappa non è richiesta durante l'hashing verso le curve di Edwards ritorte). I coefficienti della curva di Edwards ritorta corrispondenti alla curva di Montgomery sopra indicata sono:

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

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

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

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

D.2. Mappatura da Weierstrass a Montgomery

La mappa razionale dal punto (s, t) sulla curva di Montgomery K * t^2 = s^3 + J * s^2 + s al punto (x, y) sulla curva di Weierstrass 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 fornite in termini di coordinate affini. Wahby e Boneh ([WB19], Sezione 4.3) mostrano come valutare queste mappe in un sistema di coordinate proiettive (Appendice G.1), che evita le inversioni modulari.

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

E.1. Mappa di isogenia-3 per secp256k1

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

La mappa di isogenia-3 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
• k_(3,1) = 0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90fc201d71a3
• k_(3,2) = 0x29a6194691f91a73715209ef6512e576722830a201be2018a765e85a9ecee931
• k_(3,3) = 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84

Le costanti utilizzate per calcolare y_den sono le seguenti:

• k_(4,0) = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b
• k_(4,1) = 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573
• k_(4,2) = 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f

note

A causa della notevole lunghezza delle appendici E, F, G, H, I e J (che contengono numerose costanti esadecimali, codice di implementazione e vettori di test), il contenuto completo è stato omesso da questa documentazione per ragioni di brevità.

Per consultare le appendici complete, tra cui:

• Appendice E: Mappe di isogenia complete per BLS12-381 G1 e G2
• Appendice F: Implementazioni "straight-line" delle mappature deterministiche
• Appendice G: Codice di esempio ottimizzato specifico per la curva
• Appendice H: Script per la generazione dei parametri
• Appendice I: Funzioni sqrt e is_square
• Appendice J: Vettori di test completi della suite per tutte le curve

Fare riferimento al documento originale RFC 9380.

Ringraziamenti

Gli autori desiderano ringraziare Adam Langley per la sua descrizione dettagliata di Elligator 2 con Curve25519 [L13]; Dan Boneh, Benjamin Lipp, Christopher Patton e Leonid Reyzin per le discussioni pedagogiche; e David Benjamin, Daniel Bourdrez, Frank Denis, Sean Devlin, Justin Drake, Bjoern Haase, Mike Hamburg, Dan Harkins, Daira Hopwood, Thomas Icart, Andy Polyakov, Thomas Pornin, Mamy Ratsimbazafy, Michael Scott, Filippo Valsorda e Mathy Vanhoef per le loro critiche e commenti costruttivi.

Collaboratori

Sharon Goldberg
Boston University
Email: [email protected]

Ela Lee
Royal Holloway, University of London
Email: [email protected]

Michele Orru
Email: [email protected]

Indirizzi degli autori

Armando Faz-Hernandez
Cloudflare, Inc.
Email: [email protected]

Sam Scott
Oso Security, Inc.
Email: [email protected]

Nick Sullivan
Cloudflare, Inc.
Email: [email protected]

Riad S. Wahby
Stanford University
Email: [email protected]

Christopher A. Wood
Cloudflare, Inc.
Email: [email protected]