Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

MAT309 Corrig´ e partiel novembre 2020 2020-2021 Exercice no 1 1. MUBC 2. FOURI

MAT309 Corrig´ e partiel novembre 2020 2020-2021 Exercice no 1 1. MUBC 2. FOURIER 3. (a) JAIME+COVID=LODUH, MONMA+COVID=OCIUD, SQUEL+COVID=UEPMO, AVABL+COVID=CJVJO, E+C=G (b) On note T[i] l’entier donn´ e par le tableau de correspondance pour la lettre d’indice i du texte ` a chiﬀrer, C[i] l’entier donn´ e par le tableau de la lettre d’indice i de la cl´ e et CH[i] l’entier donn´ e par le tableau de la lettre d’indice i du texte chiﬀr´ e. On utilise des indices commen¸ cant ` a 0. Comment obtient-on la liste des CH[i] ` a partir de la liste des T[i] et de la liste [C[0],C[1],· · · ,C[4]] ? CH[i]=(T[i]+C[i%5])%26 (c) Combien de chiﬀrements diﬀ´ erents peut-on obtenir avec des cl´ es de 5 lettres ? 26 choix possibles pour chaque lettre donc 265 = 11881376 choix. (d) Quelle(s) m´ ethode(s) peut-on utiliser pour casser un tel chiﬀrement si on ne connait pas la cl´ e ? Si on sait que la clef est de longueur 5 et le message assez long, on peut faire une analyse statistique des lettres d’indice 0 modulo 5, puis 1 modulo 5, etc. pour retrouver chaque lettre de la clef. On peut aussi faire une attaque par force brute en testant toutes les clefs possibles (un peu plus de 11 millions de possibilit´ es). Si on ne connait pas la longueur de la clef, on peut essayer une attaque statistique ou par force brute en testant pour une clef de 1 lettre, puis de 2 lettres, puis de 3 lettres, etc. L’attaque par force brute ne peut s’envisager que pour une clef d’au plus une douzaine de lettres. (e) ´ Ecrire un algorithme en langage naturel qui ` a un texte (compos´ e uniquement des lettres A ` a Z) et une cl´ e associe le texte chiﬀr´ e par la m´ ethode pr´ ec´ edente. On supposera que — le caract` ere d’indice i d’une chaine de caract` ere s est s[i], avec des indices commen¸ cant ` a 0, — la fonction len(s) renvoie la longueur de la chaine s — la fonction ord(c) convertit un caract` ere c en entier — la fonction chr(n) convertit un entier n en caract` ere fonction codage d’arguments msg,cle l <- len(cle) n <- len(msg) msgcode <- msg pour j de 0 jusque n-1 faire msgcode[j]=chr((ord(msg[j])+ord(cle[j%l]))%26) renvoyer msgcode Code Python/Xcas correspondant (un peu plus compliqu´ e car les caract` eres ne commencent pas ` a 0) : def code(msg,cle): l=len(cle) n=len(msg) msgcode="" for j in range(n): msgcode += chr((ord(msg[j])-ord("A")+ord(cle[j%l])-ord("A"))%26 +ord("A")) return msgcode On teste : code("JAIMEMONMASQUELAVABLE","COVID") renvoie LODUHOCIUDUEPMOCJVJOG. Exercice no 2 On rappelle qu’en base 16 les chiﬀres sont donn´ es par 0,1,· · · 9,A,B,C,D,E,F. 1. 0,0b1,0b10,0b11, 0b100, 0b101, 0b110, 0b111, etc. 2. Chiﬀrer de cette mani` ere le mot COVID. 10 1110 10101 1000 11 soit en groupant par quatre 1 0111 0101 0110 0011=0x17563 Proposer un autre mot ayant le mˆ eme chiﬀrement. Par exemple 101 110 10101 1000 11 soit FGVID 3. Pour corriger le d´ efaut de la m´ ethode pr´ ec´ edente on ´ ecrit tous les nombres de 0 ` a 25 en base 2 avec 5 bits (en ajoutant des 0 au d´ ebut si n´ ecessaire). On le convertit ensuite en base 16. Chiﬀrer de cette mani` ere le mot COVID. 00010 01110 10101 01000 00011 soit 0x275503 4. Notons n le chiﬀrement du mot COVID obtenu ` a la question pr´ ec´ edente. Donner le quotient et le reste, en base 16, de la division euclidienne de n par 6. On utilisera l’algorithme de la potence. Pour s’aider, on pourra ´ ecrire la table de multiplication par 6 en base 16. 1 2 3 4 5 6 7 8 9 A B C D E F *6 6 c 12 18 1e 24 2a 30 36 3c 42 48 4e 54 5a 275503 | 6 -24 |-------- --- | 68e2b 35 | -30 | --- | 55 | -54 | --- | 10 | -c | -- | 43 | -42 | --- | 1 | On obtient quotient 0x68e2b, reste 1. Exercice no 3 1. Montrer que 2020 et 33 sont premiers entre eux et donner l’identit´ e de B´ ezout. On d´ etaillera les calculs en utilisant l’algorithme d’Euclide ´ etendu. L0 2020 1 0 L1 33 0 1 L2=L0-61L1 7 1 -61 L3=L1-4L2 5 -4 245 L4=L2-L3 2 5 -306 L5=L3-2L4 1 -14 857 Donc -14*2020+857*33=1 2. D´ eterminer tous les couples d’entiers (x, y) tels que 2020x −33y = 3. on multiplie par -3 l’identit´ e de B´ ezout pour avoir une solution particuli` ere x = −42, y = −2571 et on utilise que 2020 et 33 sont premiers entre eux pour avoir la solution g´ en´ erale x = −42 + 33k, y = −2571 + 2020k 3. Existe t-il des entiers x positifs et plus petit que 20000 tels que le reste de la dision euclidienne de x par 33 soit 1 et le reste de la dision euclidienne de x par 2020 soit 4 ? Si oui, donner toutes les solutions. Comme 33 et 2020 sont premiers entre eux, x existe parmi les entiers, mais pas forc´ ement entre 0 et 20000. Comme la longueur de l’intervalle des x possibles est 20001 qui est plus petit que 2020 × 33, il y aura 0 ou 1 solution, on ne peut pas le savoir sans faire le calcul pr´ ecis. On a x = 1 + 33v = 4 + 2020u donc −2020u + 33v = 4 −1 = 3 dont on a calcul´ e des solutions (au signe pr` es) juste avant, par exemple v = 2571 On a donc une solution particuli` ere x = 1 + 33 × 2571 = 84844 et la solution g´ en´ erale x = 84844 + 2020 × 33k. Reste ` a d´ eterminer k, on a : 0 ≤x = 84844 + 66660k ≤20000 ⇔ −84844 66660 ≤k ≤20000 −84844 66660 donc k = −1 et x = 18184. On v´ eriﬁe que x convient. Exercice no 4 1. D´ eterminer le reste de la division euclidienne de 2020873 par 14. La m´ ethode doit ˆ etre explicit´ ee. On divise 2020 par 14, il reste 4, donc on calcule 4873 mod 14. On calcule les carr´ es successifs de 4 mod 14, on obtient mod 14 41 = 4, 42 = 2, 422 = 22 = 4, 423 = 42 = 2... Comme 873=0b1101101001, les bits ` a 1 d’indice pair (indices commen¸ cant ` a 0) contribuent ` a un facteur 4 et les bits ` a 1 d’indice impair ` a un facteur 2, on a modulo 14 : 4873 = 4 × 2 × 2 × 4 × 4 × 2 = 8 R´ esultat : 8 Autre m´ ethode : Pour calculer 4873, on peut observer que 44 = 162 = 22 = 4 modulo 14. Attention, on ne peut pas simpliﬁer par 4 qui est un diviseur de 0 modulo 14, 43 ̸= 1 modulo 14. Donc 41+3k = 4 modulo 14, donc 4873 = 42 × 41+3×290 = 42 × 4 = 8 (mod 1)4 2. Donner la liste des inversibles de Z/14Z. Comme 14 = 2 × 7, ce sont les classes des entiers premiers avec 2 et 7 : 1, 3, 5, 9, 11, 13 3. R´ esoudre l’´ equation dans Z/14Z, 11x = 3. L’´ equation a une solution unique puisque 11 est inversible modulo 14. Si on voit que 3 = −11, on trouve imm´ ediatement x = −1. Sinon, on peut aussi obtenir x rapidement, comme on veut inverser 11 modulo 14, on cherche l’identit´ e de B´ ezout sur 11 et 14, or la premi` ere division euclidienne de l’algorithme d’Euclide donne la relation 14-11=3 donc modulo 14 on a 11 × −1 = 3 et x = −1 = 13. Si on ne le voit aucune de ces astuces, on utilise la m´ ethode standard L0 14 1 0 L1 11 0 1 L2=L0-L1 3 1 -1 L3=L1-3L2 2 -3 4 L4=L2-L3 1 4 -5 Donc l’inverse de 11 est −5, on multiplie par 3, on obtient −15 = 13. Exercice no 5 On consid` ere l’´ equation suivante : (∗) x2 −13y2 = 7 On suppose dans les questions 1 et 3 que (x, y) est un couple d’entiers v´ eriﬁant (∗). 1. Montrer que x2 + y2 ≡0 [7] En eﬀet, -13=1 et 7=0 modulo 7 2. Calculer les carr´ es de tous les ´ el´ ements de Z/7Z. Modulo 7, on a 02 = 0, 12 = 62 = 1, 22 = 52 = 4, 32 = 42 = 2, 3. En d´ eduire que x et y sont multiples de 7. Si on somme deux ` a deux les carr´ es non nuls 1 + 1 = 2, 1 + 4 = 5, 1 + 2 = 3, 4 + 4 = uploads/S4/ m309-nov20.pdf