Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Initiation ` a la cryptographie Correction TD de cryptographie no1 —ESIAL 2A TR

Initiation ` a la cryptographie Correction TD de cryptographie no1 —ESIAL 2A TRS— Introduction, concepts g´ en´ eraux Ce TD va permettre de revenir sur les notions de recherche exhaustive et de s’habituer ` a manipuler la cryptographie ` a cl´ e secr` ete et cl´ e publique. 1 Se familiariser avec les ordres de grandeur x Exercice 1. Mot de passe Un syst` eme est prot´ eg´ e par un mot de passe. Apr` es un essai infructueux le syst` eme attend 1s avant de redemander le mot de passe. Combien de temps faudra-t-il pour p´ en´ etrer le syst` eme dans les cas suivants : 1. le mot de passe est un pr´ enom ; 2. c’est un mot du dictionnaire ; 3. il est compos´ e de 4 chiﬀres ; 4. il fait 8 caract` eres. ! Correction : 1. L’INSEE publie la liste des 20000 pr´ enoms donn´ es en France depuis 1946. En pratique, seul un millier de pr´ enoms suﬃt ` a d´ esigner plus de la moiti´ e de la population fran¸ caise. Il faudrait ainsi, en moyenne moins de 17 minutes et dans le pire des cas moins de 5 heures et 30 minutes pour retrouver le mot de passe. 2. Le fran¸ cais compte environ 200000 mots dont seulement 3000 sont utilis´ es couramment, soit donc 2 jours et 8 heures au maximum et vraisemblablement moins de 50 minutes. 3. Il y 104 = 10000 mots de passe diﬀ´ erents constitu´ es de 4 chiﬀres, ce qui repr´ esente 2h et 45 minutes pour tous les tester. 4. Si il s’agit de 8 lettres minuscules, il faut : 268 s ≈6600 ann´ ees. Cependant si l’on s’autorise les minuscules, les majuscules, les chiﬀres et quinze signes de ponctuations : 778 s ≈4 · 106 ann´ ees. ! 1 x Exercice 2. La force brute Le facteur de travail d’un algorithme est le nombre d’instructions ´ el´ ementaires n´ ecessaire ` a son ex´ ecution. La puissance d’une machine est le nombre d’instructions qu’elle ex´ ecute par unit´ e de temps. Nous allons approximer la puissance d’un PC actuel ` a environ 2000 Mips (millions d’ins- tructions par seconde). Le facteur de travail d’un algorithme optimis´ e pour tester une cl´ e de 128 bits de l’algorithme AES est d’environ 1200 instructions ´ el´ ementaires. On dispose d’un couple clair/chiﬀr´ e connu et on d´ esire retrouver la cl´ e utilis´ ee par force brute, c’est-` a-dire en testant toutes les cl´ es les unes apr` es les autres. Une cl´ e est constitu´ ee d’un mot de 128 bits. On suppose que toutes les cl´ es sont ´ equiprobables. 1. En combien de temps une machine de 2000 Mips teste-t-elle une cl´ e ? 2. Combien y a-t-il de cl´ es possibles ? Quel est le nombre moyen de cl´ es ` a tester avant de trouver la bonne ? 3. ` A quel temps moyen de calcul cela correspond-il si on suppose qu’un seul PC eﬀectue la recherche ? Si les 1 milliard de PC de l’Internet sont mobilis´ es ` a cette tˆ ache ? ! Correction : 1. t = facteur de travail puissance = 1200 2000 = 0, 6µs. 2. Nbre de cl´ es possibles = 2128. On consid` ere les cl´ es possible comme ´ etant les entiers de 0 ` a 2128 −1, et la cl´ e secr` ete est not´ ee k. On a deux scenarios d’attaque par force brute possible. On note n = 2128. — Si on essaie tous les entiers les uns apr` es les autres. La probabilit´ e, pour un entier i donn´ e, d’avoir k = i (et donc d’avoir exactement i+1 tirages ` a eﬀectuer si on part de 0), est ´ egale ` a 1 n. L’esp´ erance du nombre d’essais est donc : n−1 X i=0 (i + 1) 1 n = n(n + 1) 2n ≈n 2 . — Si on eﬀectue un grand nombre de tirages al´ eatoires parmi 2128, on a une loi binomiale. Chaque tirage a une probabilit´ e de succ` es 1 n = p. La probabilit´ e qu’on trouve la cl´ e au bout de i tirages est : (1 −p)i−1p . On a donc l’esp´ erance du nombre de tirages n´ ecessaires : E = ∞ X i=1 i(1 −p)i−1p = pf ′(1 −p), o` u f(x) = 1 1−x. = p 1 (1 −(1 −p))2 = 1 p. 3. On use et abuse des approximations 103 = 1000 ≈210, 1jour = 216s, 1an = 29jour = 225secondes, etc. On calcule d’abord le nombre d’instructions calcul´ ees en un an ` a la fr´ equence de 2000 Mips. 2000 Mips.ann´ ees ≈2000 × 220 × 29 × 216 ≈245instructions, ≈211+20+9+16 ≈256. Le nombre d’instructions ` a eﬀectuer pour trouver la cl´ e est : 1200 × 2127 ≈2138. Soit un temps de ≈2138−56 ≈281 ann´ ees (ou, en base 10 : 2 × (210)8 ≈2 × 1024). Les un milliard (≈230) de PC d’Internet permettent de gagner un facteur 230, ou 109. Soit quelque chose comme 2 × 1015 ann´ ees, soit un petit million de fois l’ˆ age de l’univers. ! 2 x Exercice 3. La loi de Moore Il est admis que, grˆ ace aux progr` es technologiques permanents, la puissance des machines double en moyenne tous les 18 mois (loi empirique de Moore). On suppose maintenant que l’on change les machines tous les mois en commen¸ cant avec une machine d’une puissance de 1000 Mips. Pour tout entier n, on note Wn le nombre d’instructions ex´ ecut´ ees par la machine du mois n. 1. Quel est le facteur d’am´ elioration a de la puissance des machines d’un mois ` a l’autre ? 2. Calculer W0, puis Wn en fonction de W0, de a et de n. 3. Quel est le temps moyen n´ ecessaire pour trouver la cl´ e de l’exercice pr´ ec´ edent avec une machine chang´ ee tous les mois ? ! Correction : 1. On a d’un part Wn+1 = aWn et la loi de Moore nous indique que Wn+18 = a18 · Wn = 2Wn. On en d´ eduit donc que a = 18 √ 2. 2. L’hypoth` ese est que la machine a une fr´ equence de 1000 Mips (230 par seconde), donc en un mois (25 jours de 216 secondes, en gros), ¸ ca fait 251 instructions. En outre on a : Wn = anW0. 3. Au bout de n mois, le nombre d’instructions Sn eﬀectu´ e est W0 + · · · + Wn−1, soit : Sn = W0(1 + a + · · · + an−1), = 251 an −1 a −1 . Pour que Sn d´ epasse le nombre d’instructions ` a eﬀectuer, qui est (2127 × 211 = 2138), il faut une estimation ` a la louche de a −1. ` A la calculatrice on obtient a −1 ≈ 1 25. On vise donc : an −1 ≈2138−51 × (a −1), ≈287 25 ≈282, n ≈82 log 2 log a , ≈82 × 18 ≈123 ann´ ees. Ce qui est tr` es tr` es loin du temps calcul´ e ` a l’exercice pr´ ec´ edent. Il faut penser ` a rajouter qu’on a donc besoin de changer 1476 fois d’ordinateurs. ! 2 Fonctions de hachage x Exercice 4. Le buzz free mobile Aujourd’hui 6 janvier 2012, les geeks s’agitent pour savoir si les forfaits de la marque Free Mobile seront lanc´ es aujourd’hui, demain, ` a Pˆ aques, o` u ` a la Saint-Glinglin. Pour amuser la galerie, le site live.free.fr contient un dessin de fus´ ee, avec les symboles : efb7929e6a5b7dcc6ebb79aa3c45af13. Cette valeur est ce que renvoie la fonction de hachage md5 sur la donn´ ee ≪jesaispas≫. Des petits malins y voient aussi un second message cach´ e en in- terpr´ etant la chaˆ ıne efb7929e6a5b7dcc6ebb79aa3c45af13 dans le codage ascii. On y lirait ≪NIEL JOIN RACE >>START≫: 3 1. Est-il plausible de parvenir ` a fabriquer un message intelligible (si tant est que celui-ci le soit !) dans le hach´ e d’un message intelligible qu’on passe ` a une fonction de hachage ? ! Correction : 1. Non pas du tout. Il n’est pas possible de faire sortir ce qu’on d´ ecide ` a la fonction de hachage. Inverse- ment, ´ etant donn´ e une ´ ecriture, si cryptique soit-elle, d’un message cach´ e qu’on voudrait mettre dans la valeur de hachage, il est impossible de trouver un ant´ ec´ edent. ! 3 Cl´ e secr` ete x Exercice 5. C´ esar / Vig´ en` ere Le chiﬀrement de C´ esar prend un texte compos´ e de lettres, et d´ ecale chaque lettre d’un nombre constant de positions dans l’alphabet. Ce nombre de positions est la cl´ e. Pour d´ eterminer la cl´ e ` a partir d’un message chiﬀr´ e, on fait des suppositions statistiques sur le message d’entr´ ee. Par exemple, si uploads/Industriel/ td-corrige-crypto 1 .pdf