Cayrel TD [PDF]

Zitiervorschau

1 Pierre-Louis CAYREL www.cayrel.net

Protection de l’information - 61 exercices corrigés

1 / 63

2

Table des matières 1 Énoncés 1.1 Ordres de grandeur . . . . . . . . . . . . . . . . . 1.1.1 Mot de passe . . . . . . . . . . . . . . . . 1.1.2 Dénombrements . . . . . . . . . . . . . . . 1.1.3 Vider l’océan avec un dé à coudre . . . . . 1.1.4 La force brute . . . . . . . . . . . . . . . . 1.1.5 La loi de Moore . . . . . . . . . . . . . . . 1.2 Vigénère, Polybe et Hill . . . . . . . . . . . . . . 1.2.1 César/Vigénère . . . . . . . . . . . . . . . 1.2.2 Chiffrement de Vigénère . . . . . . . . . . 1.2.3 Chiffrement de Polybe . . . . . . . . . . . 1.2.4 Chiffrement affine . . . . . . . . . . . . . . 1.2.5 Chiffrement de Hill . . . . . . . . . . . . . 1.3 Chiffrement et modes de chiffrement . . . . . . . 1.3.1 Cryptographie à clé secrète . . . . . . . . . 1.3.2 Amélioration d’un système de chiffrement 1.3.3 Mode ECB . . . . . . . . . . . . . . . . . 1.3.4 Mode CBC . . . . . . . . . . . . . . . . . 1.3.5 Mode CTR . . . . . . . . . . . . . . . . . 1.3.6 Attaque par insertion . . . . . . . . . . . . 1.3.7 Malléabilité des chiffrements à flot . . . . . 1.3.8 3DES et 2DES . . . . . . . . . . . . . . . 1.3.9 Algorithme de Berlekamp-Massey . . . . . 1.4 Méthodes de calcul . . . . . . . . . . . . . . . . . 1.4.1 Square and Multiply . . . . . . . . . . . . 1.4.2 Calcul modulaire . . . . . . . . . . . . . . 1.4.3 Théorème des restes chinois . . . . . . . . 1.4.4 Autour des nombres premiers . . . . . . . 1.4.5 Test de primalité de Miller-Rabin . . . . . 1.4.6 Algorithme p − 1 de Pollard . . . . . . . . 1.4.7 Théorème de Wilson . . . . . . . . . . . . 1.5 Échange de clefs . . . . . . . . . . . . . . . . . . . 1.5.1 Fonctionnement clé privée vs clé publique 1.5.2 Clé privée vs clé publique . . . . . . . . . 1.5.3 Diffie-Hellman . . . . . . . . . . . . . . . . 1.5.4 Perte d’une clé privée . . . . . . . . . . . . 1.5.5 Attaque par le milieu de Diffie-Hellman . . 1.6 Chiffrement . . . . . . . . . . . . . . . . . . . . . 1.6.1 Kid-RSA . . . . . . . . . . . . . . . . . . . 3

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 7 7 7 7 8 8 8 9 9 9 10 11 11 11 11 12 12 12 13 13 13 15 15 15 15 17 17 17 17 18 18 18 18 18 18 19 19

4

TABLE DES MATIÈRES 1.6.2 Chiffrement/Déchiffrement RSA . . . . . . . . . 1.6.3 Exemples de RSA . . . . . . . . . . . . . . . . . 1.6.4 Chiffrement RSA . . . . . . . . . . . . . . . . . 1.6.5 RSA-3 . . . . . . . . . . . . . . . . . . . . . . . 1.6.6 Chiffrement El Gamal . . . . . . . . . . . . . . 1.6.7 Changement de clés . . . . . . . . . . . . . . . . 1.7 Attaques sur RSA . . . . . . . . . . . . . . . . . . . . . 1.7.1 Attaque par module commun . . . . . . . . . . 1.7.2 De φ(n) à la factorisation . . . . . . . . . . . . 1.7.3 RSA avec deux facteurs trop proches . . . . . . 1.7.4 Malléabilité de RSA . . . . . . . . . . . . . . . 1.7.5 Le temps de factorisation des grands entiers . . 1.8 Signature et hachage . . . . . . . . . . . . . . . . . . . 1.8.1 Signature RSA . . . . . . . . . . . . . . . . . . 1.8.2 Signature aveugle avec RSA . . . . . . . . . . . 1.8.3 Signature El Gamal . . . . . . . . . . . . . . . . 1.8.4 Signature El Gamal : utilisation de l’aléa . . . . 1.8.5 Signature El Gamal sans vérification modulaire 1.8.6 Signature GHR (Gennaro-Halevi-Rabin) . . . . 1.9 Hachage . . . . . . . . . . . . . . . . . . . . . . . . . . 1.9.1 Fonction de hachage faiblement sans collision . 1.9.2 Fonction de hachage et signature . . . . . . . . 1.9.3 Le buzz free mobile . . . . . . . . . . . . . . . . 1.10 Authentification . . . . . . . . . . . . . . . . . . . . . . 1.10.1 Authentification à clef secrète . . . . . . . . . . 1.10.2 Authentification à clef publique . . . . . . . . . 1.10.3 Schéma de Schnorr . . . . . . . . . . . . . . . . 1.11 PKI, Certificats . . . . . . . . . . . . . . . . . . . . . . 1.11.1 PKI . . . . . . . . . . . . . . . . . . . . . . . . 1.11.2 Certificats . . . . . . . . . . . . . . . . . . . . . 1.11.3 Distinguer les clefs utilisées dans PGP . . . . . 1.11.4 Hachés de mots de passe . . . . . . . . . . . . . 1.11.5 Le protocole HTTPS . . . . . . . . . . . . . . . 1.11.6 La carte bleue . . . . . . . . . . . . . . . . . . .

2 Corrections 2.1 Pour se familiariser avec les ordres de grandeur 2.1.1 Mot de passe . . . . . . . . . . . . . . . 2.1.2 Dénombrements . . . . . . . . . . . . . . 2.1.3 Vider l’océan avec un dé à coudre . . . . 2.1.4 La force brute . . . . . . . . . . . . . . . 2.1.5 La loi de Moore . . . . . . . . . . . . . . 2.2 Vigénère, Polybe et Hill . . . . . . . . . . . . . 2.2.1 César/Vigénère . . . . . . . . . . . . . . 2.2.2 Chiffrement de Vigénère . . . . . . . . . 2.2.3 Chiffrement de Polybe . . . . . . . . . . 2.2.4 Chiffrement affine . . . . . . . . . . . . . 2.2.5 Chiffrement de Hill . . . . . . . . . . . . 2.3 Chiffrement et modes de chiffrement . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 19 20 20 21 21 22 22 22 22 23 23 24 24 24 24 24 25 25 26 26 26 26 27 27 27 28 29 29 29 29 29 30 30

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

31 31 31 31 31 32 32 34 34 34 34 34 35 36

TABLE DES MATIÈRES

5

2.3.1 Cryptographie à clé secrète . . . . . . . . . . . . 2.3.2 Amélioration d’un système de chiffrement . . . 2.3.3 Mode ECB . . . . . . . . . . . . . . . . . . . . 2.3.4 Mode CBC . . . . . . . . . . . . . . . . . . . . 2.3.5 Mode CTR . . . . . . . . . . . . . . . . . . . . 2.3.6 Attaque par insertion . . . . . . . . . . . . . . . 2.3.7 Malléabilité des chiffrements par flot . . . . . . 2.3.8 3DES et 2DES . . . . . . . . . . . . . . . . . . 2.3.9 Algorithme de Berlekamp-Massey . . . . . . . . 2.4 Méthodes de calcul . . . . . . . . . . . . . . . . . . . . 2.4.1 Square and Multiply . . . . . . . . . . . . . . . 2.4.2 Calcul modulaire . . . . . . . . . . . . . . . . . 2.4.3 Théorème des restes chinois . . . . . . . . . . . 2.4.4 Autour des nombres premiers . . . . . . . . . . 2.4.5 Test de primalité de Miller-Rabin . . . . . . . . 2.4.6 Algorithme p − 1 de Pollard . . . . . . . . . . . 2.4.7 Théorème de Wilson . . . . . . . . . . . . . . . 2.5 Échange de clefs . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Fonctionnement clé privée vs clé publique . . . 2.5.2 Clé privée vs clé publique . . . . . . . . . . . . 2.5.3 Perte d’une clé privée . . . . . . . . . . . . . . . 2.5.4 Diffie-Hellman . . . . . . . . . . . . . . . . . . . 2.5.5 Attaque par le milieu de Diffie-Hellman . . . . . 2.6 Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Kid-RSA . . . . . . . . . . . . . . . . . . . . . . 2.6.2 Chiffrement/Déchiffrement RSA . . . . . . . . . 2.6.3 Exemple de RSA . . . . . . . . . . . . . . . . . 2.6.4 Chiffrement RSA . . . . . . . . . . . . . . . . . 2.6.5 RSA-3 . . . . . . . . . . . . . . . . . . . . . . . 2.6.6 Chiffrement El Gamal . . . . . . . . . . . . . . 2.6.7 Changement de clés . . . . . . . . . . . . . . . . 2.7 Attaques sur RSA . . . . . . . . . . . . . . . . . . . . . 2.7.1 Attaque par module commun . . . . . . . . . . 2.7.2 De φ(n) à la factorisation . . . . . . . . . . . . 2.7.3 RSA avec deux facteurs trop proches . . . . . . 2.7.4 Malléabilité de RSA . . . . . . . . . . . . . . . 2.7.5 Le temps de factorisation des grands entiers . . 2.8 Signature . . . . . . . . . . . . . . . . . . . . . . . . . 2.8.1 Signature RSA . . . . . . . . . . . . . . . . . . 2.8.2 Signature aveugle avec RSA . . . . . . . . . . . 2.8.3 Signature El Gamal . . . . . . . . . . . . . . . . 2.8.4 Signature El Gamal : utilisation de l’aléa . . . . 2.8.5 Signature El Gamal sans vérification modulaire 2.8.6 Signature GHR (Gennaro-Halevi-Rabin) . . . . 2.9 Hachage . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9.1 Fonction de hachage faiblement sans collision . 2.9.2 Fonction de hachage et signature . . . . . . . . 2.9.3 Le buzz free mobile . . . . . . . . . . . . . . . . 2.10 Authentification . . . . . . . . . . . . . . . . . . . . . . 5 / 63

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36 36 36 36 37 37 37 38 39 40 40 40 40 41 42 42 43 44 44 44 44 44 45 46 46 46 47 48 49 51 51 52 52 52 52 53 53 54 54 54 55 55 56 56 57 57 57 57 58

6

TABLE DES MATIÈRES 2.10.1 Authentification à clef secrète . . . . . 2.10.2 Authentification à clef publique . . . . 2.10.3 Schéma de Schnorr . . . . . . . . . . . 2.11 PKI, certificats . . . . . . . . . . . . . . . . . 2.11.1 PKI . . . . . . . . . . . . . . . . . . . 2.11.2 Certificats . . . . . . . . . . . . . . . . 2.11.3 Distinguer les clefs utilisées dans PGP 2.11.4 Hachés de mots de passe . . . . . . . . 2.11.5 Le protocole HTTPS . . . . . . . . . . 2.11.6 La carte bleue . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

Ces exercices ont été inspirés par les supports de cours/TD de : • • • • •

Didier Alquié Christine Bacchoc Florent Bernard Emmanuel Bresson Céline Chevalier

• • • • •

Philippe Gaborit Arthur Hecker Jean Leneutre Philippe Oechslin Rodolphe Ortalo

• Nouha Oualha • Emmanuel Thomé • Damien Vergnaud

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

58 58 58 59 59 59 59 60 60 61

Chapitre 1 Énoncés Cryptographie à clef secrète 1.1 1.1.1

Ordres de grandeur Mot de passe

Un système est protégé par un mot de passe, après un essai infructueux le système attend 1s avant de redemander. Combien de temps faudra-t-il pour s’identifier dans les cas suivants : 1. le mot de passe est un prénom 1 ;

3. il est composé de 4 chiffres ;

2. c’est un mot du dictionnaire 2 ;

4. il fait 8 caractères.

1.1.2

Dénombrements

Le nombre de clés disponibles dans un système de chiffrement donne une borne maximale de sa sécurité (mesure de la complexité d’une recherche exhaustive). 1. Quel est le nombre de clés possibles dans un chiffrement de César ? 2. Pour un chiffrement affine ? (C(x) = ax + b mod 26 pour chaque caractère x ∈ Z26 ) 3. Pour un chiffrement par substitution (substitution arbitraire, caractère par caractère) ? 4. Pour un chiffrement de Vigénère (avec une clé de longueur k) ?

1.1.3

Vider l’océan avec un dé à coudre

On considère qu’un dé à coudre est un cylindre de 1, 5 cm. de hauteur pour 1, 5 cm de diamètre. Selon l’Institut Français des Mers, les océans couvrent 360 millions de km2 avec une profondeur moyenne de 3800 m. Encadrer entre deux puissances de 2 consécutives le nombre de dés à coudre d’eau que contiennent les océans.

1.1.4

La force brute

Le facteur de travail d’un algorithme est le nombre d’instructions élémentaires nécessaire à son exécution. La puissance d’une machine est le nombre d’instructions qu’elle exécute par unité 1. L’INSEE publie la liste des 20 000 prénoms donnés en France depuis 1946. En pratique, seul un millier de prénoms suffit à désigner plus de la moitié de la population française. 2. Le français compte environ 200 000 mots dont seulement 3000 sont utilisés couramment.

7

8

CHAPITRE 1. ÉNONCÉS

de temps. La puissance d’un PC actuel est d’environ 2000 Mips. (millions d’instructions par secondes). Le facteur de travail d’un algorithme optimisé pour tester une clé de 128 bits de l’algorithme AES est d’environ 1200 instructions élémentaires. On dispose d’un couple clair/chiffré connu et on désire retrouver la clé utilisée par force brute, c’est- à-dire en testant toutes les clés les unes après les autres. Une clé est constituée d’un mot de 128 symboles binaires. On suppose que toutes les clés sont équiprobables. 1. En combien de temps une machine de 2000 Mips teste-t-elle une clé ? 2. Combien y a-t-il de clés possibles ? Quel est le nombre moyen de clés à tester avant de trouver la bonne ? 3. À quel temps moyen de calcul cela correspond-il si on suppose que le milliard de PC de l’internet sont mobilisés à cette tâche ?

1.1.5

La loi de Moore

Il est admis que, grâce aux progrès technologiques permanents, la puissance des machines double en moyenne tous les 18 mois (loi de Moore). On suppose maintenant que l’on change les machines tous les mois (30 jours) en commençant avec une machine d’une puissance de 1000 Mips. Pour tout entier n, on note Wn le nombre d’instructions exécutées par la machine du mois n. 1. Quel est le facteur d’amélioration a de la puissance des machines d’un mois à l’autre ? 2. Calculer W0 , puis Wn en fonction de W0 , de a et de n. 3. Quel est le temps moyen nécessaire pour trouver la clé (de l’exercice précédent) ?

1.2 1.2.1

Vigénère, Polybe et Hill César/Vigénère

Le chiffrement de César prend un texte composé de lettres, et décale chaque lettre d’un nombre constant de positions dans l’alphabet. Ce nombre de positions est la clé. Pour déterminer la clé à partir d’un message chiffré, on fait des suppositions statistiques sur le message d’entrée. Par exemple, si on suppose que le message est en français, la lettre la plus fréquente est le e. Par ordre décroissant de fréquence, on trouve : e, s, a, i, t, n, r, u. 1. Est-il plus facile de déchiffrer un texte long ou un texte court ? 2. Pouvez-vous déchiffrer le message suivant : pwpnetzyacpdtopyetpwwp Le chiffrement de Vigénère (en fait du à Alberti au XVème siècle) est une sorte de César amélioré. La clé est constituée non pas d’un, mais de plusieurs décalages. Cette clé est spécifiée sous forme d’un mot qui constitue la clé. Par exemple la clé bac, de longueur trois, spécifie que pour chiffré un message, on décale la première lettre d’une position (lettre b), la deuxième de zéro positions (lettre a), la troisième de deux positions (lettre c), et ainsi de suite en reprenant la clé au début. 3. Si l’attaquant obtient la connaissance d’un couple message clair / message chiffré, peut-il déchiffrer tous les messages chiffrés ensuite avec cette même clé ? 4. On suppose que seulement un message chiffré est à disposition de l’attaquant. Si un attaquant connaît la longueur de la clé, comment faire pour déchiffrer ?

1.2. VIGÉNÈRE, POLYBE ET HILL

9

5. D’une manière générale, ce système de chiffrement est-il difficile à casser ?

1.2.2

Chiffrement de Vigénère

1. Chiffrer à l’aide de l’algorithme de Vigénère le texte suivant : textesecretadecoder en utilisant comme clé le mot crypto ; 2. Pour le même texte clair on obtient le texte chiffré suivant brqksmzcspxiqxtcxzr. Quelle est la clé ? 3. Même question si le chiffré est aaabbbcccdddeeefffg. Que remarque-t-on ?

1.2.3

Chiffrement de Polybe

On considère l’alphabet privé du W, soit 25 lettres. Polybe a proposé le mécanisme suivant : on range les lettres dans un tableau 5 × 5, en commençant par le mot clé (et en supprimant les doublons), puis on continue avec les lettres restantes de l’alphabet, dans l’ordre. Par exemple, avec le mot-clé MYSTERE, on construit le tableau suivant :

1 2 3 4 5

1 M R F K Q

2 Y A G L U

3 S B H N V

4 T C I O X

5 E D J P Z

Le chiffrement s’effectue alors en remplaçant chqaue lettre par les deux chiffres : ligne colonne qui indiquent sa position dans la grille . Par exemple, F est chiffré 31. 1. Expliquer comment on peut cryptanalyser un tel système : par une attaque à clair connu, puis dans une attaque simple (seulement un chiffré). Raoul envoie un message à Anna pour lui fixer rendez-vous. Le cryptogramme est le suivant : 123222 322252

512215 512211

424215 515222

512242 532251

242255 142251

534352 154352

111524 225254 21

2. Décrypter ce message. Quelle est la sévérité de l’attaque (distinguer le chiffré d’un aléa, cassage total,. . .) ?

1.2.4

Chiffrement affine

1. On représente l’alphabet latin par les entiers entre 0 et 25 avec la convention A = 0, B = 1, C = 2, . . . Un chiffrement affine x 7→ ax+b mod 26 transforme le message CRYPTO en le cryptogramme ROXEYZ. Trouver la clé (a, b)correspondante. 2. Le message clair CRYPTO a cette fois été chiffré deux fois de suite par un chiffre affine de clé (a0 , b0 ) (c’est-à-dire qu’on a chiffré le chiffré) pour donner en sortie NGBAMX. (a) Montrer que NGBAMX est le chiffré de CRYPTO par un chiffre affine de clé (a00 , b00 ). Trouver (a00 , b00 ).

9 / 63

10

CHAPITRE 1. ÉNONCÉS

1.2.5

Chiffrement de Hill

Examen 2012-2013 Dans le chiffrement de Hill, chaque lettre de l’alphabet est représentée par un entier compris entre 0 et 25. L’algorithme est un chiffrement par blocs de m lettres, qui transforme un bloc (x1 , x2 , . . . , xm ) en un bloc (y1 , y2 , . . . , ym ) défini par la relation algébrique : (y1 , y2 , . . . , ym ) = (x1 , x2 , . . . , xm ) · A où A est une matrice carrée d’ordre m à coefficients dans Z26 , tous les calculs sont effectués modulo 26.   5 1 Par exemple avec m = 2 et A = , le message (10, 21) est chiffré en : 12 3 (10, 21) · A = (10 × 5 + 21 × 12, 10 + 21 × 3) = (16, 21). Sachant que le chiffrement du mot chiffrement avec la même clé donne le chiffré jvfrtqealv. Décrypter (partiellement, les 4 premiers caractères suffiront) le texte suivant qui a été obtenu en appliquant le chiffrement de Hill sur des blocs de taille 2 sur un mot de la langue française : gzatzxjihvbreosu 4pts Indications :   a b Posons : M = ∈ M4 (Z26 ) la matrice à utiliser pour le déchiffrement. c d Le fait que M transforme  le bigramme   jven le bigramme ch et le bigramme fr en le bigramme 9 5 2 8 if, nous donne 3 : M. = 21 17 7 5

3. Si la matrice n’est pas inversible, prenez le bigramme suivant.

1.3. CHIFFREMENT ET MODES DE CHIFFREMENT

1.3

11

Chiffrement et modes de chiffrement

1.3.1

Cryptographie à clé secrète

Examen 2012-2013 1. Quel candidat a gagné le concours AES ? 0.5pt 2. Expliquer la différence entre décoder, déchiffrer et décrypter. 1.5pt 3. Que signifie confusion et diffusion ? 2pts 4. Quelles sont les grandes idées utilisées en chiffrement par blocs ? 1.5pt 5. Citer 3 noms de cryptographes (célèbres) 4 ayant travaillé sur les schémas de chiffrement par blocs. 0.5pt

1.3.2

Amélioration d’un système de chiffrement

Monsieur X utilise pour chiffrer ses données privées le cryptosystème DES, paramétré par une clé secrète k de 56 bits connue de lui seul. Comme Monsieur X a entendu dire que 56 bits étaient bien peu de nos jours, il envisage de rendre plus sûr le stockage de ses données en chiffrant une seconde fois toutes ses données, avec la clé DES k 0 = k + 1 (pour chaque donnée en clair m, la donnée chiffrée est donc c = DESk+1 (DESk (m)), où k désigne la clé). 1. Est-ce une bonne idée ? 2. Discuter les avantages et/ou les inconvénients. 3. Monsieur X pense à une autre amélioration possible. Il va chiffrer une fois avec DES, et une fois avec AES128. Comme AES128 a besoin de clés de 128 bits, il va paramétrer son chiffrement DES par sa clé secrète k, et pour son chiffrement AES128 la mêeme clé secrète k, mais avec des zéros pour faire le remplissage. Est-ce mieux ? 4. Quelle erreur fondamentale Monsieur X commet-il, eu égard aux principes de Kerckhoffs ?

1.3.3

Mode ECB

Le mode de chiffrement ECB (Electronic Code Book ou Dictionnaire de code) est le mode de chiffrement le plus simple que l’on puisse imaginer : chaque bloc de données est chiffré indépendamment par la fonction de chiffrement. 1. Ce mode de chiffrement n’est pas sûr, expliquer pourquoi. 2. Jack, qui gagne 105000 euros par an, a retrouvé l’entrée chiffrée qui lui correspond dans la base de données des salaires de son entreprise : Q92DFPVXC9IO Sachant que la fonction de chiffrement utilisé a des blocs de deux caractères et que le service informatique de son entreprise ne comprend aucun expert en cryptographie (entendre par là, utilise le mode ECB !), retrouver le salaire de Jane la patronne de Jack parmi le reste de la base de données : TOAV6RFPY5VXC9, YPFGFPDFDFIO, Q9AXFPC9IOIO, ACED4TFPVXIOIO, UTJSDGFPRTAVIO 3. Exemple 2. Imaginer à quel point ce mode chiffrement est déplorable pour les photographies. 4. Cayrel n’est pas (encore) une réponse acceptable

11 / 63

12

CHAPITRE 1. ÉNONCÉS

1.3.4

Mode CBC

Le mode de chiffrement CBC (Cipher Block Chaining ou Enchaînement des blocs) suit le shéma suivant :

1. Dessiner le schéma de déchiffrement correspondant à ce mode de chiffrement. 2. À quoi sert le vecteur d’initialisation (IV) ? Doit-il rester secret ? 3. Que se passe-t-il lors du déchiffrement si l’un des blocs chiffrés a été altéré ?

1.3.5

Mode CTR

Le mode de chiffrement CTR (mode compteur) consiste à chiffrer un compteur qui est incrémenté à chaque bloc, puis à en calculer le ou exclusif avec le message. Le compteur est initialisé à une valeur choisie au hasard appelée la nonce. 1. Dessiner les schéma de chiffrement et déchiffrement de ce mode opératoire. 2. Expliquer l’intérêt de la nonce. 3. Quel intérêt voyez-vous à ce mode de chiffrement quant à son implémentation ?

1.3.6

Attaque par insertion

On considère un chiffrement par blocs utilisant un mode opératoire OFB ou CTR. Un attaquant parvient à intercepter un chiffré C = (c0 , c1 , . . . ), correspondant à un message M = (m0 , m1 , . . . ). L’attaquant connaît uniquement C, mais pas M, ni bien sûr la clé K ou encore la valeur IV (pour OFB) ou la nonce (pour CTR). On suppose que l’attaquant parvient à forcer la personne qui chiffre à re-chiffrer un message M 0 quasiment identique à M, mais avec uniquement un bloc de zéros inséré parmi les autres blocs. On suppose en outre que l’attaquant parvient à forcer ce deuxième chiffrement à être réalisé avec la même IV (pour OFB) ou nonce (pour CTR). L’attaquant obtient donc un nouveau chiffré C 0 . 1. Comment l’attaquant peut-il déterminer le bloc à partir duquel M et M 0 diffèrent ? 2. Supposons que ce premier bloc différent ait pour indice i. Que vaut alors c0i ? Comment l’attaquant peut-il en déduire mi ? 3. Que doit-on en conclure comme précaution sur l’utilisation de OFB ou CTR ?

1.3. CHIFFREMENT ET MODES DE CHIFFREMENT

1.3.7

13

Malléabilité des chiffrements à flot

1. Rappeler le fonctionnement du chiffrement à flot. 2. Soit C le chiffré d’un message M, comment pouvez vous produire le chiffré C 0 du même message que vous aurez altéré. 3. Imaginer une utilisation pratique de cette attaque.

1.3.8

3DES et 2DES

1. Expliquer le fonctionnement de 3DES (T DES). Pourquoi ce schéma de chiffrement est-il utilisé à la place de DES ? Quel facteur de complexité ajoute-t-il ? 2. Comme l’exécution de 3DES est coûteuse, on propose d’utiliser à la place l’algorithme 2DES, qui consiste à composer deux chiffrements DES classiques avec des clefs différentes. Soit m un message et k1 et k2 des clefs DES, on obtient le chiffré c de la façon suivante : c = 2DES(k2 |k1 ; m) = DES(k2 ; DES(k1 ; m)) (a) Quels sont les avantages de cette approche par rapport à 3DES ? Quelle est la première estimation naïve de la force cryptographique théorique de 2DES ? (b) Analyse de sécurité de 2DES : i. Combien y a-t-il de clefs différentes possibles ? On dé ?nit les collisions par l’existence de messages clair m et chiffré c tels que c = 2DES(k; m) = 2DES(k 0 ; m) avec k 6= k 0 . En considérant la taille des blocs de messages clairs à chiffrer, combien existe-t-il en moyenne de clefs qui pour un clair m donné, crée une collision (i.e. fournissent le même c) ? ii. En exploitant la propriété suivante de DES : si c = DES(k2 ; DES(k1 ; m)), alors il existe un chiffré c0 = DES(k1 ; m) = DES −1 (k2 ; c), construire une méthode d’attaque sur 2DES qui utilise 2 paires de messages clair/chiffré. iii. À partir du nombre moyen d’opérations nécessaires à la cryptanalyse de DES, estimer les efforts nécessaires pour cette attaque ainsi que la probabilité d’avoir trouver la bonne clef grâce à elle. Quelle est ?nalement la force estimée de 2DES ?

1.3.9

Algorithme de Berlekamp-Massey

Cet algorithme consiste à construire pour les valeurs successives de N un LFSR de longueur LN et de polynôme de rétroaction fN qui génère les N premiers bits de la suite s. Pour N = 2L, l’algorithme retourne le polynôme de rétroaction du LFSR de départ. Algorithme de Berlekamp-Massey Entrée : s0 , s1 , ..., sn−1 une suite de longueur n. Init : f (X) = 1, L = 0, m = −1, g(X) = 1 Pour N variant de 0 à n − 1 P 1. Calculer d = sN + Li=1 ci sN −i mod 2.(f (X) = 1 + c1 X + c2 X 2 + ...) 2. Si d = 1 alors • t(X) = f (X) et f (X) = f (X) + g(X)X N −m . • Si 2L 6 N alors L = N + 1 − L, m = N, g(X) = t(X). 1. Appliquer l’algorithme de Berlekamp Massey à la suite : 001101110 . 2. Puis concluez en vérifiant votre réponse. 13 / 63

14

CHAPITRE 1. ÉNONCÉS

Cryptographie à clef publique Dans toute la suite, on pourra utiliser les résultats numériques suivants : – 319 = 11 × 29 ; 1011 = 263 (mod 319) ; 2632 = 216 × 319 + 265 ; – 1333 = 12 (mod 319) ; 13325 = 133 (mod 319) ; – 112 = 121 (mod 280) ; 114 = 81 (mod 280) ; 118 = 121 (mod 280) ; 1116 = 81 (mod 280) ; – 95 = 64 + 31 ; 81.11 = 51 (mod 280) ; 81.121 = 1 (mod 280). Identité de Bezout Soient a et b deux entiers relatifs et d leur PGCD alors il existe deux entiers u et v tels que : au + bv = d Résolution d’une équation diophantienne Soient a, b et c des entiers, et d le PGCD de a et b, alors l’équation au + bv = c admet des solutions entières si et seulement si c est un multiple de d. Théorème de Bezout Soient a et b deux entiers relatifs non nuls. a et b sont premiers entre eux si, et seulement si, il existe deux entiers u et v tels que au + bv = 1. Théorème de Gauss Si un nombre a divise un produit de facteurs et si a est premier avec l’un des deux facteurs alors a divise le deuxième facteur. L’algorithme d’Euclide permet de calculer le P.G.C.D. de deux entiers naturels a et b tels que a > b . Il consiste à réitérer les manipulations suivantes : 1. Effectuer la division euclidienne de a par b. Soit r le reste. 2. Remplacer a par b et b par r. On a b > r d’après la définition de la division euclidienne. Le P.G.C.D. est le dernier reste non nul.

Exemple d’application : calcul d’inverse modulaire Déterminez d tel que 7d = 1 mod 360. (revient à calculer l’inverse de 7 mod 360). 360 = 51 × 7 + 3 7 = 2×3+1 puis "on remonte" : 1 1 1 1 1

= = = = =

7 − 2 × 3 mod 360 7 − 2 × (360 − 51 × 7) mod 360 7 + 102 × 7 mod 360 7 × (1 + 102) mod 360 7 × 103 mod 360

D’où d = 103. Entraînez-vous en montrant que : 56 = 3−1 mod 170;

37 = 13−1 mod 143;

113 = 17−1 mod 120;

219 = 19−1 mod 520.

Détailler le calcul de 3 inverses modulaires (différents de ceux proposés ci-dessus).

1.4. MÉTHODES DE CALCUL

1.4 1.4.1

15

Méthodes de calcul Square and Multiply

En utilisant l’algorithme square and multiply, montrer que : 4137 mod 527 = 113;

57 mod 403 = 346;

84113 mod 143 = 2;

12817 mod 407 = 50;

207219 mod 583 = 192.

Détailler le calcul de 3 exponentiations modulaires (différentes de celles déjà proposées).

1.4.2

Calcul modulaire

Calculer (de tête si possible) 1. 2256 mod 128 2. 529436 mod 66 3. 10234096 mod 1024 4. 4562308 mod 234327

1.4.3

Théorème des restes chinois

Comment résoudre le système de congruences suivant :  x = r1 mod m1    x = r2 mod m2 ...    x = rk mod mk

?

C’est le théorème des restes chinois qui nous fournit la réponse : Soit k nombres entiers naturels m1 , m2 , ..., mk , premiers entre eux deux à deux, et k entiers r1 , r2 , ..., rk . Le système de congruences  x = r1 mod m1    x = r2 mod m2 ...    x = rk mod mk admet une unique solution modulo M = m1 m2 ...mk . La méthode permettant de construire une solution de ce système est fournit ci-dessous. M Posons Mi = m pour i = 1, 2, ..., k. On a donc pgcd(Mi , mi ) = 1 et on peut ainsi trouver i d’après l’identité de Bezout deux entiers ui et vi tel que Mi ui + mi vi = 1.

15 / 63

16

CHAPITRE 1. ÉNONCÉS

On a alors : u1 M1 r1 + u2 M2 r2 + ... + uk Mk rk = ri mod mi pour i = 1, 2, ..., k Par conséquent le nombre x = u1 M1 r1 + u2 M2 r2 + ... + uk Mk rk est solution du système. De plus si y est une autre solution de celui-ci, alors mi divise x − y pour chaque i = 1, 2, ..., k. Ainsi x − y est divisible par M. Le système admet donc une seule solution modulo M. Autrement dit, les solutions du système sont de la forme x = u1 M1 r1 + u2 M2 r2 + ... + uk Mk rk + nM avec n entier. Application - 1 Une bande de 17 pirates s’est emparée d’un butin composé de pièces d’or d’égale valeur. Ils décident de se les partager également et de donner le reste au cuisinier chinois. Celui-ci recevrait trois pièces. Mais les pirates se querellent et six d’entre eux sont tués. Le cuisinier recevrait alors 4 pièces. Survient alors un naufrage et seuls 6 pirates, le cuisinier et le trésor sont sauvés et le partage laisserait 5 pièces d’or à ce dernier. Quelle est alors la fortune minimale que peut espérer ce dernier s’il décide d’empoisonner le reste des pirates ?

Application - 2 Pour vous entraîner, vous appliquerez le théorème des restes congruences suivants (vérifiez votre résultat) :    x = 0 mod 5  x = x = 4 mod 7 x = 1. 3.   x = 4 mod 19 x =    x = 2 mod 5  x = x = 5 mod 7 x = 2. 4.   x = 10 mod 19 x =

chinois à deux des systèmes de 0 mod 5 6 mod 7 1 mod 19 5 mod 6 4 mod 11 3 mod 17

Application - 3 Choisissez, sans me le dire, un nombre entier entre 1 et 500. Je vais seulement vous demander trois nombres construits à l’aide de celui-ci et je retrouverais sans trop de difficulté le nombre que vous aviez choisi. Pour cela, diviser votre nombre par 5 et donner moi le reste obtenu. Faites de même avec la division par 7 et celle par 19. Ces trois restes suffisent pour retrouver votre nombre. Réaliser cette expérience avec votre voisin (avec trois nombres premiers entre eux de votre choix). Noter sur une feuille, que vous me rendrez, l’ensemble des résultats.

1.4. MÉTHODES DE CALCUL

1.4.4

17

Autour des nombres premiers

1. Pour quelles valeurs du nombre entier n le nombre n2 − 8n + 15 est-il premier ? Même question pour n2 + 4n + 3. 2. Pour quelles valeurs de n et m (entiers) le nombre 2n2 + 5mn + 3m2 est-il premier ? 3. Trouver 1 000 entiers naturels consécutifs, tous composés. 4. • Théorème : Soit n un entier naturel. Si n est un nombre premier, alors pour tout entier a premier avec n, on a an−1 = 1 mod n (c’est-à-dire n divise an−1 − 1). • Remarque : Le théorème de Fermat peut être utilisé pour montrer qu’un entier n’est pas premier : si il existe un entier a premier avec n tel que an−1 6= 1 mod n alors n n’est pas premier. • Application : L’entier 37901 est-il premier ?

1.4.5

Test de primalité de Miller-Rabin

Soit p un nombre premier impair que l’on écrit sous la forme p = 2s ×d+1. Soit a ∈ {1, . . . , p−1}. i On définit une suite récurrente (bi ) en posant : bi = ad×2 . 1. Montrer que dans Z/pZ, l’équation x2 = 1 entraine x = 1 ou x = −1. 2. Montrer que bs ≡ 1 mod p. 3. On suppose que b0 n’est pas congru à 1 modulo p. Montrer l’existence de i ∈ {0, . . . , s − 1} tel que bi ≡ −1 mod p. 4. En déduire un test de non-primalité d’un entier.

1.4.6

Algorithme p − 1 de Pollard

Le but est de trouver un fecteur non trivial de n = 19 048 567. On prend B = 19 et a = 3. 1. Vérifier que gcd(a, n) = 1. 2. Déterminer, pour chaque nombre premier 6 19, sa plus grande puissance qui soit 6 n. Soit Q le ppcm de toutes ces puissances, et p un hypothétique fecteur premier de n tel que p − 1 soit 19-friable 5 . 3. Montrer que p − 1 divise Q. 4. En déduire que p divise aQ − 1 (on pourra utiliser le petit théorème de Fermat). 5. En déduire que gcd(aQ − 1, n)(= gcd((aQ − 1) mod n, n)) est différent de 1. 6. On admet le calcul intermédiaire aQ mod n = 554 56. En déduire numériquement un facteur non-trivial de n.

1.4.7

Théorème de Wilson

Le but de cet exercice est de démontrer le théorème de Wilson : un entier n > 2 est premier si et seulement si (n − 1)! ≡ −1 mod n. 1. Soit p premier. Combien de solutions l’équation x2 = 1 admet-elle dans Z/pZ ? 2. Soit p premier. Montrer que (p − 1)! = −1 mod p. 3. Soit n > 2 un entier tel que n divise (n − 1)! + 1. Montrer que pour tout a ∈ {1, . . . , n − 1}, a est inversible dans (Z/nZ, ×). En déduire que n est premier. 5. C’est-à-dire que tous les facteurs premiers sont inférieurs à 19.

17 / 63

18

CHAPITRE 1. ÉNONCÉS

1.5 1.5.1

Échange de clefs Fonctionnement clé privée vs clé publique

Expliquez les principes de fonctionnement de la cryptographie symétrique et de la cryptographie asymétrique, en mettant en évidence les différences entre ces deux catégories, leurs avantages et leurs inconvénients respectifs. Vous pourrez illustrer votre réponse par un exemple de chaque catégorie, décrit aussi précisément que possible. Réponse limitée à une page.

1.5.2

Clé privée vs clé publique

Dix-sept personnes veulent pouvoir s’échanger des messages deux à deux. Si elles choisissent un système à clé secrète, combien de clés faut-il en tout ? Même question pour un système à clé publique. Quels sont les avantages de chaque système ? Lequel conseillez-vous ?

1.5.3

Diffie-Hellman

Déterminer la clé commune d’Alice et Bob dans le cas où p = 23 et g = 3 et Alice choisit un nombre secret a = 6 et Bob choisit b = 15.

1.5.4

Perte d’une clé privée

Un utilisateur, qui utilise souvent la messagerie sécurisée de son entreprise, vient de perdre sa clé privée, mais dispose encore de la clé publique correspondante. 1. Peut-il encore envoyer des courriers électroniques chiffrés ? En recevoir ? 2. Peut-il encore signer les courriers électroniques qu’il envoie ? Vérifier les signatures des courriers électroniques qu’il reçoit ? 3. À quoi peut encore servir la clé publique de notre utilisateur ? 4. Que doit-il faire pour être à nouveau capable d’effectuer toutes les opérations mentionnées ci-dessus ?

1.5.5

Attaque par le milieu de Diffie-Hellman

Décrire une attaque dans le protocole de Diffie-Hellman dans laquelle un attaquant actif (i.e. qui peut modifier les données pendant le protocole Diffie-Hellman) peut ensuite intercepter, déchiffrer et modifier toutes les communications qu’Alice ou Bob chiffrerait avec sa clé.

1.6. CHIFFREMENT

1.6 1.6.1

19

Chiffrement Kid-RSA

Cet exemple indiqué à des fin pédagogiques par Neil Koblitz donne une idée de ce que peut être la cryptographie à clé publique. Evidemment il n’est pas réaliste dans la mesure où il est élémentairement cassable. Les lettres A, B, . . . , Z sont représentées par les nombres 0, 1, . . . , 25. Alice choisit 4 entiers > 3 notés a, b, a0 , b0 et calcule successivement : e = a0 M + a ed − 1 d = b0 M + b n= M Alice rend public (dans un annuaire par exemple) le couple (n; e) (sa clé publique) et maintient d secret (sa clé privée). L’utilisation du système se fait de la façon suivante : si Bob désire envoyer un message à Alice, il chiffre successivement toutes les lettres de ce message en faisant correspondre à tout nombre m compris entre 0 et 25 le nombre c = em mod n. M = ab − 1

1. Montrer que n > 25. Pourquoi est-il souhaitable qu’il en soit ainsi ? Montrer que e et n sont premiers entre eux. 2. Comment Alice peut elle récupérer simplement m lorsqu’elle a reçu c ? 3. Charlie écoute la ligne de communication entre Alice et Bob et disposent donc de c. Comment peut-il attaquer le système et découvrir m ? 4. Utiliser ce système pour signer un message.

1.6.2

Chiffrement/Déchiffrement RSA

On considère la clef publique RSA (11, 319), c’est-à-dire pour n = 319 et e = 11. 1. Quel est le chiffrement avec cette clé du message M = 100 ? 2. Calculer d la clé privée correspondant à la clé publique e. 3. Déchiffrer le message C = 133. 4. Le message chiffré 625 peut-il résulter d’un chiffrement avec la clé publique ?

1.6.3

Exemples de RSA

Considérer le système RSA avec p = 19 et q = 23. 1. Calculer n et φ(n). 2. Calculer l’exposant d associé à e = 9, puis e = 14. 3. Calculer l’exposant d associé à e = 17.

n e 143 17 247 5 Dans le tableau ci-contre n et e sont publics : 319 11 – n = pq avec p et q deux nombres premiers secrets. 323 25 – e a pour inverse d : ed = 1 mod (p − 1)(q − 1) qui est tenu secret. 403 7 On donne un chiffré C = m mod n. 407 17 À vous de retrouver p, q et m. 583 19 Détaillez votre méthode et vérifiez votre résultat. 4717 21 Donner un autre triplet (n, e, C) (non présent dans le tableau ci-dessus) à votre voisin. À lui de déterminer p, q et m. 19 / 63

C 84 115 133 19 346 50 207 2804

20

CHAPITRE 1. ÉNONCÉS

1.6.4

Chiffrement RSA

Examen 2012-2013 On utilise les notations habituelles du chiffrement RSA : N est un entier et p et q sont deux entiers premiers tels que N = pq. On note φ l’indicatrice d’Euler φ = φ(N ) = (p − 1)(q − 1) et e et d sont deux éléments de Z/N Z tels que ed = 1 mod φ. 1. On souhaite utiliser l’algorithme de chiffrement RSA. – Comment chiffre-t-on un message m ? 0.5pt – Et comment déchiffre-t-on un message c ? 0.5pt – Parmi les entiers N, p, q, φ, e et d quels sont ceux qui doivent rester secrets ? 0.5pt – Montrer que la divulgation de l’une quelconque des valeurs secrètes permet de retrouver toutes les autres valeurs privées. 2pts 2. On pose N = 1003 et e = 3. – Calculer p, q et φ. 1pt – Que vaut alors l’entier d associé à e ? 1pt – Que vaut le message chiffré c associé au message clair m = 4 ? 0.5pt – Dans ce cas particulier, est-il possible de retrouver m à partir de c sans connaître d ? 1pt 3. On pose désormais N = 65. – Donner tous les couples (e, d) possibles. 1pt – Chiffrer le message m = 4 en utilisant e = 5. 0.5pt – Vérifier le résultat obtenu en le déchiffrant à l’aide de la clef privée correspondante. 1.5pt

1.6.5

RSA-3

Dans tout cet exercice, on se donne trois entiers premiers impairs p, q et r differents deux à deux. Soit n l’entier égal au produit pqr. On s’intéresse ici à un cryptosystème identique à RSA. 1. Montrer que l’on peut définir, de la même manière que pour RSA, une fonction de chiffrement et de déchiffrement ainsi qu’un cryptosystème à clé publique en utilisant l’entier N. Vous exhiberez les clés publiques et privées et définirez l’ensemble des messages possibles. On notera ce cryptosystème RSA-3 dans toute la suite de l’exercice. 2. Rappeler quels sont les messages qui sont dangereux lors de l’utilisation de RSA. Quels seront ceux qui seront dangereux pour RSA-3 ? (Vous argumenterez votre réponse.) 3. Montrer qu’il est possible d’utiliser le théorème des restes chinois lors du déchiffrement d’un message. 4. Donner le chiffrement de x = 13 et le déchiffrement de y = 11 en utilisant le théorème des restes chinois avec p = 3, q = 5, et r = 7 et e (l’exposant de chiffrement) égal à 19. Réaliser un protocole de chiffrement à la RSA-3 avec votre voisin. Noter sur une feuille, que vous me rendrez, l’ensemble des résultats.

1.6. CHIFFREMENT

1.6.6

21

Chiffrement El Gamal

Alice choisit p = 97 et g = 13. (a) Elle choisit aléatoirement un nombre a, disons 45, dans l’intervalle [1, ..., 95]. (b) Elle calcule α = (1345 mod 97) = 20. (c) Elle publie sa clé (97, 13, 20) et garde secrète sa clé 45. Bob veut envoyer le message RAS à Alice. (a) En utilisant le code ASCII, son message est 118 101 119. (b) Il le découpe en nombres entre 0 et 97 : 11 81 01 11 09. (c) Il choisit aléatoirement un nombre b, disons 35, dans l’intervalle [1, .., 95]. (d) Il calcule β = 1335 mod 97 = 71 mod 97. 1. Vérifier que le chiffré de son message est (71, 21 40 46 21 26). 2. Comment Alice déchiffre-t-elle le message de Bob ? Déchiffrer-le. Réaliser un protocole de chiffrement à la El Gamal avec votre voisin. Noter sur une feuille, que vous me rendrez, l’ensemble des résultats.

1.6.7

Changement de clés

Alice change sa clé RSA tous les 25 jours. Bob lui change sa clé tous les 31 jours. Sachant qu’Alice change sa clé aujourd’hui et que Bob a changé sa clé il y a trois jours, déterminer quand sera la prochaine fois qu’Alice et Bob changeront leur clé le même jour.

21 / 63

22

CHAPITRE 1. ÉNONCÉS

1.7 1.7.1

Attaques sur RSA Attaque par module commun

Une implantation de RSA donne à deux personnes (Alice et Bob) le même nombre n (produit de deux nombres premiers) mais des clefs (eA , dA ) et (eB , dB ) différentes. On suppose de plus que eA et eB sont premiers entre eux (ce qui est le plus général). Supposons alors que Alice et Bob chiffrent un même message m et que Oscar intercepte les deux messages cA = meA mod n et cB = meB mod n qu’il sait être deux chiffrements du même message m. Montrer qu’Oscar peut alors très facilement découvrir le message m. Vous illustrerez cette attaque par un exemple de votre choix.

1.7.2

De φ(n) à la factorisation

On considère un module RSA n = pq, où p et q sont les inconnues. Montrer simplement comment la connaissance de φ(n) = (p − 1)(q − 1) (la fonction d’Euler) permet de remonter à la factorisation de n. On rappelle que si on connaît pq et p + q alors p et q sont racines d’un polynôme de degré 2 à déterminer.

1.7.3

RSA avec deux facteurs trop proches

Supposons que n soit un entier produit de deux nombres premiers p et q proches (on peut et s = p−q . toujours supposer que p > q). On pose t = p+q 2 2 Montrer que : 1. n = t2 − s2 , 2. t est légèrement supérieur à la racine carrée de n. On peut utiliser ces informations pour factoriser n. L’algorithme s’appelle l’algorithme de Fermat, le voici : √ 1. A ← d ne

(∈ N)

2. x = A2 − n

(∈ N)

3. Tant que x n’est pas carré parfait (a) A ← A + 1 (b) x ← A2 − n 4. Retourner p = A +

√

x et q = A −

√

x

1. Appliquer cet algorithme pour factoriser 24960007, puis 3649574023. 2. Déterminer la complexité de cet algorithme, en fonction de p et de n. On sait que lorsque A vaudra p+q = alors x = t2 − n = s2 sera un carré. 2 √ 3. Déterminer le nombre d’itérations de l’algorithme lorsque p diffère de n de moins de √ 4 4n.

1.7. ATTAQUES SUR RSA

1.7.4

23

Malléabilité de RSA

Nous allons montrer comment les propriétés multiplicatives de RSA rendent une utilisation naïve de ce cryptosystème complètement illusoire. 1. Proposer un procédé de signature naïf d’un message m ∈ Z/nZ par Alice avec sa clé privée RSA. 2. Ève a réussi à se procurer les signatures du message m1 et du message m2 . Montrer quels autres messages elle peut signer au nom d’Alice, et comment. 3. Nous allons montrer une sorte de généralisation de ce procédé. On suppose qu’Ève s’est procuré un ensemble de signatures de messages : elle connaît un grand nombre de couples (mi ; S(mi )). De plus, les mi sont petits et Ève a pu les factoriser : Y α ∀i, mi = µj i,j . j

On appelle falsifier une signature le fait d’en créer une de toutes pièces. Quelles signatures Ève est-elle capable de falsifier dans ces conditions ? 4. On suppose qu’Ève souhaite falsifier la signature d’un message cible noté mt qu’elle a aussi réussi à factoriser en fonction des µj : Y β mt = µj j . j

Montrer comment Ève doit s’y prendre pour falsifier la signature de mt .

1.7.5

Le temps de factorisation des grands entiers

Le meilleur algorithme connu à ce jour pour factoriser les grands entiers est le GNFS (General Number Field Sieve). SOn facteur de travail, pour factoriser un entier N est donné par la formule :
W (N ) = k exp c(log2 N )1/3 (log2 log2 N )2/3 avec : p • c = 3 64/9. • k est une constante qui dépend de la qualité du programme. 1. Calculer k sachant qu’en 1999, un entier de 512 bits a été factorisé par une équipe internationale avec un facteur de travail de 8000 Mips-années ; 2. Avec cette valeur, quel est le facteur de travail nécessaire pour factoriser un entier de 768 bits ? et 1024 bits ?

23 / 63

24

CHAPITRE 1. ÉNONCÉS

1.8

Signature et hachage

1.8.1

Signature RSA

1. Calculer le module n et l’entier φ(n) associés aux nombres premiers p = 17 et q = 23. 2. Quels sont les exposants secrets de signature associés aux exposants publics e = 11 et e = 13 ? 3. Quelle est la signature de m = 100 ? 4. Vérifier que la vérification fonctionne. Réaliser un protocole de signature RSA avec votre voisin. Noter sur une feuille, que vous me rendrez, l’ensemble des résultats.

1.8.2

Signature aveugle avec RSA

Trouver un algorithme à partir de la signature R.S.A qui permet de faire un algorithme de signature aveugle. On a un message m qu’on souhaite faire signer sans que le signataire sache ce qu’il signe, et un couple de clés publique/privée.

1.8.3

Signature El Gamal

On considère la méthode de signature d’El Gamal, avec p = 467, g = 2, x = 65 1. Justifier la validité du choix de p et g. 2. Calculer la clé publique y = g x mod p. 3. Calculer la signature du message m = 100 en utilisant les valeurs aléatoires k = 64 et k = 213. 4. Vérifier que la vérification fonctionne. Réaliser un protocole de signature à la El Gamal avec votre voisin. Noter sur une feuille, que vous me rendrez, l’ensemble des résultats.

1.8.4

Signature El Gamal : utilisation de l’aléa

Le schéma de signature El Gamal utilise un générateur g de Z∗p et une clef publique y = g x mod p, où x est la clé privée. 1. Dans quel ensemble choisir x ? Pour signer un message m, le signataire tire un aléa k et calcule r = g k mod p et s = k −1 (h(m) − xr) où h(.) est une fonction de hachage. Le couple (r, s) est la signature du message m. 2. Décrire une attaque contre ce schéma de signature si le même aléa k est utilisé pour signer deux messages différents. De quel type d’attaque s’agit-il ?

1.8. SIGNATURE ET HACHAGE

1.8.5

25

Signature El Gamal sans vérification modulaire

On suppose que le schéma de signature El Gamal est utilisé sans vérifier si 0 < r < p. On suppose que l’ataquant connaît la signature (r, s) d’un message m. Soit m0 un message arbitraire et s0 = sα avec α = h(m0 )h(m)−1 mod p − 1. 1. Trouver deux équations vérifiées par r0 (l’une modulo p et m’autre modulo p − 1) telles que (r0 , s0 ) soit une signature de m0 . 2. Comment peut-on résoudre ces équations ? 3. De quel type d’attaque s’agit-il ?

1.8.6

Signature GHR (Gennaro-Halevi-Rabin)

Ce schéma de signature proposé en 99 fonctionne de la manière suivante. On considère un module RSA de la forme N = pq où p = 2p0 + 1 et q = 2q 0 + 1, avec p, p0 , q, q 0 0 0 tous premiers. On prend au hasard u ∈ Z∗N tel que u soit d’ordre 2p0 q 0 (u2p q mod N = 1). La clé publique est (N, u). La clé privée est constituée de la factorisation de N. 1. Montrer que p0 suffit à retrouver la factorisation de N. 2. Montrer que la valeur p0 q 0 suffit également à retrouver la factorisation. 3. Quelle est la valeur de φ(N ) ? Soit h(.) une fonction de hachage qui produit des hachés de taille N. Pour signer un message −1 0 0 M, on calcule m = H(M ), puis s = um mod 2p q mod N : la valeur de la signature est s. 4. Pourquoi l’inverse de m est-il calculé modulo 2p0 q 0 ? 5. Retrouver quelle est la procédure de vérification d’un couple message/signature (M, s). La sécurité de ce schéma est liée au problème algorithmique suivant, qui est une variante du problème RSA (on l’appelle flexible RSA) : étant donnée (N, v) où N est un module RSA et v un élément de Z∗N trouver un couple (x, e) tel que e > 1 et x = v mod N. 6. Rappeler la différence avec le problème RSA classique. 7. Expliquer pourquoi on impose e > 1. 8. Montrer que si le problème RSA classique est facile, alors le problème flexible RSA présenté ci-dessus est également facile.

25 / 63

26

CHAPITRE 1. ÉNONCÉS

1.9 1.9.1

Hachage Fonction de hachage faiblement sans collision

Définition : Soit h : X → Y une fonction de hachage. • h est dite à sens unique si, pour presque tout y de Y, il est calculatoirement infaisable de trouver x tel que y = h(x). • h dite faiblement sans collision si, pour x donné, il est calculatoirement infaisable de trouver x0 tel que h(x0 ) = h(x). • h est dite sans collision s’il est calculatoirement infaisable de trouver x et x0 tels que h(x) = h(x0 ). 1. Montrer que sans collision implique faiblement sans collision et que à sens unique implique faiblement sans collision. 2. Montrer qu’une fonction peut être sans collision mais pas à sens unique.

1.9.2

Fonction de hachage et signature

Soit h une fonction de hachage à valeur dans Fn2 . On considère le cas d’un attaquant qui pour abuser une signature souhaite construire deux messages (presque identiques) ayant le même haché. 1. Donner une attaque en O(2n/2 ) pour la fonction de hachage h qui permet de construire deux messages (presque identiques) mais avec le même hachés. 2. Montrer comment l’attaque précédente peut être utilisée avec la signature RSA pour abuser un vérificateur de signature.

1.9.3

Le buzz free mobile

Le 6 janvier 2012, les geeks s’agitent pour savoir quand les forfaits de la marque Free Mobile seront lancés. Le site live.free.fr contient un dessin de fusée, avec les symboles : efb7929e6a5b7dcc6ebb79aa3c45af13 Cette valeur est ce que renvoie la fonction de hachage md5 sur la donnée jesaispas. Des petits malins y voient aussi un second message caché en interprétant la chaîne précédente dans le codage ascii. On y lirait NIEL JOIN RACE >>START

Est-il plausible d’obtenir à fabriquer un message intelligible qui donne un haché intelligible ?

1.10. AUTHENTIFICATION

1.10

27

Authentification

1.10.1

Authentification à clef secrète

Il existe des protocoles permettant d’authentifier une entité A auprès d’une entité B. Cela présuppose donc que A sache effectivement que l’entité vérificatrice est bien B, et pas un attaquant C qui se fait passer pour B. Or lors de la plupart des connexions, rien ne l’en assure. Il faudrait alors que B s’authentifie également auprès de A. C’est ce qu’on appelle l’authentification mutuelle. L’idée générale est alors de reprendre les protocoles qui existent pour l’authentification d’une entité et de l’appliquer de manière symétrique pour authentifier B auprès de A. Nous allons voir sur deux exemples qu’il est tout de même nécessaire de prévoir quelques ajustements. 1. Expliquer pourquoi il n’est pas possible de faire de l’authentification mutuelle par mot de passe. 2. Suggérer alors une attaque qui permet de récupérer un mot de passe Unix. Enumérez d’autres situations dans lesquelles une interception de mot de passe est possible en l’absence d’authentification du serveur. On cherche maintenant à utiliser une authentification de type défi-réponse utilisant un système à clé secrète. Considérons le protocole suivant qui utilise un chiffrement à clé secrète. A et B partagent au préalable une clé secrète K. (i) A tire une valeur aléatoire rA et l’envoie à B; (ii) B tire une valeur aléatoire rB et calcule β = EK (rA , rB ). B envoie β à A; (iii) A calcule DK (β). S’il n’y a pas eu d’attaque, il retrouve rA : B s’est authentifié. Il prend connaissance de rB . Il envoie rB à B : A s’est authentifié. 3. Trouver une attaque de ce protocole par rejeu. On donne les éléments de départ de l’approche. Le participant A est honnête, et l’attaquant C (malhonnête) se fait passer pour B.C va, parallèlement à la tentative d’authentification mutuelle émanant de A (vers B, pense-t-il) appelée session 1, initier une session d’authentification vers A (en faisant croire qu’elle émane de B), qu’on appellera session 2. Les messages de ces deux sessions s’entrelacent. Les premières étapes sont (exactement dans cet ordre) : • session 1 : A envoie rA à C. • session 2 : C envoie rA à A. Compléter, et expliquer d’où provient le problème. 4. Suggérer une amélioration.

1.10.2

Authentification à clef publique

Proposer un schéma basé sur le chiffrement ou sur la signature pour faire de l’authentification à clé publique.

27 / 63

28

CHAPITRE 1. ÉNONCÉS

1.10.3

Schéma de Schnorr

Dans un protocole d’identification, un vérificateur V veut vérifier l’identité d’un prouveur P. Pour cela, P doit convaincre V qu’il est en possession d’un certain secret s. Les deux objectifs essentiels d’un tel protocole sont d’une part qu’un usurpateur U ne connaissant pas s ne puisse pas convaincre V, et d’autre part que P puisse convaincre V qu’il possède s sans lui révéler la valeur de s (sinon V pourrait devenir à son tour un usurpateur de l’identité de P ). Nous décrivons maintenant le protocole d’identification de Schnorr : p et q sont des nombres premiers tels que q divise p − 1 et α est un élément d’ordre q du groupe multiplicatif (Z/pZ) ∗ . Un nombre s mod q est le secret de P, tandis que les valeurs de p, q, α, et v := α−s mod p sont publiques. Le protocole d’identification se déroule en quatre étapes : 1. Engagement : P choisit aléatoirement un entier r mod q et transmet x = αr mod p à V. 2. Challenge : V envoie un challenge e ∈ [0; q − 1[ à P. 3. Réponse : P envoie y = r + es mod q à V. 4. Vérification : V vérifie que x = αy v e mod p. P a réussit son identification auprès de V si la vérification est positive. 1. Montrer que P réussit toujours son identification auprès de V. 2. U tente de s’identifier auprès de V. Pour cela il répond un y aléatoire à l’étape 3. Quelles sont ses chances de succès ? 3. Supposons que le protocole précédent soit mal exécuté, et que l’ordre des étapes 1 et 2 soit inversé. Montrez que U peut alors réussir son identification auprès de V. 4. Montrez que, si pour un même engagement r, U est capable de répondre correctement à deux questions e et e0 distinctes posées par V, alors il connait s.

1.11. PKI, CERTIFICATS

1.11 1.11.1

29

PKI, Certificats PKI

Proposer une méthode à base de certificat pour vérifier une signature reçue par un individu, sans avoir à consulter un annuaire ou une base de données.

1.11.2

Certificats

Discuter les trois scénarios suivants en termes de sécurité : 1. Deux certificats différents sont signés par la même clef privée. 2. Deux certificats différents contiennent la même clef publique. 3. Deux certificats différents ont la même signature.

1.11.3

Distinguer les clefs utilisées dans PGP

PGP utilise 4 clefs quand un utilisateur A souhaite signer et chiffrer un courrier électronique pour un utilisateur B : • la clef utilisée pour signer le contenu du courrier, • la clef utilisée pour déchiffrer la clef utilisée dans la première étape, • la clef utilisée pour chiffrer le contenu du courrier, • la clef utilisée pour chiffrer la clef utilisée dans la troisième étape. 1. Lesquelles de ces clefs sont dites symétriques ? 2. Quelles longueurs (exprimées en bits) semblent adéquates pour des clefs symétriques ? Même question pour des clefs asymétriques. 3. Expliquer à quel moment les 4 clefs considérées sont générées.

1.11.4

Hachés de mots de passe

Les systèmes d’authentification usuels vérifient les mots de passe à l’aide de leur haché stocké dans des fichiers protégés. 1. Quelle est l’utilité de stocker les hachés des mots de passe plutôt que les mots de passe eux-mêmes ? 2. Pourquoi doit-on protéger l’accès aux hachés des mots de passe ? 3. Sous quelle condition cette précaution ne serait-elle pas nécessaire ?

29 / 63

30

CHAPITRE 1. ÉNONCÉS

1.11.5

Le protocole HTTPS

Le protocole HTTPS (HTTP sur SSL/TLS) est couramment utilisé pour sécuriser les communications entre un serveur web et un navigateur. Pour cela, une session HTTPS s’appuie sur un certificat diffusé par le serveur permettant d’effectuer une session d’authentification initiale et ensuite un chiffrement du canal de communication dans lequel transite l’échange HTTP. 1. Lors de l’authentification, le protocole utilise une clef publique contenu dans un certificat que le serveur détient et diffuse au client à l’établissement de la connexion. Quelles sont les protections offertes par cette utilisation d’un certificat serveur ? 2. Comment l’utilisateur du navigateur peut-il être assuré que cette clef publique correspond bien à l’organisme auquel il souhaite accéder ? 3. Pourquoi de nombreux services web, utilisant pourtant HTTPS, demandent-ils en plus à l’utilisateur de fournir un nom de compte et un mot de passe pour compléter l’ouverture de session ? 4. Il est possible d’utiliser un certificat client stocké sur le navigateur pour l’échange HTTPS. Quel est l’effet de l’utilisation d’un certificat client sur la protection de l’ensemble du service ? 5. Avec un certificat client, l’utilisateur doit quand même parfois fournir une passphrase : de quel mot de passe s’agit-il ? 6. Pensez-vous qu’il y ait une « passphase » utilisateur sur la partie privée du certificat serveur ? Pourquoi ?

1.11.6

La carte bleue

Une carte bancaire (à puce) possède un couple clé publique/clé privée kP , kS . Dans la perspective d’une transaction, elle accomplit plusieurs choses. En premier lieu, elle apporte une preuve qu’elle est une vraie carte, car : • Elle produit une signature valide σ = AkS (m) avec sa clé privée d’un message aléatoire qu’on lui fournit. • Elle peut exhiber une preuve que sa clé publique kP qu’elle fournit, et qui est nécessaire pour vérifier σ, est bien une clé que la banque reconnaît comme appartenant à un de ses clients. 1. Quelle forme peut prendre la preuve précédemment citée ? Quelle connaissance doit avoir le distributeur pour vérifier cette preuve ? 2. Logistiquement parlant, est-il pratique de s’assurer que tous les distributeurs sur la planète ont cette connaissance ? Quel rôle peuvent jouer alors des organismes plus mondiaux comme Visa, Mastercard ? En second lieu, la carte dit oui ou non à une proposition de valeur pour le code PIN que lui relaie le distributeur (celui-ci ne relaie le code PIN que si la carte s’est authentifiée auprès de lui). Lors d’une transaction, la carte a pour vocation de dire ok ou pas à un montant de transaction. Elle peut éventuellement aussi dire il faut demander à la banque. Pour dire ok, la carte renvoie un code d’autorisation qui est une signature du montant de la transaction et du numéro de carte. 3. Si un attaquant parvient à trouver la clé secrète kS de la carte, et qu’il dispose du matériel pour fabriquer une carte, que peut-il faire ? Même question s’il parvient à trouver la clé secrète de la banque.

Chapitre 2 Corrections 2.1

Pour se familiariser avec les ordres de grandeur

2.1.1

Mot de passe

1. 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. Soit donc 2 jours et 8 heures au maximum et vraisemblablement moins de 50 minutes. 3. Il y 104 = 10000 mots de passe différents constitués de 4 chiffres, ce qui représente 2h et 45 minutes pour tous les tester. 4. Si il s’agit de 8 lettres minuscules, il faut : 268 s ≈ 6600 années. Cependant si l’on s’autorise les minuscules, les majuscules, les chiffres et quinze signes de ponctuations : 778 s ≈ 4 × 106 années.

2.1.2

Dénombrements

1. 26, trivialement [environ 4,7 bits]. 2. On a 26 choix pour b, mais a doit être inversible modulo 26, sinon on ne peut pas déchiffrer ! Donc il y a φ(26) = (13 − 1)(2 − 1) = 12 choix pour a. Au total : 26 × 12 = 312 clés [environ 8,29 bits]. 3. On a droit à toutes les permutations des valeurs [0,26] : chaque lettre est transformée en l’une des 26 autres, mais de façon bijective. Donc 26 ! clés possibles [88,4 bits ... mais c’est sans compter l’exploitation des redondances linguistiques]. 4. Il y a 26 choix possibles pour chacun des k caractères donc 26k clés possibles [4,7 bit par caractère de clé].

2.1.3

Vider l’océan avec un dé à coudre 2

Volume d’un dé à coudre : Vde = π × 1,54 × 1, 5 ≈ 2, 6507cm3 Volume de l’océan : Vdocean = 360 × 106 × 3, 8 = 13, 68 × 108 km3 = 13, 68 × 1023 cm3 Il y a donc r = Vocean ≈ 0, 516 × 1024 dés à coudre dans l’océan. On a log2 (r) ≈ 78, 77. Vde 31

32

CHAPITRE 2. CORRECTIONS

2.1.4

La force brute

1. Le temps pour tester une clé est t=

facteur de travail 1200 = 0, 6 × 10−6 s puissance 2000 × 106

2. Il y a n = 2128 ≈ 0, 34 × 1039 clés à tester. On considère les clés possible comme étant les entiers de 0 à 2128 − 1, et la clé secrète est notée k. On a deux scenarios d’attaque par force brute possible. On note n = 2128 . • Si on essaie tous les entiers les uns après les autres. La probabilité, pour un entier i donné, d’avoir k = i (et donc d’avoir exactement i+1 tirages à effectuer si on part de 0), est égale à n1 . L’espérance du nombre d’essais est donc : n−1 X

(i + 1)

i=0

1 n(n + 1) n = ≈ . n 2n 2

3. On use et abuse des approximations : 103 = 1000 ≈ 210 , 1jour = 216 s, 1an = 29 jour = 225 secondes, etc. On calcule le nombre d’instructions calculées en un an à la fréquence de 2000 Mips : 2000 Mips.années ≈ 2000 × 220 × 29 × 216 ≈ 211+20+9+16 ≈ 256 instructions. Le nombre d’instructions à effectuer pour trouver la clé est : 1200 × 2127 ≈ 2138 . Soit un temps de ≈ 2138−56 ≈ 281 années (ou en base 10 : 2 × (210 )8 ≈ 2 × 1024 ). Le milliard (≈ 230 ) de PC d’Internet permettent de gagner un facteur 230 , ou 109 . Soit quelque chose comme 2 × 1015 années, soit un petit million de fois l’âge de l’univers.

2.1.5

La loi de Moore

1. On a d’un part Wn+1 = aWn √ et la loi de Moore nous indique que Wn+18 = a18 Wn = 2Wn . 18 On en déduit donc que a = 2. 2. L’hypothèse est que la machine a une fréquence de 1000 Mips (230 par seconde), donc en un mois (25 jours de 216 secondes, en gros), ça fait 251 instructions. En outre on a : Wn = an W0 . 3. Au bout de n mois, le nombre d’instructions Sn effectué est W0 + . . . Wn−1 , soit : Sn = W0 (1 + a + · · · + an−1 ), = 251

an − 1 . a−1

Pour que Sn dépasse le nombre d’instructions à effectuer, qui est (2127 × 211 = 2138 ), il 1 faut une estimation à la louche de a − 1. À la calculatrice on obtient a − 1 ≈ 25 . On vise donc : an − 1 ≈ 2138−51 × (a − 1), ≈

287 ≈ 282 , 25

2.1. POUR SE FAMILIARISER AVEC LES ORDRES DE GRANDEUR

n≈

82 log2 2 ≈ 82 × 18 ≈ 123 années. log2 a

Ce qui est très très loin du temps calculé à l’exercice précédent. Il faut penser à rajouter qu’on a donc besoin de changer 1476 fois d’ordinateurs.

33 / 63

33

34

CHAPITRE 2. CORRECTIONS

2.2

Vigénère, Polybe et Hill

2.2.1

César/Vigénère

1. Un texte long car les fréquences sont alors plus proche des fréquences moyennes de la langue (on a moins de variations). 2. Décalage a→p. 3. Oui puisqu’il retrouve trivialement la clé. 4. Il saucissonne le message en morceaux correspondants aux classes de congruence modulo la longueur de la clé, et il se retrouve avec une cryptanalyse de type César. 5. Non, puisqu’il est aisé de commencer par un pari sur la longueur de la clé (une hypothèse raisonnable étant que la clé fait moins de vingt caractères).

2.2.2

Chiffrement de Vigénère

1. On additionne chaque lettre du clair avec la lettre correspondante de la clé répétée suffisamment de fois. On obtient le chiffré suivant : VVVIXGGTPTMOFVADWST La réponse WWWJYHHUQUNPGWBEXTU est également acceptable mais elle correspond au cas A=1 (et non A=0). 2. On fait cette fois une soustraction du clair au chiffré. On obtient la clé suivante : INTROUVABLEINTROUVA Si on prend A=1 (mais alors on est forcé de prendre Z=0), la clé est HMSQNTUZAKD. 3. Même technique que précédemment et on trouve : HWDIXJYALZKDBACRCBP. Il n’y a pas de périodicité dans la clé : c’est un masque jetable (sécurité infinie).

2.2.3

Chiffrement de Polybe

1. Une attaque à clair connu dévoile une lettre de la clé pour chaque nouvelle lettre du message clair. Compte tenu du fait que les dernières lettres du tableau sont rangées dans l’ordre alphabétique, la reconstruction est très rapide. Pour une attaque simple, il faut se baser sur la fréquence d’apparition des lettres, le chiffrement étant une substitution mono-alphabétique. 2. CHERE ANNA RENDEZ VOUS A DEUX HEURES RUE VERTE RAOUL Le secret étant SCYTALE. La présence du 55 (supposément le Z) et la fréquence d’apparition du 22 (le E) constituent le point de départ. Les mots RAOUL et ANNA (mot symétrique facilement reconnaissable) est également prévisible.

2.2.4

Chiffrement affine

1. CRYPTO et ROXEYZ sont respectivement représentés par les suites d’entiers : [2, 17, 24, 15, 19, 14] et [17, 14, 23, 4, 24, 25]. Il s’agit de résoudre le sytème : 2a + b = 17 17a + b = 14 qui a comme solution (a, b) = (5, 7).

2.2. VIGÉNÈRE, POLYBE ET HILL

35

2. Si on chiffre deux fois par un chiffre affine de clé (a0 , b0 ) on obtient une fonction qui à x ∈ Z/26Z associe : a0 (a0 x + b0 ) + b0 = a02 x + (a0 b0 + b0 ). On obtient donc un chiffre affine de clé (a00 , b00 ) avec : a00 = a02 b00 = a0 b0 + b0 NGBAMX est représenté par la suite d’entiers : [13, 6, 1, 0, 12, 23]. La résolution du système : 2a00 + b00 = 13 17a00 + b00 = 6 donne cette fois : (a00 , b00 ) = (3, 7).

2.2.5

Chiffrement de Hill

Examen 2012-2013 La matrice multipliée à M n’est pas inversible dans M4 (Z26 ) (son déterminant est pair et donc non inversible dans Z26 ), nous considérons donc le bigramme suivant : tq qui doit être déchiffré en fr et nous obtenons la nouvelle équation :     9 19 2 5 M. = 21 16 7 17 Soit :

  −1 2 5 9 19 M= . 7 17 21 16       2 5 16 −19 1 17 mod 26) . = 7 17 −21 9 3 4 

= (5−1

Le déchiffrement du bigramme gz donne alors :       1 17 6 15 . = 3 4 25 14 soit le bigramme po et le déchiffrement complet de gzatzxjihvbreosu nous donne le texte clair : polyalphabetique.

35 / 63

36

CHAPITRE 2. CORRECTIONS

2.3

Chiffrement et modes de chiffrement

2.3.1

Cryptographie à clé secrète

Examen 2012-2013 1. Rijndael

0.5pt

2. – décoder = convertir des données encodées en données claires (aucune clef n’est en jeu, ni aucun chiffrement), – déchiffrer = déterminer le message clair à partir du texte chiffré en utilisant la clef, – décrypter = retrouver le texte clair sans connaître la clef de chiffrement. 1.5pt 3. La confusion correspond à une volonté de rendre la relation entre la clé de chiffrement et le texte chiffré la plus complexe possible. La diffusion signifie que la moindre modification du message clair entraîne une grande modification du message chiffré. 2pts 4. Le message clair est découpé en paquets qui vont subir des transformations simples (permutation, décalage, boîtes S, schéma de Feistel, etc...). 1.5pt 5. Feistel, Biham, Shamir, Anderson, etc...

2.3.2

0.5pt

Amélioration d’un système de chiffrement

Monsieur X n’a rien compris aux principes de Kerchoffs. Sa clé reste k. Son hypothèse doit être que son attaquant sait tout ce qu’il fait hormis la clé. Or, ici, on n’a toujours que 256 valeurs de k à tester.

2.3.3

Mode ECB

1. Deux blocs identiques auront le même chiffré, ainsi de l’information peut fuir. 2. On peut supposer que l’entrée de Jack donne la correspondance suivante : Ja|ck|??|10|50|00 Q9|2D|FP|VX|C9|IO FP doit correspondre au séparateur de champ. Jane a aussi un prénom de 4 lettres qui commence par Ja donc son entrée chiffrée commence par Q9??FP, c’est Q9AXFPC9IOIO. Son salaire est ainsi C9IOIO, soit 500000 euros par an. 3. Cela correspond à remplacer les couleurs si la taille du bloc correspond à un pixel, ou des blocs d’image par d’autre, on reconnaitra la forme de l’image : par ex les pixels noir deviendront tous rouges.

2.3.4

Mode CBC

1. Le voilà : 2. Si il n’y avait pas d’IV deux blocs identiques aux mêmes positions de deux fichiers alors leurs chiffrés seraient identiques et on le saurait. Si l’on pense aux exemples précédents, on pourrait dire par exemple : 4 personnes ont le même salaire ou le centre des deux images est identiques. 3. Seulement deux blocs sont altérés.

2.3. CHIFFREMENT ET MODES DE CHIFFREMENT

2.3.5

37

Mode CTR

1. Pas besoin de fonction de déchiffrement ! C’est avantageux dans certain cas : pour AES le déchiffrement est plus cher que le chiffrement. 2. C’est un IV, sinon toujours le même stream. 3. Facilement parallélisable.

2.3.6

Attaque par insertion

1. Si l’insertion est au bloc i (les blocs étant numérotés à partir de 0), alors les blocs de 0 à i − 1 des chiffrés sont identiques. 2. Le bloc c0i vaut alors 0 ⊕ Pi , où Pi est soit EK (nonce + i) pour le mode compteur, ou bien pour OFB Pi = EK (Pi−1 ) et P0 = EK (IV ). Du coup, comme ci = mi ⊕ Pi ,, on récupère mi= ci ⊕ c0i . 3. Il ne faut jamais réutiliser la même IV.

2.3.7

Malléabilité des chiffrements par flot

1. D’une clé k et d’un vecteur d’initialisation IV, on déduit une chaîne de bits pseudoaléatoire S(k, IV ). Ceci permet de définir le chiffré : C = Ek,IV (M ) = M ⊕ S(k, IV ) 2. Si on pose C 0 = C ⊕ M 0 , on a alors : C 0 = (M ⊕ S(k, IV )) ⊕ M 0 = (M ⊕ M 0 ) ⊕ S(k, IV ) = Ek,IV (M ⊕ M 0 ) 3. Si on connaît le format des messages échangés, il est alors facile d’en transformer le sens : transformer TRANSFER $0000100.00 TO ACCOUNT #199 en TRANSFER $0100000.00 TO ACCOUNT #227 ne demande pas beaucoup d’information supplémentaire. 37 / 63

38

CHAPITRE 2. CORRECTIONS

2.3.8

3DES et 2DES

1. Avec la technologie actuelle, il est recommandé d’utiliser un algorithme de chiffrement symétrique avec une clé de taille minimale de 64 bits. Puisque DES utilise une clé secrète dont 56 bits sont effectifs, il n’est pas recommandé de chiffrer avec une seule application de DES. En pratique, on utilise 3DES (noté aussi T DES) avec 2 ou 3 clés différentes : 3DES = DESk1 ◦ DESk2 ◦ DESk3 Il a été prouvé que 3DES augmente la complexité de cryptanalyse par rapport à DES d’un facteur de 2 (c.à.d. 3DES est équivalent à DES avec une clé de 112 bits). 2. 2DES = DESk1 ◦ DESk2 (a) 2DES est plus rapide que 3DES mais plus lent que DES et a priori il est plus robuste que DES. Naïvement, on peut estimer la force cryptographique ajoutée par 2DES à un facteur de 2 puisque on applique deux fois DES avec deux clés différentes. (b) Analyse de sécurité de 2DES : i. Avec DES, on chiffre un bloc de 64 bits avec une clé de 56 bits. Avec 2DES, on chiffre un bloc de 64 bits avec une clé de 112 bits (56 + 56 bits). Si on considère un message m de 64 bits, le message chiffré c avec 2DES correspondant (c = 2DES(k; m)) est aussi de 64 bits. Pour un message m donné, il y a 264 valeurs possibles pour le message chiffré c. Puisqu’il y a 2112 valeurs possibles pour la clé, en moyenne il y a donc 2112 /264 = 248 valeurs de clés possibles qui donnent le même message c. ii. Meet in the middle attack : attaque permettant de faire un compromis entre le temps de calcul et l’espace de stockage utilisé pour la cryptanalyse (Diffie et Hellman 1977). L’attaquant construit deux listes L1 et L2 telles que : L1 = {DES(k; m); ∀k} et L2 = {DES −1 (k; c); ∀k}. Il retrouve ainsi deux listes de textes chiffrés intermédiaires. Parmi ces textes intermédiaires, il y a en moyenne 248 chiffrés que l’on retrouve dans les deux listes. L’attaquant retrouve ainsi en moyenne 248 clés possibles (meet in the middle). Si l’attaquant connaît une deuxième paire de texte clair/chiffré, il peut refaire les mêmes opérations en utilisant cette fois les clés obtenues à partir de la première paire et ainsi augmenter la probabilité de retrouver la clé secrète. iii. Le nombre de clés possibles en moyenne se réduit à 248 /264 = 2−16 . La probabilité que l’attaquant retrouve la clé secrète est donc égale à 1 − 2−16 Il faut savoir que la cryptanalyse de DES requiert un effort de l’ordre de 255 opérations du fait de la propriété de complémentarité de DES. Donc, l’attaquant de 2DES effectue en tout 255 opérations de chiffrement et 255 opérations de déchiffrement pour la première paire de textes clair/chiffré et 248 opérations de chiffrement et 248 opérations de déchiffrement pour la deuxième paire : un effort de l’ordre de 2 × (255 + 248 ) < 257 opérations. La cryptanalyse de 2DES nécessite donc un effort de l’ordre d’une attaque de recherche exhaustive d’une clé de 57 bits.

2.3. CHIFFREMENT ET MODES DE CHIFFREMENT

2.3.9

39

Algorithme de Berlekamp-Massey N

sN

0 1 2 3 4 5 6 7 8

0 0 1 1 0 1 1 1 0

d L f (X) 0 1 0 0 1 0 0 1 3 1 3 X +1 3 1 3 X +X +1 3 1 3 X + X2 + X + 1 1 3 X2 + X + 1 0 3 X2 + X + 1 1 5 X5 + X2 + X + 1 1 5 X5 + X3 + 1

m -1 -1 -1 2 2 2 2 2 7 7

g(X) 1 1 1 1 1 1 1 1 2 X +X +1 X2 + X + 1

Conclusion : Le LFSR de longueur 5 ayant pour polynôme de rétroaction X 5 + X 3 + 1 génère donc la suite donnée. Attention ! Le polynôme que l’on trouve via Berlekamp-Massey correspondant aux bits que l’on considère pour la rétroaction (X étant le bit le plus à GAUCHE dans le registre). Le polynôme se lit donc dans l’autre sens ...

39 / 63

40

CHAPITRE 2. CORRECTIONS

2.4

Méthodes de calcul

2.4.1

Square and Multiply

Pas de correction

2.4.2

Calcul modulaire

1. 2256 = 27 × 2249 = 128 × 2249 = 0 mod 128 2. 529 mod 66 = 1 donc 529436 mod 66 = 1 3. 1023 mod 1024 = −1 donc 10234096 mod 1024 = 1 4. 2308 = 4 × (1 + 64 × (1 + 8)) donc 4562308 = 456 × (456 × (4568 ))64 SQ : 4562 = 207936 SQ : 4658 = 209019 SQ : 45618 = 39216 SQ : 46572 = 86184 SQ : 456288 = 181830 MUL : 465577 = 118389 SQ : 4562308 = 165471


4

SQ : 4564 = 65037 MUL : 4569 = 175902 SQ : 45636 = 6555 MUL : 456144 = 318937 SQ : 456576 = 15162 MUL : 4561154 = 154470

d’où 4562308 = 165471

2.4.3

Théorème des restes chinois

Application - 1 Il s’agit de trouver x positif et minimal vérifiant le système :   x = 3 mod 17 x = 4 mod 11  x = 5 mod 6 D’après le théorème des restes chinois (puisque 17, 11 et 6 sont premiers entre eux deux à deux), les solutions sont de la forme : x = u1 × 11 × 6 × 3 + u2 × 17 × 6 × 4 + u3 × 17 × 11 × 5 + n × 17 × 11 × 6 ou encore x = 198u1 + 408u2 + 935u3 + 1122n avec n entier. Il reste à trouver les ui . On a x mod 17 = u1 × 11 × 6 × 3 mod 17 = 3 mod 17 donc u1 est l’inverse de 11 × 6 mod 17. On a par division euclidienne : 66 = 3 × 17 + 15

17 = 1 × 15 + 2

15 = 7 × 2 + 1

2.4. MÉTHODES DE CALCUL

41

On en déduit que 1 = 15 − 7 × 2 et puisque 2 = 17 − 1 × 15, on a 1 = 15 − 7(17 − 1 × 15) c’est-à-dire 1 = 8 × 15 − 7 × 17. Mais 15 = 66 − 3 × 17 d’où 1 = 8(66 − 3 × 17) − 7 × 17. On obtient pour finir 1 = 8 × 66 − 31 × 17 et u1 = 8. De la même manière, on trouve u2 = 4 et u3 = 1. Donc x = 198 × 8 + 408 × 4 + 935 + 1122n = 4151 + 1122n. 4151 est donc une solution possible pour notre cuisinier, mais ce n’est pas la plus petite. Il suffit d’effectuer la division de 4151 par 1122 pour trouver comme reste 785 qui est le nombre minimal de pièces que peut obtenir le cuisinier. Application - 2 1. 270

3. 20

2. 257

4. 785

Application - 3 Pas de correction

2.4.4

Autour des nombres premiers

1. • n2 − 8n + 15 = (n − 3)(n − 5) Pour que n n2 − 8n + 15 soit premier il faut que n − 3 = ±3 ou n − 5 = ±1 ⇔ n = 2, 4 ou 6; n2 − 8n + 15 vaut alors 3, −1 ou 3, seul 3 est premier, les solutions sont donc : 2 et 6. • n2 + 4n + 3 = (n + 1)(n + 3) Pour que n2 + 4n + 3 soit premier il faut que n + 1 = ±1 ou n + 3 = ±1 ⇔ n = −4, −2 ou 0, il vaut alors 3, −1 ou 3, seul 3 est premier ; les solutions sont donc : −4 et 0. 2. Valeurs des nombres entiers naturels n et m pour que le nombre 2n2 + 5mn + 3m2 soit premier. On a la factorisation suivante : 2n2 + 5mn + 3m2 = (n + m)(2n + 3m) Pour que 2n2 + 5mn + 3m2 soit premier, il est nécessaire que n + m = ±1 ou que 2n + 3m = ±1. Or n et m sont des entiers naturels donc n + m = ±1 ⇔ n + m = 1 ⇔ (n = 0 et m = 1) ou (n = 1 et m = 0) et 2n + 3m = ±1 est impossible ; Examinons maintenant les deux cas restants : → n = 0 et m = 1 : 2n2 + 5mn + 3m2 = 3 ⇒ premier, → n = 1 et m = 0 : 2n2 + 5mn + 3m2 = 2 ⇒ premier ; Au final, 2 solutions : (n; m) = (0; 1) ou (1; 0). 41 / 63

42

CHAPITRE 2. CORRECTIONS 3. Les 1 000 entiers consécutifs 1001! + 2, 1001! + 3, ..., 1001! + 1001 sont respectivement divisibles par 2, 3, ... , 1 001 et sont donc tous composés ; Par exemple, 1001! + 2 = 1 × 2 × 3 × · · · × 1001 + 2 = 2(3 × · · · × 1001 + 1) donc 2|1001! + 2 (et 1 < 2 < 1001! + 2); Ils forment donc 1 000 entiers naturels consécutifs, tous composés. Ainsi, les nombres premiers sont infinis mais on peut trouver des "plages" aussi grandes qu’on veut sans nombres premiers ! 4. On calcule 237900 mod 379001 en utilisant l’exponentiation rapide. On a 37900 = 32768 + 4096 + 1024 + 8 + 4 donc 237900 = 17168 × 455 × 22213 × 256 × 16 = 12802 mod 37901 donc 37901 n’est pas premier. Malheureusement, le théorème de Fermat ne permet pas de montrer directement qu’un entier est premier.

2.4.5

Test de primalité de Miller-Rabin

Indication 1. Factoriser x2 − 1 et utiliser que Z/pZ est intègre. 2. Appliquer le petit théorème de Fermat. 3. Poser i = sup{j > 0; bj n’est pas congru à 1} modulo p. 4. Corrigé 1. On factorise x2 − 1 en (x − 1)(x + 1). Par intégrité de Z/pZ, l’équation (x − 1)(x + 1) = 0 entraine x = 1 ou x = −1. s 2. On a bs = ad×2 = ap−1 . Le résultat est donc une conséquence immédiate du petit théorème de Fermat. 3. Posons = sup{j > 0; bj n’est pas congru à 1} modulo p. Un tel nombre existe car b0 n’est pas congru à 1 modulo p (l’ensemble que l’on considère est non vide), et pour tout j > s, bj ≡ 1 [p] (l’ensemble est majoré par s, et même par s − 1). Ainsi, on a i ∈ {0, . . . , s − 1}. D’autre part, b2i = bi+1 ≡ 1 [p]. D’après le résultat de la première question, bi ≡ 1 [p] ou bi ≡ −1 [p]. La première possibilité est exclue par définition de i. Donc bi ≡ 1 [p]. 4. Soit p un entier impair dont on souhaite tester s’il est premier. On le factorise sous la forme p = d × 2s + 1. Pour différentes valeurs de a, on calcule la suite bi donnée par l’énoncé. Si b0 6= 1 et pour tout i ∈ {1, . . . , s − 1}, bi n’est pas congru à −1 modulo p, alors on est sûr que p n’est pas premier. C’est le test de (non-)primalité de Miller-Rabin.

2.4.6

Algorithme p − 1 de Pollard

1. 19 048 567 n’est pas un multiple de 3, d’où le résultat. 2. Les puissances demandées sont 224 , 315 , 510 , 78 , 116 , 136 , 175 , 195 . 3. p − 1 est supposé 19-friable, donc s’écrit 2e2 3e3 . . . 19e19 . Par ailleurs, p − 1 6 p|n donc 2e2 < n ce qui implique que e2 6 24. De même e3 6 15, . . . , e19 6 5, et au bilan p − 1 = 2e2 3e3 . . . 19e19 divise Q = 224 315 510 78 116 136 175 195 .

2.4. MÉTHODES DE CALCUL

43

4. D’après le petit théorème de Fermat, on a ap−1 = 1 mod p. Comme p − 1 divise Q, on en déduit aQ = 1 mod p, c’est-à-dire ce qui est demandé. 5. p divise n par hypothèse et p divise aQ − 1 d’après la question précédente. Donc gcd(aQ − 1, n) est divisible par p, en particulier il est 6= 1. À cette étape, on a peut-être pas encore un facteur non trivial de n : en effet le gcd est certes 6= 1 mais peut être très bien égal à n. Aller plus loin et trouver un facteur de n nécessite donc d’avoir la chance que le pgcd soit < n. Ne pas avoir cette chance signifie que l’hypothèse p − 1 est 19-friable était fausse. Il faut alors recommencer l’algorithme avec une borne de friabilité plus grande (c’est-à-dire moins contraignante). 6. On calcule gcd(554 505, 19 048 567) = 5 281. Ce dernier est un facteur non trivial de 19 048 567.

2.4.7

Théorème de Wilson

Indication 1. Factoriser x2 − 1. 2. On pourra regrouper chaque élément de {¯1, . . . , p − 1} avec son inverse dans Z/pZ. 3. Appliquer le théorème de Bezout. Corrigé 1. L’équation x2 = 1 est équivalente à (x−1)(x+1) = 0, ce qui est équivalent à dire, puisque Z/pZ est un corps, x = 1 ou x = −1. ¯ . . . , p − 1} est inversible et son inverse est 2. Travaillons dans Z/pZ. Tout élément de {1, ¯ différent de lui-même, sauf pour 1 et −1 d’après la question précédente. Dans le produit ¯2 × · · · × p − 2, on peut donc regrouper chaque élément avec son inverse, et on trouve que ¯1 × · · · × p − 1 = ¯1 × p − 1 = −1 ce qui est le resultat attendu. 3. Soit a ∈ {1, . . . , n − 1}. Alors a est un facteur de (n − 1)! et donc il existe k tel que (n − 1)! = ak. On en déduit a × (−k) ≡ 1 [n], et donc a est inversible dans Z/nZ. Par le théorème de Bézout, ceci signifie que a est premier avec n, et ceci est vrai pour tout a de {1, . . . , n − 1}. Autrement dit, n est premier.

43 / 63

44

CHAPITRE 2. CORRECTIONS

2.5 2.5.1

Échange de clefs Fonctionnement clé privée vs clé publique

En cryptographie symétrique, une même clé K est utilisée pour le chiffrement et pour le déchiffrement, alors qu’en cryptographie asymétrique, une clé publique Kpub est utilisée pour chiffrer et une clé privée Kpriv est utilisée pour déchiffrer. Rappelons que les clés paramétrisent les algorithmes de chiffrement et de déchiffrement, mais que ces algorithmes sont supposés connus de tous. Pour assurer la confidentialité en symétrique, il faut que les protagonistes de l’échange, Alice et Bob, possèdent tous les deux la clé K, mais pas l’attaquant Oscar. Le problème majeur est donc celui de l’échange initial de cette clé. En contrepartie, les algorithmes symétriques sont très rapides et utilisent des clés courtes (ex : 128 bits pour AES). En asymétrique, seul le destinataire doit posséder Kpriv , laquelle ne doit pas être en possession de l’attaquant Oscar. Par contre la clé publique Kpub peut être connue de tous donc il n’y a pas de problème d’échange de clé. Bien sûr, on ne doit pas pouvoir calculer Kpriv à partir de Kpub . Ces algorithmes sont plus lents et les clés sont plus grandes (ex : 1024 bits pour RSA). Un exemple simple d’algorithme symétrique peut être pris parmi les chiffrements anciens (à détailler dans la rédaction) ; ces chiffrements sont abandonnés depuis bien longtemps. Un exemple d’algorithme symétrique moderne et sûr est l’algorithme Rijndael, actuel standard du chiffrement symétrique (AES). Pour le chiffrement asymétrique, RSA est l’exemple standard (à détailler dans la rédaction).

2.5.2

Clé privée vs clé publique

Pour qu’il y a de couples de personnes soit
un système à clé secrète, il faut autant de clés n,2 n(n−1) 16 . Ici cela vaut 17 × 8 = 136 et non 17 , ni 17!. Ce n’est pas non plus n(n − 1) 2 = (nombre d’arrangements), car les clés sont symétriques. Pour un système à clé publique, il faut 17 clés (autant que de participants).

2.5.3

Perte d’une clé privée

1. Il peut envoyer des courriers chiffrés en utilisant les clés publiques de ces interlocuteurs, il ne peut plus déchiffrer de messages reçus. 2. Il ne peut plus signer de courriers. Par contre, il peut vérifier les signatures des courriers qu’il reçoit à l’aide des clés publiques de ces interlocuteurs. 3. Á rien, car on ne peut absolument pas retrouver la clé privée à partir d’une clé publique. 4. Il n’a pas d’autre choix que de régénérer une nouvelle clé privée et de distribuer la clé publique correspondante à ses interlocuteurs.

2.5.4

Diffie-Hellman

Elle envoie à Bob la valeur g a mod p = 36 mod 23 = 16. Bob envoie à Alice la valeur g b mod p = 315 mod 23 = 12. Alice peut maintenant calculer la clé secrète : (g b mod p)a mod p = 126 mod 23 = 9 Bob fait de même et obtient la même clé qu’Alice : (g a mod p)b mod p = 1615 mod 23 = 9.

2.5. ÉCHANGE DE CLEFS

2.5.5

45

Attaque par le milieu de Diffie-Hellman

Dans le protocole de Diffie-Helmman, il suffit de supposer que l’attaquant actif réalise les opérations suivantes : 1. Lorsqu’ Alice envoie la valeur Ka à Bob, Eve bloque la communication puis tire uni˜ a ∈ G et envoie la valeur à formément aléatoirement un entier a ˜ ∈ Zq , calcule g a˜ = K Bob ; 2. Lorsque Bob envoie la valeur Kb à Alice, Eve bloque la communication puis tire uni˜ ˜ b ∈ G et envoie la valeur à formément aléatoirement un entier ˜b ∈ Zq , calcule g b = K Alice ; ˜ b , Alice calcule K ˜a ; 3. à réception de K b

˜ a , Alice calcule K ˜b ; 4. à réception de K a ˜ ab n’est ˜a = K 5. Contrairement au protocole réalisé entre utilisateurs honnêtes, l’égalité K b plus vérifiée. Cependant, si Alice envoie par la suite un message chiffré de façon symétrique ˜ a , Eve peut déchiffrer grâce à sa connaissance de ˜b (puisque K ˜ a = K ˜b ), avec la clé K a b b ˜ b = K a˜ prendre connaissance du ,message et éventuellement le rechiffrer avec la clé K a b (que Bob croit partager avec Alice) pour que la communication ait l’apparence d’une communication normale.

45 / 63

46

CHAPITRE 2. CORRECTIONS

2.6

Chiffrement

2.6.1

Kid-RSA

1. ed − 1 = (a0 M + a)(b0 M + b) = a0 b0 M 2 + M (a0 b + ab0 ) + ab − 1 = M (a0 b0 M + a0 b + ab0 + 1). Donc n = a0 b0 M + a0 b + ab0 + 1. Par suite si les nombres a, a0 , b, b0 sont > 3 alors M > 8 et n > 91. Il est important que n soit > 25 car comme on travaille modulo n si on veut avoir une chance que deux messages m et m0 distincts (0 6 (m, m0 ) 6 25) soient toujours chiffrés différemment il est nécessaire que cette condition soit réalisée. Remarquons que nM − ed = 1 et donc que tout nombre qui divise n et e divise 1. Donc e et n sont premiers entre eux. 2. Alice calcule cd mod n = edm mod n = m mod n = m. 3. Il suffit à Charlie de trouver un nombre d1 tel que ed1 = 1 + kn Comme e est premier avec n ceci revient à la résolution d’un problème de Bézout. 4. Pour signer un message m Alice utilise sa clé privée pour calculer s = md mod n et joint la signature s au message m. Celui qui reçoit le message m signé avec s n’a plus qu’à utiliser la clé publique d’Alice pour calculer se mod n et vérifier qu’il obtient bien m.

2.6.2

Chiffrement/Déchiffrement RSA

1. M 0 = 10011 (mod 319) = 265 2. On doit résoudre 11 × d = 1 (mod 280). On trouve d = 51 – soit en utilisant l’algorithme d’Euclide ; – soit en essayant à la main car 51 = (280/11) × 2 donc il suffit de deux essais pour trouver ; – soit en utilisant Euler, d = 11−1 (mod 280) d’où d = 11φ(280)−1 (mod 280) = 11φ(7.5.8)−1 (mod 280) = 11(6.4.4)−1 (mod 280) = 1195 (mod 280) = 1164+16+8+4+2+1 (mod 280) = 81.81.121.81.121.11 = 81.11 = (mod 280) = 51 (mod 280). 3. On doit calculer 13351 (mod 319). Dans les notes on donne 13325 = 133 (mod 319). Le résultat est donc 133 × 133 × 133 (mod 319) = 12. 4. Évidemment non car les messages à chiffrer/déchiffrer doivent appartenir à Zn , c’est à dire Z319 dans ce cas.

2.6. CHIFFREMENT

2.6.3

47

Exemple de RSA

1. n = 437 et φ(n) = (p − 1)(q − 1) = 396 2. gcd(e, φ(n)) 6= 1 dans les deux cas donc le d correspondant n’existe pas. 3. On a via Euclide d = −163 = 233 mod 396

n 143 247 319 323 403 407 583 4717

e C 17 84 5 115 11 133 25 19 7 346 17 50 19 207 21 2804

47 / 63

p 11 13 11 17 13 11 11 53

q m 13 2 19 20 29 12 19 19 31 5 37 128 53 192 89 2

48

CHAPITRE 2. CORRECTIONS

2.6.4

Chiffrement RSA

Examen 2012-2013 1. – Chiffrement : on convertit le message en un entier m ∈ [[1; N ]] et on calcule le chiffré c ≡ me mod N. 0.5pt – Déchiffrement : on calcule m ≡ cd mod N. 0.5pt – p, q, φ et d doivent rester secrets. 0.5pt – • Révéler p permet d’obtenir q = N/p, puis φ et donc d, de même avec q. • Révéler φ permet d’obtenir d à partir de e. • Il reste à voir comment d permet d’obtenir le reste. Supposons donc e et d connus. Il existe un entier k tel que ed = 1 + k, donc k est une approximation de ed/n (puisque φ est de l’ordre de n). On sait que (ed − 1)/k = φ = (p − 1)(q − 1), ce qui s’écrit (ed − 1) = k − 1 = N − p − q. On obtient donc le système  p + q = N − (ed − 1)/k + 1 pq = N

2. • • • • ?

3. •

• •

Finalement, il suffit d’essayer de résoudre ce système pour des valeurs proches de k, par exemple celles de l’intervalle [[ed/n − 5; ed/n + 5]]. Quand on obtient une solution (p; q), on a trouvé k. 2pts La factorisation de N donne p = 59 et q = 17 (ou l’inverse). L’entier φ vaut alors 58 × 16 = 928 1pt En utilisant l’algorithme d’Euclide, nous obtenons : 928 = 3 × 309 + 1. Donc 1 = 928 + 3 × (−309) et l’inverse de e = 3 mod φ est 619 (= 928 − 309). 1pt Le chiffré c vaut 43 = 64. 0.5pt Il est facile connaissant cette valeur de retrouver m = 641/3 . En effet, il n’y a pas de réduction modulaire puisque m < N 1/e . 1pt Pour éviter ce problème, on utilise une technique de remplissage, appelée padding, c’est-à-dire qu’on ajoute au texte clair avant de le chiffrer une valeur structurée et aléatoire. On a 65 = 5×13, donc p = 5, q = 13 (ou l’inverse) et φ = (p−1)×(q −1) = 4×12 = 48. Il faut choisir un couple de clefs publique/privée (e; d) tel que e soit premier avec φ (donc e n’est divisible ni par 2 ni par 3) et ed ≡ 1 mod 48. En ignorant les couples symétriques, on obtient la table suivante : e 5 7 11 13 17 19 23 25 31 41 47 d 29 7 35 37 17 43 23 25 31 41 47 Il faut éliminer tous les cas triviaux où e = d dans lesquels le déchiffrement est évident, pour conserver les couples (5; 29), (11; 35), (13; 37) et (19; 43) (et leurs symétriques). 1pt Le chiffré de m = 4 est c ≡ 45 mod 65. Or, 43 ≡ 64 ≡ 1 mod 65, donc c ≡ 16 ≡ 49 mod 65. 0.5pt La clef privée associée à e = 5 est d = 29. Pour faciliter le calcul, effectuons une exponentiation modulaire en remarquant que 29 = 24 + 23 + 22 + 1 : 492 ≡ (16)2 ≡ 256 ≡ 4 mod 65 494 ≡ (−4)2 ≡ 16 mod 65 8 2 49 ≡ 16 ≡ −4 mod 65 4916 ≡ (−4)2 ≡ 16 mod 65 On en déduit que : 1.5pt c29 ≡ 4916 × 498 × 494 × 49 = −4 × 16 × 16 × (−16) ≡ (−64) × 4 ≡ 4 mod 65

2.6. CHIFFREMENT

2.6.5

49

RSA-3

1. Il n’y a rien a changer, on choisit un couple d’entiers (e; d) tel que ed = 1 mod φ(n), on chiffre le message clair x par y = xe mod n et on déchiffre le message chiffré y par x = y d mod n. La clef publique est (e; n), la clef privée (d; p; q; r) et l’ensemble des messages possibles est Z/nZ car pour tout message m ∈ Z/nZ nous pouvons montrer comme pour RSA que m = DRSA−3 (ERSA−3 (m)). On a x = y d mod n = (xe )d mod n = xed mod n. • Si x est premier avec n, alors d’apres le petit théorème de Fermat, xφ(n) = 1 mod n donc xed = x1+`φ(n) = x mod n pour un certain `. Cas plus compliqué (un peu au-delà de notre programme) : • Si x n’est pas premier avec n, alors x est un multiple de p premier avec qr ou un multiple de q premier avec pr ou un multiple de r premier avec pq. Par exemple pour un multiple de p premier avec qr, la représentation de x ∈ Z/nZ dans Z/pZ × Z/qrZ est : (0e = 0; xqr = x mod qr) qui est chiffré par ERSA en : (0; xeqr mod qr = yqr ), lui-même déchiffré par DRSA en : d (0d = 0; yqr = (xeqr )d mod (qr) = xed qr mod (qr)).

Or si ed = 1 mod φ(n), il existe k tel que ed = 1 + k(p − 1)(q − 1)(r − 1) donc ed = 1 mod (q − 1)(r − 1) = 1 mod φ(qr). xqr = x mod (qr) est premier avec qr (parce que x est un multiple de p premier avec qr) φ(qr) donc d’après le petit théorème de Fermat, xqr = 1 mod (qr) et xed qr = xqr mod (qr). d Dans Z/nZ, le couple (0; yqr mod (qr) = xqr ) de Z/pZ × Z/qrZ redonne évidemment par le théorème des restes chinois x.

2. Les messages dangereux pour RSA sont ceux qui ne sont pas premiers avec n, puisqu’alors on trouve un facteur commun au message et à n donc un des deux facteurs premiers de n, on en déduit l’autre puis φ(n), on obtient alors d l’inverse modulaire de e modulo φ(n), c’est-a-dire toute la clef secrète. Il en va de même ici : les messages dangereux pour RSA-3 sont ceux qui ne sont pas premiers avec n, puisqu’alors on trouve un facteur commun au message et à n, c’est-àdire soit un facteur, disons p, soit le produit de deux facteurs pq et on déduit le facteur n , dans tous les cas on déduit un des trois facteurs de n et le produit des deux autres. r = pq En soi un seul message n’est pas dangereux, il faudra avoir la chance d’en trouver un second qui nous apporte la connaissance d’un autre facteur de n pour connaître alors la factorisation de n, d’où φ(n) et d l’inverse modulaire de e modulo φ(n), c’est-a-dire toute la clef secrète. 49 / 63

50

CHAPITRE 2. CORRECTIONS 3. Algorithme On reçoit y et on doit calculer x = y d mod n. On calcule dp = d mod (p − 1);

dq = d mod (q − 1);

dr = d mod (r − 1);

puis xp = y dp mod p;

xq = y dq mod q;

xr = y dr mod r

On a x = xp mod p, x = xq mod q et x = xr mod r. On utilise une première fois le théorème chinois pour déduire x modulo le produit pq. La relation de Bézout pour p et q est up + vq = 1, on a x = xpq mod (pq) avec xpq = vqxp + upxq . On utilise une seconde fois le théorème chinois pour déduire x modulo n. La relation de Bézout pour pq et r est u0 pq + v 0 r = 1, on a finalement x = v 0 rxpq + u0 pqxr mod n. 4. e = 19, N = pqr = 105, φ(N ) = (p − 1)(q − 1)(r − 1) = 48, d = e−1 mod 48 = −5 = 43 car −5 × 19 = 95 = 2 × 48 − 1. Le chiffre de x = 13 est xe mod N = 1319 mod 105. On a 132 = 169 = 105 + 64 = 64 mod 105 et 642 = 4096 = 39 × 105 + 1 = 1 mod 105 donc xe mod N = 1319 mod 105 = 649 × 13 = 14 × 64 × 13 = 64 × 13 = 832 = 8 × 105 − 8 = −8 = 97 mod 105. Le déchiffré de y = 11 est y d mod N = 1143 mod 105. On a 112 = 121 = 105 + 16 = 16 mod 105, 16 × 16 = 256 = 2 × 105 + 46 = 46 mod 105, 462 = 2110 = 20 × 105 + 16 = 16 mod 105 et 16 × 46 = 736 = 7 × 105 + 1 = 1 mod 105, donc y d mod N = 1143 mod 105 = 1621 × 11 = 4610 × 16 × 11 = 165 × 16 × 11 = 166 × 11 = 463 × 11 = 16 × 46 × 11 = 1 × 11 = 11.

2.6. CHIFFREMENT

2.6.6

51

Chiffrement El Gamal

1. Il chiffre alors son message nombre par nombre : 11 est chiffré en 2035 × 11 mod 97 = 46 × 11 mod 97 = 21 81 est chiffré en 2035 × 81 mod 97 = 46 × 81 mod 97 = 40 01 est chiffré en 2035 × 1 mod 97 = 46 × 1 mod 97 = 46 09 est chiffré en 2035 × 9 mod 97 = 46 × 9 mod 97 = 26 Il transmet enfin à Alice le couple (71, 21 40 46 21 26). 2. Pour déchiffrer le message de Bob, Alice détermine le nombre x = 97 − 1 − 45 = 51. Pour chaque partie m0 du message, elle calcule 7151 × m0 mod 97 : 7151 × 21 mod 97 = 19 × 21 mod 97 = 11 7151 × 40 mod 97 = 19 × 40 mod 97 = 81 7151 × 46 mod 97 = 19 × 46 mod 97 = 1 7151 × 21 mod 97 = 19 × 21 mod 97 = 11 7151 × 26 mod 97 = 19 × 26 mod 97 = 9. Elle retrouve le message 118 101 119 après concaténation.

2.6.7

Changement de clés

Notons d le nombre de jours jusqu’à ce que Alice et Bob changent leur clé le même jour. Puisque Alice change sa clé tous les 25 jours et qu’elle a changé sa clé aujourd’hui, d doit être divisible par 25. Puisque Bob change sa clé tous les 31 jours et qu’il a changé sa clé il y a trois jours, d + 3 doit être divisible par 31. Ainsi d doit véri ?er le système de congruences : d = 0 mod 25 d = −3 mod 31 Par le théorème des restes chinois, ce système équivaut à la congruence d = 400 mod 775, et donc Alice et Bob changeront leurs clés le même jour dans 400 jours.

51 / 63

52

CHAPITRE 2. CORRECTIONS

2.7

Attaques sur RSA

2.7.1

Attaque par module commun

Oscar connaît (eA , eB , n) et (cA , cB ). Par l’algorithme d’Euclide étendu, il calcule facilement (en temps -presque- linéaire du nombre de bits de n) les coefficients de Bezout r et s tels que reA + seB = 1. Oscar peut alors calculer (par exponentiation rapide) crA .csB mod n = mr.eA +s.eB mod n = m Moralité : ne jamais utiliser le même n pour un groupe d’utilisateurs.

2.7.2

De φ(n) à la factorisation

n = pq et φ(n) = (p − 1)(q − 1) = n − p − q + 1 donc p + q = n − φ(n) + 1. Nous avons la somme et le produit de p et q. Nous en déduisons alors que p et q sont les deux racines de l’équation du second degré : X 2 − (n − φ(n) + 1)X + n = 0 Vérification : p2 − (n − n + p + q − 1 + 1)p + n = p2 − pn + pn − p2 − pq + p − p + n = 0.

2.7.3

RSA avec deux facteurs trop proches

1. 1 1 1 t2 − s2 = ((p + q)2 − (p − q)2 ) = (p2 + 2pq + q 2 − p2 + 2pq − q 2 ) = (4pq) = pq = n. 4 4 4 2. t2 = n + s2 > n donc t >

√

n, de plus s est petit dès que p et q sont proches.

1. Avec n = 24960007, on trouve t = 4996 et s2 = 9 en une seule itération. Donc n = 4993 × 4999. Avec n = 3649574023, on démarre à t = 60412, on trouve s2 = 35721 = 1892 , donc une seule itération suffit et n = 60601 × 60223. 2. Compléxité de l’algorithme : √ = t. A varie dans le pire des cas de d ne à p+q 2 Le nombre d’itérations de la boucle est majoré par (valeur d’arrivée - valeur de départ) : √ √ √ √ √ p+q−2 pq ( p− q)2 t − n = p+q − n = = 2 √ 2 √ 2 (p− pq)2 ( n−p)2 = = 2p 2p √ √ 4 3. Donc si p diffère de n de moins de 4n, le nombre d’itérations est majoré par √ √ 4n n = 6 1. 2p p Donc le nombre d’itérations est égal à 1.

2.7. ATTAQUES SUR RSA

2.7.4

53

Malléabilité de RSA

1. Rappelons le principe de la signature dite RSA naïf c’est-à-dire la primitive qui ne prend pas en compte les renforcements rendus nécessaires par les attaques. Paramètre public : ` : la taille de la clé RSA, i.e. la taille en nombre de bits du module n Initialisation : • Tirer aléatoirement deux nombres premiers p et q de taille 2` bits • Calculer n = pq • Tirer une valeur e aléatoire telle que gcd(e, (p − 1)(q − 1)) = 1 • Calculer d = e−1 mod (p − 1)(q − 1) – Message : un élément x ∈ {1, . . . , n} – Clé publique : KP = (e; n) – Clé privée : KS = (d; n) – Signature : S(x) = s = xd mod n – Vérification : x = se mod n 2. Ève a réussi à se procurer s1 = md1 mod n et s2 = md2 mod n. Dans ce cas, elle est capable de signer le message mε11 mε22 mod n, où εi ∈ {−1, 1} puisque la signature vaut alors : (mε11 mε22 )d mod n = mε11 d mod n × mε22 d mod n = sε11 sε22 mod n 3. Pour tous les couples (mi , S(mi )) connus d’Ève, on a Y dα S(mi ) = µj i,j mod n j

Eve est donc capable de calculer toutes les signatures de la forme : Y d P εi αi,j Y Y Y dε α mod n µj i S(mi )εi mod n = µj i i,j mod n = i

i

j

j

où εi ∈ {−1, 1}. 4. Compte tenu du résultat de la question précédente, il faut qu’Ève ait en sa possession des messages tels qu’il soit possible de trouver un ensemble d’indices I pour lesquels ∀j,

X

εi αi,j = βj .

i∈I

Si elle ne trouve pas un tel ensemble d’indices, elle doit trouver un moyen de faire signer à Alice un message d’apparence anodine de la forme ci-dessus tel qu’il complète l’ensemble d’indices recherché. L’ensemble d’indices recherché peut être vu comme un vecteur solution d’un système linéaire.

2.7.5

Le temps de factorisation des grands entiers

1. On a W = 8000 pour log2 N = 512 et log2 512 = 9 soit :
W = k exp (64/9)1/3 5121/3 (log2 512)2/3 √
3 = k exp (64 × 9 × 512)1/3 = k exp( 294912) ≈ k exp(66.563) D’où k ≈ 9.89 × 10−26 Mips-year. 53 / 63

54

CHAPITRE 2. CORRECTIONS 2. • Pour log2 N = 768, on obtient : W = 9.89 × 10−26 exp((64 × 768 × 9.582 /9)1/3 ) = 9.89 × 10−26 exp(79.46) ≈ 3200 millions de Mips-year. • Pour log2 N = 1024, on obtient : W = 9.89 × 10−26 exp((64 × 1024 × 100/9)1/3 ) = 9.89 × 10−26 exp(89.97) ≈ 117 millions de millions de Mips-year.

2.8

Signature

2.8.1

Signature RSA

1. Avec p = 17 et q = 23, on a n = p × q = 391 et φ(n) = (p − 1)(q − 1) = 352. 2. e = 11 n’est pas un exposant de vérification correct car il n’est pas premier avec φ(n). En effet on a pgcd(11, 352) = 11. e = 13 en revanche convient et on peut calculer l’exposant de signature correspondant par l’algorithme d’Euclide étendu : 352 = 13 =

13 × 27 + 1 1 × 13 + 0

On a donc : 1 × 352 + (−27) × 13 = 1 Donc modulo φ(n) on a 13 × (−27) = 1. D’où d = −27 = 325 mod 352 3. SIGN (100, 325) = 100325 mod 391. On a 325 = 256 + 64 + 4 + 1 donc on calcule : 100325

= = = = = = =

100 × (100 × (100 × 1004 )16 )4 mod 391 100 × (100 × (100 × 186)16 )4 mod 391 100 × (100 × 22316 )4 mod 391 100 × (100 × 52)4 mod 391 100 × (117)4 mod 391 100 × 16 mod 391 36 mod 391

4. On calcule 3613 mod 391. On a 13 = 8 + 4 + 1 donc on calcule : 3613

2.8.2

= = = = =

36 × (36 × 362 )4 mod 391 36 × (46656)4 mod 391 36 × (127)4 mod 391 36 × 220 mod 391 100 mod 391

Signature aveugle avec RSA

Soit m le message à signer on cherche à obtenir md mod n. On envoie xe m pour signature, on reçoit donc en retour (xe m)d = xmd mod n comme x est aléatoire le signataire n’a aucun moyen de savoir quel message est signé.

2.8. SIGNATURE

2.8.3

55

Signature El Gamal

1. p = 467 est un nombre premier (il suffit de tenter une division par 2, 3, 5, 7, 11, 16, 17 ou p−1 19 pour s’en apercevoir) et on a g 2 6= 1 : g est donc d’ordre p − 1 (générateur). 2. y = g x = 265 mod p. Comme 65 = 64 + 1, ça va très vite : 265 = 2 × (216 )4 = 2 × 655364 = 2 × 1564 = 2 × 369 = 271 mod 467. 3. • k = 64 est un mauvais choix de nombre aléatoire, car on ne pourrait peut-être pas trouver b tel que m = xa + kb mod (p − 1). On peut vérifier que pour tous les b allant de 1 à 466, 100 6= 65 × (264 mod 467) + 64 × b. Mais il y a d’autres valeurs de m qui donnerait une égalité. Ainsi a = 369 = 264 mod 467, b = 42 et m = 111 vérifient l’égalité : 111 = 65 × 369 + 64 × 42 mod 466. • k = 213 est un bon choix car gcd(213, 466) = 1, donc on pourra diviser par k : Via Euclide on a : 16 × 466 + (−35) × 213 = 1 mod 466. L’inverse de 213 est donc −35 qui vaut 431 mod 466. La signature est a = g k = 2213 mod 467 = 29 et b = (m − xa) × k −1 = (100 − 65 × 29) × 431 mod 466 = 31. 4. On calcule les deux valeurs suivantes : gm y a ab

2.8.4

= = =

4

2100 = (2 × (26 )4 ) = (2 × 644 )4 (2 × 241)4 = 189 mod 467 27129 × 2931 = 322 × 295 = 189 mod 467.

Signature El Gamal : utilisation de l’aléa

1. L’exposant x est choisi dans [1, φ(p)] = [1, p − 1]. 2. Soient m et m0 les deux messages et (r, s) et (r, s0 ) les deux signatures (les composantes r de la signature sont nécessairement identiques si le même aléa est utilisé). On a alors : s = k −1 (h(m) − xr) mod p − 1 et s0 = k −1 (h(m0 ) − xr) mod p − 1 d’où par soustraction : s − s0 = k −1 (h(m) − h(m0 )) mod p − 1. On en tire k = (h(m) − h(m0 ))(s − s0 )−1 mod p − 1, puis on peut calculer x = (h(m) − ks)r−1 mod p − 1. Il s’agit donc d’un cassage total (récupération de la clé secrète) dans une attaque à deux messages connus. 55 / 63

56

CHAPITRE 2. CORRECTIONS

2.8.5

Signature El Gamal sans vérification modulaire

1. De s0 = sα on déduit : s0 = k −1 (h(m)α − xrα) = k −1 (h(m0 ) − xrα) mod p − 1 D’où l’idée de poser r0 = rα mod p − 1 pour que s0 ait la bonne forme. Mais il faut aussique le résidu modulo p soit correct, donc on doit avoir r = r0 mod p car c’est le même aléa k sous-jacent. 2. On a deux équations qui définissent r0 modulo p et r0 modulo p − 1 : comme p et p − 1 sont premiers entre eux, il existe une solution r0 à ces deux équations et elle est unique modulo p(p − 1) (d’après le théorème des restes chinois). 3. Le type d’attaque est une attaque à messages connus (avec un seul message), produisant une falsification universelle (cpacité à signer n’importe quel message).

2.8.6

Signature GHR (Gennaro-Halevi-Rabin)

1. Connaissant p0 , on a p = 2p0 + 1, un diviseur de N. 2. On peut écrire N en fonction du produit p0 q 0 comme suit : N = (2p0 + 1)(2q 0 + 1) = 4p0 q 0 + (2p0 + 2q 0 ) + 1. Si on connait la valeur de p0 q 0 , on peut donc connaître aussi la valeur de p0 + q 0 . Avec la somme et le produit, on en déduit une équation du second degré dont p0 et q 0 sont les racines. 3. On a φ(N ) = (p − 1)(q − 1) = 4p0 q 0 . 4. Puisque u est d’ordre 2p0 q 0 , les exposants dans une exponentiation en base u peuvent être 0 0 calculés modulo 2p0 q 0 . En effet u2p q = 1 mod N par hypothèse donc ajouter un multiple de 2p0 q 0 à un exposant revient à multiplier le résultat par une puissance de 1. −1

5. On a s = um mod N et celui qui vérifie la signature connaît M (et donc m) et s, en plus des paramètres publics. Il lui suffit donc de vérifier que sm = u mod N. 6. Dans le problème RSA, étant donné (N, e, v), il faut trouver x tel que xe = v mod N. Ici, étant donné (N, v), il faut trouver (x, e) satisfaisant la même relation : la différence, c’est que l’attaquant a le choix de e. 7. Si on autorise e = 1, le problème est trivial : (x = v, e = 1) serait toujours une solution. 8. Supposons que l’on sait résoudre un problème RSA : à partir de (N, e, v), trouver x. Il est alors trivial de résoudre le flexible RSA : étant donné (N, v), on prend n’importe quel e, et par hypothèse on sait trouver le x correspondant.

2.9. HACHAGE

2.9 2.9.1

57

Hachage Fonction de hachage faiblement sans collision

1. Si pour x0 donné on peut trouver x tel que h(x) = h(x0 ) alors on peut utiliser ce même couple pour montrer que h n’est pas sans collision. Donc non faiblement sans collision implique non sans collision : par contraposée, on obtient le résultat. Si une fonction n’est pas faiblement sans collision alors, pour x donné, on peut trouver x0 tel que h(x0 ) = h(x). Comme on est capable de trouver un antécédent à y = h(x), la fonction n’est pas à sens unique. 2. On prend, pour n fixé, la fonction de Fn2 → Fn2 qui à x associe x. Cette fonction est bien sans collision, mais elle n’est pas à sens unique puisque l’on peut facilement trouver des antécédents.

2.9.2

Fonction de hachage et signature

1. Supposons que l’on ait un message de n/2 mots avec une signification donnée. On prend le même message mais en ajoutant soit un nouveau caractère blanc entre les mots soit pas. Cela donne 2n/2 messages qui ont le même sens, mais il peut y avoir un léger décalage entre les mots auquel on ne fait pas forcément attention. Par paradoxe des anniversaires on peut donc trouver une collision pour un haché de longueur n avec ces 2n/2 possibilités. 2. La vérification de la signature se fait uniquement à partir du haché d’un message donc deux messages avec le même haché auront la même signature.

2.9.3

Le buzz free mobile

Non pas du tout. Il n’est pas possible de faire sortir ce qu’on décide à la fonction de hachage. Inversement, étant donné une écriture, si cryptique soit-elle, d’un message caché qu’on voudrait mettre dans la valeur de hachage, il est impossible de trouver un antécédent.

57 / 63

58

CHAPITRE 2. CORRECTIONS

2.10

Authentification

2.10.1

Authentification à clef secrète

1. Il n’est pas possible de faire de l’authentification mutuelle par mot de passe tout simplement parce qu’on ne peut donner un mot de passe qu’à une entité de confiance (on doit être sûr de qui elle est) ce qui n’est évidemment pas le cas si on a besoin d’authentification mutuelle 2. Le faux écran de login (par exemple). Il est possible si un serveur DNS est compromis qu’un nom renvoie à une adresse IP différente. Un utilisateur non averti peut donc penser communiquer avec le véritable serveur. 3. Il suffit que l’attaquant C lance en parallèle une autre session d’authentification mutuelle vers A en rejouant immédiatement les aléas envoyés et en entrelaçant correctement les envois de manière à faire calculer à A les valeurs des réponses. Cela donne : 1

A tire une valeur aléatoire rA et l’envoie à C qui se fait passer pour B; C rejoue immédiatement la valeur en lançant en parallèle une autre session d’authentification ; 0 et calcule A tire une valeur aléatoire rA 0 α = EK (rA , rA ). A envoie α à C;

1bis

2bis 2 3

C renvoie alors α (qu’il ne peut pas déchiffrer) à A; A calcule DK (α). Il retrouve rA : C s’est authentifié. Il prend connaissance 0 0 à C; . Il envoie rA de rA

3bis

0 à A. C renvoie rA

4. Le problème provient du fait que les messages ne sont pas personnalisés et que les procédés sont symétriques. Afin d’introduire de la dissymétrie dans un procédé à clé secrète, il faut utiliser des MAC. On aménage alors le protocole précédent en concaténant les identités aux valeurs aléatoires tirées par chaque partie avant de calculer le MAC.

2.10.2

Authentification à clef publique

On fait un protocole de défi-réponse. Par exemple pour du chiffrement à clé publique. On veut authentifier la personne qui connait la clé secrète associée à une clé publique. On choisit un message aléatoire qu’on chiffre avec la clé publique. Le défi est de déchiffrer le message chiffré. Si la personne est capable de renvoyer le message déchiffré c’est qu’il connait le secret. Pour la signature le défi est de signer un message aléatoire qu’on vérifie avec la clé publique.

2.10.3

Schéma de Schnorr

1. Comme P connait s, il calcule y = r + es mod q et le transmet à V. Alors αy v e = αr+es α−es = αr = x mod p donc la vérification est positive.

2.11. PKI, CERTIFICATS

59

2. U réussit son identification si x = αy v e mod p, soit si αy = xv −e mod p, αr−se mod p, ce qui est équivalent à y = r − se mod q. Donc U a une chance sur q de succès. 3. U peut procéder de la façon suivante : il choisit d’abord y aléatoirement, puis calcule x = αy v e mod p. Notons qu’il n’a pas besoin de connaitre s pour cela, et que le calcul de x est rapide. Il envoie ensuite x, puis y. 4. En effet, U a trouvé y tel que y = r + es mod q et y 0 tel que y 0 = r + e0 s mod q. Alors y − y 0 = (e − e0 )s et, comme (e − e0 ) 6= 0 mod q, (e − e0 ) est inversible modulo q. Il peut donc calculer s par la formule : s = (e − e0 )−1 (y − y 0 ) mod q. Notons que pour cela il a seulement besoin d’inverser un entier modulo q et de multiplier deux entiers modulo q, toutes opérations rapides.

2.11 2.11.1

PKI, certificats PKI

On suppose que tout le monde a la clé publique d’une autorité. Pour signer un message on envoie, message signé avec sa clé publique plus le certificat de la clé signé par l’autorité. En recevant le message on commence par vérifier la validité du certificat avec la clé publique de l’autorité, puis si c’est bon la clé publique du signataire est validée et on peut vérifier la signature. De façon il suffit simplement d’avoir la clé publique d’une autorité et pas besoin de passer par un annuaire. La vérification se fait donc sans connexion nécessaire.

2.11.2

Certificats

1. Le fait que deux certificats soient signés par la même clef ne pose aucun problème. C’est tout simplement le cas quand une autorité de certification signe des certificats suivant la norme X.509 ou lorsque qu’une personne signe des certificats PGP de plusieurs autres personnes. 2. C’est ici une situation très problématique puisque deux personnes différentes possèdent des clefs publiques identiques : d’une part chacune d’entre elles peut lire les messages chiffrés destinés à l’autre personne ; d’autre part il sera impossible de différencier les signatures des deux personnes. 3. Si deux certificats différents ont la même signature, cela signifie que la fonction de hachage utilisée pour la signature a créé une collision. La signature de l’un des deux certificats peut avoir été faite par un pirate qui a constaté une collision sur la fonction de hachage.

2.11.3

Distinguer les clefs utilisées dans PGP

On note respectivement k1 , k2 , k3 et k4 les clefs introduites dans l’énoncé de cet exercice. 1. k2 et k3 sont symétriques, k1 est la clef privée de A et k4 est la clef publique de B. 2. On considère généralement qu’une clef symétrique devrait posséder entre 128 et 256 bits (128 bits est le cas le plus courant en pratique). La taille d’une clef asymétrique devrait être entre 1024 et 4096 (1024 est le cas le plus courant en pratique). 59 / 63

60

CHAPITRE 2. CORRECTIONS 3. La clef k1 (resp. k4 ) est typiquement générée quand A (resp. B) configure son environnement PGP pour la première fois. Cette clef ne devrait être générée qu’une seule fois, sauf si elle a expiré ou a été révoquée. La clef k2 est également générée quand A configure son environnement PGP, ou quand A change son mot de passe. En effet, la clef k2 est dérivée directement du mot de passe de A. Elle est utilisée pour protéger k1 sur le disque. La clef k3 est une clef de session qui n’est utilisée qu’un seule fois et une nouvelle est générée à chaque fois qu’un courrier est chiffré.

2.11.4

Hachés de mots de passe

1. Étant donné que la fonction de hachage utilisée dans le mécanisme d’authentification est irréversible, le vol du fichier des hachés ne divulgue pas les mots de passe. 2. Il est préférable de protéger l’accès aux hachés des mots de passe car, bien que la fonction de hachage soit irréversible, les mots de passe peuvent souvent être retrouvés en utilisant soit une attaque par dictionnaire. 3. Cette protection ne serait pas nécessaire si les utilisateurs choisissaient des mots de passe suffisamment complexes.

2.11.5

Le protocole HTTPS

1. Le protocole SSL avec un certificat serveur offre d’abord une authentification du partenaire accédé par une vérification que ce serveur détient bien la clef privée correspondant à la clef publique diffusée. Ensuite, la communication est chiffrée, on a donc des garanties sur la confidentialité des échanges ainsi que sur l’intégrité de la communication pendant toute sa durée. 2. Le certificat n’inclut pas seulement la clef publique, mais également une signature de cette clef publique par un autre certificat. (Celui-ci pouvant également être un certificat intermédiaire.) La racine de cette chaîne de certification doit être un certificat pré-installé sur le navigateur (ou obtenu indépendamment en préalable à la communication). L’utilisateur peut alors être sûr que le certificat diffusé par le serveur appartient bien à l’organisme indiqué s’il vérifie la chaine de certification, s’il a confiance dans le certificat racine et s’il a confiance dans les organismes détenteurs des certificats intermédiaires pour avoir fait les vérifications nécessaires avant de signer les certificats dérivés. (Il s’agit alors de tiers de confiance ou d’autorités de certification.) 3. Le certificat serveur n’offre qu’une authentification du serveur. Si le service accédé gère une base de comptes utilisateurs, ceux-ci doivent donc également en plus s’authentifier. Cette authentification du client peut éventuellement s’effectuer via un nom d’utilisateur et un mot de passe. Cette méthode est moins forte qu’une technique faisant appel à des algorithmes de cryptographie asymétriques, mais elle est bénéficie néanmoins via HTTPS de la protection offerte par le canal chiffré et signé de SSL. 4. Dans ce cas, l’authentification du client, appuyée sur un certificat et une authentification à clef privée/clef publique offre des garanties bien plus importantes en terme de sécurité. Par contre, il faut alors gérer une procédure de délivrance de ces certificats clients (incluant leur signature par un tiers de confiance, après vérification de l’identité du demandeur par exemple).

2.11. PKI, CERTIFICATS

61

5. La clef privée associée à un certificat ne doit être que très rarement stockée en clair (notamment sur disque). Elle est protégée par un chiffrement symétrique dont la passphrase constitue la clef. C’est donc un mot de passe permettant de déverrouiller l’usage du certificat et de protéger la clef privée de l’utilisateur en cas de vol (par exemple afin de lui laisser le temps de détecter le vol et de révoquer son certificat). 6. Si une passphrase est aussi utilisée sur le serveur, à chaque lancement du service web, il sera nécessaire de la fournir au programme afin qu’il puisse accéder à la clef privée du certificat serveur. Il est peu probable que ceci soit effectué de manière interactive (à chaque redémarrage...). Il est plus probable qu’en pratique, soit la clef privée est effectivement stockée en clair sur le serveur, soit la passphrase en question est stockée dans les paramètres de configuration du serveur (ce qui n’est pas mieux). Ce faisant, les administrateurs web/système dérogent vis à vis du certificat serveur aux règles de protection qu’ils recommandent à leurs utilisateurs pour les certificats clients.

2.11.6

La carte bleue

1. Une signature de la clé publique, ou même d’un message contenant la clé publique kP et d’autres infos comme le nom du détenteur, le numéro de la carte, sa date d’expiration etc, le tout signé avec une clé privée de la banque. Cette signature (certificat) peut être vérifiée par qui dispose de la clé publique de la banque. 2. Il faudrait que tous les distributeurs connaissent les clés publiques de toutes les banques. C’est facile en terme de stockage, ou du moins pas trop dur, mais logistiquement irréalisable (on ne peut pas mettre à jour tous les distributeurs de la planète chaque fois qu’une nouvelle banque est créée). Visa et Mastercard, eux, permettent de résoudre ce problème. Ils donnent aux banques un certificat où leur clé publique est signée par la clé privée de Visa (par exemple). Alors il suffit pour vérifier que les distributeurs connaissent les clés publiques d’une poignée d’organismes centraux : Visa, Mastercard, GIE Cartes bancaires, ... 3. Avec la clé secrète de la carte, un attaquant peut fabriquer une fausse carte qui semble valide, puisqu’elle présente le bon certificat signé par la banque, et (puisque la clé secrète est découverte par l’attaquant) qu’elle peut s’authentifier. D’autre part, cette carte peut répondre toujours oui à toutes les questions (oui c’est le bon code, oui j’approuve la transaction, etc). On appelle cela une yes-card. S’il découvre la clé secrète de la banque, l’attaquant peut produire des nouveaux certificats. Il peut donc créer des yes-cards associées à d’autres identités, avec d’autres numéros, d’autres dates d’expiration, etc.

61 / 63