RSA : calculs cryptographiques
Le théorème des restes chinois permet d'accélérer les calculs de déchiffrement de la méthode RSA, une méthode cryptographique asymétrique, où clef de chiffrement et clef de déchiffrement sont distinctes. Elle est très utilisée sur Internet pour l'authentification et l'échange de clefs symétriques ainsi que dans les cartes bancaires. Son principe repose sur les nombres premiers et l'arithmétique modulaire.
La méthode consiste à choisir deux nombres premiers p et q, comme 101 et 113, et à en faire le produit n, ici 11 413 (dans la pratique, on utilise des nombres bien plus grands afin que la factorisation de n soit impossible par les méthodes connues). On considère alors le produit (p – 1)(q – 1), ici 11 200, puis a et b tels que ab soit égal à 1 modulo (p – 1)(q – 1). Dans notre cas particulier, 6 597 et 3 533 conviennent. Le chiffrement d'un nombre x entre 0 et n – 1 consiste alors à calculer x b modulo n ; le déchiffrement du même nombre consiste à calculer x a modulo n.
Ici, pour chiffrer x, on calcule x 3 533 modulo 11 413 ; pour le déchiffrer, on calcule x 6 597 modulo 11 413. Vous pouvez vérifier que le chiffré de 9 726 est bien 5 761, et que le déchiffré est bien 9 726. Bien entendu, ces calculs sont impraticables par la méthode brutale, c'est-à-dire en effectuant trois mille cinq cent trente-deux multiplications consécutives dans le premier cas, six mille cinq cent quatre-vingt-seize dans le second. Pour rendre ce calcul possible, la remarque essentielle est que l'on obtient x 2 048 en seulement onze multiplications : x2 = x × x, x4 = x2 × x2, x8 = x4 × x4… x 2 048 = x 1 024 × x 1 024. On obtient alors la puissance cherchée en décomposant 3 533 en somme de puissances de 2, ce qui correspond à son écriture binaire. Plus précisément, 3 533 = 2 048 + 1 024 + 256 + 128 + 64 + 8 + 4 + 1, ce qui ajoute sept multiplications. Nous sommes donc passés de trois mille cinq cent trente-deux multiplications à seulement dix-huit, et d'un problème impraticable à un calcul rapide, même s'il suppose l'usage d'un ordinateur.
RSA et le théorème des restes chinois
On peut accélérer les calculs utilisés dans la méthode RSA grâce au théorème des restes chinois, à condition de supposer connue la clef secrète, c'est-à-dire p et q, ce qui est le cas pour le déchiffrement mais pas pour le chiffrement.
Le déchiffrement de x correspond au calcul de x a modulo n. Comme on connaît la factorisation de n en pq quand on déchiffre, on peut considérer c = a modulo p – 1 et d = a modulo q – 1. Le théorème des restes chinois permet de reconstituer x a à partir de x c et x d, qui sont plus rapides à calculer, car x a = x c modulo p et x a = x d modulo q d'après le petit théorème de Fermat. Dans le cas de notre exemple, 97 et 101.
Les œufs du paysan chinois
Un vieux paysan chinois s'apprête à porter ses œufs au marché pour les vendre. Les mettant dans son panier, il s'aperçoit que s'il les compte par deux, il lui en reste un. De même s'il les compte par trois, par quatre, par cinq, par six : il lui en reste toujours un ! Enfin, s'il les compte par sept, alors il ne lui en reste plus. Combien possède-t-il d'œufs ?
Appelons n ce nombre. On voit que n – 1 est divisible par 2, 3, 4, 5 et 6, et donc par leur plus petit commun multiple, soit 60. Les valeurs de n possibles sont donc 61, 121, 181, 241, 301, 361… Or ce nombre doit être divisible par 7. Un essai rapide nous montre que 301 est le plus petit nombre qui convienne ; mais en existe-t-il d'autres ?
Si deux nombres m et n sont solutions, leur différence p est divisibles par 2, 3, 4, 5, 6 et 7, donc par leur plus petit commun multiple, qui est 420. Ainsi les solutions sont de la forme n = 361 + 420k où k désigne un nombre entier positif ou nul. Le mathématicien dira qu'il existe une infinité de solutions. Il oublie que le paysan chinois est âgé et qu'avec k = 1, soit n = 761, c'est près de cinquante kilos que devrait porter le vieil homme. Le bon sens paysan nous indique donc l'unique réponse : n = 361.
Ce même problème se retrouve chez le mathématicien indien Bhaskara, chez le savant arabe al-Haytam et chez Bachet de Méziriac. Leonhard Euler précise même « qu'il traine un peu partout ».
Lire la suite gratuitement