La façon la plus directe de casser le cryptosystème RSA est de factoriser la clé publique. Nous donnons ici quelques éléments scientifiques et historiques pour comprendre le fonctionnement des algorithmes de factorisation.
1 Introduction : émergence d’une communauté
De tous temps, il s’est trouvé des mathématiciens pour aimer faire des calculs que d’aucuns trouvaient anecdotiques, voire inutiles. Ces passionnés passaient de longs jours, à la main, à prouver la primalité de grands entiers (souvent de la forme 2p−1), calculer des zéros de la fonction de Riemann, factoriser des entiers, faire des tables de polynômes. Cela les a souvent conduits à inventer des méthodes astucieuses qui pour certaines n’ont pu être mises en œuvre avec succès qu’à partir du moment où des ordinateurs ont été disponibles.
La factorisation des entiers a donc sa préhistoire (cf. [WS94]), et son histoire récente est liée à l’informatique. La théorie de la complexité a été formalisée dans le but de classifier les problèmes à résoudre en fonction de leur facilité ou leur difficulté, leur vitesse. La cryptographie asymétrique (à clé publique) est née dans ce mouvement vers le...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première