EXAMEN CRYPTOGRAPHIE | SUJET 05
Examen cryptographie
Questions de Cours (0.5pt x 11 = 5.5 pts)
1. Expliquer pourquoi la substitution monoalphabétique, notamment le Chiffre de César et Chiffre affine, ne résiste pas à la cryptanalyse par analyse de fréquence des lettres.
2. Décrire le principe du chiffrement polygraphique, encore appelé substitutions polygrammiques.
3. Expliquer pourquoi le chiffrement polygraphique, notamment le chiffre de Playfair (1854) et chiffre de Hill (1929), résiste à la cryptanalyse basée uniquement sur l'analyse de fréquence des lettres.
4. Un chiffrement polygraphique qui substitue un digramme toujours par le même digramme peut il résister à la cryptanalyse par analyse de fréquence des digrammes ?
5. Expliquer pourquoi le chiffre de Hill (1929) résiste à la cryptanalyse basée uniquement sur l'analyse de fréquence des digrammes.
6. Expliquer pourquoi le chiffre de Vigenère (1568) résiste à la cryptanalyse basée uniquement sur l'analyse de fréquence des lettres, digrammes, trigrammes...
7. Quel est l'objectif de la cryptanalyse de Friedman (basée sur la notion d'Indice de Coïncidence) ?
8. Définir la notion d'Indice de Coïncidence (IC).
9. Quel est l'objectif de la cryptanalyse de Kasiski?
10. Décrire une-cryptanalyse pour le chiffre de Vigenère (1568).
11. Expliquer pourquoi le chiffre de Vernam (One Time Pad - 1917) résiste à cryptanalyse de Friedman, la cryptanalyse de Kasiski et la cryptanalyse par analyse de fréquence.
Exercice 1 (3pts)
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. Poser un système d'équations à congruences modélisant ce problème et résoudre ledit système à l'aide du théorème des restes chinois m(n) des entiers
Théorème des restes chinois (Chinese Remainder Theorem): Prenons m(1), ...,supérieurs à 2 deux à deux premiers entre eux, et a(1), ..., a(n) des entiers. Le système d'équations
x = a(1) mod m(1)
..........
x = a(n) mod m(n)
admet une unique solution modulo M = m(1) * m(2)... * m(n) donnée par la formule :
x = a(1)M(1)y(1) + ... + a(n)M(n)y(n) mod M où M(i) = M/m(i), et y(i)= M(i)¹ mod m(i) pour i ∈ [1, n].
Exercice 2 (1pt + 3pts = 4pts)
Bob utilise le protocole RSA et publie sa clé publique (e,n)=(3, 187).
1. Encoder le message m= 15 avec la clé publique de Bob.
2. En utilisant le fait que φ(n) = 160, retrouver la factorisation de n, puis la clé privée de Bob. Indication: (1) Calculer la valeur de p+q, (2) montrer que p et q sont des racines du polynôme X² - (p+q)X + pq, (3) en déduire les valeurs de p et de q, (4) poser l'équation modulo permettant d'obtenir la valeur de d et trouver cette valeur, (5) utiliser le théorème de Euler pour avoir l'expression de d, (6) utiliser le deuxième propriété de la fonction totient d'Euler (φ) pour obtenir la valeur numérique de d.
Rappel sur RSA: Ce cryptosystème utilise deux clés (e,n) et (d,n), interchangeables. Le chiffrementse fait selon C = Me mod n et le déchiffrement par M = Cd mod n. La sécurité repose sur le coût nécessaire pour factoriser de grands nombres.
Le Principe de fabrication des clés RSA: On possède une paire de clés, l'une publique (e,n) et une privée (d,n). La première étape revient à choisir n. Il doit s'agir d'une valeur assez élevée, produit de 2 nombres premiers très grands p et q. En pratique, si p et q ont 100 chiffres décimaux, n possèdera 200 chiffres. Selon le niveau de sécurité souhaité, la taille de n peut varier : 512 bits, 768, 1024 ou 2048³. La deuxième étape revient à choisir un très grand entier e, relativement premier à (p-1)*(q-1). La clé publique sera formée par (e,n). On choisira ensuite un d tel que e* d = 1 mod (ϕ(n)). La clé privée sera donnée par (d,n). La dernière étape revient à jeter p et q. Le cryptanalyste devant retrouver ces valeurs, il faut les détruire pour éviter les fuites.
Rappel sur la fonction totient d'Euler: p(n) = #{1 ≤ m ≤n pgcd(n, m) = 1}. φ(n) est l'indicateur d'Euler, c'est-à-dire le cardinal des entiers relativement premiers à n. Par exemple, φ(11)=10 et φ(7)=
6 et φ(4)=2. Nous avons les deux propriétés suivantes :
1. Si n est premier, alors φ(n) = n-l
2. Si p et q deux nombres premiers et n = pq, alors φ(n) =φ(pq)= φ(p) * φ(q)= (p − 1)(q − 1)
Théorème 4 (Euler): Si pgcd(a,m) = 1, alors aφ(m) = 1 mod (m),
Ce théorème permet de calculer facilement l'inverse de a modulo m : aφ(m)-1 mod m.
Exercice 3 (3.5 pts)
Bob 1 et Bob 2 ont pour clé publique RSA respectivement (el, n) et (e2, n) avec el et e2 premiers entre eux (pgcd(el, e2)-1). Alice envoie le même message m crypté par les clés publiques RSA de Bob 1 et Bob 2 en cl et c2. Le bit de l'exercice est d'expliquer comment Eve, qui intercepte les deux messages cryptés et qui connaît les clés publiques de Bob I et Bob 2, peut retrouver le
message clair m.
1. Montrer qu'il existe deux entiers u et v tels que u*el + v*e2 = 1 (0.5pt)
2. Montrer que m(u*e1+v*e2) ≡ m (1 pt)
3. Montrer que m(u*e1+v*e2) ≡ c1uc2u(1 pt)
4. Déduire des questions précédentes comment Eve procède pour retrouver le message initial m. (0.5pt)
5. Que peut on faire pour éviter ce type type d'attaque ? (0.5pt)
Rappel: Identité de Bezou : Si p et q sont premiers entre eux (pgcd(p,q)=1) alors il existe deux entiers u et v tels que p*u + q*v = 1.
Exercice 4 (4 pts)
On considère un texte de 2n lettres dans lequel exactement une lettre sur deux est un A.
1. Quelle est la contribution de la lettre A dans l'indice de coïncidence de ce texte (C'est à dire la probabilité de tirer deux A parmi les 2n lettres du texte)? (1 pt)
2. En déduire que si n ≥ 2, alors l'indice de coïncidence du texte est ≥ 1/6. (1 pt)
3. Supposons à présent que toute les lettres autres que A sont des B. Vers quelle valeur l'indice de coïncidence du texte tend quand n tend vers l'infini? (1 pt) Sachant que si on prend deux lettres au hasard, on a les quatre possibilités suivantes AA, AB, BA, BB, calculer la probabilité que deux lettres choisis au hasard soient égales. (1 pt)