Brevet FR3125189A1 — publié le 20230113

Un procédé de génération d’un élément (p) d’une clé cryptographique comprend l’application d’itérations successives, jusqu’à ce qu’au moins le plus grand dénominateur commun de la différence entre une variable (Y) et 1, et d’un exposant public (e) égale 1, où : - chaque itération comprend la détermination de restes modulaires (ri) associés chacun à un nombre premier (pi) d’une base de nombres premiers (pi), lesdits restes modulaires (ri) étant égaux respectivement au reste de la variable (Y) modulo ledit nombre premier (pi), - l’élément (p) généré est la valeur de la variable (Y) lors de la dernière itération. - le procédé comprend, antérieurement aux itérations successives, la détermination des nombres premiers de la base facteurs de l’exposant public (e), - le procédé contourne, lorsque, lors d’une desdites itérations, au moins un des restes modulaires (rk) associés auxdits nombres premiers déterminés égale 1, le calcul dudit plus grand dénominateur commun. Figure pour l’abrégé : Fig.2 Procédé de generation d’un element d’une cle cryptographique, procéde de traitement cryptographique, dispositif de traitement cryptographique et programme d’ordinateur associés Domaine technique de l'invention La présente invention concerne de manière générale le domaine du traitement cryptographique utilisant l’arithmétique modulaire. Elle concerne plus particulièrement un procédé de génération d’un élément d’une clé cryptographique, un procédé de traitement cryptographique, un dispositif de traitement cryptographique et un programme d’ordinateur associés. Etat de la technique Certains protocoles de cryptographie (en particulier de cryptographie asymétrique), tels que le protocole RSA, utilisent les principes de l’arithmétique modulaire. La génération de clés cryptographiques, présentant des éléments publics et privés, est nécessaire préalablement au chiffrement de messages. Les éléments privés doivent être choisis calculatoirement impossibles à retrouver à partir des éléments publics. Des algorithmes de génération de clés RSA peuvent être trouvés par exemple dans « Information Technology Laboratory National Institute of Standards and technology. Digital Signature Standard (DSS). Technical Report », in FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION, July 2013. Parmi les algorithmes du document ci-dessus, concernant la génération des éléments privés, l’un consiste à énumérer des nombres candidats en incrémentant un nombre initial jusqu’à obtenir un résultat satisfaisant des conditions avec l’un des éléments publics de la clé cryptographique à générer, dit exposant public. Lors de l’évaluation de chaque nombre candidat, des calculs de plus grands dénominateurs communs sont effectués, qui impactent les performances de la génération de clés. Il est connu d’effectuer une opération de tamisage visant à éliminer lors de l’énumération certains nombres candidats par l’utilisation d’une base de nombres premiers. Cependant, malgré cette opération, demeurent la difficulté et le volume de calculs sollicités lors de la génération des éléments privés, en particulier la vérification que le plus grand dénominateur commun de la différence entre le nombre candidat et 1 et de l’exposant public est égal à 1. Présentation de l'invention Dans ce contexte, la présente invention propose un procédé de génération d’un élément d’une clé cryptographique, la clé cryptographique comprenant également un exposant public, dans lequel : le procédé comprend l’application d’itérations successives, jusqu’à ce qu’au moins le plus grand dénominateur commun de la différence entre une variable et 1, et de l’exposant public soit égal à 1, dans lequel chaque itération comprend la détermination d’une pluralité de restes modulaires associés chacun à un nombre premier d’une base d’une pluralité de nombres premiers pi, lesdits restes modulaires étant égaux respectivement au reste de la variable modulo le nombre premier associé, et l’élément généré est la valeur de la variable lors de la dernière itération, caractérisé en ce que le procédé comprend, antérieurement aux itérations successives, la détermination des nombres premiers de la base facteurs de l’exposant public, et en ce que le procédé contourne une étape de calcul du plus grand dénominateur commun de la différence entre la variable et 1, et de l’exposant public lorsque, lors d’une desdites itérations, au moins un parmi la pluralité de restes modulaires associés auxdits nombres premiers déterminés est égal à 1. Autrement dit, lorsque, lors d’une desdites itérations, au moins un parmi la pluralité de restes modulaires associés auxdits nombres premiers déterminés est égal à 1, l’étape de calcul du plus grand dénominateur commun n’est pas mise œuvre pour cette itération. Le procédé de génération selon l’invention permet ainsi de diminuer le nombre de calculs de plus grand dénominateur commun effectués. Ainsi grâce à l’invention, le procédé de génération d’un ou plusieurs éléments d’une clé cryptographique présente un volume de calculs et donc un temps de calcul réduits. Lorsque, lors d’une desdites itérations, aucun parmi la pluralité des restes modulaires associés auxdits nombres premiers déterminés n’est égal à 1, l’itération comprend en revanche la mise en œuvre du calcul du plus grand dénominateur commun de la différence entre la variable et 1, et de l’exposant public. D’autres caractéristiques avantageuses et non limitatives du procédé conforme à l’invention, prises individuellement ou selon toutes les combinaisons techniquement possibles, sont les suivantes : - l’élément de la clé cryptographique est généré et égal à la valeur de la variable correspondant à la dernière itération si la valeur de la variable est un nombre premier, - les nombres premiers de la base sont référencés chacun par un indice et les indices des nombres premiers déterminés sont mémorisés dans un ensemble, - le procédé comprend en outre, antérieurement aux itérations successives, la détermination d’un nombre résiduel égal à 1 si l’ensemble des facteurs premiers de l’exposant public correspondent aux nombres premiers déterminés, ou, sinon, égal à un facteur de l’exposant public qui est premier avec chacun des nombres premiers de l’ensemble, - lorsque le nombre résiduel est égal à un facteur de l’exposant public et est premier avec chacun des nombres premiers de l’ensemble et que le nombre résiduel est inférieur à une borne supérieure, le nombre résiduel est ajouté à la base, - lorsque le nombre résiduel est premier, le procédé comprend une étape d’affectation de la valeur 1 au nombre résiduel, - lors d’une desdites itérations, lorsque tous les restes modulaires associés aux nombres premiers facteurs de l’exposant public dans la base sont différents de 1 et lorsque le nombre résiduel est égal à 1, le procédé contourne un calcul du plus grand dénominateur commun de la différence entre la variable et 1, et de l’exposant public, - la détermination des nombres premiers facteurs de l’exposant public dans la base consiste au calcul de réductions modulaires de l’exposant public modulo pour chaque nombre premier de la base et à la comparaison du reste desdites réductions modulaires avec 0, - la variable est mise à jour à chaque itération, - à chaque itération, la variable est incrémentée d’un incrément, - lors de certaines au moins desdites itérations, la détermination d’une pluralité de restes modulaires consiste en l’affectation, au reste modulaire courant, de la somme du reste modulaire courant et du reste de l’incrément par le nombre premier associé, - le procédé comprend, antérieurement aux itérations successives, une étape d’initialisation de la variable à une valeur aléatoire. - le procédé est un procédé de génération d’un premier élément et d’un second élément d’une clé cryptographique. L’invention propose également un procédé de traitement cryptographique comprenant un procédé de génération d’un élément d’une clé cryptographique tel que défini précédemment. Le procédé de traitement cryptographique selon l’invention peut comprendre une étape d’application, à des données, d’un algorithme cryptographique utilisant l’élément généré ou les éléments générés. L’invention propose également un programme d’ordinateur comprenant des instructions exécutables par un processeur et adaptées pour la mise en œuvre d’un procédé de génération ou de traitement cryptographique tel que défini précédemment, lorsque ces instructions sont exécutées par le processeur. L’invention propose aussi un dispositif de traitement cryptographique, comprenant une unité de génération d’un élément d’une clé cryptographique comprenant également un exposant public, dans lequel : - l’unité de génération est conçue pour appliquer des itérations successives, de manière à ce qu’au moins le plus grand dénominateur commun de la différence entre une variable et 1 et de l’exposant public soit égal à 1, - l’unité de génération est également conçue pour activer, à chaque itération, un bloc de détermination d’une pluralité de restes modulaires associés chacun à un nombre premier d’une base d’une pluralité de nombre premiers, de telle sorte que lesdits restes modulaires sont égaux respectivement au reste de la variable modulo le nombre premier associé, - l’unité de génération est aussi conçue pour générer la valeur de la variable correspondant à la dernière itération en tant que l’élément à générer, - l’unité de génération comprend un bloc de calcul du plus grand dénominateur commun de la différence entre la variable et 1 et de l’exposant public, le dispositif étant caractérisé en ce que l’unité de génération est conçue pour activer, antérieurement auxdites itérations successives, un bloc de détermination des nombres premiers facteurs de l’exposant public dans la base, et en ce que l’unité est conçue pour désactiver le bloc de calcul du plus grand dénominateur commun lors de chaque itération, où un parmi la pluralité de restes modulaires associés aux nombres premiers déterminés est égal à 1. Ce dispositif de traitement cryptographique peut être configuré pour la mise en œuvre de chacune des possibilités de réalisation envisagées pour le procédé de génération ou de traitement cryptographique tel que défini précédemment. Bien entendu, les différentes caractéristiques, variantes et formes de réalisation de l'invention peuvent être associées les unes avec les autres selon diverses combinaisons dans la mesure où elles ne sont pas incompatibles ou exclusives les unes des autres. Procédé de génération d’un élément (p) d’une clé cryptographique, ladite clé cryptographique comprenant également un exposant public (e), dans lequel : le procédé comprend l’application d’itérations successives, jusqu’à ce qu’au moins le plus grand dénominateur commun de la différence entre une variable (Y) et 1, et de l’exposant public (e) soit égal à 1, dans lequel chaque itération comprend la détermination d’une pluralité de restes modulaires (r i ) associés chacun à un nombre premier (p i ) d’une base (B) d’une pluralité de nombres premiers (p i ), lesdits restes modulaires (r i ) étant égaux respectivement au reste de la variable (Y) modulo ledit nombre premier (p i ) associé, et dans lequel l’élément (p) généré est la valeur de la variable (Y) lors de la dernière itération, caractérisé en ce que : le procédé comprend, antérieurement aux itérations successives, la détermination des nombres premiers (p k ) de la base (B) facteurs de l’exposant public (e), et en ce que le procédé contourne une étape de calcul du plus grand dénominateur commun de la différence entre la variable (Y) et 1, et de l’exposant public (e) lorsque, lors d’une desdites itérations, au moins un parmi la pluralité de restes modulaires (r k ) associés auxdits nombres premiers (p k ) déterminés est égal à 1. Procédé de génération selon la revendication 1, dans lequel l’élément (p) est généré et égal à la valeur de la variable (Y) correspondant à la dernière itération si ladite valeur de la variable (Y) est un nombre premier. Procédé de génération selon la revendication 1 ou 2, dans lequel les nombres premiers (p i ) de la base (B) sont référencés par un indice (i) et dans lequel les indices (k) des nombres premiers (p k ) déterminés sont mémorisés dans un ensemble (B K ). Procédé de génération selon l’une des revendications 1 à 3, comprenant, en outre, antérieurement aux itérations successives, la détermination d’un nombre résiduel (t) égal à 1 si l’ensemble des facteurs premiers de l’exposant public (e) correspondent aux nombres premiers déterminés (p k ), ou, sinon, égal à un facteur de l’exposant public (e) qui est premier avec chacun des nombres premiers (p k ) de l’ensemble (B K ). Procédé de génération selon la revendication 4, caractérisé en ce que, lorsque le nombre résiduel (t) est égal à un facteur de l’exposant public (e) et est premier avec chacun des nombres premiers (p k ) de l’ensemble (B K ) et que le nombre résiduel (t) est inférieur à une borne supérieure (B T ), le nombre résiduel (t) est ajouté à la base (B). Procédé de génération selon la revendication 5, dans lequel, lorsque le nombre résiduel (t) est premier, le procédé comprend une étape d’affectation de la valeur 1 au nombre résiduel (t). Procédé de génération selon la revendication 4 ou 6, dans lequel, lors d’une desdites itérations, lorsque tous les restes modulaires (r k ) associés aux nombres premiers (p k ) facteurs de l’exposant public (e) dans la base (B) sont différents de 1 et lorsque le nombre résiduel (t) est égal à 1, le procédé contourne un calcul du plus grand dénominateur commun de la différence entre la variable (Y) et 1, et de l’exposant public (e). Procédé de génération selon l’une des revendications 1 à 7, caractérisé en ce que la détermination des nombres premiers (p k ) facteurs de l’exposant public (e) dans la base (B) consiste au calcul de réductions modulaires de l’exposant public (e) modulo (p i ) pour chaque nombre premier (p i ) de la base (B) et à la comparaison du reste desdites réductions modulaires avec 0. Procédé de génération selon l’une des revendications 1 à 8, dans lequel la variable (Y) est mise à jour à chaque itération. Procédé de génération selon la revendication 9, dans lequel : - à chaque itération, la variable (Y) est incrémentée d’un incrément (dY), - lors de certaines au moins desdites itérations, la détermination d’une pluralité de restes modulaires (r i ) consiste en l’affectation, au reste modulaire courant (r i ), de la somme du reste modulaire courant (r i ) et du reste de l’incrément (dY) par ledit nombre premier (p i ) associé. Procédé de génération d’un premier élément (p) et d’un second élément (q) d’une clé cryptographique comprenant un exposant public (e), dans lequel le premier élément (p) est généré selon un procédé de génération selon l’une des revendications 1 à 10, et le second élément (q) est généré selon un procédé de génération selon l’une des revendications 1 à 10. Procédé de traitement cryptographique comprenant un procédé de génération d’un élément (p) d’une clé cryptographique, selon l’une des revendications 1 à 10. Procédé de traitement cryptographique selon la revendication 12, comprenant une étape d’application, à des données, d’un algorithme cryptographique utilisant l’élément (p) généré. Programme d’ordinateur comprenant des instructions exécutables par un processeur et adaptées pour la mise en œuvre d’un procédé selon l’une des revendications 1 à 13, lorsque ces instructions sont exécutées par le processeur. Dispositif de traitement cryptographique, comprenant une unité de génération d’un élément (p) d’une clé cryptographique, ladite clé cryptographique comprenant également un exposant public (e), ladite unité de génération étant conçue pour appliquer des itérations successives, de manière à ce qu’au moins le plus grand dénominateur commun de la différence entre une variable (Y) et 1 et de l’exposant public (e) soit égal à 1, dans lequel ladite unité est conçue pour activer, à chaque itération, un bloc de détermination d’une pluralité de restes modulaires (r i ) associés chacun à un nombre premier (p i ) d’une base (B) d’une pluralité de nombre premiers (p i ), de telle sorte que lesdits restes modulaires (r i ) sont égaux respectivement au reste de la variable (Y) modulo ledit nombre premier (p i ) associé, dans lequel ladite unité est conçue pour générer la valeur de la variable (Y) correspondant à la dernière itération en tant que l’élément (p), dans lequel ladite unité comprend un bloc de calcul du plus grand dénominateur commun de la différence entre la variable (Y) et 1 et de l’exposant public (e), caractérisé en ce que ladite unité est conçue pour activer, antérieurement auxdites itérations successives, un bloc de détermination des nombres premiers (p k ) facteurs de l’exposant public (e) dans la base (B), et en ce que la dite unité est conçue pour désactiver ledit bloc de calcul du plus grand dénominateur commun, lors de chaque itération où un parmi la pluralité de restes modulaires (r k ) associés auxdits nombres premiers (p k ) déterminés est égal à 1.