INF 421 - Projet Informatique

Bruno.Salvy@inria.fr

Une bonne partie de la cryptographie actuelle repose sur des clés publiques qui sont des produits de (grands) nombres premiers, auxquelles correspond une clé secrète qui est grosso modo la factorisation. Être capable de trouver ces factorisations révèle le secret. Ce sujet explore des algorithmes ayant récemment permis de montrer la faiblesse de nombreuses clés utilisées par des sites web ou des routeurs.

1. Sujet (version 1.2). Changements par rapport à la version 1.1:
   en question 2, il n’y a que 9 facteurs premiers à trouver;
   les notations de la section 3 sont clarifiées.
   

2. Les fichiers pour la section 1.3 :
                       minicle.pub        minisecret.txt
   

3. Indications sur l’utilisation d’openssl.
   

4. Les listes de clés publiques, présentées comme des entiers :
   keys100.txt    keys1000.txt    keys10000.txt    keys100000.txt.
   

5. Version en développement des BigInteger, prise sur ce site.
   

6. Des indications pour dire à java de charger cette version, et des indications complémentaires si vous êtes en Windows.
   

7. Le fichier bigsecret.txt à découvrir.
   

8. Références bibliographiques :

1. •Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, New York, 2003.
   

2. •Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman, Mining your Ps and Qs: Detection of widespread weak keys in network devices, 21st Usenix Security Symposium, 2012.