Abonnez-vous

Application des restes chinois


Hervé Lehning et Bertrand Hauchecorne

Le théorème des restes chinois trouve, entre autres, des applications en cryptographie


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 xb modulo n ; le déchiffrement du même ... Lire la suite gratuitement