RSA Unidirectionnel et Bidirectionnel

Chiffrement RSA

Fonctionnement

Le chiffrement RSA[W6] est asymétrique : il utilise une paire de clés (des nombres entiers) composée d’une clé publique pour chiffrer et d’une clé privée pour déchiffrer des données confidentielles. Les deux clés sont crées par une personne, souvent nommée par convention Alice, qui souhaite que lui soient envoyées des données confidentielles. Alice rend la clé publique accessible. Cette clé est utilisée par ses correspondants (Bob, etc.) pour chiffrer les données qui lui sont envoyées. La clé privée est quant à elle réservée à Alice, et lui permet de déchiffrer ces données. La clé privée peut aussi être utilisée par Alice pour signer une donnée qu’elle envoie, la clé publique permettant à n’importe lequel de ses correspondants de vérifier la signature.
Une condition indispensable est qu’il soit « impossible par calcul » de déchiffrer à l’aide de clé publique, en particulier de reconstituer la clé privée à partir de la clé publique, c’est-à-dire que les moyens de calcul disponibles et les méthodes connues au moment de l’échange (et le temps que le secretdoit être conservé) ne le permettent pas.
Le chiffrement RSA est souvent utilisé pour communiquer une clé de chiffrement symétrique, qui permet alors de poursuivre l’échange de façon confidentielle : Bob envoie à Alice une clé de chiffrement symétrique qui peut ensuite être utilisée par Alice et Bob pour échanger des données.

Principe du chiffrement

Il est basé sur le calcul exponentiel[W5]. Sa sécurité repose sur la fonction unidirectionnelle suivante : le calcul du produit de 2 nombres premiers est aisé. La factorisation d’un nombre en ses deux facteurs premiers est beaucoup plus complexe. Il s’agit du système le plus connu et le plus largement répandu, basé sur l’élévation à une puissance dans un champ fini sur des nombres entiers modulo un nombre premier. Il emploie de grands nombres entiers (par exemple représentés sur 1024 bits). Ce cryptosystème utilise deux clés d et e, interchangeables. Le chiffrement se fait selon.

Signature RSA

Le cryptosystème[5] à clé publique RSA fournit un schéma de signature numérique cryptographiquement sécurisé (signe + vérifier), basé sur les mathématiques des exponentiations modulaires et des logarithmes discrets et sur la difficulté du problème de factorisation d’entiers (IFP). Le processus de signature / vérification RSA fonctionne comme suit :
• L’algorithme de signe RSA calcule un hachage de message, puis chiffre le hachage avec l’exposant de clé privée pour obtenir la signature. La signature obtenue est un nombre entier (le hachage du message chiffré RSA).
• L’algorithme de vérification RSA calcule d’abord le hachage du message, puis déchiffre la signature du message avec l’exposant de clé publique et compare le hachage déchiffré obtenu avec le hachage du message signé pour s’assurer que la signature est valide.
Les signatures RSA sont déterministes (le même message + la même clé privée produisent la même signature). Une variante non déterministe des signatures RSA est facile à concevoir en complétant le message d’entrée avec quelques octets aléatoires avant de signer. Les signatures RSA sont largement utilisées dans la cryptographie moderne, par ex. pour signer des certificats numériques, pour protéger les sites Web. Par exemple (à partir de novembre 2018), le site Web officiel de Microsoft utilise Sha256RSA pour son certificat numérique. Néanmoins, la tendance au cours de la dernière décennie est de passer de RSA et DSA à des signatures basées sur des courbes elliptiques (comme ECDSA et EdDSA). Les cryptographes et développeurs modernes préfèrent les signatures ECC pour leur longueur de clé plus courte, leur signature plus courte, une sécurité plus élevée (pour la même longueur de clé) et de meilleures performances.

Efficacité et robustesse de RSA

Grâce aux algorithmes[5] tel-que : El Gamal, Menezes-Vanstonne, McEliece et Chor-Rivest, il est facile de générer des grands nombres premiers, tout au moins en acceptant un taux d’erreur dans le cas de RSA, l’erreur n’est pas trop grave. En effet, si l’on commet une erreur en croyant que p et q sont premiers, le destinataire se rendra rapidement compte que les nombres ne sont pas premiers : soit la clef d n’est pas inversible, soit certains blocs du message décrypté sont incompréhensibles. Dans ce cas, on peut procéder à un changement de système RSA (recalcul de p et q). – Le calcul du couple (e, d) est extrêmement facile, il suffit d’appliquer l’algorithme d’Euclide étendu . – Enfin, le chiffrement et le déchiffrement sont réalisés par exponentiation modulaire. Nous avons vu que cette exponentiation pouvait être réalisée assez efficacement. La sécurité fournie par RSA repose essentiellement sur la difficulté à factoriser de grands entiers. En effet, si un attaquant peut factoriser le nombre n = p*q, de la clé publique, il peut alors déduire directement (p-1) *(q-1) et donc calculer la clé privée Kd à partir de la clé publique Ke par l’algorithme d’Euclide étendu. Donc, si l’on dispose d’un algorithme rapide pour factoriser de grands entiers, casser RSA devient facile aussi. Après 20 ans de recherche, aucun moyen plus efficace que la factorisation de n n’a été publié pour casser RSA. Cependant, la réciproque : « si factoriser de grands entiers est dur alors casser un message crypté par RSA est dur » n’a pas été prouvée. Autrement dit, on ne sait pas aujourd’hui si casser RSA est aussi difficile que factoriser n. On peut cependant montrer l’équivalence entre « déterminer d à partir de (n, e) » et « factoriser n ». Un sens est trivial : connaissant p et q, on peut facilement calculer d puisque c’est ce qui est fait dans le cadre de la génération de clé. Réciproquement, calculer p et q à partir de (n, e, d) peut être obtenu : – par un algorithme déterministe si e est petit – par un algorithme probabiliste (une variante de l’algorithme de MillerRabin) dans le cas général. La robustesse du RSA est basée sur la difficulté pratique de factoriser un grand nombre entier n (qui est le produit de deux grands nombres premiers p et q) dans un temps raisonnable. Il utilise généralement des clés de 1024 bits.

Sécurité de RSA

Comme indiqué[5] plus haut, la sécurité de RSA repose sur la difficulté que représente la factorisation de grands entiers. Cependant, à mesure que la puissance de traitement augmente et que des algorithmes de factorisation plus efficaces sont découverts, il devient possible de factoriser des nombres de plus en plus élevés. La puissance du chiffrement est directement liée à la taille de la clé. De ce fait, un doublement de la longueur de la clé renforce le chiffrement de façon exponentielle, au détriment toutefois des performances.
Les clés RSA font généralement 1024 ou 2048 bits, mais les experts pensent que les clés de 1024 bits pourraient être déchiffrées à brève échéance.
C’est la raison pour laquelle l’administration et le secteur privé commencent à adopter des clés d’une longueur minimale de 2048 bits. A moins d’une percée imprévue en informatique quantique, de nombreuses années devraient s’écouler avant que des clés plus longues soient nécessaires, mais la cryptographie à courbe elliptique (ECC, Elliptic Curve Cryptography) fait de plus en plus d’adeptes parmi les spécialistes de la sécurité pour mettre en oeuvre le chiffrement à clé publique en remplacement de RSA.
En effet, cette technologie permettra de créer des clés de chiffrement à la fois plus rapides, plus petites et plus efficaces. La plupart des matériels et logiciels actuels sont déjà compatibles ECC et la popularité de la discipline devrait encore augmenter, car elle offre une sécurité équivalente pour une puissance de traitement et une consommation d’énergie moindres, ce qui la rend plus adaptée que RSA aux applications mobiles. Enfin, une équipe de chercheurs parmi lesquels Adi Shamir, co-inventeur de RSA, a réussi à déchiffrer une clé RSA de 4096 bits en utilisant la cryptanalyse acoustique. Cependant, n’importe quel algorithme de chiffrement est vulnérable à ce type d’attaque.
Les inventeurs de l’algorithme RSA ont fondé RSA Data Security en 1983. La société a ensuite été acquise par Security Dynamics, à son tour rachetée par EMC Corporation en 2006. L’algorithme RSA a été diffusé dans le domaine public par RSA Security en 2000.

RSA Unidirectionnel

Système de cryptage unidirectionnel basée sur RSA Aujourd’hui, RSA[W2] est considéré comme le premier algorithme, publié scientifiquement, qui permet la transmission de données chiffrées sans échange de clé secrète.
Le chiffrement RSA utilise un algorithme basé sur la multiplication de grands nombres premiers. Bien qu’il n’y ait généralement pas de problème à multiplier deux nombres premiers par 100, 200 ou 300 chiffres, il n’y a toujours pas d’algorithme efficace capable de décomposer le résultat d’une telle opération de calcul en ses facteurs premiers dans l’étape inverse. La factorisation en nombres premiers peut être illustrée par l’exemple ci-dessous.
Si on multiplie les nombres premiers 14.629 et 30.491, on obtient le produit 446.052.839, qui n’a que quatre diviseurs : 1, lui-même et les deux nombres premiers qui ont été multipliés. Si on supprime les deux premiers diviseurs, puisque chaque nombre est divisible par 1 et par lui-même, on obtient les valeurs initiales 14.629 et 30.491.
Ce schéma est la base de la génération des clés RSA. Les clés publiques et privées représentent deux paires de nombres entiers :
Clé publique : (e, N)
Clé privée : (d, N)
N est le module RSA. Ceci est contenu dans les deux clés et les résultats du produit de deux nombres premiers très grands p et q (N = p x q) sélectionnés au hasard.
Pour générer la clé publique, on a besoin de e, qui est un nombre choisi au hasard avec certaines restrictions. Si on combine N et e, on obtient la clé publique accessible à chaque abonné de communication en texte clair.
Pour générer la clé privée N et d sont nécessaires. d est une valeur résultant des nombres premiers p et q générés aléatoirement ainsi que du nombre aléatoire e, qui sont calculés sur la base de la fonction phi d’Euler (φ).
Les nombres premiers inclus dans le calcul de la clé privée doivent être tenus secrets afin de garantir la sécurité du cryptage RSA. Le produit des deux nombres premiers, d’autre part, peut être utilisé en texte clair dans la clé publique, puisqu’il est supposé qu’il n’y a pas d’algorithme efficace aujourd’hui qui peut décomposer le produit de nombres premiers très grands en ses facteurs dans le temps pertinent. Il n’est donc pas possible de calculer p et q à partir de N. Sauf si nous pouvons raccourcir le calcul. Une telle trappe représente la valeur d, qui n’est connue que du propriétaire de la clé privée.
La sécurité de l’algorithme RSA dépend fortement du progrès technique.
La puissance de calcul des ordinateurs double tous les deux ans. Il n’est donc pas exclu qu’une méthode efficace de factorisation primaire soit disponible dans un avenir prévisible à l’échelle habituelle. Dans ce cas, RSA offre la possibilité d’adapter l’algorithme au développement technique en utilisant des nombres premiers encore plus grands pour calculer les clés.
Supposons que nous ayons le schéma de cryptage RSA E = (Enc-Gen, Enc, Dec). L’algorithme de génération de clé RSA produit la clé publique EK = (e,N) et la clé secrète SK = (d, N, φ(N)), où e ∗ d = 1 mod φ(N), N = pq, p,q sont deux grands nombres premiers et φ est la fonction Euler. Le cryptage est défini comme suit : EncEK(m) = me mod N = c. L’algorithme de décryptage est DecEK(c) = c d mod N = m. L’algorithme de génération de clé unidirectionnelle E’ = (UniGen, UniEnc, UniDec, PDec, FDec). Pour chaque utilisateur U, l’algorithme de génération de clés UniGen(1 k ) génère une paire de clés publiques (EK,DK) et divise la clé secrète en deux parties d1 et d2 telles que d = d1+d2 mod φ(N). Le mandataire P obtient DKP = d1 et l’utilisateur F obtient DKF = d2. La fonction de cryptage UniEnc et les algorithmes UniDec sont identiques aux algorithmes originaux Enc et Dec. La transformation des fonctions PDec et FDec exécutent le décryptage avec les clés d1 et d2 respectivement. La fonction d’exactitude du RSA unidirectionnel est donnée par l’égalité FDecd2(PDecd1(Ence(m))) = m.

Signature unidirectionnelle basée sur RSA

RSA-Hash unidirectionnel Régime de signature Supposons que[2] nous ayons S = (Sig-Gen, Sig, Ver) une signature standard RSA-Hash (Full Domain Hash). Sig-Gen génére la clé publique VK = (e,N) et la signature clé secrète SK = (d, N). La fonction de signature est définie comme Sig = hash(m) dmodN = s, où hash est une fonction de hachage associée à Sig.