Exercice 1 : Cryptage affine

1 CHIFFREMENT ET CRYPTOGRAPHIE. Exercice 1 : Cryptage affine Chacune des 26 lettres est associ e l'un des entiers de 0 25, selon le tableau de correspondance suivant. A B C D E F G H I J K L M. 0 1 2 3 4 5 6 7 8 9 10 11 12. N O P Q R S T U V W X Y Z. 13 14 15 16 17 18 19 20 21 22 23 24 25. Le Cryptage affine se fait l'aide d'une cl , qui est un nombre entier k fix , compris entre 1 et 25. Pour crypter une lettre donn e on suit le processus suivant : on rep re le nombre x associ la lettre dans le tableau de correspondance pr c dent on multiplie ce nombre x par la cl k on calcule le reste r de la division euclidienne du nombre obtenu par 26.

2 On rep re la lettre associ e au nombre r dans le tableau de correspondance, qui devient la lettre crypt e Par exemple, pour crypter la lettre P avec la cl = 11 : le nombre x associ la lettre P est le nombre 15. on multiplie 15 par la cl k, ce qui donne 11 15 = 165. on calcule le reste de la division euclidienne par 26 : on obtient 165 % 26 = 9. on rep re finalement la lettre associ e 9 dans le tableau, c'est- -dire J. Ainsi avec la cl k = 11, la lettre P est crypt e en la lettre J. On crypte un mot en cryptant chacune des lettres de ce mot. En Python, on cr e une liste L qui contient les 26 lettres de l'alphabet rang es dans l'ordre alphab tique l'aide de la commande ci-dessous : L = [ A', B', C', D', E', F', G', H', I', J', K', L', M', N', O', P', Q', R', S', T', U', V', W', X', Y', Z'].

3 1. Que penser du Cryptage obtenu lorsque la cl k est gale 1 ? 2. En quoi la lettre A constitue-t-elle un cas particulier dans le processus de Cryptage ? 3. Dans le cas o la cl est gale 11, crypter le mot MIRO. 4. Ecrire une fonction indice qui prend en param tre une lettre de l'alphabet et qui renvoie son indice dans la liste L (L tant suppos e d finie comme variable globale). 5. Ecrire une fonction crypterLettre qui prend en param tre une cha ne de caract res constitu es d'une lettre majuscule de l'alphabet et une cl et qui renvoie la lettre crypt e. Cette fonction utilisera la fonction indice pr c dente. En supposant qu'un appel la fonction indice compte pour une op ration l mentaire, quel est le nombre d'op rations l mentaires effectu es chaque appel de la fonction crypterLettre ?

4 6. (a) Ecrire une fonction crypterTexte qui prend en param tre une cha ne de caract res dont les l ments sont soit des lettres majuscules soit des espaces (qui ne seront pas modifi s), et une cl . La fonction renvoie la cha ne de caract res crypt s. (b) Donner l'appel effectuer pour r pondre la question 3. (c) Soit N la longueur de la cha ne de caract res en param tre de la fonction crypterTexte et M le nombre d'espaces qu'elle contient. D terminer en fonction de N et M la complexit de la fonction crypterTexte. 7. On dit qu'une cl est une bonne cl de Cryptage si elle poss de une cl associ e k', qui est un nombre entier compris entre 1 et 25 tel qu'en appliquant le processus avec la cl k' une lettre crypt e (avec la cl k) on obtient la lettre initiale.

5 K' est alors appel e cl de d Cryptage associ e k. On admet qu'une cl k est une bonne cl de Cryptage si et seulement si 1 et 26 = 1, c'est- -dire si k est diff rent de 1 et si le seul diviseur commun dans k et 26 est 1. (a) On suppose que 19 est une cl de d Cryptage associ e la cl k = 11. Avec la cl k = 11, un mot a t . crypt . On a obtenu le mot HARK. Retrouver le mot initial l'aide de la cl de d Cryptage la main , puis donner l'appel la fonction crypterTexte donnant le m me r sultat. (b) Soit F la liste qui contient les termes de la suite de Fibonaci strictement inf rieurs 26 rang s par ordre croissant. On rappelle que la suite de Fibonacci est d finie par ses deux premiers termes 0 et 1 et par le fait qu' partir de son troisi me terme, chaque terme est gal la somme des deux pr c dents.

6 Expliciter F. (c) D terminer la liste G des l ments de F qui sont de bonnes cl s de Cryptage . (d) On admet que la cl de d Cryptage k' associ e une bonne cl de Cryptage k est unique et que c'est le nombre entier strictement compris entre 0 et 26 qui est tel que le reste de la division euclidienne par 26 de est 1. V rifier que 19 est la cl de d Cryptage associ e la cl k = 11. 8. Ecrire une fonction cleDecryptage qui prend en param tre un entier k premier avec 26 et qui renvoie la cl de d Cryptage associ e k'. On dispose de bonnes cl s de Cryptage avec les l ments de G, la fonction cleDecryptage nous permet ainsi de calculer aussi les cl s de d Cryptage associ es.

7 9. Un petit fut cherche d crypter un long message crypt crit en fran ais sans conna tre ni la cl de Cryptage , ni la cl de d Cryptage . Pour cela, il rep re dans la cha ne de caract res que constitue le message la lettre la plus fr quente et en d duit que c'est la lettre crypt e qui correspond E (la lettre la plus utilis e en fran ais). (a) Que renvoie la fonction suivante ? On ne justifiera pas la r ponse. import numpy as np def mystere (C) : """ C est une cha ne de caract res dont les l ments sont soit des lettres majuscules, soit des espaces """. V = (26). max, indexMax = 0 , 0. for j in range(26) : for i in range(len(C)) : if C[i] == L[j] : V[j] += 1.

8 If V[j] > max : max, indexMax = V[j], j return L[indexMax]. (b) Donner une preuve rapide de la terminaison de cette fonction. (c) Question bonus. En utilisant les fonctions count, max et index de Python, r crire la fonction pr c dente avec le moins de lignes possible, et donner lui aussi un nom plus explicite. 10. Connaissant E et la lettre crypt e correspondante, le petit fut peut en d duire la cl de Cryptage et ainsi cracker le code. Ecrire une fonction cracker qui prend en param tre la lettre crypt e correspondant . E et qui renvoie la liste des cl s de Cryptage possibles (liste pouvant tre vide) permettant de crypter E en cette lettre.

9 11. Que se passe-t-il s'il essaie de cracker un message crypt o la lettre E n'est pas la lettre la plus fr quente du message ? Exercice 2 : Codage de C sar On cherche crypter un texte t de longueur n compos de caract res en minuscules (soit 26 lettres diff rentes) repr sent s par des entiers compris entre 0 et 25 (0 pour a, 1 pour b, etc.). Nous ne tenons pas compte des ventuels espaces. Ainsi, le texte capesmathoptioninfo est repr sent par le tableau suivant o la premi re ligne repr sente le texte, la seconde les entiers correspondants, et la troisi me les indices dans le tableau t. c a p e s m a t h o p t i o n i n f o 2 0 15 4 18 12 0 19 7 14 15 19 8 14 13 8 13 5 14.

10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18. Dans cette partie, on supposera que les textes sont d j repr sent s par des listes de nombres et que donc toutes les fonctions de codage et d codage prendront en arguments des listes de nombres et renverront des listes de nombres. Le codage de C sar est le plus rudimentaire que l'on puisse imaginer. Il a t utilis par Jules C sar (et m me auparavant) pour certaines de ses correspondances. Le principe est de d caler les lettres de l'alphabet vers la droite d'une ou plusieurs positions. Par exemple, en d calant les lettres d'une position, le caract re a se transforme en b, le b en c, etc. et le z en a.