Aller au contenu principal

5. The X25519 and X448 Functions

5. Fonctions X25519 et X448​

Les fonctions "X25519" et "X448" effectuent une multiplication scalaire sur la forme de Montgomery des courbes ci-dessus. (Ceci est utilisé lors de l'implémentation de Diffie-Hellman.) Les fonctions prennent un scalaire et une coordonnée u comme entrées et produisent une coordonnée u comme sortie. Bien que les fonctions fonctionnent en interne avec des entiers, les entrées et sorties sont des chaînes de 32 octets (pour X25519) ou de 56 octets (pour X448) et cette spécification définit leur encodage.

Les coordonnées u sont des éléments du corps sous-jacent GF(2^255 - 19) ou GF(2^448 - 2^224 - 1) et sont encodées sous forme de tableau d'octets, u, en ordre petit-boutien tel que u[0] + 256u[1] + 256^2u[2] + ... + 256^(n-1)*u[n-1] est congru à la valeur modulo p et u[n-1] est minimal. Lors de la réception d'un tel tableau, les implémentations de X25519 (mais pas X448) DOIVENT masquer le bit le plus significatif de l'octet final. Ceci est fait pour préserver la compatibilité avec les formats de points qui réservent le bit de signe pour une utilisation dans d'autres protocoles et pour augmenter la résistance à l'empreinte digitale d'implémentation.

Les implémentations DOIVENT accepter les valeurs non canoniques et les traiter comme si elles avaient été réduites modulo le premier du corps. Les valeurs non canoniques sont 2^255 - 19 à 2^255 - 1 pour X25519 et 2^448 - 2^224 - 1 à 2^448 - 1 pour X448.

Les fonctions suivantes implémentent ceci en Python, bien que le code Python ne soit pas destiné à être performant ni exempt de canaux auxiliaires. Ici, le paramètre "bits" doit être défini à 255 pour X25519 et 448 pour 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)])

Les scalaires sont supposés être des octets générés aléatoirement. Pour X25519, afin de décoder 32 octets aléatoires comme un scalaire entier, définissez les trois bits les moins significatifs du premier octet et le bit le plus significatif du dernier à zéro, définissez le deuxième bit le plus significatif du dernier octet à 1 et, enfin, décodez en petit-boutien. Cela signifie que l'entier résultant est de la forme 2^254 plus huit fois une valeur entre 0 et 2^251 - 1 (inclus). De même, pour X448, définissez les deux bits les moins significatifs du premier octet à 0, et le bit le plus significatif du dernier octet à 1. Cela signifie que l'entier résultant est de la forme 2^447 plus quatre fois une valeur entre 0 et 2^445 - 1 (inclus).

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)

Pour implémenter les fonctions X25519(k, u) et X448(k, u) (où k est le scalaire et u est la coordonnée u), décodez d'abord k et u puis effectuez la procédure suivante, qui est tirée de [curve25519] et basée sur les formules de [montgomery]. Tous les calculs sont effectués dans GF(p), c'est-à-dire qu'ils sont effectués modulo p. La constante a24 est (486662 - 2) / 4 = 121665 pour curve25519/X25519 et (156326 - 2) / 4 = 39081 pour 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))

(Notez que ces formules sont légèrement différentes de l'article original de Montgomery. Les implémentations sont libres d'utiliser n'importe quelles formules correctes.)

Enfin, encodez la valeur résultante en 32 ou 56 octets en ordre petit-boutien. Pour X25519, le bit le plus significatif inutilisé DOIT être zéro.

La fonction cswap DEVRAIT être implémentée en temps constant (c'est-à-dire indépendamment de l'argument swap). Par exemple, cela peut être fait comme suit:

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)

Où mask(swap) est le mot tout-1 ou tout-0 de la même longueur que x_2 et x_3, calculé, par exemple, comme mask(swap) = 0 - swap.

5.1. Considérations sur les canaux auxiliaires​

X25519 et X448 sont conçues de sorte que les implémentations rapides à temps constant soient plus faciles à produire. La procédure ci-dessus garantit que la même séquence d'opérations de corps est effectuée pour toutes les valeurs de la clé secrète, éliminant ainsi une source commune de fuite par canal auxiliaire. Cependant, cela seul ne prévient pas tous les canaux auxiliaires par lui-même. Il est important que le schéma des accès mémoire et des sauts ne dépende pas des valeurs de l'un quelconque des bits de k. Il est également important que l'arithmétique utilisée ne divulgue pas d'informations sur les entiers modulo p, par exemple en rendant bc distinguable de cc. Sur certaines architectures, même les instructions machine primitives, telles que la division à un mot, peuvent avoir un timing variable basé sur leurs entrées.

Les attaques par canaux auxiliaires constituent un domaine de recherche actif qui produit encore des résultats nouveaux importants. Il convient que les personnes chargées de l'implémentation suivent de près ces travaux.

5.2. Vecteurs de test​

Deux types de tests sont fournis. Le premier est une paire de vecteurs de test pour chaque fonction qui consistent en des sorties attendues pour les entrées données. Les entrées sont généralement données sous forme de 64 ou 112 chiffres hexadécimaux qui doivent être décodés en 32 ou 56 octets binaires avant le traitement.

X25519:

Scalaire d'entrée:

a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4

Scalaire d'entrée en nombre (base 10):

31029842492115040904895560451863089656472772604678260265531221036453811406496

Coordonnée u d'entrée:

e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c

Coordonnée u d'entrée en nombre (base 10):

34426434033919594451155107781188821651316167215306631574996226621102155684838

Coordonnée u de sortie:

c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552

Scalaire d'entrée:

4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d

Scalaire d'entrée en nombre (base 10):

35156891815674817266734212754503633747128614016119564763269015315466259359304

Coordonnée u d'entrée:

e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493

Coordonnée u d'entrée en nombre (base 10):

8883857351183929894090759386610649319417338800022198945255395922347792736741

Coordonnée u de sortie:

95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957

X448:

Scalaire d'entrée:

3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3

Scalaire d'entrée en nombre (base 10):

599189175373896402783756016145213256157230856085026129926891459468622403380588640249457727683869421921443004045221642549886377526240828

Coordonnée u d'entrée:

06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086

Coordonnée u d'entrée en nombre (base 10):

382239910814107330116229961234899377031416365240571325148346555922438025162094455820962429142971339584360034337310079791515452463053830

Coordonnée u de sortie:

ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239fe14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f

Scalaire d'entrée:

203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c538345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f

Scalaire d'entrée en nombre (base 10):

633254335906970592779259481534862372382525155252028961056404001332122152890562527156973881968934311400345568203929409663925541994577184

Coordonnée u d'entrée:

0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db

Coordonnée u d'entrée en nombre (base 10):

622761797758325444462922068431234180649590390024811299761625153767228042600197997696167956134770744996690267634159427999832340166786063

Coordonnée u de sortie:

884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d

Le deuxième type de vecteur de test consiste en le résultat de l'appel de la fonction en question un nombre spécifié de fois. Initialement, définissez k et u aux valeurs suivantes:

Pour X25519:

0900000000000000000000000000000000000000000000000000000000000000

Pour X448:

050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Pour chaque itération, définissez k comme le résultat de l'appel de la fonction et u comme l'ancienne valeur de k. Le résultat final est la valeur restée dans k.

X25519:

Après une itération:

422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079

Après 1 000 itérations:

684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51

Après 1 000 000 itérations:

7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424

X448:

Après une itération:

3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113

Après 1 000 itérations:

aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38

Après 1 000 000 itérations:

077f453681caca3693198420bbe515cae0002472519b3e67661a7e89cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37
Dernière mise à jour le