L'idée d'un système à clef publique est de trouver un algorithme difficilement inversible de telle sorte que tout le monde puisse coder, mais qu'il n'y ait qu'une personne qui puisse décoder. Par exemple Alice communiquera son adresse et la clef à utiliser ; la clef publique. Quand Bob voudra lui envoyer un message, il le codera avec cette clef publique et ainsi plus personne ne pourra lire le message sauf Alice , puisqu'elle est la seule à savoir inverser son algorithme, au moyen de sa clef secrète.
Voyons l'exemple du système " RSA " :

1. Historique :
   Le système de cryptographie RSA est considéré comme le code public le plus sûr. Cette méthode a été créée en 1977 par Rivest, Shamir et Adleman, d'où le nom de RSA. Il est utilisé dans le monde entier et sert aujourd'hui à des protections de toutes sortes notamment dans les cartes bancaires.
2. Théorie :
   Etude Préalable de l'expediteur :
   On choisit 2 nombres premiers p et q avec lesquels on calcule n = p*q puis phi(n)=(p-1)*(q-1) , ou f est la fonction d'Euler (c'est à dire le nombre d'entiers premiers avec n et plus petit que n). On cherche alors k tel que k < phi(n) et k premier avec phi(n), puis on calcule alpha tel que k*alpha = 1 mod [phi(n)]. Les nombres k et n sont publiés : Ce sera la clef publique. Par ailleurs, alpha sera la clef secrète d'Alice.
   Codage :
   Pour envoyer un message à Alice, Bob le transforme en nombre, puis un ensemble de nombres inférieurs à n, puis pour chacun de ces nombres m il calcule c = m^k mod [n] et il envoie les nombres c à Alice.
   Décodage :
   Pour décoder le message, Alice doit calculer c^alpha mod [n] et, grâce au petit théorème de Fermat, on montre qu'elle va retrouver m et, en le recomposant, le message initial.
   
   
3. Echange de clef :
   On peut utiliser cette méthode pour éviter le problème de la transmission préalable et se communiquer des clefs afin d'utiliser un codage symétrique, c'est à dire un système à clef privée.
   Soit n et k les clefs publiques d'Alice. Elle va choisir un nombre aléatoire x inférieur à n et calculer X= k^x mod [n] qu'elle enverra à Bob. De son coté, celui ci choisira son aléa y et élèvera X à la puissance y pour obtenir C. Par ailleurs il enverra Y= k^y mod [n] à Alice qui, en élevant ce nombre à la puissance x trouvera également C.
   Nos deux interlocuteurs se seront mis d'accord sur une clef C sans donner le moindre renseignement à un éventuel pirate. En effet celui-ci, placé entre les deux, n'aura pu avoir que n et k,qui sont publics, et X et Y, ce qui ne permet pas de trouver C ni de retrouver x ou y. Donc Alice et Bob pourront maintenant communiquer à l'aide d'un algorithme à clefs privée en utilisant la clef C.
4. Application :
   Sur Maple…
   
   Choix des nombres :
   > p:=389;q:=167;k:=17;n:=p*q;phi:=(p-1)*(q-1);
   p := 389
   q := 167
   k := 17
   n := 64963
   phi := 64408
   > (phi mod k)*[1,2,3,4,5,6,7,8] mod k;alpha:=(7*phi+1)/k;
   [12, 7, 2, 14, 9, 4, 16, 11]
   alpha := 26521
   Procédures de passage lettre/nombre :
   a <=> 1 : b <=> 2 : c <=> 3 : d <=> 4 ... ... ç <=> 113.
   Procédures RSA :
   Coder : c = m^k mod [n]. Décoder : c^alpha mod [n] = m.
   Exemples :
   > codersa(`Bonjour tout le monde! Voici une application du système de codage RSA.`,17,64963);
   éR8jõ-33/cCZXk=vDäc@ôFgqèPk¤#i^ù&:9ku"XP<n'¨"pAxXMçO+tëwJFKD[z;J*vãàëMa
   > decodersa(%,26521,64963);
   Bonjour tout le monde! Voici une application du système de codage RSA.
   Temps de codage : 4 secondes. Temps de décodage : 1 minute et 31 secondes.
   > codersa(`Plus les nombres sont grands, plus il sera difficile de "pirater" le message.`,26521,64963);
   uZ}*0[q9[JiPnYa!c6££_fez!éün_pjûb"et~)CL5ä[îèëTDYïxrhXµUA¤S1h!KDpL1îmâD9:e"
   > decodersa(%,17,64963);
   Plus les nombres sont grands, plus il sera difficile de "pirater" le message.
   (voir les documents Maple : liens en bas de la page)
   Effectuons une application numérique, avec des nombres de taille modeste : on choisit k et 2 nombres premiers p et q. On a les valeurs indiquées (p = 389, q = 167 et k = 17). Puis on calcule n et phi(n) (n = 64 963 et phi(n) = 64 408) et on résout une petite équation pour trouver un intermédiaire i. On trouve i= 7 ce qui nous donne alpha (alpha = 26 521).
   On utilise des procédures de passage lettre/nombre classiques : Ce sont de simples changements de base ; à chaque caractère on associe un nombre. Ici on travaille avec 114 caractères. On a entré des procédures de codage de type RSA dont on pourra détailler le fonctionnement plus tard, éventuellement.
   On a effectué ici une application. Et on peut remarquer que cela fonctionne également dans l'autre sens, c'est à dire que dans le cadre d'une signature : Alice peut prouver qu'elle est l'auteur d'un message en diffusant son message après l'avoir codé avec ses clefs, alpha et n. Ainsi tout le monde pourra décoder en utilisant les clefs publiques, k et n, et lire le message en étant sur que Alice en est l'auteur, puisqu'elle est la seule à connaître alpha.
   Mais cette méthode de calcul prend du temps à cause de l'élévation à des puissances élevées. Pour des applications plus sérieuses, on sera amené à introduire une procédure d'exponantiation modulaire bien plus rapide.
5. Exemple de piratage :
   Cassage pratique, sur Maple :
   
   Exemples :
   Pour casser le RSA, il suffit de factoriser "n".
   On avait n = 64 963 : la factorisation donne instantanément p et q : 389 et 167.
   > ifactor(3344643740003778401017000702389103);
   (52684000000012361) (63485000000056823)
   Temps de calcul : 2 minutes et 45 secondes (pour un nombre de 34 chiffres).
   Nombres premiers :
   > nextprime(12785496834578965847*10^180+12548968687535489658);
   1278549683457896584700000000000000000000000000000000000000000000\
   0000000000000000000000000000000000000000000000000000000000\
   0000000000000000000000000000000000000000000000000000000000\
   12548968687535490593
   Temps de calcul : 1 minute et 54 secondes (pour un nombre de 200 chiffres).
   (voir les documents Maple : liens en bas de la page)
   Pour de petits nombres, il est très facile de pirater un code RSA ... Il suffit de factoriser le nombre n comme ici (n = 64 963) ; on trouve p et q instantanément et on en déduit f, puis i, et enfin alpha et on peut finalement pirater.
   Mais la procédure de factorisation de Maple ne fonctionne aisément que pour des nombres inférieurs à 10^35. Par contre, il est relativement facile de trouver de grands nombres premiers, même sous Maple.
   La fiabilité du RSA repose sur l'écart entre la difficulté de factorisation et la facilité à trouver de grands nombres premiers.
   A propos de cassage, on peut citer le cassage du RSA-129 en 1994, ou encore des récents travaux de Serge Humpich.