algorithme RSA

L'algorithme RSA est à la base d'un système de cryptographie -- une suite d'algorithmes cryptographiques utilisés pour des services ou des objectifs de sécurité spécifiques -- qui permet le cryptage à clé publique et est largement utilisé pour sécuriser des données sensibles, notamment lorsqu'elles sont envoyées sur un réseau non sécurisé comme l'internet.

La RSA a été décrite publiquement pour la première fois en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman du Massachusetts Institute of Technology, bien que la création en 1973 d'un algorithme à clé publique par le mathématicien britannique Clifford Cocks ait été gardée secrète par le GCHQ du Royaume-Uni jusqu'en 1997.

La cryptographie à clé publique, également connue sous le nom de cryptographie asymétrique, utilise deux clés différentes mais mathématiquement liées : une clé publique et une clé privée. La clé publique peut être partagée avec tout le monde, tandis que la clé privée doit être gardée secrète.

Dans la cryptographie RSA, les clés publique et privée peuvent toutes deux chiffrer un message ; la clé opposée à celle utilisée pour chiffrer un message est utilisée pour le déchiffrer. Cet attribut est l'une des raisons pour lesquelles la RSA est devenue l'algorithme asymétrique le plus utilisé : Il fournit une méthode pour assurer la confidentialité, l'intégrité, l'authenticité et la non-répudiation des communications électroniques et du stockage des données.

De nombreux protocoles tels que Secure Shell, OpenPGP, S/MIME et SSL/TLS s'appuient sur le RSA pour les fonctions de cryptage et de signature numérique. Il est également utilisé dans les logiciels -- les navigateurs en sont un exemple évident, car ils doivent établir une connexion sécurisée sur un réseau non sécurisé, comme l'internet, ou valider une signature numérique. La vérification de la signature RSA est l'une des opérations les plus couramment effectuées dans les systèmes connectés au réseau.

Pourquoi l'algorithme RSA est-il utilisé ?

La RSA tire sa sécurité de la difficulté à factoriser de grands nombres entiers qui sont le produit de deux grands nombres premiers. La multiplication de ces deux nombres est facile, mais la détermination des nombres premiers originaux à partir du total - ou factorisation - est considérée comme impossible en raison du temps qu'il faudrait pour utiliser les superordinateurs actuels

. L'algorithme de génération de clés publiques et privées est la partie la plus complexe de la cryptographie RSA. Deux grands nombres premiers, p et q, sont générés à l'aide de l'algorithme de test de primalité de Rabin-Miller. Un module, n, est calculé en multipliant p et q. Ce nombre est utilisé à la fois par les clés publiques et privées et assure le lien entre elles. Sa longueur, généralement exprimée en bits, est appelée longueur de la clé.

La clé publique se compose du module n et d'un exposant public, e, qui est normalement fixé à 65537, car il s'agit d'un nombre premier qui n'est pas trop grand. Le chiffre e ne doit pas nécessairement être un nombre premier choisi secrètement, car la clé publique est partagée avec tout le monde. La clé privée se compose du module n et de l'exposant privé d, qui est calculé à l'aide de l'algorithme euclidien étendu pour trouver l'inverse multiplicatif par rapport au quotient de n.

 

Comment fonctionne l'algorithme RSA ?

Claire génère ses clés RSA en sélectionnant deux nombres premiers : p=11 et q=13. Le module est n=p×q=143. Le totient est n ϕ(n)=(p-1)x(q-1)=120. Elle choisit 7 pour sa clé publique RSA e et calcule sa clé privée RSA en utilisant l'algorithme euclidien étendu, qui lui donne 103. Paul veut envoyer à Claire un message crypté, M, il obtient donc sa clé publique RSA (n, e) qui, dans cet exemple, est (143, 7). Son message en texte clair ne contient que le chiffre 9 et est crypté en texte chiffré, C, comme suit : Me mod n = 97 mod 143 = 48 = C Lorsque Claire reçoit le message de Paul, elle le décrypte en utilisant sa clé privée RSA (d, n) comme suit : Cd mod n = 48103 mod 143 = 9 = M Pour utiliser les clés RSA pour signer numériquement un message, Claire devrait créer un hachage (un condensé de son message à Paul), chiffrer la valeur du hachage avec sa clé privée RSA et ajouter la clé au message. Paul peut alors vérifier que le message a été envoyé par Claire et n'a pas été altéré en décryptant la valeur de hachage avec sa clé publique. Si cette valeur correspond au hachage du message original, alors seule Claire a pu l'envoyer -- authentification et non-répudiation -- et le message est exactement comme elle l'a écrit -- intégrité. Claire pourrait, bien sûr, chiffrer son message avec la clé publique RSA de Paul - confidentialité - avant de l'envoyer à Paul. Un certificat numérique contient des informations qui identifient le propriétaire du certificat et contient également la clé publique du propriétaire. Les certificats sont signés par l'autorité de certification qui les émet et peuvent simplifier le processus d'obtention des clés publiques et de vérification du propriétaire.

Sécurité RSA

La sécurité de la RSA repose sur la difficulté de calculer la factorisation de grands nombres entiers. À mesure que la puissance de calcul augmente et que des algorithmes de factorisation plus efficaces sont découverts, la capacité à factoriser des nombres de plus en plus grands augmente également.

La puissance de cryptage est directement liée à la taille de la clé, et le fait de doubler la longueur de la clé peut entraîner une augmentation exponentielle de la puissance, bien que cela nuise aux performances. Les clés RSA ont généralement une longueur de 1024 ou 2048 bits, mais les experts estiment que les clés de 1024 bits ne sont plus totalement sûres contre toutes les attaques. C'est pourquoi le gouvernement et certains secteurs industriels adoptent une longueur de clé minimale de 2048 bits.

À moins d'une percée imprévue dans le domaine de l'informatique quantique, il faudra de nombreuses années avant que des clés plus longues soient nécessaires, mais la cryptographie à courbe elliptique (ECC) gagne la faveur de nombreux experts en sécurité comme alternative à la RSA pour mettre en œuvre la cryptographie à clé publique. Elle permet de créer des clés cryptographiques plus rapides, plus petites et plus efficaces.

Le matériel et les logiciels modernes sont prêts pour l'ECC, et sa popularité est susceptible de croître, car il peut offrir une sécurité équivalente avec une puissance de calcul et une utilisation des ressources de la batterie plus faibles, ce qui le rend plus adapté aux applications mobiles que la RSA. Enfin, une équipe de chercheurs, dont fait partie Adi Shamir, co-inventeur de la RSA, a réussi à créer une clé RSA de 4096 bits en utilisant la cryptanalyse acoustique ; cependant, tout algorithme de cryptage est vulnérable aux attaques