Nicolas Maillard
On cherche à coder un document pour assurer sa confidentialité. On s'intéresse ici à l'un des codes dits ``à clé publique'' les plus employés pour l'instant : le code RSA (algorithme trouvé par Rivest, Shamir et Adlemann en 1978). Il repose sur le calcul modulaire.
L'algorithme est le suivant : le (futur) destinataire d'un message crypté part d'un nombre entier produit de deux (grands) nombres premiers n = pq. Il détermine ensuite deux nombres d et e vérifiant :
La clé de codage (qu'il rend publique à tout le monde) est alors le couple (n,e), et le codage d'un entier x est le nombre
Le décodage de y par le destinataire se fait à l'aide de la clé (connue de lui seul) (n,d). Il n'a qu'à calculer :
On montre ``facilement'' que z = x et que l'on retrouve donc le message
de départ (exemple : 
. 
. Or
donc on peut prendre ici d = e= 11. Si
on veut crypter l'entier x=2 il vient 
qui
est la valeur codée de 2. Pour décoder on calcule 
et on retrouve bien la valeur de x).
Le secret dans le code vient de la difficulté, étant donné un (grand) nombre entier n, d'en déduire une factorisation n=pq. La donnée de n et e ne permet donc pas avec les moyens actuels de trouver la clé d de décodage.
Le travail demandé est le suivant : implémenter une version parallèle de RSA pour crypter/décrypter un fichier de caractères. Quelques éléments de réflexion :