Correction TD4 Asymmetric Ciphers

Ce document présente la correction de plusieurs exercices sur les chiffrements asymétriques, notamment RSA, Diffie-Hellman, les fonctions de hachage et le paradoxe des anniversaires. Il s’adresse aux étudiants en cryptographie ou sécurité informatique souhaitant comprendre les mécanismes mathématiques et algorithmiques des systèmes cryptographiques asymétriques.

Correction de l’exercice 1 : RSA

Le chiffrement RSA est basé sur la factorisation d’un nombre n en deux nombres premiers p et q, et sur la fonction indicatrice de Euler phi(n) = (p – 1)(q – 1).

1) Calcul des paramètres

Soit n = p * q = 253, avec p = 11 et q = 23.

Phi(n) = (p – 1)(q – 1) = 10 * 22 = 220.

Choix de e : e = 3 (car e = 2 est rejeté puisque gcd(2, 220) = 2, et e = 1 n’est pas un bon choix).

On cherche d tel que d = e⁻¹ mod phi(n), c’est-à-dire d tel que d * e ≡ 1 mod 220.

Application de l’algorithme d’Euclide étendu :

220 = 3 * 73 + 1
1 = 220 – 3 * 73

On en déduit que -73 est l’inverse modulaire de 3 modulo 220, donc d = 147 mod 220.

2) Taille des blocs

La taille du bloc du plaintext k est donnée par :

k = E[log₄ 253] = entier de (ln 253 / (4 ln 4)) = 3.

La taille maximale d’un bloc du ciphertext sera donc k + 1 = 4.

3) Chiffrement d’un message

Le message « abb » correspond à 122 selon le tableau de conversion en base 4 :

122 = 1 * 4² + 2 * 4¹ + 2 * 4⁰ = 26 en décimal.

Le chiffrement est donné par :

C = P^e mod n = 26^3 mod 253 = 119

Le nombre 119 s’écrit en base 4 :

119 = 1 * 4³ + 3 * 4² + 1 * 4¹ + 3 * 4⁰ = 1313 en base 4, ce qui correspond au message « acac ».

4) Déchiffrement

Le ciphertext « acac » correspond à 1313 en base 4, soit :

1 * 4³ + 3 * 4² + 1 * 4¹ + 3 * 4⁰ = 119.

Le déchiffrement est :

M = C^d mod n = 119^147 mod 253

Utilisation de l’exponentiation rapide avec 147 = 128 + 16 + 2 + 1 = (10010011)₂ :

i	bᵢ	Exp	Résultat
7	1	1	119
6	0	2	246
5	0	4	49
4	1	9	82
3	0	18	146
2	0	36	64
1	1	73	146
0	1	147	26

Le plaintext en décimal est donc 26, qui s’écrit en base 4 :

26 = 1 * 4² + 2 * 4¹ + 2 * 4⁰ = (122)₄, correspondant au message « abb ».

Correction de l’exercice 2 : Diffie-Hellman

Le protocole Diffie-Hellman permet à deux parties, Alice et Bob, de calculer une clé secrète commune sur un canal non sécurisé.

• Alice calcule A = g^a mod p = 3^7 mod 17 = 11 et envoie A à Bob.
• Bob calcule B = g^b mod p = 3^4 mod 17 = 13 et envoie B à Alice.
• Alice calcule la clé secrète K = B^a mod p = 13^7 mod 17 = 4.
• Bob calcule la clé secrète K = A^b mod p = 11^4 mod 17 = 4.

Les deux parties obtiennent ainsi la même clé secrète K = 4.

Correction de l’exercice 3 : Fonctions de hachage

• H(01101) = 1.
• Pour un message de longueur paire, H(msg) = 0 ; pour un message de longueur impaire, H(msg) = 1.
• Exemples : H(111) = 1 et H(100) = 0.
• H est une fonction à sens unique, mais ne vérifie pas les propriétés de collision forte et faible.

Correction de l’exercice 4 : Fonctions de hachage et paradoxe des anniversaires

Le paradoxe des anniversaires illustre la probabilité qu’au moins deux personnes dans un groupe partagent la même date d’anniversaire. Par exemple, dans un groupe de 23 personnes, cette probabilité est supérieure à 0,5, ce qui est contre-intuitif.

1) Probabilité qu’une personne ait la même empreinte qu’une autre

Soit p la probabilité qu’au moins une personne possède un certificat avec la même empreinte que Foulen Fouleni, et p' la probabilité complémentaire que personne ne possède cette même empreinte.

Soit H le nombre d’empreintes possibles (2^160) et N le nombre d’habitants sur Terre.

La probabilité qu’une personne donnée ait la même empreinte que Foulen est 1/H, donc la probabilité qu’elle ait une empreinte différente est 1 – 1/H.

Pour les N – 1 autres personnes, la probabilité que personne n’ait la même empreinte est :

p' = (1 – 1/H)^(N – 1)

On peut utiliser l’approximation :

(1 – x) ≈ e^(-x) pour x proche de 0.

2) Probabilité qu’au moins deux personnes aient la même empreinte

Soit p’ la probabilité que tous les habitants aient des empreintes distinctes, et p la probabilité complémentaire qu’au moins deux personnes partagent la même empreinte.

Imaginons une table de H cases. Chaque personne marque une croix dans la case correspondant à son empreinte.

• La première croix tombe forcément sur une case libre.
• La deuxième a une probabilité (H – 1)/H de tomber sur une case libre.
• La troisième a une probabilité (H – 2)/H, etc.

La probabilité que toutes les empreintes soient distinctes est donc :

p’ = (H / H) * ((H – 1) / H) * ((H – 2) / H) * ... * ((H – N + 1) / H)

Glossaire des termes clés

• RSA : Algorithme de chiffrement asymétrique basé sur la factorisation d’un nombre n en deux nombres premiers p et q.
• Phi(n) : Fonction indicatrice d’Euler, égale à (p – 1)(q – 1) pour n = p * q.
• e : Exposant public choisi tel que gcd(e, phi(n)) = 1.
• d : Exposant privé, inverse modulaire de e modulo phi(n).
• Exponentiation rapide : Méthode efficace pour calculer a^b mod n en décomposant b en puissances de 2.
• Diffie-Hellman : Protocole d’échange de clé permettant à deux parties de calculer une clé secrète commune.
• Fonction de hachage : Fonction à sens unique qui transforme un message en une empreinte de taille fixe.
• Paradoxe des anniversaires : Phénomène probabiliste où la probabilité que deux personnes partagent une même valeur (date d’anniversaire, empreinte) est plus élevée qu’intuitivement attendu.

Points clés à retenir

• Le chiffrement RSA repose sur la difficulté de factoriser n et sur le calcul des exposants e et d liés à phi(n).
• La taille des blocs en RSA dépend de la base utilisée et de la taille de n.
• Le protocole Diffie-Hellman permet un échange sécurisé de clé sans partage préalable.
• Les fonctions de hachage sont à sens unique mais peuvent ne pas garantir l’absence de collisions.
• Le paradoxe des anniversaires montre que la probabilité de collisions est élevée même pour un nombre relativement faible d’éléments.