5. The X25519 and X448 Functions (Le funzioni X25519 e X448)

Le funzioni "X25519" e "X448" eseguono la moltiplicazione scalare nella forma di Montgomery delle curve sopra indicate. (Ciò si usa nell'implementazione di Diffie-Hellman.) Le funzioni prendono in ingresso uno scalare e una coordinata u e producono in uscita una coordinata u. Sebbene le funzioni lavorino internamente con interi, ingressi e uscite sono stringhe di 32 byte (per X25519) o 56 byte (per X448) e questa specifica ne definisce la codifica.

Le coordinate u sono elementi del campo sottostante GF(2^255 - 19) o GF(2^448 - 2^224 - 1) e sono codificate come un array di byte, u, in ordine little-endian tale che u[0] + 256u[1] + 256^2u[2] + ... + 256^(n-1)*u[n-1] sia congruo al valore modulo p e u[n-1] sia minimale. Alla ricezione di un tale array, le implementazioni di X25519 (ma non X448) DEVONO mascherare il bit più significativo nell'ultimo byte. Ciò serve a preservare la compatibilità con formati di punto che riservano il bit di segno per altri protocolli e ad aumentare la resistenza all'impronta delle implementazioni.

Le implementazioni DEVONO accettare valori non canonici e processarli come se fossero stati ridotti modulo il primo del campo. I valori non canonici sono 2^255 - 19 fino a 2^255 - 1 per X25519 e 2^448 - 2^224 - 1 fino a 2^448 - 1 per X448.

Le funzioni seguenti lo implementano in Python, sebbene il codice Python non sia pensato per essere performante né privo di leakage per canale laterale. Qui il parametro "bits" va impostato a 255 per X25519 e a 448 per X448:

def decodeLittleEndian(b, bits):
    return sum([b[i] << 8*i for i in range((bits+7)/8)])

def decodeUCoordinate(u, bits):
    u_list = [ord(b) for b in u]
    # Ignore any unused bits.
    if bits % 8:
        u_list[-1] &= (1<<(bits%8))-1
    return decodeLittleEndian(u_list, bits)

def encodeUCoordinate(u, bits):
    u = u % p
    return ''.join([chr((u >> 8*i) & 0xff)
                    for i in range((bits+7)/8)])

Si assume che gli scalari siano byte generati in modo casuale. Per X25519, per decodificare 32 byte casuali come intero scalare, si azzerano i tre bit meno significativi del primo byte e il bit più significativo dell'ultimo, si imposta il secondo bit più significativo dell'ultimo byte a 1 e infine si decodifica in little-endian. Ciò implica che l'intero risultante è della forma 2^254 più otto volte un valore tra 0 e 2^251 - 1 (estremi inclusi). Analogamente, per X448, si impostano a 0 i due bit meno significativi del primo byte e a 1 il bit più significativo dell'ultimo byte. Ciò implica che l'intero risultante è della forma 2^447 più quattro volte un valore tra 0 e 2^445 - 1 (estremi inclusi).

def decodeScalar25519(k):
    k_list = [ord(b) for b in k]
    k_list[0] &= 248
    k_list[31] &= 127
    k_list[31] |= 64
    return decodeLittleEndian(k_list, 255)

def decodeScalar448(k):
    k_list = [ord(b) for b in k]
    k_list[0] &= 252
    k_list[55] |= 128
    return decodeLittleEndian(k_list, 448)

Per implementare le funzioni X25519(k, u) e X448(k, u) (dove k è lo scalare e u è la coordinata u), si decodificano prima k e u e quindi si esegue la procedura seguente, tratta da [curve25519] e basata sulle formule di [montgomery]. Tutti i calcoli sono eseguiti in GF(p), cioè modulo p. La costante a24 è (486662 - 2) / 4 = 121665 per curve25519/X25519 e (156326 - 2) / 4 = 39081 per curve448/X448.

x_1 = u
x_2 = 1
z_2 = 0
x_3 = u
z_3 = 1
swap = 0

For t = bits-1 down to 0:
    k_t = (k >> t) & 1
    swap ^= k_t
    // Conditional swap; see text below.
    (x_2, x_3) = cswap(swap, x_2, x_3)
    (z_2, z_3) = cswap(swap, z_2, z_3)
    swap = k_t

    A = x_2 + z_2
    AA = A^2
    B = x_2 - z_2
    BB = B^2
    E = AA - BB
    C = x_3 + z_3
    D = x_3 - z_3
    DA = D * A
    CB = C * B
    x_3 = (DA + CB)^2
    z_3 = x_1 * (DA - CB)^2
    x_2 = AA * BB
    z_2 = E * (AA + a24 * E)

// Conditional swap; see text below.
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
Return x_2 * (z_2^(p - 2))

(Si noti che queste formule differiscono leggermente dall'articolo originale di Montgomery. Le implementazioni sono libere di usare qualsiasi formulazione corretta.)

Infine, si codifica il valore risultante come 32 o 56 byte in ordine little-endian. Per X25519, il bit più significativo inutilizzato DEVE essere zero.

La funzione cswap DOVREBBE essere implementata a tempo costante (cioè indipendentemente dall'argomento swap). Ad esempio, ciò può essere fatto come segue:

cswap(swap, x_2, x_3):
      dummy = mask(swap) AND (x_2 XOR x_3)
      x_2 = x_2 XOR dummy
      x_3 = x_3 XOR dummy
      Return (x_2, x_3)

Dove mask(swap) è la parola tutta-1 o tutta-0 della stessa lunghezza di x_2 e x_3, calcolata, ad esempio, come mask(swap) = 0 - swap.

5.1. Side-Channel Considerations (Considerazioni sui canali laterali)

X25519 e X448 sono progettate in modo che sia più facile ottenere implementazioni veloci e a tempo costante. La procedura sopra garantisce che la stessa sequenza di operazioni di campo sia eseguita per tutti i valori della chiave segreta, eliminando così una comune fonte di leakage per canale laterale. Ciò da solo, tuttavia, non impedisce tutti i canali laterali. È importante che lo schema di accessi alla memoria e i salti non dipendano dai valori dei bit di k. È inoltre importante che l'aritmetica utilizzata non riveli informazioni sugli interi modulo p, ad esempio rendendo distinguibile bc da cc. Su alcune architetture, persino istruzioni macchina primitive, come la divisione su parola singola, possono avere tempi variabili in funzione degli operandi.

Gli attacchi a canale laterale sono un'area di ricerca attiva che continua a produrre risultati nuovi e significativi. Si consiglia agli implementatori di seguire da vicino tale ricerca.

5.2. Test Vectors (Vettori di test)

Sono forniti due tipi di test. Il primo è una coppia di vettori di test per ciascuna funzione che consiste negli output attesi per gli input dati. Gli input sono in genere forniti come 64 o 112 cifre esadecimali da decodificare in 32 o 56 byte binari prima dell'elaborazione.

X25519:

Scalare in ingresso:

a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4

Scalare in ingresso come numero (base 10):

31029842492115040904895560451863089656472772604678260265531221036453811406496

Coordinata u in ingresso:

e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c

Coordinata u in ingresso come numero (base 10):

34426434033919594451155107781188821651316167215306631574996226621102155684838

Coordinata u in uscita:

c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552

Scalare in ingresso:

4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d

Scalare in ingresso come numero (base 10):

35156891815674817266734212754503633747128614016119564763269015315466259359304

Coordinata u in ingresso:

e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493

Coordinata u in ingresso come numero (base 10):

8883857351183929894090759386610649319417338800022198945255395922347792736741

Coordinata u in uscita:

95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957

X448:

Scalare in ingresso:

3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3

Scalare in ingresso come numero (base 10):

599189175373896402783756016145213256157230856085026129926891459468622403380588640249457727683869421921443004045221642549886377526240828

Coordinata u in ingresso:

06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086

Coordinata u in ingresso come numero (base 10):

382239910814107330116229961234899377031416365240571325148346555922438025162094455820962429142971339584360034337310079791515452463053830

Coordinata u in uscita:

ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239fe14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f

Scalare in ingresso:

203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c538345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f

Scalare in ingresso come numero (base 10):

633254335906970592779259481534862372382525155252028961056404001332122152890562527156973881968934311400345568203929409663925541994577184

Coordinata u in ingresso:

0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db

Coordinata u in ingresso come numero (base 10):

622761797758325444462922068431234180649590390024811299761625153767228042600197997696167956134770744996690267634159427999832340166786063

Coordinata u in uscita:

884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d

Il secondo tipo di vettore di test consiste nel risultato di invocare la funzione in questione un numero specificato di volte. Inizialmente, si impostano k e u ai seguenti valori:

Per X25519:

0900000000000000000000000000000000000000000000000000000000000000

Per X448:

050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Per ogni iterazione, si imposta k al risultato della chiamata alla funzione e u al vecchio valore di k. Il risultato finale è il valore lasciato in k.

X25519:

Dopo un'iterazione:

422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079

Dopo 1.000 iterazioni:

684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51

Dopo 1.000.000 iterazioni:

7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424

X448:

Dopo un'iterazione:

3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113

Dopo 1.000 iterazioni:

aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38

Dopo 1.000.000 iterazioni:

077f453681caca3693198420bbe515cae0002472519b3e67661a7e89cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37