Cryptographie et arithmétique Corrigé d’examen Université de Bordeaux Cryptogra

Cryptographie et arithmétique Corrigé d’examen Université de Bordeaux Cryptographie et arithmétique – Corrigé de l’examen 2014 Exercice 1. 1. Si x ̸≡±y mod N et x2 ≡y2 mod N, alors N ne divise pas x ± y mais divise x2 −y2 = (x −y)(x + y). La première condition de congruence implique donc que pgcd(N, x ± y) ̸= N, et la seconde que pgcd(N, x ± y) ̸= 1 (si p est un diviseur premier de N, alors par le lemme d’Euclide il divise x −y ou x + y) : le pgcd de N et x ± y est donc un diviseur non trivial de N. 2. On peut résoudre ceci de manière systématique, sans faire des essais au hasard. Je prends le temps de détailler la méthode, mais cela n’est pas nécessaire d’en faire autant dans la rédaction (voir les corrections en TD). On cherche à obtenir une congruence du type x2 ≡y2 mod N, en prenant pour x un produit de certains nombres du membre de gauche ; le membre de droite est alors un carré (noté y2) si −1 et les nombres premiers apparaissant dans le membre de droite (dont on s’est débrouillé pour qu’ils soient dans B), une fois le produit formé, sont tous à une puissance paire. Mathématiquement, ceci revient à trouver des entiers α1, . . ., α8 dans {0,1} tels que, dans (−1)α1+α2+α3+α7+α822α3+α4+α7+2α83α3+α4+4α5+α6+α752α1+2α27α3+α611α5+α7+α813α6+α7+α817α123α237α4, toutes les puissances soient paires (αi = 0 si le i-ième nombre de notre colonne ne figure pas dans le produit, et 1 sinon). Ceci revient donc à résoudre le système suivant modulo 2, donc dans Z/2Z :                            α1 + α2 + α3 + α7 + α8 = 0, α4 + α7 = 0, α3 + α4 + α6 + α7 = 0, α3 + α6 = 0, α5 + α7 + α8 = 0, α6 + α7 + α8 = 0, α1 = 0, α2 = 0, α4 = 0. On peut encore le simplifier un peu avant de le résoudre, puisqu’on voit immédiatement que α1 = α2 = α4 = 0 (et donc que 21049, 22984 et 48669 ne figureront pas dans le produit x) :                α3 + α7 + α8 = 0, α7 = 0, α3 + α6 + α7 = 0, α3 + α6 = 0, α5 + α7 + α8 = 0, α6 + α7 + α8 = 0. On en arrive facilement à α3 = α5 = α6 = α8, le reste étant nul. Donc α3 = α5 = α6 = α8 = 1 est une solution, ce qui signifie que x = 47607 · 67495 · 67747 · 88633 = 19294251454456364715 fournit une solution à notre problème (il est bien sûr plus commode de plutôt prendre x ≡925744 mod 5680267). On a dans ce cas y2 = 243672112132 = 1081082, et : pgcd(N, x −y) = 2879, pgcd(N, x + y) = 1973, calculés grâce à l’algorithme d’Euclide étendu, qui sont deux diviseurs non triviaux de N (en vérité, ce sont deux diviseurs premiers, et ce sont les seuls). 1 2013/2014 Cryptographie et arithmétique Corrigé d’examen Université de Bordeaux Exercice 2. 1. Notons d’abord que c ≡me mod N par définition, et donc c ≡me mod p et mod q. Montrons que cd ≡m mod p et mod q. Par le théorème des restes chinois, la congruence sera alors vraie modulo N. Comme d est l’inverse de e modulo R, on a de ≡1 mod R, et donc de ≡1 mod p−1. En particulier, il existe un entier k tel que de = 1 + (p −1)k. Ainsi, cd ≡(me)d ≡med ≡m1+(p−1)k ≡m · (mp−1)k ≡m mod p dans tous les cas : si m n’est pas premier à p, alors m ≡0 mod p et donc c ≡0 mod p, si bien que cd ≡0 ≡m mod p trivialement, sans même avoir à effectuer tous ces calculs ∗, tandis que si m est premier à p, alors mp−1 ≡1 mod p par le petit théorème de Fermat. On a bien montré que cd ≡m mod p, et on procède de même modulo q, d’où le résultat. 2. Ici, φ(N) = φ(pq) = φ(p)φ(q) = (p −1)(q −1). Comme (p −1)(q −1) et R ont exactement les mêmes diviseurs premiers, qui sont ceux de p −1 et q −1 †, être premier à R et être premier à φ(N) sont équivalents. 3. Si N = 77 = 7 × 11 et e = 7, alors l’inverse de e modulo φ(N) = 60 est 43 (on le calcule en établissant une relation de Bézout entre 60 et 7, grâce à l’algorithme d’Euclide étendu), tandis que l’inverse de e modulo R = 30 est 13 ‡. 4. Comme N = pq et φ(N) = (p −1)(q −1) = N −(p + q) + 1, la connaissance de N et φ(N) permet de connaître pq et p + q, et donc de connaître p et q en résolvant l’équation polynomiale X2 −(p + q)X + pq = 0 (équivalente à X2 + (φ(N) −N −1)X + N = 0). La résolution, dans notre exemple, donne {p, q} = {2897,1901}. 5. On a R = ppcm(p −1, q −1) = (p−1)(q−1) pgcd(p−1,q−1), écriture qui permet de s’affranchir de factorisations de p −1 et q −1 : on calcule en effet leur pgcd grâce à l’algorithme d’Euclide étendu, pour obtenir pgcd(p −1, q −1) = 4, et donc R = 1375600. 6. On doit choisir e premier à R. Ici, pgcd(R, e) = 181 : c’est un mauvais choix. 7. Cette fois-ci, pgcd(R, e) = 1 : e et R sont bien premiers entre eux. 8. Grâce à l’algorithme d’Euclide étendu, on trouve une relation de Bézout entre e = 547 et R = 1375600, et l’inverse de e mod R est d = 812283. 9. Comme 547 = 29 + 25 + 21 + 20, on a : m547 =             m2
222 · m !2  2   2   2 · m     2 · m. On voit alors que m547 requiert 12 multiplications modulo N. Exercice 3. 1. On a y ⊕z ⊕eB = x ⊕eB ⊕eA ⊕eB = x ⊕eA = m ⊕eA ⊕eA = m. Donc Bob a juste besoin d’ajouter y et sa clé eB au message z d’Alice pour retrouver m. 2. On a x ⊕y ⊕z = x ⊕y ⊕(y ⊕eA) = x ⊕eA = m ⊕eA ⊕eA = m. Donc la connaissance de x, y et z suffit à reconstituer le message m (sans connaître eA ou eB). ∗. C’est aussi pour traiter ce cas qu’il est très commode de passer par le théorème des restes chinois : si m n’est pas premier à N, on ne peut pas en déduire pour autant que m ≡0 mod N et conclure rapidement. †. Car p −1 et q −1 divisent R qui, lui-même, divise (p −1)(q −1), selon la définition du ppcm et le fait que (p −1)(q −1) soit un multiple commun à p −1 et q −1. ‡. Ce n’est pas un hasard si ces deux clés de déchiffrement diffèrent d’un multiple de R : pourquoi était-ce prévisible ? 2 2013/2014 Cryptographie et arithmétique Corrigé d’examen Université de Bordeaux 3. Le cas où p divise m est trivial, donc on l’exclut. Notons que Bob connaît z ≡ydA ≡xdAeB ≡mdAeAeB mod p. Comme eAdA ≡1 mod p −1 et mp−1 ≡1 mod p, on a même z ≡meB mod p, donc zdB ≡m mod p. Il suffit donc, pour Bob, d’élever le message chiffré z à la puissance dB (qu’il connaît) pour connaître m. 4. L’homme du milieu choisit un entier eC inversible modulo p−1 connu de lui seul, d’inverse dC. Ensuite, interceptant un message d’Alice x, il lui renvoie y = xeC en se faisant passer pour Bob, et enfin Alice calcule z = ydA que l’homme du milieu intercepte encore à la place de Bob. Il peut décoder le message en calculant zdC, comme on l’a vu dans la troisième question, à l’insu d’Alice et Bob. 5. Sachant résoudre le problème du Log Discret, la connaissance de y et z permet de calculer logy(z) = dA, et donc d’obtenir xdA ≡m mod p. 6. Non : n’importe quel élément m de (Z/pZ)∗peut donner x = 1 par un choix de eA convenable (qui est multiple de l’ordre de m). 7. Soit G un groupe. Si g ∈G est d’ordre k, alors gl est d’ordre k pgcd(l,k) ; c’est un résultat classique. Ainsi, si m est une racine primitive modulo p, alors m est d’ordre p −1, et x ≡meA mod p est d’ordre p−1 pgcd(p−1,eA). On a uploads/Litterature/ corrige-examen14 1 .pdf

Documents similaires

Le Père Goriot Honoré de Balzac L i v r e t p é d a g o g i q u e correspondant 0 0

Par iosiane Rabemanan :i Voici un ( cahier ) riche en pièces inédites ! Grâce a 0 0

‪INTRODUCTION : QUEL CONCEPT POUR L’ART DES ARCHIVES ?‪ Gabriel Ferreira Zacari 0 0

La révélation des pyramides. Décryptage et analyse. Présentation et 1/3 : Pi et 0 0

Cahiers slaves Le thème de la dolja dans le rite funéraire slave Olga Sedakova, 0 0

LEXIQUE de la critique COLLECTION DIRIGÉE PAR JEAN-MARIE COTTERET LEXIQUE de la 0 0

1 Altan Gokalp (1942-2010) Né en 1942 à Izmir de parents instituteurs : mère al 0 0

__________________ Programmer dans .Net Framework avec le langage C# version 2. 0 0

DE LA POS TURE À L’ATTI TUDE Isabelle LAUNAY Christine ROQUET ou ce qu’un dan s 0 0

1 Que donne à penser les poètes en temps de détresse ? Séparation. Notre temps 0 0

• Détails
• Publié le Fev 14, 2022
• Catégorie Literature / Litté...
• Langue French
• Taille du fichier 0.2098MB