Le code RSA ( de MM Ron Rivest, Adi Shamir et Len Adleman) vient d'un petit théorème, qu'on aurait découvrir bien plus tôt, à la suite de Fermat et Euler :
Théorème du RSA : soit p et q deux nombres premiers. On pose n=pq. Si e est un entier premier avec (p-1)(q-1), alors il existe un entier d>0, tel que ed=1 (mod(p-1)(q-1)) ; pour cet entier d et un entier a premier avec n, on a a^ed =a (mod n)
J'écris a^ed pour dire : a à la puissance ed. Et a^ed= a (mod n) pour dire que le reste de la division de a^ed par n est a : on dit "modulo n".
Alors comment ça marche?
- M Destinataire choisit un quaduplet p, q, e, d comme dans l'énoncé, et calcule n = pq. Il efface ensuite p et q, ou les cache dans son coffre-fort.
- M Destinataire rend public n et e. Il peut les envoyer à qui les lui demande.
- M Expéditeur, qui veut chiffrer un message pour M Destinataire, transforme son texte en suite de nombres A inférieurs à N, et calcule B=A^e (mod n), et l'envoie à M Destinataire. Tout le monde peut pirater, ou voir passer le nombre B.
-M Destinataire, pour décoder B, calcule B^d (mod n), ce qui lui donne A, car B^d=A^ed=A mod(n).
- les pirates (ou le gouvernement) ne peuvent décrypter B que s'ils arrivent à décomposer n en ses 2 composants p et q, ce qui est très difficile.
En effet, on prend des clés, telles que n fait par exemple 1024 bits, soit 309 chiffres décimaux, et on choisit un nombre e assez grand. Un jour, quelqu'un arrivera à casser un code, et bien on change les clés souvent, on rallonge la longueur de la clé. Ça fait 20 ans que ça marche, et ça semble tenir la route.
Prenons un exemple. Trouvons nos p, q, e, d. Pourquoi pas p= 47 et q= 71 (nombres premiers). Je calcule n = 47.71 = 3337 et (p-1).(q-1)= 46.70= 3220. Essayons e=79, et je vérifie par l'algorithme d'Euclide qu'il est premier avec 3220. Ce qui donne d= 1019, tel que ed=80501=25.3220+1 =1 (mod 3220). J'envoie les nombres 3337 et 79 à mon copain.
Il coupe son message en morceaux plus petits que 3337 : par blocs de 3 chiffres, ça va.
Soit A = 688. Il le crypte en calculant 688^79 (mod 3337), ce qui est assez facile pour un ordinateur: B=1570.
Je reçois 1570, le met à la puissance 1019 (mod 3337), et je trouve 688, CQFD.
Un pirate trouverait facilement, dans ce cas que 3337 = 47.71, mais si je vous dis que n = 2^256 + 1, vous aurez du mal à trouver que c'est le produit de 59 649 589 127 497 217 par 5 704 689 200 685 129 054 721.
NB : prenez du paracétamol plutôt que de l'aspirine!
PS : Merci à Jean-Paul Delahaye, "Merveilleux nombres premiers", Belin ed.
4 commentaires:
Je n'ai appris qu'une seule chose en vieillissant:on peut vivre sans les mathématiques . Ce fut une révélation extraordinaire!
Derrière l'inconnu, il y a la peur !
Ca date du temps des cavernes.Ceux qui savaient foutre la trouille aux autres arrivaient à les garder enfermés dans les grottes et gerer leur rôle de guerrier et de fournisseur d'alimentation, de fourrures, de rêves....en allant chasser à l'extérieur renforçant ainsi leur pouvoir sur les masses des trouillards.C'est l'origine des dessins et les peintures à l'intérieur des grottes: montrer un monde extérieur dangereux, remplis d'animaux plus gras,plus méchants et plus rapides les uns que les autres et nécessitant donc des êtres extraordinaires pour les chasser.
Les outils du pouvoir n'ont pas changé : faire peur et jouer les gros bras, les parrains et les pourvoyeurs pour assurer les masses de leur généreuse assistance.
Mais il y a toujours eu de plus futés pour aller voir par eux-même si tout celà était bien tel qu'on le disait d'où l'évolution du language.
Merci François de venir confirmer cette hypothèse !
Je reconnais bien là l'inégalité de Schwartz!
Mais st Augustin l'a dit : "seules les mathématiques permettent d'approcher le divin".
RSA: revenu de soladirité active???
M'aurait-on menti, moi qui touche les prestations sociales et ne paye pas d'impôt?
Enregistrer un commentaire