cours-maths

Math´ematiquespourl’informatiqueIUP NTIE M22006–2007Yannick Chevalierychevali@irit.fr12Table des mati`eres1 Introduction 41.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.1 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Chiffrement par blocs . . . . . . . . . . . . . . . . . . . . 51.2 Quelques attaques... . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.1 Attaques de petit exposant . . . . . . . . . . . . . . . . . 51.2.2 RSA pour la signature . . . . . . . . . . . . . . . . . . . . 61.2.3 Attaque sur SSL/TLS . . . . . . . . . . . . . . . . . . . . 71.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 D´efinitions 92.1 Probabilit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9´2.1.1 Ev´enements n´egligeables . . . . . . . . . . . . . . . . . . . 102.2 Machines de Turing probabilistes avec Oracle . . . . . . . . . . . 102.2.1 Machines de Turing . . . . . . . . . . . . . . . . . . . . . 102.2.2 Machines de Turing probabilistes . . . . . . . . . . . . . . 112.2.3 Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Quelques probl`emes difficiles 133.1 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Calcul de racine carr´ees et r´esidus quadratiques . . . . . . . . . . 133.2.1 Symbole de Jacobi. . . . . . . . . . . . . . . . . . . . . . . 143.2.2 Lien avec la factorisation. . . . . . . . . . . . . . . ...