L’algorithme RSA

Histoire :

L’algorithme RSA a été inventé  en 1977. Il est nommé RSA à cause des initiales de ses inventeurs : Ronald Rivest, Adi Shamir et Leonard Adleman. Cet algorithme est un algorithme de cryptographie asymétrique. Il est très utilisé dans le commerce électronique, pour les sites sécurisés et pour chiffrer les emails.

En août 1977, Martin Gardner a publié dans la revue Scientific American un article intitulé « Un nouveau type de chiffrement qui prendrait des millions d’années pour être déchiffré » dans lequel il explique en détail le fonctionnement des systèmes à clé publique.

Il met ensuite au défi les lecteurs de déchiffrer un message chiffré et promet une récompense de 100 dollars (somme importante à l’époque) pour celui qui trouverait en premier les deux clés primaires. La bonne réponse ne fut trouvée  que 17 ans plus tard et a demandé la collaboration de plus de 600 personnes.

Théorie :

L’algorithme RSA est un système de cryptographie dit à « clé publique ». Dans ce système, la clé de chiffrement est connue de tous afin que tous puissent chiffrer leurs données à envoyer au récepteur. Ces données peuvent être déchiffrées seulement par une clé dite « privée » que seul le récepteur connaît.

La fonction d’Euler : c’est l’ensemble des nombres inférieurs à n et premiers avec n exprimé par φ(n).

  1. On calcule n = p × q, où p et q sont deux nombres premiers (sensiblement de même taille) qui ne sont pas fournis (seul le récepteur les connaît). Ils sont nommés nombres RSA. Comme p et q sont premiers, φ(n) = (p – 1)(q – 1).
  2. On choisit un nombre e qui n’a aucun facteur en commun avec  φ(n). C’est-à-dire que pgcd[φ(n);e] = 1.
  3. On calcule d, tel que e × d ≡ 1 (mod φ(n)) , qui sera notre clé privée. Nous savons que cette valeur d existe.
  4. Nous avons donc la clé publique (n,e) et la clé privée (d).
  5. L’émetteur utilise la clé publique pour chiffrer son message m par blocs inférieurs à n, en effet si la taille des blocs était supérieure à la taille de m, une simple analyse de fréquence suffirait à casser le chiffrement. Nous utilisons ensuite la fonction M ≡ me(mod n) où M est le message chiffré.
  6. Le récepteur réalise l’opération Md ≡ (me)d(mod n) afin de déchiffrer le message m.
Exemple concret :
  1. Nous prenons p = 47 et q = 43. Nous calculons n = p × q = 47 × 43 = 2021.
  2. Nous choisissons notre nombre e (sans facteur en commun avec φ(n)). φ(n) = (p – 1)(q – 1) = 46 × 42 = 1932. Nous allons prendre e = 53 car 53 ne possède aucun diviseur commun avec 1932. Notre clé publique sera (2021,53).
  3. Nous cherchons notre nombre d qui sera l’inverse de 53 modulo 1932, c’est-à-dire 53 × d ≡ 1 (mod 1932). d = 401 vérifie cette congruence. Nous avons ainsi notre clé privée (401).
  4. Clé publique (2021,53) et clé privée (401).
  5. Nous allons maintenant « tester » nos clés en nous envoyant un message que nous aurons chiffré avec notre clé publique. Prenons comme message m = 3. Nous calculons 353 = 19 383 245 667 680 019 896 796 723 ≡ 589 (mod 2021). Donc M = 589. Le récepteur (ici nous) reçoit le message M = 589 qui est le message chiffré de m.
  6. Nous allons maintenant déchiffrer ce message M afin de retrouver le message m original. Nous calculons 589401 = 6 549 877 982 813 532 679 471 754 029 037 276 297 525 118 235 874 530 535 667 714 861 715 317 994 797 496 170 642 892 800 979 596 688 204 947 751 732 191 974 594 378 877 982 721 185 474 298 325 012 165 031 442 856 909 686 881 786 894 012 481 094 996 001 463 881 074 613 574 180 414 388 233 522 373 275 763 946 910 343 124 746 788 544 452 395 243 410 769 142 250 094 206 866 447 093 213 803 499 558 041 543 028 116 155 099 370 580 174 592 207 762 576 945 902 328 273 883 315 130 359 061 362 119 735 409 943 153 227 804 153 916 242 264 374 895 477 581 583 628 587 748 273 131 582 397 402 203 481 478 882 947 901 330 236 782 137 736 212 445 491 906 179 033 858 942 156 017 575 356 537 648 621 722 071 199 345 245 013 978 326 725 219 263 452 499 090 951 889 593 227 017 927 783 442 610 748 874 317 173 540 268 133 508 581 825 545 503 986 227 111 431 804 052 444 355 509 126 694 113 410 278 493 914 869 853 232 366 046 905 564 336 569 397 263 231 988 992 911 739 374 276 145 918 452 377 439 920 380 016 811 996 418 625 733 025 488 755 111 523 667 942 516 540 876 400 634 863 774 158 039 808 155 355 376 828 197 040 324 893 009 757 972 804 801 710 787 844 967 859 147 923 697 885 171 999 654 859 379 735 289 233 704 049 550 801 280 474 118 474 344 518 283 348 116 181 409 954 305 072 299 302 899 181 798 182 812 392 007 930 032 948 505 998 568 623 011 220 478 735 775 645 201 719 488 948 550 500 077 372 566 440 725 762 453 399 329 162 042 409 431 003 141 030 094 988 177 819 859 016 589 ≡ 3 (mod 2021). Nous avons donc bien retrouvé le message original m = 3 après déchiffrement.
Décrypter :

Pour décrypter un message, nous avons besoin de la valeur de d et de n (cette dernière est déjà connue car elle est délivrée avec la clé publique). Or, pour calculer d, il faut connaître φ(n) et par conséquent p et q. Nous sommes donc dans l’obligation de décomposer n comme produit de deux nombres premiers, ce qui représente un temps qui n’est pas raisonnable pour n possédant plus de 100 chiffres. Actuellement la taille recommandée des clés RSA est de 2048 bits, c’est-à-dire 256 chiffres.

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.