Utilisateur:Thilp/Brouillons/Chirurgie esthétique

Rivest Shamir Adleman (dont le sigle, plus utilisé, est RSA) est un algorithme cryptographique à clé publique : il permet de chiffrer des données (messages, fichiers, etc.) en utilisant le principe de la clef publique, et est très utilisé dans le domaine du commerce électronique (pour les cartes bancaires, en particulier) et des communications militaires.

Historique

RSA est un sigle qui rassemble les initiales de ses trois créateurs : les mathématiciens Ronald Rivest, Adi Shamir et Leonard Adleman. Ils ont décrit RSA en 1977, qui a été breveté par le MIT en 1983. Le brevet a expiré en 2000 : cela signifie qu'aujourd'hui, tout le monde peut l'utiliser en toute liberté.

Le principe de la cryptographie asymétrique (c'est-à-dire à clef publique), inventé en 1976 par W. Diffie et M. Hellman, existait donc avant RSA ; mais aucun algorithme n'était encore conçu pour l'utiliser. La légende raconte que Ronald Rivest a imaginé les bases d'un tel algorithme (RSA, donc) lors d'une soirée arrosée chez ses étudiants !

Applications

Le commerce électronique (puces électroniques, transactions par Internet) et la sécurité militaire sont les principaux domaines d'utilisation du système RSA. Malheureusement, les mafias ou le terrorisme pourraient également se servir d'un tel moyen de communication ...

De nombreux systèmes de cryptographie s'inspirent de RSA pour renforcer encore la sécurité des messages : en particulier, le système PGP et ses variantes. Tous ces systèmes sont basés sur l'utilisation d'une fonction asymétrique, utilisée dans RSA.

Principe de base de la cryptographie à clef publique

• Cette section ne donne que les informations de base. Vikidia possède un article dédié (et donc plus riche) à ce sujet : Clef publique.

Prenons deux personnes quelconques : Artémis et Bigorneau.

Artémis veut envoyer des messages à Bigorneau, mais elle ne veut pas que quiconque d'autre puisse les lire. Elle utilise donc un système de codage simple, à clef secrète. Seuls elle (pour chiffrer) et Bigorneau (pour déchiffrer) connaissent la clef choisie par Artémis.

Mais Artémis change de ville et se fait plein d'amis. Si elle garde le système de la clef secrète, elle doit créer énormément de nouvelles clefs, autant qu'elle a d'amis (car elle ne réutilise pas la même clef plusieurs fois, bien sûr). Que faire si elle a des millions d'amis ? Elle ne peut quand même pas créer des millions de clefs secrètes : c'est ingérable !

Elle a alors recours au système de la clef publique. Elle se fabrique une clef publique, et la clef privée qui va avec. La clef publique ne servira qu'à chiffrer les messages, et la clef privée seulement à les déchiffrer. Puisqu'il faut la clef privée pour déchiffrer, Artémis peut donner sa clef publique à tout le monde, à ses millions d'amis, qui pourront seulement chiffrer des messages avec. Ils ne pourront rien déchiffrer en connaissant seulement la clef publique, et donc les messages des autres seront en sécurité ! Artémis sera la seule à pouvoir lire les messages qu'on lui envoie.

L'élément fondamental de la cryptographie : la clef

Principe

Dans tous les systèmes de codage, on utilise ce que l'on appelle une clef. C'est cette clef qui transforme le message, et qui, dans le cas d'une cryptographie symétrique, la plus courante, peut le décoder.

Par exemple : mon message est : « Vikidia ». Je veux le coder.
Disons que chaque lettre du mot est remplacée par son numéro dans l'alphabet (A = 1, B = 2, C = 3, ... , Z = 26). On obtient donc, à la place de « Vikidia », 22 ; 9 ; 11 ; 9 ; 4 ; 9 ; 1. Si ma clef est une fonction du type $f(x)=x+3$ (c'est-à-dire que la lettre codée est le numéro de la lettre d'origine, plus trois), alors mon message codé sera 22+3 ; 9+3 ; 11+3 ; 9+3 ; 4+3 ; 9+3 ; 1+3, soit : 25 ; 12 ; 14 ; 12 ; 7 ; 12 ; 4, soit : YLNLGLD ! Ainsi, par ma clef privée $f(x)=x+3$, VIKIDIA devient YLNLGLD. On parle de clef privée car il faut la garder secrète (privée) si mon message veut le rester ! Il faut seulement la donner au destinataire du message, pour que lui seul puisse le lire.

Ce destinataire du message codé pourra donc le déchiffrer en inversant la clef, c'est-à-dire en appliquant la fonction $f^{-1}(x)=x-3$.

Récapitulatif : chiffrage simple de « Vikidia »

Message clair :	V	I	K	I	D	I	A
Équivalent en nombres :	22	9	11	9	4	9	1
Clef de chiffrement :	$x\to x+3$
Résultat de l'opération :	25	12	14	12	7	12	4
Message chiffré :	Y	L	N	L	G	L	D

Détail d'une paire de clefs publique/privée

En cryptographie, on appelle trousseau de clefs le couple clef publique/clef privée.

Pour créer son trousseau de clefs pour RSA, il faut effectuer plusieurs opérations. Une mauvaise conception peut détruire la sécurité du système, il faut donc faire très attention ! Les étapes nécessaires sont :

1. Choix de deux nombres premiers, nommés en général $p$ et $q$.

   On calcule $n=p\times q$. Plus ces deux nombres seront grands, plus la clé sera sûre, parce que les ordinateurs ont du mal à retrouver $p$ et $q$ (à partir de $n$) lorsque ceux-ci sont très grands. C'est là toute la sécurité du RSA ! On appelle factorisation d'un produit de nombres entiers l'action de retrouver $p$ et $q$ en partant de $n$. $n$ sera le module de chiffrement (le modulo).

2. Calcul de l'indicatrice d'Euler, c'est-à-dire le nombre $\varphi (n)=(p-1)\times (q-1)$.

   Concrètement, c'est le nombre d'entiers naturels premiers avec $n$ (c'est-à-dire les $x$ tels que $pgcd(n,x)=1~;~x\in \mathbb {N}$).

   $\varphi (n)$, et donc $p$ et $q$, doivent absolument rester secrets ! Dans le cas contraire, si une personne mal intentionnée les connait, celle-ci peut trouver la clef privée très facilement.

3. Choix d'un nombre $e$ tel que $e$ soit premier avec $\varphi (n)$.

   C'est-à-dire que $pgcd(e,\varphi (n))=1$ (autrement dit, le plus grand diviseur commun à $e$ et à $\varphi (n)$ doit être 1).

4. Choix d'un nombre $d$ tel que $e\times d\equiv 1{\pmod {\varphi (n)}}$.

   En français, cela veut dire que $d$ doit valoir $\varphi (n)$ (ou l'un de ses multiples) plus un, le tout divisé par $e$ (voir l'article Modulo).

Exemple de création

• choisissons $p$ = 593 et $q$ = 613. $n$ vaut donc $p\times q=593\times 613=363509$.
• $\varphi (n)=(p-1)\times (q-1)=(593-1)\times (613-1)=592\times 612=362304$.
• $pgcd(\varphi (n),e)=1\Leftrightarrow e=5$.
• $d\equiv {\frac {1{\pmod {\varphi (n)}}}{e}}={\frac {k\times 362304+1}{5}}\quad {\stackrel {k=1fonctionne}{=}}\quad {\frac {362305}{5}}=72461$.
• On a donc :
  • $n$ = 363509
  • $e$ = 5
  • $d$ = 72461

Notre trousseau de clefs va donc se présenter sous cette forme :

• Clé publique (distribuable à tout le monde) : $(n;e)$, soit $(363509;5)$
• Clé privée (à garder secrète !) : $(d;e)$, soit $(72461;5)$

Fonctionnement d'un trousseau RSA

Cryptage

• Tout d'abord, (re)précisons bien une chose :

  on se sert de la clef publique de quelqu'un pour lui envoyer des messages cryptés ;

  attention à ne pas confondre, ce n'est pas lui qui utilise sa clef publique pour nous écrire !

L'intérêt du RSA, c'est d'utiliser une fonction asymétrique : on ne peut l'inverser qu'à certaines conditions, c'est-à-dire, ici ... seulement si l'on en est le créateur !

Nous avons vu comment inverser une clef secrète : par exemple, dans le chiffre de César, au lieu d'effectuer la transformation « trois lettres après », on faisait « trois lettres avant ». Alors, comment une clef peut-elle être impossible à inverser ?

Il faut se servir du principe du modulo.

Article détaillé : Modulo

Voici une clef publique : $(n~;~e)$.

• $n$ le module de chiffrement de la clef ;
• $e$ est en est l'exposant.

Voici comment ils sont utilisés :

• pour commencer, donnons-nous un message à chiffrer : ${\mathcal {M}}$. Il contient des informations sur les services secrets d'un pays.
• On effectue l'opération ${\mathcal {M}}^{e}\equiv {\mathcal {C}}{\pmod {n}}$.

  Cela signifie qu'on prend notre message ${\mathcal {M}}$ (sous forme d'un nombre), qu'on l'élève à la puissance $e$, et qu'enfin on applique au résultat un modulo $n$ ; on a alors le message chiffré ${\mathcal {C}}$.

Exemple

Nous allons chiffrer notre message ${\mathcal {M}}$ = « VIKIDIA » avec la clef publique (2501 ; 7) :

1. On remplace les lettres par leur numéro dans l'alphabet (comme tout à l'heure) :

   V = 22, I = 9, K = 11, ...

   « VIKIDIA » est donc « pré-chiffré » en « 22-09-11-09-04-09-01 ».

2. On regroupe par deux les nombres obtenus :

   « 22-09-11-09-04-09-01 » devient ainsi « 2209-1109-0409-0127 »

   Il faut obtenir dans tous les cas des nombres de même longueur (ici, quatre chiffres). On peut remarquer que, comme le mot Vikidia contient un nombre impair de lettres, le « A » (pré-chiffré par « 01 ») ne peut pas être associé à une autre lettre. Pour qu'il ne reste pas tout seul (et donc faire un nombre à quatre chiffres comme il le faut), on rajoute après lui un nombre choisi, qui n'est pas une place dans l'alphabet ; par exemple, 27 : cela fait donc « 0127 ».

   Remarque très importante : pour des raisons mathématiques, le module de chiffrement choisi doit être plus grand que le plus grand nombre qu'on veut chiffrer ! Ici, on a évidemment choisi un bon module : 2501 est plus grand que 2209.

3. On applique l'exposant à chacun des nombres à quatre chiffres formés :

   Il s'agit simplement de monter chaque nombre à la puissance demandée. Ici, l'exposant de chiffrement vaut 7, j'élève donc chaque nombre à la puissance 7 :

   $2209^{7}=\underbrace {2209\times 2209\times \cdots \times 2209} _{7fois}=256666986187667409334369$

   et, de même, $1109^{7}=2063102584170216968669$

   $409^{7}=1914534320537457769$

   $127^{7}=532875860165503$.

   Pour le moment, à mi-chiffrement, notre « VIKIDIA » vaut donc « 256666986187667409334369-2063102584170216968669-1914534320537457769-532875860165503 »

4. Enfin, on applique le module de chiffrement :

   Rappelons qu'ici, il vaut 2501. Dans l'article modulo, on explique comment marche cette opération. Là, on indique juste le résultat : $256666986187667409334369\equiv 1538{\pmod {2501}}$.

   Pour le reste du message, cela fait :

   $2063102584170216968669\equiv 538{\pmod {2501}}$

   $1914534320537457769\equiv 368{\pmod {2501}}$

   $532875860165503\equiv 2485{\pmod {2501}}$

Par la clef publique (2501 ; 7), « VIKIDIA » est chiffré en 1538-538-368-2484.

Ce qui empêche d'inverser une clef publique, c'est le module de chiffrement, parce qu'une fois que j'ai ${\mathcal {C}}_{1}=1538$, comment puis-je deviner combien de fois j'ai soustrait 2501 à ${\mathcal {M}}_{1}^{7}$ ? C'est impossible !

Exemple : nous allons essayer de retrouver X₁ à partir de Y₁

Y₁ vaut 25. Supposons que je connaisse aussi la clé : puisse qu'elle est publique, n'importe qui peut la connaitre. Je dispose donc de 2 informations : Y₁ = 25 et clé_publique = (33 ; 3). Voyons si on peut inverser cette clé ...

On va commencer par faire 25 + 33. Peut-être que X₁ était juste un peu plus grand que 33 ? 25 + 33 = 58. On va maintenant tenter d'inverser la "puissance 3" pour retrouver X₁. Pour cela, on utilise un objet mathématique bizarre, nommé racine cubique. C'est comme si, au lieu de "puissance 3", on calculait "puissance 1/3". Cela donne ... ${\sqrt[{3}]{58}}=58^{\frac {1}{3}}=3.870876640627796$ ? Ah non, ce n'est pas cela, puisque l'on cherche un nombre entier de 4 chiffres !

Il faudrait continuer, en faisant 25 + (33 × 2), puis 25 + (33 × 3), ... Mais c'est très hasardeux, et beaucoup trop long ! Pour retrouver 10779215329, il faudrait en fait calculer 25 + (33 × [un nombre plus grand que 300 000]), mais pour en arriver là, en partant de 25 + (33 × 2), le temps à passer est énorme (surtout à la main ...).

Plus loin dans cet article, nous verrons comment retrouver X_i, c'est-à-dire casser RSA. Mais cela ne fonctionne qu'avec des clefs de faible taille ...

• Mais si personne ne peut le décoder, le destinataire ne peut pas lire le message !

Si, parce que ce destinataire (celui qui a créé sa clef publique), a en même temps créé sa clef privée.

Décryptage

Il suffit de suivre les mêmes opérations que pour le cryptage, mais en sens inverse et avec la clef privée. Pour cela, il faut savoir que la clef privée associée à (33 ; 3) est... (33 ; 7) !

Pourquoi (33 ; 7) ?

C'est simple : les deux nombres premiers (p et q) utilisés pour former n (qui vaut 33) sont 11 et 3 (car 3 × 11 = 33). De là, on peut calculer $\varphi (n)$ :

$\varphi (n)=(p-1)\times (q-1)=(11-1)\times (3-1)=10\times 2=20$. e valant 3, on sait que $d={\frac {1{\pmod {\varphi (n)}}}{e}}={\frac {21}{3}}=7$.

Cependant, à cause d'une propriété (la taille, trop faible) de cette clef publique, celle-ci n'est pas utilisable dans cet exemple. Nous allons donc considérer notre second trousseau qui, lui, est nettement suffisant : clé_publique = (363509 ; 5) ; clé_privée = (363509 ; 72461). Par cette clé, VI est codé en 31015.

Voir le détail du cryptage de VI en 31015

V est la la 22^e place dans l'alphabet, I à la 9^e. On définit donc V = 22 et I = 9, ce qui nous fait un X₁ valant 2209 (les deux nombres accolés, avec un zéro devant 9 pour obtenir un X de quatre chiffres).

$X_{1}=2209X_{1}^{e}=2209^{5}=52599132235830049\equiv 31015{\pmod {363509}}=Y_{1}$

On récupère donc tous les Y_i qu'on nous a envoyés grâce à notre clef publique. On procède comme si l'on cryptait chaque Y_i, sauf que l'on se sert cette fois de la clef privée ; pour Y₁, cela donne :

$Y_{1}=31015Y_{1}^{d}=31015^{72461}$

Pourquoi ne pas afficher le résultat de cette dernière opération ?

Ici, le détail de l'opération n'est pas donné ; en effet, 31015⁷²⁴⁶¹ est un nombre si énorme (31015 multiplié par lui-même 72461 fois !) que la calculatrice Windows refuse de donner le résultat ("Entrée fonction incorrecte"). Il en va de même pour le logiciel de calcul formel utilisé (Maxima). Cependant, il ne faut jamais baisser les bras : le résultat de 31015⁷²⁴⁶¹ mod. 363509 nous est donné ... par une simple calculatrice programmable (beaucoup moins puissante qu'un ordinateur) ! Comment est-ce possible ?

Explication : pour une clarté la plus grande possible, nous avons choisi d'afficher dans cet article tous les résultats intermédiaires de nos calculs. Alors, quand on demande à l'ordinateur "Combien vaut 31015⁷²⁴⁶¹ mod. 363509 ?", celui-ci calcule 31015⁷²⁴⁶¹, puis applique le modulo au résultat obtenu ; nous avons vu qu'il ne pouvait pas afficher ce résultat, il est donc dans l'incapacité de résoudre ce calcul. C'est parce que nous nous y prenons mal ! La calculatrice parvient à nous donner 2209 car elle ne le calcule pas directement, comme l'a tenté l'ordinateur. Il suffit de créer un programme adéquat, et elle résout les opérations selon ce programme. Comme c'est assez compliqué, nous dirons simplement que la méthode utilisée ici par la calculatrice s'inspire de l'exponentiation modulaire. Le résultat, si le programme est correct, est calculé en 3 secondes, tandis que Maxima n'a rien trouvé depuis plus d'une demi-heure !

$Y_{1}^{d}=31015^{72461}\equiv 2209{\pmod {363509}}$

On retrouve bien notre 2209 qui, une fois décomposé, signifie VI !

Faiblesses, failles : casser RSA... oui, c'est possible !

Taille des clés dans le fonctionnement

Précédemment, nous avons délaissé la clé publique (33 ; 3) au profit d'une autre, (363509 ; 5). Pourquoi ?

La première chose à remarquer, c'est la différence entre les deux modules de chiffrement (les modulo) : 363509 est bien plus grand que 33 ! Cela a beaucoup d'importance. Pour mieux comprendre, nous allons tenter de décoder VI codé par (33 ; 3).

Y₁ = 25 (c'est notre VI, mais crypté, voir l'opération ici)
Y₁^d = 25⁷ = 6103515625
Y₁^d mod. 33 = 6103515625 mod. 33 = 31
Ce n'est pas le bon résultat ! On attendait 2209, c'est-à-dire VI.

Pourquoi cela ne fonctionne-t-il pas ? C'est que notre clef est trop petite ; en effet, on ne peut pas avoir 2209 en appliquant un modulo 33, parce que la définition du modulo est « soustraire 33 jusqu'à ce que le résultat soit plus petit que 33 (ou égal à 33) ». Or 2209 est plus grand que 33, on a donc continué à soustraire. Il nous faut alors choisir un module de chiffrement plus grand, ce que nous avons fait en prenant 363509. Bien sûr, n'importe quel module supérieur à 2626 (pour coder ZZ, les deux lettres de l'alphabet ayant le plus grand nombre associé) aurait fait l'affaire.

Taille des clefs dans la sécurité

(33 ; 3) fait une longueur de 7 bits, c'est minuscule. (363509 ; 5) fait une longueur de 20 bits, c'est déjà mieux, mais toujours ridicule face à la puissance des ordinateurs et des algorithmes de calcul. Aujourd'hui, il est recommandé d'utiliser des clés de 1024 bits, mais on préfèrera du 2048 bits pour plus de sûreté. Une clef de 2048 bits ressemble à cela :

> :

Clé publique

$n$ = 157337274758507425107029228955215686099941097688476114125797309964725569445099084282865193398522521162144493616 82866749560338954234110352584686966932883272324308025164873428704365159788021160614285949582887492130119123606790 59878332902595761383236749547050737155791664594965844745372607462276878025226072275288094194842912099720292917832 69818822737937265649393278700098884255449184345441514075614392408691843795136876705080454633600409425663640688371 63141426439081530844311056997699690802430711400673169786551672145227374747966163496099536087275525782831460299705 474407052534428504092022073149317528816814347550986601

$e$ = 7

Clef privée

$n$ = 157337274758507425107029228955215686099941097688476114125797309964725569445099084282865193398522521162144493616 82866749560338954234110352584686966932883272324308025164873428704365159788021160614285949582887492130119123606790 59878332902595761383236749547050737155791664594965844745372607462276878025226072275288094194842912099720292917832 69818822737937265649393278700098884255449184345441514075614392408691843795136876705080454633600409425663640688371 63141426439081530844311056997699690802430711400673169786551672145227374747966163496099536087275525782831460299705 474407052534428504092022073149317528816814347550986601

$d$ = 44953507073859264316294065415775910314268885053850318321656374275635876984314024080818626685292148903469855319 09390499874382558352602957881339133409395220664088007189963836772675759939434617318367414166539283465748321030511 59965237972170217538067642727728782044511904169990241355820744989221965150064592078646292360382871004201823486854 09035415057345597526031882187762403432581196473699901312170462740233911870979074620403885426794038143105649973535 76240588772750516827090317961048076761393432965167070093867557259571280760973798188859325213519581931075307232408 651437736781722151992867032200283172044418261997678543

Ce n'est pas rien. Pourquoi a-t-on besoin de tels nombres ?

Nous avons vu qu'il faut pour créer son trousseau deux nombres entiers premiers, p et q. Ces nombres sont aussi utilisés pour déterminer l'indicatrice d'Euler $\varphi (n)$, qui elle permet de créer sa clé privée. Il est donc indispensable de conserver p et q secrets !

Les machines à calculer parviennent très bien à calculer un produit (le résultat d'une multiplication) ; ainsi, on peut avoir p et q long chacun comme les nombres écrits plus haut, cela ne pose aucun problème et p × q est effectué en très peu de temps. En revanche, ces machines ont d'énormes difficultés à faire l'opération dite de « décomposition en facteurs premiers » dès lors que les nombres deviennent très grands. Ainsi, les plus puissants ordinateurs ne parviendront pas à décomposer le n de la clef de 2048 bits montrée précédemment, ou alors en travaillant pendant une durée équivalente à plusieurs milliards d'années (ce qui, d'un point de vue humain, est inacceptable).

Cependant, avec des clés plus petites, de l'ordre de 512 bits et moins, il est possible de retrouver p et q. Plus le module de chiffrement est petit, plus il est simple de le décomposer ! Avec un ordinateur pas très récent et un logiciel de calcul formel renommé, 33 est décomposé en moins d'une seconde : 11 × 3 (même une calculatrice le fait). 363509 en une seconde : 593 × 613. 487244884854344046304090844893 (100 bits) est décomposé en 20 secondes : 669536424408869 × 727734693873497. Mais pour décomposer un module de chiffrement de 120 bits, il faut plus de 3 minutes 30 ! On observe que le temps nécessaire à la décomposition augmente beaucoup plus rapidement que la taille de la clé. Plus une clé est grande, moins il y a de risques de la voir « cassée », c'est-à-dire de découvrir la clé privée associée. Les communications importantes entre gouvernement (utilisant des systèmes semblables à RSA) utilisent des clés de 4096 bits, voir davantage. Cela garantit une excellente sécurité.

Et demain ?

Selon la loi de Moore, la puissance des ordinateurs double tous les 18 mois. Il faut donc s'attendre à voir les algorithmes de décomposition en facteurs premiers de plus en plus efficaces. De plus, il est possible que des algorithmes plus performants que ceux qu'on utilise actuellement voient le jour dans un futur proche... Et le développement de l'ordinateur quantique pourrait annoncer la fin des cryptosystèmes tels que RSA, car ils sont présentés comme extrêmement puissants. Cependant, il faut noter que leur record de décomposition est, en octobre 2001, la factorisation de 15 = 3 × 5 !

Sources

• http://www.bibmath.net/crypto/moderne
• Wikipédia

Références

Portail de l'information —  Tout sur les écritures, les codes secrets, les médias...

Catégorie:Technique Catégorie:Informatique Catégorie:Article long à illustrer

wp:Rivest Shamir Adleman simple:RSA