EXAMEN CRYPTOGRAPHIE, cryptologie | SUJET 10

Examen corrige cryptographie

Examinateur : Mr JoëlYK

Questions de Cours (3pts)

1. Expliquer comment plusieurs personnes peuvent signer numériquement un même document.
2. Décrire un protocole d’authentification (basé sur la signature numérique) d’une entité auprès d’un serveur 3. Vous disposez d’un cryptosystème moderne qui code bloc par bloc. Quel est la taille d’un bloc sachant que les caractères du texte en clair à chiffrer sont codés sur huit (8) bits. Justifiez votre réponse.

Exercice 1 : Substitution monoalphabétique : Chiffre de César (2.5pts = 1pt+1.5pt) Le tableau ci-dessous donne l’indice de chaque lettre de l’alphabet français.

1. 1. Chiffrement/déchiffrement : On suppose  que la clé est k=2 (qui représente la valeur du décalage). Chiffrer « ZONE » et déchiffrer « DQP ».
   2. Cryptanalyse : La suite de lettres «HOOH HVW SUHWH» est le chiffrement d’un texte dans la langue française par le chiffre de César. Retrouver la clé de chiffrement par analyse de fréquence des lettres. On rappelle que la lettre dont la fréquence est la plus élevée dans les textes de la langue française est « E ». Retrouver la clé de chiffrement et le texte en clair par la cryptanalyse par analyse de fréquences des lettres.

Exercice 2 : Substitution monoalphabétique : Chiffre affine (2.5 pts= + 1pt + 1.5pt)

1. 1. Chiffrement et déchiffrement : On considère la  fonction de chiffrement  c(x) = (3x + 11) mod 26 et la fonction de déchiffrement c^-1(y) = 9(y − 11) mod 26 = (9y + 5) mod 26.  Chiffrer « LA » et déchiffrer « OBY ».
   2. Cryptanalyse :  La suite de lettres  « NIIND DROGU ANGND »  est le chiffrement d’un texte dans la langue française par le chiffre  c(x) = (ax + b) mod 26, où gcd(a , 26) = 1, a et b sont des constantes, et où x est la lettre à chiffrer. Retrouver la clé de chiffrement et le texte en clair par la cryptanalyse par analyse de fréquences des lettres. On rappelle que la lettre dont la fréquence est la plus élevée dans les textes de la langue française est « E » et la deuxième la plus fréquente est S.  On rappelle aussi que  c^-1(y) = a⁻¹  (y − b) mod 26,  ∗ (y − b) mod 26,   où a⁻¹  désigne l’inverse de a modulo 26, c’est à dire que a*a⁻¹ mod 26 = 1..

Exercice 3 : Substitutions polyalphabétiques : Chiffre de Vigenère (2 pts=1pt + 1pt +1pt)

1. 1. Sachant que la clé de chiffrement est « ABC » chiffrer « BON » et déchiffrer « SPP ».
   2. Le chiffre de Vigenère résiste t’elle à la cryptanalyse par analyse de fréquences des lettres ? Le chiffre de Vigenère résiste t’il à la cryptanalyse par analyse de fréquences des bigrammes ? Justifiez votre réponse.
   3. Cryptanalyse du commandant Bazeries : La suite de lettres  « NIIND DROGU ANGND »  est le chiffrement d’un texte dans la langue française « MF HVJEF ». Sachant que le texte initial contient l’article « LE », retrouver la clé de chiffrement et le message en clair.

Exercice 4 (2.5 pts)

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

Théorème des restes chinois (Chinese Remainder Theorem) : Prenons m(1) , ..., m(n) des entiers 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 :∗ m(2)... ∗ m(n) donnée par la formule :                    ∗ 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 5 (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 chiffrement se fait selon C = M^e mod n et le déchiffrement par M = C^d 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)). ∗ (y − b) mod 26,   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 :  φ(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 − 1

2. Si p et q deux nombres premiers et n = pq, alors φ(n) = φ(pq)= φ(p)  φ(q)= (p − 1)(q − 1)∗ m(2)... ∗ m(n) donnée par la formule :

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 6 (3.5 pts)

Bob 1 et Bob 2 ont pour clé publique RSA respectivement (e1, n) et (e2, n) avec e1 et e2 premiers entre eux (pgcd(e1, e2)=1). Alice envoie le même message m crypté par les clés publiques RSA de Bob 1 et Bob 2 en c1 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 1 et Bob 2 , peut retrouver le message clair m.

1. Montrer qu’il existe deux entiers u et v tels que u*e1 + v*e2 = 1 (0.5pt)
2. Montrer que m^{(u*e1 + v*e2)} ≡ m  (1 pt)
3. Montrer que m(u*e1 + v*e2) = c1uc2v  (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.

Bientot

Si vous avez trouvé les examenscorrigés en Cryptographie de Mr JoëlYk intéressants et utiles, pourquoi ne pas les partager avec d'autres personnes qui pourraient également en bénéficier ? Partagez ce lien sur les réseaux sociaux ou envoyez-le à vos amis et collègues. Vous pourriez aider quelqu'un à améliorer ses compétences en programmation ou à trouver des solutions à des problèmes complexes. N'oubliez pas que la connaissance doit être partagée pour grandir. Merci pour votre soutien et votre partage !

Contact WhatsApp : +237 652027193 | Réaliser Par Joël_Yk

 encore plus d'examen corriges ici !!!