Examen Final – Cryptographie jeudi 19 janvier 2006 Correction Exercice 1 Alice

Examen Final – Cryptographie jeudi 19 janvier 2006 Correction Exercice 1 Alice change sa cl´ e RSA tous les 25 jours. Bob lui change sa cl´ e tous les 31 jours. Sachant qu’Alice change sa cl´ e aujourd’hui et que Bob a chang´ e sa cl´ e il y a trois jours, d´ eterminer quand sera la prochaine fois qu’Alice et Bob changeront leur cl´ e le mˆ eme jour. Solution. Notons d le nombre de jours jusqu’` a ce que Alice et Bob changent leur cl´ e le mˆ eme jour. Puisque Alice change sa cl´ e tous les 25 jours et qu’elle a chang´ e sa cl´ e aujourd’hui, d doit ˆ etre divisible par 25. Puisque Bob change sa cl´ e tous les 31 jours et qu’il a chang´ e sa cl´ e il y a trois jours, d + 3 doit ˆ etre divisible par 31. Ainsi d doit v´ erifier le syst` eme de congruences : ( d ≡0 (mod 25) d ≡−3 (mod 31). Par le th´ eor` eme des restes chinois, ce syst` eme ´ equivaut ` a la congruence d ≡400 (mod 775), et donc Alice et Bob changeront leurs cl´ es le mˆ eme jour dans 400 jours. Exercice 2 Bob utilise le protocole RSA et publie sa cl´ e publique N = 187 et e = 3. 1. Encoder le message m = 15 avec la cl´ e publique de Bob. 2. En utilisant le fait que ϕ(N) = 160, retrouver la factorisation de N, puis la cl´ e priv´ ee de Bob. Solution. 1. Le message cod´ e est c = 153 mod 187 = 9. 2. Ecrivons N = pq. On a donc ϕ(N) = (p−1)(q−1) = pq−p−q+1 = N −(p+q)+1, et ainsi p + q = N −ϕ(N) + 1 = 187 −160 + 1 = 28. Les nombres p et q sont racines du polynˆ ome X2 −(p + q)X + pq = X2 −28X + 187. Le discriminant est 282 −4 × 187 = 36 et ainsi p = (28 −6)/2 = 11 et q = (28 + 6)/2 = 17. Exercice 3 Soient p et q deux nombres premiers impairs tels que p ≡1 (mod 3) et q ≡1 (mod 3). On pose N = pq. 1. Montrer que  3 N  = (−1)(N−1)/2. 2. On suppose de plus que N ≡3 (mod 4). En d´ eduire que : ou bien 3 est un carr´ e modulo p et 3 n’est pas un carr´ e modulo q ; ou bien 3 n’est pas un carr´ e modulo p et 3 est un carr´ e modulo q. Solution. 1. Par la loi de r´ eciprocit´ e quadratique, on a  3 N  = (−1)(N−1)/2 pq N  et comme pq ≡1 (mod N), on trouve que pq N  = 1, d’o` u le r´ esultat. 2. On a N −1 ≡2 (mod 4) et ainsi (N −1)/2 ≡1 (mod 2). Par la question 1., il suit que  3 N  = −1. Puisque  3 N  = 3 p 3 q  , on trouve que : ou bien 3 p  = 1 et 3 q  = −1 d’o` u 3 est un carr´ e modulo p, mais pas modulo q ; ou bien 3 p  = −1 et 3 q  = 1 d’o` u 3 est un carr´ e modulo q, mais pas modulo p. Exercice 4 Bob1 et Bob2 ont pour cl´ e publique RSA respectivement (N, e1) et (N, e2) avec e1 et e2 premiers entre eux. Alice envoie le mˆ eme message m crypt´ e par les cl´ es publiques RSA de Bob1 et Bob2 en c1 et c2. Expliquer comment Eve, qui intercepte les deux messages crypt´ es et qui connait les cl´ es publiques de Bob1 et Bob2, peut retrouver le message clair m. Solution. Puisque e1 et e2 sont premiers entre eux, il existe deux entiers u et v tels que ue1 + ve2 = 1. Eve peut calculer u et v, et finalement retrouve le message en faisant cu 1cv 2 ≡mue1mve2 ≡mue1+ve2 ≡m (mod N). Exercice 5 On consid` ere 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 ? 2. En d´ eduire que si n ≥2, alors l’indice de co¨ ıncidence est ≥1/6. 3. Supposons ` a pr´ esent 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 ? Pourquoi cette r´ eponse est-elle bien celle que l’on attend ? Solution. 1. Puisque le nombre de ’A’ dans le texte est n, la contribution cA de A est cA = n(n −1) 2n(2n −1) = n −1 2(2n −1). 2. On a (n−1)/(4n−2) ≥1/6 si et seulement 6n−6 ≥4n−2 si et seulement 2n ≥4 si et seulement si n ≥2, d’o` u le r´ esultat. 3. Notons cB la contribution de ’B’. Puisqu’une lettre sur deux est un ’B’, on a donc par la question 1. que cB = (n −1)/(4n −2). La contribution des autres lettres est nulle et donc l’indice de co¨ ıncidence du texte est cA + cB = n −1 2n −1. Il suit que la limite de l’indice de co¨ ıncidence quand n tend vers +∞est 1/2. On explique pourquoi cette r´ eponse est conforme ` a ce qu’on attend. En effet, si on prend une lettre au hasard, elle peut ˆ etre un ’A’ ou un ’B’ avec la mˆ eme probabilit´ e. Ainsi, si on prend deux lettres au hasard, on a les quatre possibilit´ es suivantes avec la mˆ eme probabilit´ e : AA, AB, BA, BB. Donc la probabilit´ e que deux lettres choisit au hasard soient ´ egales est bien 1/2. Exercice 6 On consid` ere un diagramme de Feistel ` a deux rondes sur des chaˆ ınes de 8 bits avec deux fonctions f1 et f2. 1. On pose f1(a) := a ⊕1011 et f2(a) := ¯ a ⊕0101 pour toute chaˆ ıne a de 4 bits. (a) Calculer l’image de la chaˆ ıne 11010011 par ce diagramme. (b) D´ eterminer une chaˆ ıne de 8 bits dont l’image par le diagramme est elle-mˆ eme. 2. La propri´ et´ e pr´ ec´ edente, ` a savoir il existe une chaˆ ıne dont l’image par le diagramme de Feistel est elle-mˆ eme, est-elle vraie pour toutes les fonctions f1 et f2 ? Justifier votre r´ eponse par une d´ emonstration ou un contre-exemple. Solution. 1. (a) On calcule les formules donnant le mot de sortie w′ 1 · w′ 2 en fonction du mot d’entr´ ee w1 · w2 : w′ 1 = f2(f1(w1) ⊕w2) ⊕w1 = w1 ⊕1011 ⊕w2 ⊕0101 = w1 ⊕w2 ⊕1111 ⊕0101 = w1 ⊕w2 ⊕1010, w′ 2 = f1(w1) ⊕w2 = w1 ⊕w2 ⊕1011. Ainsi pour w1 = 1101 et w2 = 0011, on obtient w′ 1 = 1101 ⊕0011 ⊕1010 = 0100 et w′ 2 = 1101⊕0011⊕1011 = 0101. Donc finalement l’image de 11010011 par ce diagramme est 01000101. (b) On veut que w′ 1 = w1 et w′ 2 = w2. En rempla¸ cant dans les formules ci-dessus, on obtient ( w1 = w1 ⊕w2 ⊕1010, w2 = w1 ⊕w2 ⊕1011. et donc w1 ⊕1010 = 0000 et w1 = 0101, w2 ⊕1011 = 0000 d’o` u w2 = 0100. En conclusion, le mot 01010100 est invariant par le diagramme. 2. On consid` ere l’´ equation w′ 2 = f1(w1) ⊕w2. Si on prend f1 telle que f1(w1) ̸= 0000 pour tout w1, alors on ne peut jamais avoir w′ 2 = w2 et donc, pour ce choix de f1, il n’existe pas de mot invariant. uploads/Litterature/ masterpro-final-2005-correction.pdf

Tags
littérature modulo exercice solution. carr´ alice
Documents similaires
  • 19
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager