É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
