cours-maths

Sujets

• informatique

Informations

• Publié par: Hamef
• Nombre de lectures: 40
• Langue: Français

Extrait

Math´ematiques
pour
l’informatique
IUP NTIE M2
2006–2007
Yannick Chevalier
[e-mail]
12Table des mati`eres
1 Introduction 4
1.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Chiffrement par blocs . . . . . . . . . . . . . . . . . . . . 5
1.2 Quelques attaques... . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Attaques de petit exposant . . . . . . . . . . . . . . . . . 5
1.2.2 RSA pour la signature . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Attaque sur SSL/TLS . . . . . . . . . . . . . . . . . . . . 7
1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 D´efinitions 9
2.1 Probabilit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
´2.1.1 Ev´enements n´egligeables . . . . . . . . . . . . . . . . . . . 10
2.2 Machines de Turing probabilistes avec Oracle . . . . . . . . . . . 10
2.2.1 Machines de Turing . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Machines de Turing probabilistes . . . . . . . . . . . . . . 11
2.2.3 Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Quelques probl`emes difficiles 13
3.1 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Calcul de racine carr´ees et r´esidus quadratiques . . . . . . . . . . 13
3.2.1 Symbole de Jacobi. . . . . . . . . . . . . . . . . . . . . . . 14
3.2.2 Lien avec la factorisation. . . . . . . . . . . . . . . . . . . 15
3.3 RSAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 S´ecurit´e s´emantique – Indistinguabilit´e 17
4.1 Exemple : le bureau de vote . . . . . . . . . . . . . . . . . . . . . 17
4.2 Jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 S´ecurit´e s´emantique . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.4 Indistinguabilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.5 Avantage par rapport a` un chiffrement . . . . . . . . . . . . . . . 21
35 Crit`eres de s´ecurit´e de primitives 22
5.1 Note sur les fonctions de hachage . . . . . . . . . . . . . . . . . . 22
5.2 Chiffrement asym´etrique . . . . . . . . . . . . . . . . . . . . . . . 23
5.2.1 Robustesse . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2.2 Le premier algorithme IND-CPA . . . . . . . . . . . . . . 24
5.3 Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.3.1 Sch´ema de signature . . . . . . . . . . . . . . . . . . . . . 25
5.3.2 Niveaux de s´ecurit´e . . . . . . . . . . . . . . . . . . . . . 25
5.3.3 Capacit´es de l’attaquant . . . . . . . . . . . . . . . . . . . 26
5.3.4 Exemples de sch´emas de signature (bas´es sur RSA) . . . . 26
5.4 Chiffrement sym´etrique . . . . . . . . . . . . . . . . . . . . . . . 27
4Chapitre 1
Introduction
Commentaires: L’analyse de la s´ecurit´e des informations est
un domaine tr`es large, qui va des pare-feux a` la d´efinition d’une
politique de confidentialit´e. Dans ce cours, nous allons nous pla-
cer a` un niveau interm´ediaire, celui de la transmission confidentielle
de donn´ees `a travers un r´eseau non s´ecuris´e. Pour une vision plus
g´en´erale, je conseille la lecture (en anglais) du document :
http://csrc.nist.gov/publications/nistpubs/800-12/
800-12-html/index.html
Dans ce chapitre, nous allons voir 3 exemples d’attaques sur des
protocoles a priori surs.ˆ Ces attaques sont vari´ees, et servent a` illus-
trer les probl`emes contre lesquels on veut se pr´emunir.
1.1 Rappels
1.1.1 RSA
La g´en´eration de couples clef publique/clef priv´ee pour le chiffrement RSA
peut ˆetre d´ecrit de la mani`ere suivante :
1. Choisir deux grands entiers p et q premiers, et calculer N =p·q;
2. Calculer φ(N) = (p−1)·(q−1), le nombre d’´el´ements premiers avec N
et inf´erieurs a` N ;
3. Choisirdeuxentierseetdinf´erieursa`N telsquepourtoutnombrem<N
e don ait (m ) =m(N). La clef publique sera e et la clef priv´ee d.
e d e·dOn voit rapidement que (m ) = m(N) est ´equivalent a` m = m(N). Le
principe de RSA repose sur le constat suivant :
– si on connaˆıt φ(N), il est facile de calculer e en fonction d’un d arbitraire
ou d a` partir d’un e arbitraire;
– on ne connaˆıt pas d’algorithme permettant de calculer d en fonction de e
et N plus rapidement qu’en calculant d’abord φ(N).
51.1.2 Chiffrement par blocs
Il y a deux types de chiffrement par blocs, ECB et CBC. On dispose d’un
algorithme de chiffrement qui ne peut chiffrer que des messages de taille≤ N
octets.Lechiffrementparblocs´epareunmessagea`envoyerenblocsdeN octets.
Le message effectivement envoy´e est ensuite reconstruit `a partir de ces blocs.
ECB (Electronic Code Book). On suppose que le message a` envoyer est
compos´e des blocs x ,...,x . Pour i = 1,...,N, on calcule y = Enc (x ), et1 N i K i
on envoie le message y|...|y .1 N
CBC (Cipher Block Chaining). On suppose que le message a` envoyer est
compos´edesblocsx ,...,x .Oncommenceparfixerunvecteurd’initialisation1 N
IV = y de la taille d’un bloc chiffr´e. Pour i = 1,...,N, on calcule ensuite0
y = Enc (y ⊕x ), et on envoie le message y|...|y . L’op´eration⊕ est lei K i−1 i 1 N
`ou exclusif bit `a bit (xor) entre deux messages. A noter qu’il faut que la taille
d’un chiffr´e soit ´egale a` la taille d’un texte clair a` cause du xor.
Exercice 1 : CBC
Q1. Donner un algorithme pour d´ecoder un message recu.¸
Commentaires. Si un attaquant connaˆıt la structure d’un message chiffr´e,
avec le chiffrement ECB, il peut r´eorganiser les blocs a` sa guise pour former de
nouveaux messages. Pour le chiffrement CBC, l’attaquant peut juste extraire
un pr´efixe d’un message chiffr´e, qui forme lui aussi un message valide.
1.2 Quelques attaques...
1.2.1 Attaques de petit exposant
Une pratique courante, pour les algorithmes de g´en´eration de clefs, a ´et´e de
choisir, pour rendre le chiffrement plus rapide (cf. exponentiation rapide), un e
premier ayant peu de bits `a 1, et si possible des bits de poids faible. Les choix
1 0 4 0 16 0´evidents sont 3 = 2 +2 , 17 = 2 +2 , voire 65537 = 2 +2 . En cons´equence,
plusieurs algorithmes de g´en´eration de clefs choisissaient toujours la mˆeme clef
publique, 3.
Ce choix conduit a` un probl`eme lorsqu’un mˆeme message m est envoy´e `a au
moins trois personnes A , A et A ayant le mˆeme exposant publique 3, avec1 2 3
des modulesN ,N etN . Lors de l’envoi, un attaquant voit passer 3 messages,1 2 3
3 3 3m (N ),m (N ) etm (N ). En utilisant le th´eor`eme chinois, il peut en d´eduire1 2 3
3m (N ·N ·N ). Mais comme m est plus petit que chaque module N , on a1 2 3 i
3 3m < N ·N ·N . Donc la racine cubique dans Z de m (N ·N ·N ), qui1 2 3 1 2 3
3peut ˆetre facilement calcul´ee, est aussi la racine cubique dans Z de m (pas de
6modulo!), donc m. Conclusion : il est possible de d´echiffrer un message envoy´e
a` plusieurs personnes.
Exercice 2 : D´ecodage sans clef priv´ee A, B et C ont pour
clef publique RSA (3,343633073743)(3,474256143577) et (3,558458718989). Le
texte est chiffr´e par bloc (mode ECB) de 4 octets et chaque octet est le code
ascii d’un caract`ere. Un attaquant voit passer les messages :
– pour A : 39803337908, 110247087493, 216688969176, 181926583795;
– pour B : 333376184945, 56006607557, 251479715129, 306590004534;
– pour C : 286403902706, 274977199138, 222814260414, 443600837760;
Q1. Enutilisant,dansmaple,chremetroot[3],donnezlesclairstransmis.
Q2. En utilisant le programme de d´econversion :
http://www.irit.fr/~Yannick.Chevalier/NTIE/deconvertisseur.c
donnez le message transmis a` A, B et C.
1.2.2 RSA pour la signature
On (vous) a vu que RSA pouvait aussi ˆetre utilis´e pour signer des messages,
en chiffrant avec la clef priv´ee. Il y a cependant plusieurs d´efauts :
– en connaissant la clef publique, il est possible de forger de nouvelles signa-
tures, mais on ne maˆıtrise pas du tout le message sign´e;
– il est possible de fabriquer de nouvelles signatures a` partir de signatures
connues, mais avec un contrˆole assez faible sur le contenu envoy´e;
– Il est possible de fabriquer un message m tel qu’on peut d´eduire de la
0 0signature de m la signature d’un autre message m , avec m choisit arbi-
trairement.
Exercice 3 : (Optionnel)
Q1. Pour chacun des cas ´enum´er´es, indiquer comment faire...
Chacun de ces points correspond a` une faiblesse possible d’un algorithme
de chiffrement. On remarque que pour le dernier, l’intrus a` une condition plus
compliqu´ee `a remplir, il doit r´eussir `a faire signer le message m pour obtenir
0m .
Il faut faire un peu attention pour le chiffrement, on ne rencontrera pas
exactement les mˆemes conditions : n’importe qui est capable de fabriquer un
message chiffr´e, le probl`eme est de reconnaˆıtre le texte contenu dans un chiffr´e.
71.2.3 Attaque sur SSL/TLS
1Cetteattaque estdiff´erentedespr