Cryptographie: exemple de la méthode RSA

On se donne 2 nombres premiers $p$ et $q$, on pose $n=pq$, donc $\varphi (n)=(p-1)(q-1)$. Soit $c$ un entier premier avec $\varphi (n)$ et $d$ son inverse modulo $\varphi (n)$. Alors, pour tout entier $a$ premier avec $n$, on a:

$$(a^c)^d = a$$    mod $$n$$

Cette égalité est le principe de base des codages à clefs publiques (RSA et les logiciels qui l'utilisent comme Pretty Good Privacy, Gnu Privacy Guard, ssh, etc.). L'entier $n$ est connu de tout le monde mais $p$ et $q$ ne le sont pas (si $n$ est suffisament grand la factorisation de $n$ est infaisable en un temps raisonnable), ou ce qui revient au meme $\varphi (n)$ est inconnu. Il est donc impossible de déduire $d$ de $c$, $c$ est appelé clef publique de Mr X et $d$ clef secrète de Mr X. Le codage d'un entier $a$ à destination de Mr X uniquement se fait en envoyant $a^c$ mod $n$. Seul Mr X peut décoder $a$ car lui seul connait $d$. Mr X peut s'authentifier (signer un message par exemple) en envoyant $a^d$ mod $n$, chacun pourra décoder la signature $a$ en utilisant la clef publique $c$. Pour crypter un message complet, on commence par transformer ce message en suite d'entiers (premiers avec $n$).
Essayez de crypter/décrypter un message de cette manière: prenez 2 nombres premiers, faites en le produit $n$, calculer $\varphi (n)$, choisissez une clef publique $c$, déduisez en la clef secrète associée, etc.

Remarques:

• L'algorithme RSA est rentré dans le domaine public début septembre 2000 aux États-Unis (contrairement à l'Europe pour l'instant, les États-Unis autorisent le brevetage de ce type d'algorithmes).
• actuellement on est capable de factoriser des nombres jusqu'à environ $n=10^{128}$ (soit environ 400 bits). Les systèmes à clef publique permettent donc la confidentialité pour des clefs de 512 bits ou plus. La législation française autorise les clefs de 40 bits actuellement, un décret devrait faire passer cette limite à 128 bits très bientot avant une libéralisation plus complète promise par le premier ministre en janvier 99.
• le cryptage public avec de grandes clefs peut nécessiter un temps de calcul trop long, certains logiciels ne l'utilisent que pour crypter un échange de clef de systèmes de cryptographie classique (la cryptographie a clef non publique assurant une confidentialité avec des clefs de taille plus faible ou des algorithmes plus rapides, par exemple 128 bits).