Cryptographie Générale

Dernière màj: 05/06/2010

Un rapport sur la cryptographie (chiffrement symétrique et asymétrique, hashage cryptographique) et les fondements mathématiques associés.
Plusieurs notions préliminaires sont introduites pour une meilleure compréhension (probabilités, théorie des ensembles, groupes/anneaux/corps, mesure de l'entropie) ainsi que le vocabulaire spécifique.

Le contenu du document comprend principalement une analyse détaillée (mathématique et informatique) des algorithmes suivants :

• Chiffrement symétrique : Vernam, DES, AES
• Chiffrement asymétrique : RSA, El Gamal
• Fonctions de hashage : MD5, SHA1

Le document a été rédigé en 2009, si vous remarquez des erreurs merci de me contacter. J'espère bien un jour avoir un peu de temps pour l'actualiser, notamment avec le chiffrement à base de courbes elliptiques, l'algorithme d'échange de clé Diffie-Hellman et les fonctions de hashage SHA256, SHA512 et Whirlpool.

Document principal : media/cryptographie_mathreport.pdf
Annexes : media/cryptographie_mathreport_annexes.pdf
Présentation : media/cryptographie_mathreport_presentation.ppt

Générateurs de nombre pseudo-aléatoires

« La génération de nombres aléatoires est trop importante pour être confiée au hasard. »
Robert R. Coveyou

Un rapport sur la génération de nombre pseudo-aléatoires (PRNG : Pseudo-Random Number Generator), c'est à dire les techniques pour produire des suites de nombres “au hasard”, ce hasard étant par définition imparfait du fait des algorithmes déterministes employés.

• Le document décrit un certain nombre de généralités sur les PRNG et présente plusieurs formes de générateur à congruence linéaire/matricielle (LFSR, GFSR, TGFSR et Mersenne Twister). Ces générateurs sont très rapide mais ne sont cependant pas suffisamment aléatoire pour être utilisés en cryptographie. Les nombres aléatoires sont en effet la base de tout système cryptographique, si le générateur n'est pas sûr (i.e., si les prochains nombres peuvent être devinés à l'avance) alors le chiffrement est compromis.
• Deux PRNG cryptographiques sont exposés dans la suite du document : Blum Blum Shub et Blum-Micali (qui utilise le même principe que le chiffrement El Gamal (voir rapport technique sur le chiffrement).
• Dans une seconde partie, le document décrit plusieurs méthodes mathématiques pour l'analyse de la qualité des PRNG (analyse de la distribution, test spectral, test du X², test de Monte Carlo, etc.).

Le document a été rédigé en 2010, si vous remarquez des erreurs merci de me contacter. Certaines parties mériteraient d'être retravaillée (ce que j'espère pouvoir faire un jour) et je voudrais compléter le document avec d'autres algorithmes, comme Fortuna. Il serait aussi intéressant de parler du cas de Dual_EC_DRBG, un PRNG dans lequel la NSA avait introduit une backdoor.

Document principal : media/prng_mathreport.pdf
Présentation : media/prng_mathreport_presentation.pptx