4. Fonctions utilitaires

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

Pour des raisons de sécurité, les implémentations de ces fonctions DEVRAIENT s'exécuter en temps constant : en bref, cela signifie que le temps d'exécution et les motifs d'accès 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 aborde brièvement les questions de sécurité liées au temps constant.

Les recommandations sur l'implémentation des opérations de bas niveau (en temps constant ou non) dépassent le cadre de ce document ; le lecteur est invité à consulter les ouvrages de référence standard [MOV96] [CFADLNV05].

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

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

• is_square(x) : cette fonction renvoie True dès lors que la valeur x est un carré dans le corps F. D'après le critère d'Euler, cette fonction peut être calculée en temps constant comme suit :

is_square(x) := { True,  if x^((q - 1) / 2) is 0 or 1 in F;
                { False, otherwise.

Dans certains corps d'extension, is_square peut être calculée 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 optimisée en ligne droite (straight-line) pour GF(p^2).

• sqrt(x) : l'opération sqrt est une fonction multivaluée, c'est-à-dire qu'il existe deux racines de x dans le corps F dès lors que x est un carré (sauf lorsque x = 0). Afin de préserver 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. À la place, comme expliqué à la Section 6.4, toute fonction qui appelle sqrt spécifie également comment déterminer la racine correcte.

La façon préférée de calculer les racines carrées consiste à fixer un algorithme déterministe propre à F. Nous donnons plusieurs algorithmes à l'Annexe I.

• sgn0(x) : cette fonction renvoie 0 ou 1, indiquant le « signe » de x, sgn0(x) == 1 précisément lorsque x est « négatif ». (Autrement dit, cette fonction considère toujours 0 comme positif.) La Section 4.1 définit cette fonction et discute de son implémentation.

• inv0(x) : cette fonction renvoie l'inverse multiplicatif de x dans F, étendu à tout F en fixant inv0(0) == 0. Une manière simple d'implémenter inv0 en temps constant consiste à calculer

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

Notons que, pour l'entrée 0, la sortie vaut 0, comme requis. Certains corps peuvent autoriser 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 servent à convertir une chaîne d'octets en un entier non négatif et réciproquement, comme décrit dans [RFC8017]. (Notons que ces fonctions opèrent sur des chaînes d'octets en ordre gros-boutiste (big-endian).)

• a || b : désigne 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 des chaînes d'octets str1 et str2, strxor(str1, str2) renvoie le OU exclusif bit à bit des deux chaînes. Par exemple, strxor("abc", "XYZ") == "9;9" (les chaînes de cet exemple sont des littéraux ASCII, mais strxor est définie pour des chaînes d'octets arbitraires). Dans ce document, strxor n'est appliquée qu'à des entrées de longueur égale.

4.1. La fonction sgn0

Cette section définit une implémentation générique de sgn0 applicable à 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 représentation vectorielle, des éléments du corps, et itère sur l'intégralité de la représentation vectorielle de l'élément d'entrée. Par conséquent, 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 la Section 2.1 pour une discussion sur la représentation des éléments des corps d'extension sous forme de vecteurs.

sgn0(x)

Parameters:
- F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above).

Input: x, an element of F.
Output: 0 or 1.

Steps:
1. sign = 0
2. zero = 1
3. for i in (1, 2, ..., m):
4.   sign_i = x_i mod 2
5.   zero_i = x_i == 0
6.   sign = sign OR (zero AND sign_i) # Avoid short-circuit logic ops
7.   zero = zero AND zero_i
8. return sign

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

sgn0_m_eq_1(x)

Input: x, an element of GF(p).
Output: 0 or 1.

Steps:
1. return x mod 2

Le cas m == 2 n'est que légèrement plus compliqué :

sgn0_m_eq_2(x)

Input: x, an element of GF(p^2).
Output: 0 or 1.

Steps:
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) # Avoid short-circuit logic ops
5. return s