X Informatique MP/PC 2008

ÉCOLE POLYTECHNIQUE ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES CONCOURS D'ADMISSION 2008 FILIÈRE MP - OPTION PHYSIQUE ET SCIENCES DE L'INGÉNIEUR FILIÈRE PC COMPOSITION D'INFORMATIQUE (Durée : 2 heures) L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie. Ave Cesar (zud bdrzq) 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 a, 1 b, . . . 25 z). Nous ne tenons pas compte des éventuels espaces. Ainsi, le texte ecolepolytechnique 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. e 4 0 c 2 1 o 14 2 l 11 3 e 4 4 p 15 5 o 14 6 l 11 7 y 24 8 t 19 9 e 4 10 c 2 11 h 7 12 n 13 13 i 8 14 q 16 15 u 20 16 e 4 17 Codage de César Ce codage 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 gauche de 1 ou plusieurs positions. Par exemple, en décalant les lettres de 1 position, le caractère a se transforme en z, le b en a, ... le z en y. Le texte avecesar devient donc zudbdrzq. Question 1 Que donne le codage du texte maitrecorbeau en utilisant un décalage de 5 ? Question 2 Écrire la fonction codageCesar(t, n, d) qui prend en arguments le tableau t, sa longueur n et un entier d ; et qui retourne un tableau de même taille que t contenant le texte t décalé de d positions. Question 3 Écrire de même la fonction decodageCesar(t, n, d) prenant les mêmes arguments mais qui réalise le décalage dans l'autre sens. 1 Pour réaliser ce décodage, il faut connaître la valeur du décalage. Une manière de la déterminer automatiquement est d'essayer de deviner cette valeur. L'approche la plus couramment employée est de regarder la fréquence d'apparition de chaque lettre dans le texte crypté. En effet, la lettre la plus fréquente dans un texte suffisamment long en français est la lettre e. Question 4 Écrire la fonction frequences(t , n) qui prend en argument un tableau t de taille n représentant le texte crypté ; et qui retourne un tableau de taille 26 dont la case d'indice i contient le nombre d'apparitions du nombre i dans t (0 i < 26). Question 5 Écrire la fonction decodageAuto(t , n) qui prend en argument le tableau t de taille n représentant le texte crypté ; et qui retourne le texte t d'origine (en calculant la clé pour que la lettre e soit la plus fréquente dans le texte décrypté). Codage de Vigenère Au XVIème siècle, Blaise de Vigenère a modernisé le codage de César très peu résistant de la manière suivante. Au lieu de décaler toutes les lettres du texte de la même manière, on utilise un texte clé qui donne une suite de décalages. Prenons par exemple la clé concours. Pour crypter un texte, on code la première lettre en utilisant le décalage qui envoie le a sur le c (la première lettre de la clé). Pour la deuxième lettre, on prend le décalage qui envoie le a sur le o (la seconde lettre de la clé) et ainsi de suite. Pour la huitième lettre, on utilise le décalage a vers s, puis, pour la neuvième, on reprend la clé à partir de sa première lettre. Sur l'exemple ecolepolytechnique avec la clé concours, on obtient : (la première ligne donne le texte, la seconde le texte crypté et la troisième la lettre de la clé utilisée pour le décalage) e g c c q o o b n l n c e s o p j u o f r l d s y a c t h o e r n c e c h v o n h u i z r q i s u w c e s o Question 6 Donner le codage du texte becunfromage en utilisant la clé de codage jean. Question 7 Écrire la fonction codageVigenere(t, n, c, k) qui prend comme arguments un tableau t de taille n représentant le texte à crypter, et un tableau d'entiers c de longueur k donnant la clé servant au codage ; et qui retourne un tableau de taille n contenant le texte crypté t . Maintenant, on suppose disposer d'un texte t assez long crypté par la méthode de Vigenère, et on veut retrouver le texte t d'origine. Pour cela, on doit trouver la clé c ayant servi au codage. On procède en deux temps : 1) détermination de la longueur k de la clé c, 2) détermination des lettres composant c. La première étape est la plus difficile. On remarque que deux lettres identiques dans t espacées de × k caractères (où est un entier et k la taille de la clé) sont codées par la même lettre dans t . Mais cette condition n'est pas suffisante pour déterminer la longueur k de la clé c puisque des répétitions peuvent apparaître dans t sans qu'elles existent dans t. Par exemple, les lettres t et n sont toutes deux codées par la lettre h dans le texte crypté à partir de ecolepolytechnique avec concours comme clé. Pour éviter ce problème, on recherche les répétitions non pas d'une 2 lettre mais de séquences de lettres dans t puisque deux séquences de lettres répétées dans t, dont les premières lettres sont espacées par × k caractères, sont aussi cryptées par deux mêmes séquences dans t . Dans la suite de l'énoncé, on ne considère que des séquences de taille 3 en supposant que toute répétition d'une séquence de 3 lettres dans t provient exclusivement d'une séquence de 3 lettres répétée dans t. Ainsi, la distance séparant ces répétitions donne des multiples de k. La valeur de k est obtenue en prenant le PGCD de tous ces multiples. Si le nombre de répétitions est suffisant, on a de bonnes chances d'obtenir la valeur de k. On suppose donc que cette assertion est vraie. Question 8 Écrire la fonction pgcd(a, b) qui calcule le PGCD des deux entiers strictement positifs a et b par soustractions successives de ses arguments. Question 9 Écrire la fonction pgcdDesDistancesEntreRepetitions(t , n, i) qui prend en argument le texte crypté t de longueur n et un entier i (0 i < n - 2) qui est l'indice d'une lettre dans t ; et qui retourne le pgcd de toutes les distances entre les répétitions de la séquence de 3 lettres ht[i], t[i + 1], t[i + 2]i dans la suite du texte ht[i + 3], t[i + 4], . . . t[n - 1]i. Cette fonction retourne 0 s'il n'y a pas de répétition. Question 10 Écrire la fonction longueurDeLaCle(t , n) qui prend en argument le texte crypté t de longueur n ; et qui retourne la longueur k de la clé de codage. Question 11 Donner le nombre d'opérations réalisées par la fonction longueurDeLaCle en fonction de la longueur n ? (On ne comptera que le nombre d'appels à la fonction PGCD). Question 12 Une fois la longueur de la clé connue, donner une idée d'algorithme permettant de retrouver chacune des lettres de la clé. (Il s'agit de décrire assez précisément l'algorithme plutôt que d'écrire le programme). Question 13 Écrire la fonction decodageVigenereAuto(t , n) qui prend en argument le tableau t de taille n représentant le texte crypté ; et qui retourne le texte t d'origine. (On n'hésitera pas à recopier des parties de texte dans des tableaux intermédiaires). 3

 X Informatique MP/PC 2008 -- Corrigé Ce corrigé est proposé par Arnaud Borde (École Polytechnique) ; il a été relu par Céline Chevalier (ENS Cachan) et Vincent Puyhaubert (Professeur en CPGE). Le sujet propose l'étude de deux méthodes de codage de texte basées sur le décalage des lettres dans l'alphabet. On travaille cependant sur une représentation simpliste d'un texte par des tableaux d'entiers. Dans les deux méthodes, on commence par écrire les fonctions simples qui permettent de coder un texte à partir d'une clé. Puis on étudie des techniques pour décoder le texte automatiquement, c'est-à-dire sans connaître la clé. Il s'agit du travail qu'est amené à faire tout pirate qui se respecte. La plupart des questions demandent d'écrire du code. Il est rédigé en Maple dans ce corrigé car ce langage est le plus utilisé en classe préparatoire, même s'il est plus destiné au calcul formel qu'à la programmation. D'autres langages comme C, C++, Caml, Pascal et Java étaient autorisés pour cette épreuve. Les fonctions écrites n'utilisant que la syntaxe de base, vous pourrez sans difficulté les réécrire dans le langage de votre choix. · La première partie a pour objectif l'étude du codage de César. Ce codage basique paraîtra familier à tout le monde puisqu'il consiste simplement à choisir un entier k (une lettre en fait, mais peu importe) et à remplacer chaque lettre du texte par la k e qui la suit dans l'alphabet. Par exemple, pour k = 1, on remplace « a » par « b », « b » par « c », et ainsi de suite jusqu'au « z » remplacé par « a ». Comme mentionné précédemment, l'objectif de cette partie est non seulement de rédiger les programmes qui codent un texte, mais aussi de trouver une méthode de décodage automatique, basée sur l'hypothèse (souvent vérifiée) que la lettre « e » est la plus présente dans le texte original. Elle ne devrait poser aucun problème à tout candidat familier avec l'usage des boucles. · La seconde partie étudie le codage de Vigenère, qui est une amélioration de la méthode de César. Il s'agit cette fois d'utiliser non pas un unique entier, mais p entiers k1 , . . . , kp (en fait, un mot de p lettres). On code alors la ne lettre du texte grâce à un décalage de k(n mod p) caractères. À nouveau, la difficulté de cette partie réside essentiellement dans l'écriture de la fonction de décodage automatique. Heureusement, le travail est en grande partie facilité par l'énoncé, qui détaille de façon précise les hypothèses à effectuer sur le texte et l'algorithme à employer. Au final, le problème est assez long, mais en étant efficace il est possible d'en venir à bout dans les deux heures imparties. Il est bien écrit et très agréable à suivre. On peut passer pas mal de temps à s'amuser avec les fonctions de codage/décodage une fois le problème résolu en totalité. Indications 2 Écrire dès maintenant une fonction reste(a,b) qui renvoie le reste de la division de a par b. 3 Penser à réutiliser le code de la question 2 sans tout refaire. 4 Initialiser le tableau contenant les fréquences avec des 0. Parcourir le tableau de sorte que pour chaque nouvelle lettre lue, on mette à jour la case correspondante dans le tableau des fréquences. 5 Pour trouver la lettre qui code « e », rechercher la lettre dont l'entrée dans le tableau frequences est maximale. C'est cette lettre qui servira à calculer la clé de décodage. 7 Utiliser la fonction reste afin d'associer le bon décalage à chaque lettre du texte original. 8 Utiliser une méthode récursive. A partir d'un couple d'entier donné en argument, retrancher le plus petit au plus grand jusqu'à ce que le résultat de la soustraction soit nul. 9 Passer en revue tous les triplets de lettres qui suivent t[i], t[i+1], t[i+2] et les comparer à ce dernier. Faire attention aux indices de début et de fin de la boucle. Utiliser la propriété d'associativité du pgcd pour mettre à jour le résultat au fur et à mesure du parcours. 10 Utiliser les fonctions des questions 8 et 9. Utiliser encore la propriété d'associativité du pgcd et appliquer l'algorithme donné par l'énoncé. 11 Bien compter le nombre d'itérations dans les boucles. 12 Voir les différents tableaux t[j], t[j+k], t[j+2k],..., pour j {0, k - 1}, comme des textes codés par la méthode de César. 13 Conserver la vision de t comme un ensemble de textes codés par la méthode César et les décoder successivement comme dans la première partie. Utiliser une matrice (un tableau de tableaux) pour faciliter la remise en ordre du texte. Codage de César Ce corrigé introduit deux fonctions locales (reste et quotient) qui ne sont pas indispensables pour cette épreuve mais qui permettent de gagner du temps et évitent d'utiliser des fonctions de Maple qui ne sont peut-être pas connues de tous. Rappelons également que tout ce qui est précédé d'un # dans un programme en Maple n'est pas interprété par le compilateur, ce qui permet d'insérer des commentaires dans le code. 1 Représentons les phases du codage dans un tableau. Les différentes lignes représentent : le texte d'origine, les entiers correspondants, les entiers après décalage, le texte codé. m 12 7 h a 0 21 v i 8 3 d t 19 14 o r 17 12 m e 4 25 z c 2 23 x o 14 9 j r 17 12 m b 1 22 w e 4 25 z a 0 21 v u 20 15 p Le codage de maitrecorbeau avec un décalage de 5 vers la gauche est donc : hvdomzxjmwzvp Il faut être attentif au fait que le décalage se fait vers la gauche. 2 Commençons par écrire une fonction reste(a,b) qui renvoie le reste de la division de a par b. On programme cette fonction de manière récursive, en partant de a et en soustrayant b autant de fois qu'il le faut pour le résultat devienne égal à b. Notons qu'il faut aussi penser à prendre en compte le cas où a est négatif. reste:=proc(a,b) if 0<=a and a=b then RETURN(reste(a-b,b)); else RETURN(reste(a+26,b)); # correspond au cas où a est négatif fi; end; Cette fonction peut être remplacée par la fonction Maple irem(a,b). Cette fonction va principalement servir dans le cas particulier b = 26 pour se ramener à un entier compris entre 0 et 25 dès qu'on effectue un décalage. Pour coder un texte, chaque lettre doit être décalée vers la gauche du nombre d. Pour cela, on construit au moyen d'une boucle for un tableau resultat de même taille que le tableau t donné en entrée, dans lequel on stocke le texte chiffré. Pour chaque indice, l'élément rajouté au tableau est le reste de la division par 26 du chiffre t[i] auquel on a soustrait d. codageCesar:=proc(t,n,d) local resultat,i; resultat:=[seq(0,i=0..n-1)]; for i from 0 to n-1 do resultat[i+1]:=reste(t[i+1]-d,26); od; RETURN(resultat); end; Dans Maple, contrairement aux autres langages de programmation, les indices de tableaux commencent par défaut à 1 et non à 0. Si vous utilisez ce langage, il est bien de préciser la convention que vous adoptez pour les indices car le sujet suppose qu'ils débutent à 0. On respecte ici la convention utilisée par l'énoncé pour les boucles tout en conservant un code exécutable en réajustant les indices dans le corps de la boucle avec la syntaxe tableau[i+1]. La commande seq permet de fabriquer une séquence. Sa syntaxe générale est seq(f(compteur),compteur=début..fin). Elle produit alors la séquence f(début), f(début+1), ..., f(fin). Ici, cette séquence est placée entre crochets afin de fabriquer une liste. Il existe une fonction de Maple, nops(), qui permet de récupérer la longueur du tableau ou de la liste placé en argument. On aurait donc pu se passer du second argument de la fonction (et de même pour beaucoup de fonctions demandées par l'énoncé). Mais il y a fort à parier que les concepteurs du sujet n'ont pas voulu pénaliser les élèves qui ne connaîtraient pas cette fonction. 3 Il suffit d'utiliser la fonction précédente avec un décalage opposé. decodageCesar:=proc(t,n,d) codageCesar(t,n,-d); end; 4 On remplit en premier lieu le tableau des fréquences appelé freq à l'aide de 0 avant de parcourir le texte et de le mettre à jour au fur et à mesure. À chaque fois que l'on rencontre une lettre, on augmente la case correspondante (à savoir celle dont l'indice est t'[i]) dans le tableau des fréquences de 1. frequences:=proc(tprime,n) local freq,i; # on crée le tableau des fréquences avec des 0 freq:=[seq(0,i=0..26)]; # on met à jour le tableau des fréquences for i from 0 to n-1 do freq[tprime[i+1]+1]:=freq[tprime[i+1]+1]+1; od; RETURN(freq); end;