RSA et la cryptographie à clé publique
Partie 3 sur 4
6Pourquoi on ne sait pas le casser
Tout ce que l’attaquant voit est public : le module n, l’exposant e, et le message chiffré c. Pour lire le message, la voie directe est de retrouver d. Cela revient à connaître φ(n), donc p et q, donc à factoriser n. On pense, sans l’avoir démontré, que casser RSA est aussi difficile que factoriser (il n’y a pas de preuve qu’une autre voie, plus facile, n’existe pas).
6.1Les records de factorisation
Pour mesurer ce qui est « difficile », on regarde les records, que les chercheurs établissent en public. Le défi lancé par la société RSA a vu tomber des nombres de plus en plus gros : 129 chiffres (426 bits) en 1994, 768 bits en 2009, et 829 bits (250 chiffres) en 2020, après des milliers d’années de calcul d’un seul processeur réparties sur de nombreuses machines. Aucun nombre de 1 024 bits n’a été publiquement factorisé à ce jour, et ceux de 2 048 bits sont très loin du possible. Chaque doublement de la taille multiplie l’effort bien plus que par deux : la difficulté croît plus vite que la taille.
6.2Quelle taille de clé choisir ?
La taille d’une clé RSA est celle du module n, en bits. Voici les repères à retenir :
- 512 bits et moins : cassable en quelques heures avec de la puissance de calcul louée. Interdit depuis longtemps.
- 1 024 bits : retiré des usages sérieux par les autorités depuis les années 2010.
- 2 048 bits : le minimum actuel, accepté pour les usages courants jusqu’à environ 2030.
- 3 072 bits : le choix prudent pour des données ou des signatures qui doivent durer ; c’est la valeur que l’ANSSI (l’agence nationale française de la sécurité des systèmes d’information) recommande pour les systèmes qui devront résister après 2030.
Ces chiffres sont revus régulièrement dans des guides publiés par l’ANSSI en France, par le NIST (l’institut de normalisation américain) aux États-Unis et par leurs équivalents européens. Vérifiez toujours leur version la plus récente avant de fixer une politique. Retenez cette règle d’ordre de grandeur : passer de 2 048 à 3 072 bits demande une fois et demie plus de bits, mais les opérations qui emploient la clé privée (déchiffrer, signer) deviennent environ trois fois plus lentes.
7RSA en pratique : bourrage et chiffrement hybride
Ce qui précède est le « RSA des manuels », parfois appelé RSA brut. Il a deux défauts graves. Il est déterministe : le même message donne toujours le même résultat chiffré, si bien qu’un curieux peut deviner un message court (« oui » ou « non ») en chiffrant lui-même les possibilités avec la clé publique, qui est publique. Et il est malléable : quelqu’un peut modifier un message chiffré d’une manière qui modifie le message déchiffré de façon prévisible.
7.1Le bourrage
La parade s’appelle le bourrage (padding en anglais) : avant de chiffrer, on mélange au message des octets aléatoires et des marqueurs, selon un format précis défini par une norme. Le format moderne s’appelle OAEP (Optimal Asymmetric Encryption Padding, soit « bourrage asymétrique optimal »). Il garantit que deux chiffrements du même message donnent deux résultats différents, et qu’un message modifié est rejeté au déchiffrement. Les normes qui le décrivent s’appellent PKCS#1 (publiées sous forme de RFC, les documents de référence de l’Internet). Un ancien format, appelé « PKCS#1 v1.5 », est encore répandu mais a été attaqué plusieurs fois, notamment en 1998 par Daniel Bleichenbacher, puis par ses successeurs ; on l’abandonne dès que possible.
Le bourrage a un prix : il occupe de la place. Pour une clé de 2 048 bits (256 octets), OAEP avec un condensat de 32 octets laisse environ 190 octets pour le message. Cela montre à quel point RSA est fait pour de petites données.
7.2Le chiffrement hybride
RSA est aussi lent : à taille égale, il est des centaines à des milliers de fois plus lent qu’un algorithme symétrique comme AES (Advanced Encryption Standard, la norme de chiffrement symétrique la plus utilisée au monde, adoptée en 2001). On combine donc les deux, ce qui s’appelle le chiffrement hybride (figure 3) :
- l’expéditeur tire au hasard une petite clé de session (par exemple 32 octets) ;
- il chiffre le fichier avec cette clé de session, par un algorithme symétrique rapide ;
- il chiffre la clé de session avec la clé publique du destinataire, par RSA avec bourrage ;
- il envoie les deux éléments ;
- le destinataire retrouve la clé de session avec sa clé privée, puis déchiffre le fichier.
C’est la méthode de la messagerie chiffrée (voir le courrier chiffré), de nombreux formats de fichiers et, longtemps, des connexions sécurisées du web. Dans le protocole TLS qui protège aujourd’hui les sites web (TLS), RSA ne sert plus à transporter la clé de session depuis la version 1.3, publiée en 2018 : on lui préfère un échange de clés qui garantit la confidentialité persistante (même si la clé privée d’un serveur fuite un jour, les conversations passées restent illisibles). RSA y sert surtout à signer, pour prouver l’identité du serveur.
7.3Quelques usages concrets
- Connexion à distance par SSH (Secure Shell, une connexion à un ordinateur distant protégée par chiffrement) : une paire de clés peut remplacer le mot de passe ; la clé publique est déposée sur le serveur, la clé privée reste sur votre poste.
- Certificats : une autorité signe la clé publique d’un site (voir les certificats).
- Signature de logiciels et de courriers : voir la signature électronique.
- Cartes à puce : carte bancaire, carte d’identité électronique, qui gardent la clé privée dans la puce et ne la laissent jamais sortir.
Pour s’exercer
Exercice 4 : combien de blocs pour un fichier d’un mégaoctet ?
Une clé RSA de 2 048 bits avec OAEP laisse environ 190 octets utiles par bloc. Combien de blocs faudrait-il pour chiffrer un fichier de 1 000 000 d’octets, et pourquoi n’est-ce pas une bonne idée ?
Voir la réponse
1 000 000 / 190 ≈ 5 263,2, soit 5 264 blocs, chacun nécessitant un calcul de grande puissance sur des nombres de 2 048 bits. Ce serait très lent et produirait un fichier plus gros que l’original (chaque bloc donne 256 octets en sortie). On chiffre le fichier avec un algorithme symétrique rapide (AES) et on ne chiffre avec RSA que la petite clé de session : un seul calcul RSA suffit.
Exercice 5 : RSA brut et message court
Un site chiffre des réponses « oui » ou « non » avec RSA brut, sans bourrage. Quelle faiblesse cela crée-t-il, et quelle parade ?
Voir la réponse
RSA brut est déterministe : « oui » donne toujours le même résultat chiffré, « non » aussi. Comme la clé publique est connue de tous, un curieux chiffre lui-même les deux mots, compare avec ce qu’il voit passer, et lit la réponse sans rien casser. La parade est le bourrage aléatoire (OAEP), qui rend chaque chiffrement différent, même pour un même message.