CRT : Chinese Remainder Theorem
Cryptographie
CRT : Chinese Remainder Theorem. « Théorème des restes chinois », par analogie avec une addition faite à deux petites caisses séparées puis recollée au comptoir, plus vite qu'à une seule grande caisse.
Principe : Connaissant les restes d'un nombre modulo plusieurs entiers premiers entre eux, on reconstruit ce nombre, de façon unique, modulo leur produit. Un résultat de plusieurs siècles qui accélère encore les serveurs d'aujourd'hui, preuve que l'arithmétique vieillit mieux que les frameworks.
Accélération RSA : Pour déchiffrer ou signer, on calcule séparément modulo p et modulo q, sur des nombres deux fois plus courts, puis on recombine. Le calcul devient plusieurs fois plus rapide, d'où les paramètres supplémentaires stockés dans presque toutes les clés privées.
Attaque par faute : Une seule erreur de calcul dans l'une des deux moitiés, accidentelle ou provoquée, et la signature fautée livre, par un calcul de plus grand commun diviseur, un facteur du module. La clé privée s'enfuit alors par la porte qu'on avait ouverte pour gagner du temps ; d'où la règle de vérifier chaque signature avant de la publier.
Ce qui arrive si on s'en passe
Une implémentation RSA qui accélère ses calculs par le théorème des restes chinois sans vérifier chaque signature avant de la publier offre sa clé privée à qui sait provoquer une faute. Une seule erreur dans l'une des deux moitiés du calcul, due à un défaut matériel, à une perturbation électrique ou à une injection volontaire, produit une signature fautée dont un simple calcul de plus grand commun diviseur extrait un facteur du module. Le secret tombe alors en une opération, sans force brute ni génie. Le gain de temps obtenu est bien réel, mais il profite surtout à l'attaquant, qui n'en demandait pas tant.
Explication de la marmotte
Imaginer qu'on cherche un nombre et qu'on ne connaît que deux indices : rangé par paquets de 3, il en reste 2 ; rangé par paquets de 5, il en reste 1. Une vieille astuce mathématique garantit qu'avec ces indices on retrouve le nombre, ici 11, parmi les nombres de 0 à 14. En informatique, on s'en sert pour découper un énorme calcul en deux calculs plus petits, les mener séparément, puis rassembler les morceaux. Le résultat est le même, mais il arrive beaucoup plus vite.
Où ce terme est utilisé
- Quand l’implémentation parle : temps, cache, fautes et oracles (4 occurrences)
- Courbes elliptiques : compacité, validation et pièges (1 occurrence)
- Les problèmes difficiles qui rendent la clé publique possible (1 occurrence)