{"id":473,"date":"2010-12-03T20:37:59","date_gmt":"2010-12-03T19:37:59","guid":{"rendered":"http:\/\/sciencetonnante.wordpress.com\/?p=473"},"modified":"2010-12-03T20:37:59","modified_gmt":"2010-12-03T19:37:59","slug":"protegez-vos-petits-secrets-grace-aux-nombres-premiers","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2010\/12\/03\/protegez-vos-petits-secrets-grace-aux-nombres-premiers\/","title":{"rendered":"Prot\u00e9gez vos petits secrets gr\u00e2ce aux nombres premiers"},"content":{"rendered":"

\"matrix_300\"<\/a>Imaginons que vous soyez le chef de la diplomatie de votre pays, et que vos ambassadeurs aient besoin de vous envoyer des messages top secrets. Afin d\u2019\u00e9chapper aux oreilles de l\u2019ennemi et de Wikileaks, vous allez avoir besoin de coder ces messages<\/strong>. Comment faire ?<\/p>\n

La cryptographie basique<\/h3>\n

Pour cela, vous pouvez choisir une m\u00e9thode simple, comme substituer une lettre par une autre dans l\u2019alphabet. C\u2019est le principe qu\u2019utilisait C\u00e9sar pour communiquer avec ses g\u00e9n\u00e9raux. Les messages \u00e9taient cod\u00e9s de la mani\u00e8re suivante\u00a0: chaque lettre est remplac\u00e9e par la lettre situ\u00e9e 3 cases plus loin dans l\u2019alphabet\u00a0: A devient D, B devient E, etc. En voici le principe en image pour coder le mot \u00ab\u00a0BONJOUR\u00a0\u00bb :
\n<\/a><\/p>\n

\"\"<\/a><\/p>\n

Les m\u00e9thodes de substitution simples sont malheureusement assez peu s\u00fbres car chaque lettre est toujours cod\u00e9e de la m\u00eame mani\u00e8re\u00a0: on peut donc casser ces codes en faisant de la statistique<\/strong> et en analysant les occurrences des lettres\u00a0: ainsi en fran\u00e7ais, le E est la lettre qui doit revenir le plus souvent, suivie des lettres AIST, qui bien s\u00fbr sont elles-m\u00eames bien plus fr\u00e9quentes que WXYZ.<\/p>\n

La cryptographie \u00e0 cl\u00e9<\/h3>\n

Pour \u00e9viter cela, il faut un codage dans lequel une m\u00eame lettre n\u2019est pas toujours cod\u00e9e de la m\u00eame mani\u00e8re. C\u2019est le principe des codes \u00e0 cl\u00e9<\/strong>. Imaginons que l\u2019on veuille encoder le mot \u00ab\u00a0BONJOUR\u00a0\u00bb et qu\u2019on choisisse comme cl\u00e9 de cryptage le mot \u00ab\u00a0DECO\u00a0\u00bb. On convertit chaque lettre du mot et de la cl\u00e9 en chiffre (A=1, B=2, \u2026,Z=26), on les additionne et on reconvertit les chiffres obtenus en lettre. Comme la cl\u00e9 est souvent un simple mot, on la r\u00e9p\u00e8te autant de fois que n\u00e9cessaire pour coder l\u2019ensemble du message. Pour d\u00e9coder, on fait la m\u00eame chose mais en soustrayant la cl\u00e9 au message cod\u00e9. En voici l\u2019illustration\u00a0:<\/p>\n

\"\"<\/a><\/p>\n

Et vous voyez ici que les deux lettres O du mot \u00ab\u00a0BONJOUR\u00a0\u00bb sont bien cod\u00e9es par une lettre diff\u00e9rente. On ne peut pas facilement casser ce code par des analyses statistiques.<\/p>\n

Toutefois le codage \u00e0 cl\u00e9 pose un autre probl\u00e8me car il s\u2019agit d\u2019un codage sym\u00e9trique\u00a0: si vous savez coder les messages, alors vous savez aussi automatiquement les d\u00e9coder<\/strong>. Donc si un espion parvient \u00e0 se procurer la cl\u00e9 que vous donnerez \u00e0 votre ambassadeur, alors l\u2019ennemi saura ensuite d\u00e9crypter les messages qu’il vous enverra !<\/p>\n

La cryptographie asym\u00e9trique<\/h3>\n

La solution pour s\u2019en sortir est d\u2019utiliser une m\u00e9thode de cryptographie asym\u00e9trique, c’est-\u00e0-dire o\u00f9 les proc\u00e9dures de codage et de d\u00e9codage sont tr\u00e8s diff\u00e9rentes<\/strong>, de sorte que quelqu\u2019un qui sache encoder les messages ne sache pas pour autant les d\u00e9coder. Comment est-ce possible\u00a0?<\/p>\n

Un algorithme asym\u00e9trique fait appel \u00e0 deux cl\u00e9s : une cl\u00e9 dite \u00ab\u00a0publique\u00a0\u00bb qui sert \u00e0 encoder le message, et une cl\u00e9 dite \u00ab\u00a0priv\u00e9e\u00a0\u00bb qui sert \u00e0 le d\u00e9coder<\/strong>. Donc si vous \u00eates le chef de la diplomatie, vous exp\u00e9diez une cl\u00e9 publique \u00e0 votre ambassadeur, et vous gardez pour vous la cl\u00e9 priv\u00e9e correspondante. Vos diplomates pourront encoder les messages, mais s\u2019ils se font voler la cl\u00e9 publique, l\u2019ennemi ne pourra pas pour autant d\u00e9coder vos communications, car seule la cl\u00e9 priv\u00e9e permet de le faire\u00a0!<\/p>\n

\"\"<\/a><\/p>\n

L\u2019algorithme RSA<\/h3>\n

L\u2019algorithme asym\u00e9trique le plus populaire s\u2019appelle l\u2019algorithme RSA<\/strong>, en r\u00e9f\u00e9rence \u00e0 ses concepteurs Rivest Shamir et Adleman (ci-dessous), qui l\u2019ont invent\u00e9 au MIT \u00e0 la fin des ann\u00e9es 70. Il est relativement simple car il ne fait appel qu\u2019\u00e0 des notions \u00e9l\u00e9mentaires d\u2019arithm\u00e9tique. Ceux qui veulent le calcul pr\u00e9cis peuvent aller voir plus bas, mais pour ceux que les maths fatiguent, il est bas\u00e9 en gros sur le principe suivant\u00a0: vous choisissez deux nombres premiers P et Q, vous les multipliez pour obtenir un nombre N=P.Q. Le nombre N donne la cl\u00e9 publique, alors que la priv\u00e9e n\u00e9cessite de conna\u00eetre la d\u00e9composition en P et Q.<\/strong><\/p>\n

Il est vrai qu\u2019en th\u00e9orie, la connaissance de la cl\u00e9 publique N permet de d\u00e9duire la cl\u00e9 priv\u00e9e (P,Q)\u00a0: il suffit de factoriser N. Sauf que factoriser un nombre peut \u00eatre une op\u00e9ration tr\u00e8s longue, m\u00eame avec un gros ordinateur. Donc il suffit de choisir des nombres premiers suffisament grands et en pratique la d\u00e9composition de N en P*Q sera tr\u00e8s difficile et le codage RSA impossible \u00e0 violer par le calcul (sauf en un temps \u00e9gal au nombre de protons dans l\u2019Univers\u2026)<\/p>\n

Le RSA en pratique<\/strong><\/h3>\n

L\u2019algorithme RSA est assez difficile \u00e0 utiliser pour chiffrer des grands messages, car bien que les op\u00e9rations de base soient \u00e9l\u00e9mentaires (multiplication, puissance, division), les calculs peuvent se faire sur des nombres \u00e9normes et prendre pas mal de temps. N\u00e9anmoins pour des codes de carte bleue ou des requ\u00eates vers des sites internet, \u00e7a reste faisable. D\u2019ailleurs le RSA est largement employ\u00e9 dans ce type d\u2019applications.<\/p>\n

Pour en revenir \u00e0 nos ambassadeurs, la puissance et l\u2019importance strat\u00e9gique du RSA est telle qu\u2019en France, il a longtemps \u00e9t\u00e9 class\u00e9 \u00ab\u00a0Arme de deuxi\u00e8me cat\u00e9rogie\u00a0\u00bb<\/strong> (cat\u00e9gorie \u00e0 laquelle appartiennent entre autres les Rafales, les porte-avions et les sous-marins). Dans le m\u00eame genre, le gouvernement am\u00e9ricain l’a aussi class\u00e9 comme arme et a interdit pendant longtemps l\u2019exportation de l\u2019algorithme en dehors du territoire. Evidemment interdire l\u2019exportation d\u2019un algorithme, \u00e7a para\u00eet difficile, et des petits malins anarcho-libertaires se sont amus\u00e9s \u00e0 se transformer en \u00ab\u00a0arme d\u2019exportation ill\u00e9gale\u00a0\u00bb en se faisant tatouer l\u2019algorithme RSA. Tr\u00e8s tendance sur la plage\u2026<\/p>\n

\"\"<\/a><\/p>\n

<\/a><\/p>\n

\n

Pour aller plus loin : le d\u00e9tail de l\u2019algorithme RSA<\/em><\/h3>\n

Choisissez deux nombres premiers P et Q (que vous gardez pour vous), prenons par exemple P=5 et Q=11.<\/em><\/p>\n

Fabriquez le produit des deux N=P.Q, dans notre cas N=55.<\/em><\/p>\n

Choisissez un nombre E n\u2019ayant pas de facteur premier commun avec (P-1).(Q-1) Dans notre cas puisque (P-1).(Q-1) = 40 = 2*2*2*5, on peut choisir par exemple E = 7.<\/em><\/p>\n

La paire (E,N) constitue la cl\u00e9 publique, que vous donnez \u00e0 votre ambassadeur<\/em><\/p>\n

Choisissez ensuite un nombre D tel E.D mod (P-1).(Q-1) = 1 par exemple dans notre cas D = 23 fait l\u2019affaire car 7*23 mod 40 = 1<\/em><\/p>\n

La paire (D,N) constitue la cl\u00e9 priv\u00e9e, que surtout vous gardez pour vous.<\/em><\/p>\n

Comment se passe la proc\u00e9dure d\u2019encodage\u00a0? Tout d\u2019abord il vous faut ramener votre message \u00e0 un nombre. Vous pouvez le faire par le moyen que vous voulez\u00a0comme A=01\u00a0; B=02\u00a0; \u2026\u00a0;Z =26 par exemple. Une fois votre message traduit sous la forme d\u2019un nombre M, vous allez encoder ce nombre avec la cl\u00e9 publique (E,N) de la mani\u00e8re suivante\u00a0:<\/em><\/p>\n

C = M^E modulo N<\/em><\/p>\n

Pour d\u00e9coder C (et donc retrouver M), il vous faut appliquer une op\u00e9ration diff\u00e9rente, utilisant la cl\u00e9 priv\u00e9e (D,N)\u00a0:<\/em><\/p>\n

C^D modulo N.<\/em><\/p>\n

Et c\u2019est l\u00e0 que les maths des nombres premiers nous sont utiles, car elles permettent de prouver que \u00e7a marche c’est-\u00e0-dire que l\u2019op\u00e9ration de d\u00e9codage permet effectivement bien de retrouver le message M initial. On peut en effet d\u00e9montrer que\u00a0:<\/em><\/p>\n

(M^E modulo N)^D modulo N = M<\/em><\/p>\n

Cr\u00e9dits<\/h4>\n