Chiffrement asymétrique : RSA et PKI

Le chiffrement symétrique achoppe sur un problème qu’il ne peut résoudre par lui-même : les deux parties doivent partager une clé secrète, or comment la convoyer sûrement sans disposer déjà d’un canal sûr ? La cryptographie asymétrique dénoue ce cercle. À chaque entité on associe désormais un couple de clés : une clé publique $k_{pub}$, que l’on diffuse sans réserve pour chiffrer, et une clé privée $k_{priv}$, jalousement gardée pour déchiffrer. La première ne permet pas de retrouver la seconde — toute la sécurité tient dans cette dissymétrie.

Fonctions à sens unique à trappe

Le procédé repose sur une classe de fonctions particulières : faciles à calculer dans un sens, difficiles à inverser sans un secret, mais faciles à inverser dès qu’on le détient. Ce secret, c’est la trappe.

Définition

Une fonction à sens unique à trappe est une fonction $f$ aisée à évaluer, dont l’inversion est calculatoirement infaisable sans une information privilégiée — la trappe —, et redevient aisée avec celle-ci.

Ainsi le chiffrement ${\mathrm{Enc}}_{k_{pub}}(m)$ est-il efficace pour quiconque, mais le déchiffrement supposé infaisable pour qui ne possède pas $k_{priv}$. C’est cette clé privée qui joue le rôle de trappe.

Les prérequis arithmétiques

RSA ne se comprend qu’armé de quelques résultats d’arithmétique modulaire, que je rappelle sans les démontrer.

La division euclidienne garantit, pour $a,b\in \mathbb{N}$ avec $b\ne 0$, une écriture unique $a=bq+r$ avec $0\le r<b$. Le théorème de Bézout assure l’existence de $(u,v)\in {\mathbb{Z}}^2$ tels que $au+bv=\gcd (a,b)$ ; c’est lui qui, appliqué à l’algorithme d’Euclide étendu, fournit l’inverse modulaire dont RSA a besoin. Deux entiers sont congrus modulo $n$, noté $a\equiv b(\mathrm{mod}n)$, lorsque $n$ divise $a-b$ ; la congruence est compatible avec l’addition et la multiplication, et $a$ admet un inverse modulo $n$ dès que $\gcd (a,n)=1$.

Enfin, deux résultats sont au cœur de la justification de RSA. Le petit théorème de Fermat énonce que $a^{p-1}\equiv 1(\mathrm{mod}p)$ pour $p$ premier ne divisant pas $a$. Et pour $n=pq$ produit de deux premiers distincts, l’indicatrice d’Euler vaut $\phi (n)=(p-1)(q-1)$, avec $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ dès que $\gcd (a,n)=1$.

RSA

RSA tire sa sécurité de la difficulté de factoriser un grand entier — retrouver $p$ et $q$ à partir de leur seul produit $n$.

Génération des clés

On choisit deux grands premiers distincts $p$ et $q$, puis l’on calcule $n=pq$ et $\phi (n)=(p-1)(q-1)$. On élit ensuite un exposant public $e$ tel que $1<e<\phi (n)$ et $\gcd (e,\phi (n))=1$, et l’on en déduit l’exposant privé $d$ vérifiant

$ed\equiv 1(\mathrm{mod}\phi (n)).$

La clé publique est le couple $(e,n)$, la clé privée l’exposant $d$ (ou $(d,n)$). C’est ici que $\phi (n)$ fait office de trappe : sans connaître $p$ et $q$, on ne sait pas le calculer, donc pas remonter à $d$.

Chiffrer et déchiffrer

Pour un clair $m<n$, on chiffre et déchiffre par exponentiation modulaire :

$c=m^e\mathrm{mod}n,m=c^d\mathrm{mod}n,$

l’exactitude découlant de $m^{ed}\equiv m(\mathrm{mod}n)$, conséquence directe du théorème d’Euler.

L’exponentiation modulaire rapide

Calculer $m^e\mathrm{mod}n$ naïvement — par $e$ multiplications successives — est hors de portée pour les exposants en jeu. On recourt à l’exponentiation rapide (dite par carrés) : en décomposant $e$ en base 2 et en n’effectuant que des mises au carré et des multiplications modulo $n$, la complexité devient logarithmique en $e$. Quelques dizaines d’opérations remplacent alors des milliers.

RSA en pratique

RSA reste bien plus lent qu’un chiffrement symétrique. On ne l’emploie donc presque jamais pour chiffrer les données elles-mêmes, mais pour transporter une clé symétrique : c’est le principe du chiffrement hybride, RSA scellant la clé, AES chiffrant le trafic.

sequenceDiagram
    Alice->>Bob: Clé AES chiffrée avec RSA (k_pub de Bob)
    Bob->>Bob: Déchiffrement avec k_priv
    Alice->>Bob: Données chiffrées avec AES

Fragilités

RSA « brut » (textbook RSA) ne doit jamais être déployé tel quel. Il devient vulnérable dès que $p$ et $q$ sont trop proches, que l’exposant $e$ est trop petit, ou en l’absence de bourrage sécurisé ; une implémentation naïve ouvre par ailleurs la porte aux attaques par canaux auxiliaires. On l’assortit donc systématiquement d’un schéma de padding (OAEP pour le chiffrement, PSS pour la signature).

Signature et intégrité

En inversant les rôles de $e$ et $d$, RSA fournit un mécanisme de signature. Le signataire calcule $\sigma =m^d\mathrm{mod}n$ avec sa clé privée ; quiconque possède la clé publique vérifie en calculant ${\sigma }^e\mathrm{mod}n$ et en le comparant à $m$.

Signer directement le message est toutefois périlleux. La bonne pratique est le Hash-and-Sign : on ne signe que l’empreinte $H(m)$ produite par une fonction de hachage, soit $\sigma ={\mathrm{Sign}}_{k_{priv}}(H(m))$. On se prémunit ainsi contre la malléabilité et les attaques algébriques exploitant la structure multiplicative de RSA.

Signature contre MAC

Signature numérique et code d’authentification de message assurent tous deux l’intégrité et l’authenticité, mais dans des modèles de confiance opposés.

MAC	Signature
clé secrète partagée	paire clé publique / privée
pas de non-répudiation	non-répudiation
symétrique	asymétrique
les deux parties peuvent forger	seul le signataire peut produire

La non-répudiation est la propriété propre à la signature : puisque seul le détenteur de la clé privée a pu produire $\sigma$, il ne peut nier l’avoir fait.

Distribuer les clés publiques : la PKI

Reste une question que l’asymétrie ne résout pas d’elle-même : à qui appartient réellement une clé publique donnée ? Sans réponse, l’attaque de l’homme du milieu guette — l’adversaire substitue sa propre clé et intercepte tout.

La réponse tient dans les certificats et l’infrastructure qui les gère.

Définition

Un certificat numérique lie une identité à une clé publique. Il est signé par une autorité de confiance, borné dans le temps et révocable.

Deux modèles de confiance coexistent : le modèle hiérarchique (X.509), où la confiance descend d’autorités racines, et la toile de confiance (OpenPGP), où elle se tisse entre pairs. Un certificat X.509 contient l’identité du sujet, sa clé publique, une période de validité, les usages autorisés, et la signature de l’autorité de certification (AC).

L’AC vérifie les identités, signe les certificats et propage ainsi la confiance — laquelle est transitive : je fais confiance à un certificat parce que je fais confiance à l’AC qui l’a signé. C’est aussi la faille structurelle du modèle, puisque la compromission d’une AC racine compromet tout ce qu’elle a validé.

Définition

Une PKI (Public Key Infrastructure) est l’ensemble organisationnel et technique qui gère le cycle de vie des certificats : création, publication, validation, révocation.

Elle articule plusieurs organes : l’autorité de certification (AC), l’autorité d’enregistrement (AE) qui instruit les demandes, le service de publication (SP), le service de validation (SV), et — plus contestable — un éventuel service de séquestre des clés, dont la seule existence affaiblit la confidentialité.

Un certificat se valide en remontant une chaîne de certification jusqu’à une AC racine de confiance :

flowchart TB
    Root[AC Racine]
    AC1[AC Intermédiaire]
    User[Certificat utilisateur]
    Root --> AC1
    AC1 --> User

et son émission suit le circuit organisationnel de la PKI :

sequenceDiagram
    Alice->>AE: Demande de certificat
    AE->>AC: Identité validée
    AC->>AC: Signature du certificat
    AC->>SP: Publication
    SP->>Alice: Certificat disponible