4. Fonctions utilitaires

Les algorithmes de ce document utilisent les fonctions utilitaires décrites ci-dessous, plus des opérations arithmétiques standard (addition, multiplication, réduction modulaire, etc.) et des opérations sur les points de courbe elliptique (addition de points et multiplication scalaire).

Pour la sécurité, les implémentations de ces fonctions DEVRAIENT être en temps constant : en résumé, cela signifie que le temps d'exécution et les schémas d'accès à la mémoire ne DEVRAIENT PAS dépendre des valeurs des entrées secrètes, des valeurs intermédiaires ou des sorties. Pour de telles implémentations en temps constant, toutes les opérations arithmétiques, comparaisons et affectations DOIVENT également être implémentées en temps constant. La section 10.3 traite brièvement des questions de sécurité liées au temps constant.

Les conseils sur l'implémentation des opérations de bas niveau (en temps constant ou autrement) dépassent le cadre de ce document ; les lecteurs devraient consulter les documents de référence standard [MOV96] [CFADLNV05].

• CMOV(a, b, c) : Si c est Faux, CMOV renvoie a ; sinon, il renvoie b. Pour les implémentations en temps constant, cette opération doit s'exécuter dans un temps indépendant de la valeur de c.

• AND, OR, NOT et XOR sont des opérateurs logiques bit à bit standard. Pour les implémentations en temps constant, les opérateurs de court-circuit DOIVENT être évités.

• is_square(x) : Cette fonction renvoie Vrai chaque fois que la valeur x est un carré dans le corps F. Par le critère d'Euler, cette fonction peut être calculée en temps constant comme :

  is_square(x) := { Vrai, si x^((q - 1) / 2) est 0 ou 1 dans F ; { Faux, sinon.

  Dans certains corps d'extension, is_square peut être calculé en temps constant plus rapidement que par l'exponentiation ci-dessus. [AR13] et [S85] décrivent des méthodes optimisées pour les corps d'extension. L'Annexe I.5 donne une méthode en ligne droite optimisée pour GF(p^2).

• sqrt(x) : L'opération sqrt est une fonction à valeurs multiples, c'est-à-dire qu'il existe deux racines de x dans le corps F chaque fois que x est un carré (sauf quand x = 0). Pour maintenir la compatibilité entre les implémentations tout en laissant aux implémenteurs une marge de manœuvre pour les optimisations, ce document n'exige pas que sqrt() renvoie une valeur particulière. Au lieu de cela, comme expliqué dans la section 6.4, toute fonction qui appelle sqrt spécifie également comment déterminer la racine correcte.

  Le moyen privilégié de calculer les racines carrées est de fixer un algorithme déterministe particulier à F. Nous donnons plusieurs algorithmes dans l'Annexe I.

• sgn0(x) : Cette fonction renvoie soit 0 soit 1 indiquant le « signe » de x, où sgn0(x) == 1 exactement quand x est « négatif ». (En d'autres termes, cette fonction considère toujours 0 comme positif.) La section 4.1 définit cette fonction et traite de son implémentation.

• inv0(x) : Cette fonction renvoie l'inverse multiplicatif de x dans F, étendu à tout F en fixant inv0(0) == 0. Un moyen simple d'implémenter inv0 en temps constant est de calculer :

  inv0(x) := x^(q - 2).

  Notez que sur l'entrée 0, la sortie est 0 comme requis. Certains corps peuvent permettre des méthodes d'inversion plus rapides ; une discussion détaillée de ces méthodes dépasse le cadre de ce document.

• I2OSP et OS2IP : Ces fonctions sont utilisées pour convertir une chaîne d'octets vers et depuis un entier non négatif comme décrit dans [RFC8017]. (Notez que ces fonctions opèrent sur des chaînes d'octets dans l'ordre big-endian.)

• a || b : dénote la concaténation des chaînes d'octets a et b. Par exemple, "ABC" || "DEF" == "ABCDEF".

• substr(str, sbegin, slen) : Pour une chaîne d'octets str, cette fonction renvoie la sous-chaîne de slen octets commençant à la position sbegin ; les positions sont indexées à partir de zéro. Par exemple, substr("ABCDEFG", 2, 3) == "CDE".

• len(str) : Pour une chaîne d'octets str, cette fonction renvoie la longueur de str en octets. Par exemple, len("ABC") == 3.

• strxor(str1, str2) : Pour les chaînes d'octets str1 et str2, strxor(str1, str2) renvoie le XOR bit à bit des deux chaînes. Par exemple, strxor("abc", "XYZ") == "9;9" (les chaînes dans cet exemple sont des littéraux ASCII, mais strxor est défini pour des chaînes d'octets arbitraires). Dans ce document, strxor n'est appliqué qu'à des entrées de longueur égale.

4.1. La fonction sgn0

Cette section définit une implémentation sgn0 générique qui s'applique à tout corps F = GF(p^m). Elle donne également des implémentations simplifiées pour les cas F = GF(p) et F = GF(p^2).

La définition de la fonction sgn0 pour les corps d'extension repose sur la base polynomiale ou la représentation vectorielle des éléments du corps, et itère sur l'ensemble de la représentation vectorielle de l'élément d'entrée. En conséquence, sgn0 dépend du polynôme primitif utilisé pour définir la base polynomiale ; voir la section 8 pour plus d'informations sur cette base, et voir la section 2.1 pour une discussion sur la représentation des éléments des corps d'extension sous forme de vecteurs.

sgn0(x)

Paramètres :

• F, un corps fini de caractéristique p et d'ordre q = p^m.
• p, la caractéristique de F (voir immédiatement ci-dessus).
• m, le degré d'extension de F, m >= 1 (voir immédiatement ci-dessus).

Entrée : x, un élément de F. Sortie : 0 ou 1.

Étapes :

1. sign = 0
2. zero = 1
3. pour i allant de 1, 2, ..., m :
4. sign_i = x_i mod 2
5. zero_i = x_i == 0
6. sign = sign OR (zero AND sign_i) # Éviter les opérations logiques court-circuit
7. zero = zero AND zero_i
8. retourner sign

Lorsque m == 1, sgn0 peut être considérablement simplifié :

sgn0_m_eq_1(x)

Entrée : x, un élément de GF(p). Sortie : 0 ou 1.

Étapes :

1. retourner x mod 2

Le cas m == 2 est seulement légèrement plus compliqué :

sgn0_m_eq_2(x)

Entrée : x, un élément de GF(p^2). Sortie : 0 ou 1.

Étapes :

1. sign_0 = x_0 mod 2
2. zero_0 = x_0 == 0
3. sign_1 = x_1 mod 2
4. s = sign_0 OR (zero_0 AND sign_1) # Éviter les opérations logiques court-circuit
5. retourner s