Factorisation d’entiers : la voie royale du cassage de RSA

Magazine
Marque
MISC
HS n°
Numéro
5
Mois de parution
avril 2012
Domaines


Résumé

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...

Cet article est réservé aux abonnés. Il vous reste 95% à découvrir.
à partir de 21,65€ HT/mois/lecteur pour un accès 5 lecteurs à toute la plateforme
J'en profite


Articles qui pourraient vous intéresser...

Encore StopCovid, ou stop ?

Magazine
Marque
MISC
Numéro
112
Mois de parution
novembre 2020
Domaines
Résumé

Comment fonctionne StopCovid ? Quels sont les problèmes ? À quels risques s’expose-t-on ? Dans cet article, nous tentons d’éclaircir ces questions et de nourrir quelques réflexions sur l’usage du numérique.

Introduction aux TPM (Trusted Platform Modules)

Magazine
Marque
MISC
HS n°
Numéro
22
Mois de parution
octobre 2020
Domaines
Résumé

Les TPM (Trusted Platform Modules), brique de base du Trusted Computing, ont été imaginés il y a une vingtaine d’années, et pourtant ils ne sont pas très utilisés malgré leurs réelles qualités. Comment expliquer cela ? Cet article tend à fournir de premiers éléments de réponse.

Applications des TPM

Magazine
Marque
MISC
HS n°
Numéro
22
Mois de parution
octobre 2020
Domaines
Résumé

Les TPM, inventés il y a une vingtaine d’années, ont pénétré progressivement les plateformes numériques. Malgré ce long historique, les TPM ont encore aujourd’hui du mal à s’imposer. Pourtant, leurs applications potentielles sécuritaires sont très intéressantes : Authenticated Boot, Remote Attestation, Scellement, amélioration de la sécurité de la cryptographie logicielle. Cet article détaille ces principales applications et liste quelques produits connus qui utilisent les TPM.

Exploitations de collisions MD5

Magazine
Marque
MISC
HS n°
Numéro
21
Mois de parution
juillet 2020
Domaines
Résumé

Vous trouvez un système indexant des fichiers via MD5. À quel point est-il vulnérable ? Depuis l'attaque [1] en 2008 qui a généré un faux certificat SSL, la fonction d'empreinte MD5 est considérée comme inutilisable par les experts, car vulnérable en pratique. Cela dit, elle est encore souvent utilisée, et parfois à bon escient. Par exemple en juillet 2019, on apprenait que le système de censure de WeChat [2] était basé sur une liste noire indexée avec MD5. Cet article a pour but de clarifier les attaques par collisions contre MD5.