Brevet FR3129262A1 — publié le 20230519

Réduction et conversion d'un scalaire en une représentation tau-adique La présente description concerne un procédé cryptographique comprenant : l'exécution, par un circuit cryptographique, d'un algorithme appliqué à un scalaire afin de générer un vecteur de sortie, de longueur l+n, dont les éléments sont , l'algorithme comprenant des itérations i, chaque itération i prenant une valeur de donnée d'entrée, initialement égale audit scalaire et un vecteur d'entrée de longueur c, dont les éléments sont , où pour chaque l'élément est tel que . Figure pour l'abrégé : Fig. 2 Réduction et conversion d'un scalaire en une représentation tau-adique La présente description concerne de façon générale le domaine de la cryptographie et, en particulier, un procédé et un dispositif destinés à mettre en œuvre une opération de cryptographie sur la base d'une cryptographie à courbe elliptique. La cryptographie à courbe elliptique (ECC) est bien adaptée pour des procédés de cryptographie à clef publique dans la mesure où elle permet d'utiliser une clef cryptographique de taille réduite. Par exemple, une cryptographie à courbe elliptique peut être utilisée pour mettre en œuvre une opération de cryptage, d'échange de clef, de validation de clef, de signature numérique ou d'authentification. En outre, l'utilisation d'une courbe de Koblitz permet d'accroître la vitesse de certaines opérations de cryptographie, en particulier la multiplication d'un point par un scalaire. Toutefois, pour être efficace, le scalaire doit généralement être converti en une représentation particulière avant d'être utilisé dans des opérations cryptographiques sur une courbe de Koblitz. Il serait souhaitable de rendre plus rapide le processus de conversion et/ou de rendre la valeur du scalaire difficile à détecter pendant l'exécution, par un dispositif électronique, d'opérations cryptographiques l'impliquant. Il existe un besoin d'améliorer le processus de conversion de la valeur d'un scalaire en une représentation appropriée pour un usage sur des courbes de Koblitz. Il existe un besoin d'améliorer la protection de la valeur d'un scalaire utilisée pendant des opérations cryptographiques, en particulier celles basées sur des courbes de Koblitz. Un mode de réalisation prévoit un procédé cryptographique comprenant : l'exécution, par un circuit cryptographique, d'un algorithme appliqué à un scalaire afin de générer un vecteur de sortie, de longueur l+n, dont les éléments sont , l'algorithme comprenant des itérations i, chaque itération i prenant une valeur de donnée d'entrée, initialement égale audit scalaire et un vecteur d'entrée de longueur c, dont les éléments sont , où pour chaque l'élément est tel que , où m est un entier positif et chaque itération i comprend : a) le calcul d'une première valeur de donnée intermédiaire par une première opération appliquée, modulo , à la première donnée d'entrée et au vecteur d'entrée, où est un nombre complexe ; b) la mise à jour de la valeur de la première valeur de donnée d'entrée par une deuxième opération appliquée à la première valeur de donnée d'entrée, au vecteur d'entrée, à la première valeur de donnée intermédiaire et à ; et c) la mise à jour de l'élément à la position i modulo m du vecteur de sortie égal à la première valeur de donnée intermédiaire, dans lequel le nombre total d'itérations est déterminé par le circuit cryptographique sur la base d'un critère d'arrêt. Selon un mode de réalisation, chaque itération comprend en outre : d) la mise à jour de i à i+1 ; et e) lorsque , la réinitialisation de à . Selon un mode de réalisation, le premier entier l est supérieur au deuxième entier m, le procédé comprenant en outre, après l'exécution de l'étape e) de l'itération l-1, l'application d'une fonction aux c-1 éléments du vecteur de sortie à la position j, où j appartient à , ainsi qu'avec la première valeur de donnée d'entrée, et la mise à jour de ces éléments du vecteur de sortie, ainsi que de la première valeur de données d'entrée, par ceux résultant de l'application de la fonction, la fonction étant telle que : une quantité égale à demeure la même avant et après la mise à jour des éléments par la fonction ; et les éléments mis à jour à satisfassent un prédicat C, le prédicat C dépendant d'une représentation en base . Selon un mode de réalisation, le procédé cryptographique comprend l'établissement des n derniers coordonnées du vecteur de sortie à une représentation en base de la première valeur de donnée d'entrée de la dernière itération. Selon un mode de réalisation, les coordonnées du vecteur de sortie correspondent à des éléments du scalaire sous une forme -adique réduite. Selon un mode de réalisation, la longueur de la conversion -adique réduite du scalaire ne dépend pas de la valeur dudit scalaire. Selon un mode de réalisation, le critère d'arrêt est que la première valeur de donnée d'entrée est suffisamment basse pour qu'elle puisse être représentée par n éléments en base . Selon un mode de réalisation, le résultat de la première opération est un reste, pas nécessairement minimal, d'une division euclidienne de la somme de la première valeur de donnée d'entrée et du premier élément du vecteur d'entrée par le nombre complexe. Selon un mode de réalisation, l'entier m est défini conformément à une courbe de Koblitz définie par un ensemble de points ayant la forme suivante : où est égal à 0 ou 1 et est un champ fini de cardinalité . Selon un mode de réalisation, le procédé cryptographique comprend la multiplication scalaire d'une donnée correspondant à un point P appartenant à la courbe de Koblitz par le scalaire. Selon un mode de réalisation, le nombre complexe est égal à , où est égal à . Selon un mode de réalisation, le scalaire est une clef cryptographique stockée dans une mémoire d'un dispositif électronique. Selon un mode de réalisation, l'entier l est égal à m et le vecteur de sortie est constitué d'un nombre de m+n coordonnées et, avant l'exécution des étapes a) à c) de la première itération i=0, chaque coordonnée est égal à 0. Selon un mode de réalisation, le premier entier l est supérieur au deuxième entier m et, avant l'exécution des étapes a) à c) de la première itération i=0, les l premiers éléments du vecteur de sortie sont les éléments d'un multiple de sous une forme –adique. Selon un mode de réalisation, avant l'exécution des étapes a) à c) de la première itération i=0, les l premiers éléments (d 0 ,…,d l+n-1 ) du vecteur de sortie sont fixés de sorte que : - l'élément à la position j, où j est compris entre 0 et l-m-1, soit l'opposé de l'élément à la position m+j ; et - chaque élément à la position j, où j est compris entre l-m et m-1, soit égal à 0. Un mode de réalisation prévoit une mémoire non transitoire stockant des instructions destinées à la mise en œuvre du procédé cryptographique, lorsque ces instructions sont exécutées par un circuit cryptographique. Un mode de réalisation prévoit un dispositif électronique comprenant un circuit cryptographique configuré pour mettre en œuvre le procédé cryptographique. Ces caractéristiques et avantages, ainsi que d'autres, seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non limitatif en relation avec les figures jointes parmi lesquelles : la représente schématiquement un exemple d'un dispositif électronique selon un mode de réalisation de la présente description ; la est un organigramme représentant des opérations d'un procédé de mise en œuvre d'une conversion scalaire selon un mode de réalisation ; la représente un exemple d'un état initial d'une valeur à l éléments utilisée dans le procédé de la ; la est un organigramme représentant des opérations d'un procédé de mise en œuvre d'une conversion scalaire selon un autre mode de réalisation ; la représente un exemple d'un état initial d'une valeur à l éléments utilisée dans le procédé de la ; et la est un organigramme représentant un exemple d'un procédé cryptographique selon un mode de réalisation de la présente description. Procédé cryptographique comprenant : - l'exécution, par un circuit cryptographique (104), d'un algorithme appliqué à un scalaire (k) afin de générer un vecteur de sortie, de longueur l+n, dont les éléments sont , l'algorithme comprenant des itérations i, chaque itération i prenant une valeur de donnée d'entrée ( ), initialement égale audit scalaire et un vecteur d'entrée de longueur c, dont les éléments sont , où pour chaque l'élément est tel que , où m est un entier positif et chaque itération i comprend : a) le calcul d'une première valeur de donnée intermédiaire (u) par une première opération appliquée, modulo , à la première donnée d'entrée ( ) et au vecteur d'entrée, où est un nombre complexe ; b) la mise à jour de la valeur de la première valeur de donnée d'entrée ( ) par une deuxième opération appliquée à la première valeur de donnée d'entrée, au vecteur d'entrée, à la première valeur de donnée intermédiaire (u) et à ; et c) la mise à jour de l'élément ( ) à la position i modulo m du vecteur de sortie égal à la première valeur de donnée intermédiaire (u), dans lequel le nombre total d'itérations est déterminé par le circuit cryptographique sur la base d'un critère d'arrêt. Procédé cryptographique selon la revendication 1, dans lequel chaque itération comprend en outre : d) la mise à jour de i à i+1 ; et e) lorsque , la réinitialisation de à . Procédé cryptographique selon la revendication 2, dans lequel le premier entier l est supérieur au deuxième entier m, le procédé comprenant en outre, après l'exécution de l'étape e) de l'itération l-1, l'application d'une fonction (CORRECT) aux c-1 éléments du vecteur de sortie (d0, … dl+n-1) à la position j, où j appartient à , ainsi qu'avec la première valeur de donnée d'entrée ( ), et la mise à jour de ces éléments du vecteur de sortie, ainsi que de la première valeur de données d'entrée ( ), par ceux résultants de l'application de la fonction, la fonction étant telle que : - une quantité égale à demeure la même avant et après la mise à jour des éléments par la fonction ; et - les éléments mis à jour à satisfassent un prédicat C, le prédicat C dépendant d'une représentation en base . Procédé cryptographique selon l'une quelconque des revendications 1 à 3, comprenant l'établissement des n derniers coordonnées du vecteur de sortie à une représentation en base de la première valeur de donnée d'entrée ( ) de la dernière itération. Procédé cryptographique selon l'une quelconque des revendications 1 à 4, dans lequel les coordonnées du vecteur de sortie ( ) correspondent aux éléments du scalaire (k) sous une forme -adique réduite. Procédé cryptographique selon la revendication 5, dans lequel la longueur de la conversion -adique réduite du scalaire (k) ne dépend pas de la valeur dudit scalaire. Procédé cryptographique selon l'une quelconque des revendications 1 à 6, dans lequel le critère d'arrêt est que la première valeur de donnée d'entrée est suffisamment basse pour qu'elle puisse être représentée par n éléments en base . Procédé cryptographique selon l'une quelconque des revendications 1 à 7, dans lequel le résultat de la première opération est un reste, pas nécessairement minimal, d'une division euclidienne de la somme de la première valeur de donnée d'entrée ( ) et du premier élément du vecteur d'entrée (d’ i ) par le nombre complexe ( ). Procédé cryptographique selon l'une quelconque des revendications 1 à 8, dans lequel l'entier m est défini conformément à une courbe de Koblitz définie par un ensemble de points ayant la forme suivante : où est égal à 0 ou 1 et est un champ fini de cardinalité . Procédé cryptographique selon la revendication 9, comprenant la multiplication scalaire d'une donnée correspondant à un point P appartenant à la courbe de Koblitz (E) par le scalaire (k). Procédé cryptographique selon la revendication 9 ou 10, dans lequel le nombre complexe est égal à , où est égal à . Procédé cryptographique selon l'une quelconque des revendications 1 à 11, dans lequel le scalaire (k) est une clef cryptographique stockée dans une mémoire d'un dispositif électronique. Procédé cryptographique selon l'une quelconque des revendications 1 à 12, dans lequel l'entier l est égal à m et dans lequel le vecteur de sortie est constitué d'un nombre de m+n coordonnées et, avant l'exécution des étapes a) à c) de la première itération i=0, chaque coordonnée est égal à 0. Procédé cryptographique selon l'une quelconque des revendications 1 à 12, dans lequel le premier entier l est supérieur au deuxième entier m et dans lequel, avant l'exécution des étapes a) à c) de la première itération i=0, les l premiers éléments du vecteur de sortie (d 0 ,…,d l+n-1 ) sont les éléments d'un multiple de sous une forme –adique. Procédé cryptographique selon la revendication 14, dans lequel, avant l'exécution des étapes a) à c) de la première itération i=0, les l premiers éléments du vecteur de sortie (d 0 ,…,d l+n-1 ) sont fixés de sorte que : - l'élément à la position j, où j est compris entre 0 et l-m-1, soit l'opposé de l'élément à la position m+j ; et - chaque élément à la position j, où j est compris entre l-m et m-l, soit égal à 0. Mémoire non transitoire stockant des instructions destinées à mettre en œuvre le procédé cryptographique selon l'une quelconque des revendications 1 à 15, lorsque ces instructions sont exécutées par un circuit cryptographique. Dispositif électronique comprenant un circuit cryptographique configuré pour mettre en œuvre le procédé cryptographique selon l'une quelconque des revendications 1 à 15.