next up previous
Next: Correction d'erreurs de transmission: Up: Arithmétique et exemples d'applications. Previous: Polynomes


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:

$\displaystyle (a^c)^d = a$    mod $\displaystyle 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:


next up previous
Next: Correction d'erreurs de transmission: Up: Arithmétique et exemples d'applications. Previous: Polynomes
2001-01-19