Brevet FR3030085A1 — publié le 20160617

La présente invention concerne un procédé pour la mise en oeuvre du hash qui consiste à effectuer Xd mod N, l'exponentiation par un nombre d secret, modulo N donné, d'un nombre X dont on veut obtenir l'empreinte stockée dans la base « MICROSOFT » SAM, procédé destiné à protéger le mot de passe d'une session « WINDOWS », procédé selon lequel l'exponentiation est réalisée à partir de la formule : k0 mn=E Pm, i*Bi ,n t=0 avec k0 petit, de l'ordre de la dizaine. Les Pi,j sont les binomiaux et les Bi,j sont les coefficients de la matrice B, obtenue par la formule matricielle : Puis = P.B avec P la matrice du triangle de Pascal et Puis la matrice des puissances entières rangées en colonne, Puisi,j = La présente invention concerne également un dispositif mettant en oeuvre un tel procédé. Le système de chiffrement RSA est le crypto-système à clé publique le plus utilisé et le plus éprouvé dans le monde pour protéger des données confidentielles ou pour l'authentification. L'idée sous-jacente de cette invention est de faire intervenir le cryptosystème RSA comme outil de- hachage. Effectivement l'innovation réside dans le fait d'utiliser le procédé et les dispositifs d'application de la signature RSA optimisée, où l'exponentiation est réalisée par la formule ci-dessus, pour le hachage d'une donnée que l'on veut protéger par le stockage de son empreinte. Le cas le plus parlant est celui de la protection du code confidentiel qui permet d'ouvrir une session « WINDOWS » d'un utilisateur définissant au préalable un mot de passe associé à son identifiant. Cette donnée sensible est stockée dans la base de registres, dans le SAM, dans une forme brouillée que l'on appel l'empreinte ou le hash. Le hachage est aussi utilisé dans l'indexation de fichier. Le hachage dans le cadre de notre invention permet de protéger des données sensibles stockées, définitivement illisibles. Le hachage permet de sécuriser une donnée en appliquant un procédé qui transforme cette donnée en une autre donnée illisible que l'on peut stocker en toute sécurité, dans la base de registres « MICROSOFT » par exemple. Pour un mot de passe il existe une et une seule empreinte. Si un utilisateur essaie de rentrer un autre mot de passe, pour ouvrir la session « WINDOWS » protégée, dans ce cas le système génère une empreinte correspondante et il compare cette donnée transformée et le hash du véritable mot de passe. Comme l'empreinte stockée est unique, si le mot de passe inséré dans la zone de saisie est différent du mot de passe définie par l'utilisateur qui veut protéger son compte alors les deux empreintes seront différentes et le code entré sera rejeté, ce qui entraîne un dénie d'accès. Ainsi juste les données illisibles sont comparées et non les codes saisis. De plus le mot de passe n'est pas stocké en clair, la sécurité de la session appartenant à son propriétaire est garantie. Cependant dans 3030085 2 certain cas, très peu probables, il est possible d'avoir pour une même empreinte deux antécédents différents. On parle alors de collision. Même si le hachage est un système fiable pour sécuriser les mots de passe en les stockant brouillés pour éviter qu'ils soit facilement récupérés, il existe des failles. 5 Le hachage le plus répandu et l'un des plus fiables est le système SHA. La version la plus pertinente est le SHA-2 dont une déclinaison est le SHA 512. Il est utilisé par exemple pour l'authentification de mails. Cependant une étude sur ce système de hachage montre qu'il présente des failles trop importantes. Elles sont exposées dans l'article New collision attacks 10 against up to 24-step SHA-2. Un autre système de hachage de référence est le SHA-3 réalisé par la fonction Keccak. Mais celui-ci présente aussi des faiblesses, présentées dans la publication Pratical complexity cube attacks on round-reduced keccak sponge function . Il est donc nécessaire de trouver un dispositif plus fiable pour le hachage. 15 La présente invention a l'avantage de ne pas être sensible aux attaques par collision contrairement au système de sécurité à clés privées et aux procédés de hachage présentés ci-dessus. De plus on utilise une signature RSA optimisée. Dans ce cadre la signature correspond à l'empreinte. Ici l'idée est d'utiliser le procédé d'authentification le plus avancé dans l'état de l'art pour créer une empreinte de la donnée sensible, inversement à l'utilisation du hachage 20 SHA-2 pour l'authentification. Aussi, en plus d'être immunisé contre les attaques par collisions, on bénéficie des avantages de ce procédé de signature RSA. Dans le hachage, la fonction inverse n'existe pas. Donc e l'exposant public n'est pas délivré dans les hypothèses. Cela a pour conséquences de se placer hors de la relaxe présentée dans 25 le livre the LLL-Algorithms de Phong Nguyen. Ainsi la signature RSA-CRT avec petits exposants, dp, dq petits, et procédés rattachés sont plus fiables et non vulnérables aux attaques par la LLL-réduction multivariables. En effet pour appliquer la cryptanalyse des signatures RSA optimisées par l'algorithme LLL, l'exposant public e doit être connu. 30 L'objectif de la présente invention est de proposer un procédé et un dispositif de hachage pour sécuriser le mot de passe d'une session « WINDOWS » sécurisée. Dans le cadre général elle sert à obtenir une empreinte d'une donnée sensible, par la signature RSA, la plus avancée dans l'état de l'art. Le principal avantage réside dans le fait que le procédé et le dispositif sont immunisés contre les attaques par collision à partir du moment où on utilise un cryptosystème à 35 clé public et non un système à clés privés comme le 3-DES ou un système de hachage courant comme le SHA-512. Un atout de cette invention réside dans le haut niveau de performance du RSA optimisé. Il est possible d'atteindre des vitesses 30 fois plus importantes que le RSA 3030085 3 classique. La performance en terme de nombre de multiplications modulaires du procédé ne dépend pas de la taille de la clé, qu'elle soit de 512, 1024, 2048, 4096. Selon l'invention, on propose un procédé d'obtention de l'empreinte qui correspond à I' 5 opération qui est l'exponentiation par d, l'exposant privé, modulo N comportant les étapes suivantes : Déterminer au préalable les éléments de la clé privée: - Choisir p et q premiers assez grands, de longueur supérieure à 512 bits par exemple. 10 - Calculer N=p*q. - Calculer la matrice B modulo N, où B est définie par l'égalité matricielle Puis=P*B avec P matrice des binomiaux et Puis matrice des puissances entières rangées par colonnes Pi,j=i'. Conjecturer par observation sur les colonnes de B des coefficients en nombre 15 limité. Récupérer l'indice dO d'une des colonnes dont les coefficients sont nuls à partir d'un certain rang petit kO, de l'ordre de la dizaine. - Trouver un d, représentant l'exposant privé, supérieur à dO de tel sorte que l'écart Delta entre dO et d soit petit, de l'ordre de la dizaine et tel que d respecte 20 le standard PKCS#1. - Mémoriser les coefficients de la matrice B présents dans les colonnes d'indices dO ou d. La clé privée est représentée par les coefficients 131,d° avec i REVENDICATIONS1. Dispositif permettant le calcul de l'exponentiation Xd mod N pour le hachage, ledit dispositif ayant pour objectif l'amélioration de la sécurité des données sensibles à hacher et de leur protection face aux attaques par collision, caractérisé en ce qu'il comporte: a. un module d'entrée 10 apte à récupérer les coefficients et les termes, correspondant à la clé privée : N, B2d0 Bko_id°, Delta où N=p*q avec p,q nombres premiers choisis aléatoirement. les ai sont les coefficients de la matrice B calculée à partir de la relation matricielle : Puis=P.B avec P matrice des binomiaux et Puis matrice des puissances entières rangées par colonnes, P =P. dO est l'indice colonne pour lequel les sont nuls à partir de k0 avec k0 petit, de l'ordre de la dizaine, et Delta = d - dO où d est l'exposant privé choisi de tel sorte que d soit premier et que l'écart Delta soit petit, de l'ordre de la dizaine et tel que d respecte le standard PKCS#1. Ils sont préalablement calculés par une machine extérieure. b. un module d'entrée 11 permettant de récupérer X le mot de passe à hacher. c . une zone mémoire 20 permettant de stocker les coefficients et les autres éléments de la clé privée. d. une zone mémoire 21 permettant de stocker X. e. une unité de calcul 3 apte à calculer Y=Xd mod N selon l'opération suivante: y=0( + c2 *B2d0 cx3*B3d0 cxk0-1*Bk01n*XDelta mod N où les C sont les binomiaux. f . un module de sortie 4 apte à fournir l'empreinte Y. 2. Dispositif permettant le calcul de l'exponentiation Xd mod N pour le hachage, ledit dispositif ayant pour objectif l'amélioration de la sécurité de données sensibles à hacher et de leur protection face aux attaques par collision, caractérisé en ce qu'il comporte: a . un module d'entrée 10 apte à récupérer les coefficients et les termes, correspondant à la clé privée : N, B2d Bko+Deita-id où N=p*q avec p,q nombres premiers choisis aléatoirement, d=dO+Delta avec dO l'indice colonne pour lequel les B sont nuls à partir de k0 avec k0 petit, de l'ordre de la dizaine, et Delta est rajouté à l'indice dO pour avoir d premier, respectant le standard PKCS#1. Delta est de l'ordre de la dizaine. les 13,' sont les coefficients de la matrice B calculée à partir de la relation matricielle : Puis=P.B avec P matrice 3030085 9 des binomiaux et Puis matrice des puissances entières rangées par colonnes, P Ils sont préalablement calculés par une machine extérieure. b. un module d'entrée 11 permettant de récupérer X le mot de passe à hacher. c . une zone mémoire 20 permettant de stocker les coefficients et les autres 5 éléments de la clé privée. d. une zone mémoire 21 permettant de stocker X. e . une unité de calcul 3 apte à calculer Y=Xd mod N selon l'opération suivante: Y=X + Cx2 *B2d + C2*B3d +...+ CxkO+Delta-1*BkO+Delta-1d mod N où les Cil sont les binomiaux. 10 f . un module de sortie 4 apte à fournir l'empreinte Y.