Exercices TD Numération et Cryptographie
Télécharger PDFMPSI831 Lycée Masséna
DS 1 : Numération et Cryptographie
Préambule. Ce sujet comporte 4 exercices et un problème, tout cela est indépendant. Le sujet est très long et n’est pas fait pour être terminé. Les quatre exercices sont proches du cours, le problème est proche de ce qui a été fait en TP sur la manipulation de tableaux en Python. Ce problème se divise en deux parties, la deuxième étant d’un niveau plus relevé.
1 Exercices proches du cours
Exercice 1
On considère l’entier N = 541. Donnez sa représentation dans les bases 2,3,4 et 9 et 16. Vous êtes libres d’utiliser la méthode que vous voulez, mais les calculs devront apparaître clairement sur la copie. On rappelle à toute fin utile que 4 = 22, 9 = 32et 16 = 42 = 24.
Exercice 2
On considère l’entier N = 12101 3. Déroulez l’algorithme de Hörner à la main pour calculer son interpré tation en base 10.
Exercice 3
On considère les deux entiers codés en binaire sur 8 bits par N = 10110100 2et M = 01101001 2. On rappelle dans le tableau qui suit les puissances de 2 de 20 à 27.
| i | 2i |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| 6 | 64 |
| 7 | 128 |
1. Donnez l’interprétation de N et de M comme entiers naturels sur 8 bits.
2. Donnez l’interprétation de N et de M comme entiers relatifs codés en représentation en complément à 2 sur 8 bits.
3. Effectuez l’addition en binaire de N et de M (on fera apparaître clairement les retenues et la retenue sortante). Y a-t-il dépassement de capacité sur entiers naturels ? sur entiers relatifs ? Justifiez.
Exercice 4
On souhaite tracer le graphe de la fonction x 7→ x2sur l’intervalle [0, 3]. Quel est le problème dans le code suivant ? Donnez une modification possible pour résoudre ce problème.
abscisses=[] ordonnees=[] x=0 while x!=3.1: # != est le symbole pour différent. abscisses.append(x) ordonnees.append(x*x) x+=0.1 import matplotlib.pyplot as plt plt.plot(abscisses,ordonnees) plt.show()
2 Problème : Ave Cesar (Zud Bdrzq)
Introduction
La cryptanalyse est la science du décodage des messages codés. Le principe est simple, le texte d’origine est transformé (on parle de chiffrement) à l’aide d’une clé, qui est secrète. Quiconque possède la clé de chiffrement est capable de déchiffrer le message. Le travail du cryptanalyste consiste à casser le chiffrement, c’est à dire découvrir la clé de chiffrement pour retrouver le message d’origine. On étudie ici deux (vieilles !) méthodes de chiffrement, et des méthodes de cryptanalyse associées. La plupart des questions demandent d’écrire du code Python, on attachera une importance particulière à l’indentation sur la copie.
On cherche à chiffrer un texte t composé de caractères en minuscules (soit 26 lettres différentes) représentés par des entiers compris entre 0 et 25, avec l’identification naturelle : 0 ↔ a, 1 ↔ b, ..., 25 ↔ z. On suppose pour simplifier que le texte ne contient pas d’autres caractères (ni espaces, ni ponctuation...). Le tableau qui suit pourra vous servir à l’occasion.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 |
Ainsi, le texte lyceemassena est représenté par le tableau suivant, où la première ligne représente les indices des lettres, la seconde le texte et la troisième les entiers correspondants.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| l | y | c | e | e | m | a | s | s | e | n | a |
| 11 | 24 | 2 | 4 | 4 | 12 | 0 | 18 | 18 | 4 | 13 | 0 |
En Python, on utilisera simplement le tableau [11, 24, 2, 4, 4, 12, 0, 18, 18, 4, 13, 0] pour représenter le texte lyceemassena. Mis à part pour les questions 1 et 7, qui portent sur des exemples, un texte à chiffrer ou à déchiffrer sera toujours un tel tableau de nombres.
Boucles et fonctions
On rappelle ici la structure de boucles, structures conditionnelles et fonctions en Python.
def fonction(arguments): [corps de la fonction] return(sortie) for element in iterable: [instructions] if booleen: [si booleen vaut True] elif autre_booleen: [si booleen vaut False et autre_booleen vaut True] else: #on peut mettre autant de elif qu'on veut ! [si aucune des autres conditions n'est vérifiée] while booleen: [instructions]
On peut récupérer la sortie d’une fonction par affectation : a=fonction(arguments). Quand on parle de booléen dans un test, celui-ci est en général donné par l’évaluation d’une expression booléenne, du type a<=b and c==d. Dans une boucle for, l’itérable est en général donné par range. Si m, n sont deux entiers et p > 0 est un entier strictement positif, dans for i in range(m,n,p), i prendra toutes les valeurs m, m + p, m + 2p... strictement inférieures à n. Si p est omis, il vaut 1 et si de plus m est omis, il vaut 0. Avec if, le else et les elif sont facultatifs.
Le modulo
On rappelle que si a et b sont deux entiers, avec b strictement positif, a%b donne le reste de la division euclidienne de a par b, c’est à dire l’unique entier r ∈ [[0, b − 1]] tel qu’il existe un entier q, tel que a = bq + r. On fera un usage intensif du modulo dans ce problème, en particulier avec b=26.
Les tableaux
Si T est un tableau, on accède à sa longueur avec la commande len. Les indices des éléments du tableau vont de 0 à len(T)-1. En particulier, for i in range(len(T)) parcourt tous les indices des éléments du tableau.
On accède à un élément du tableau par T[i], ce qui permet de récupérer l’élément dans une variable (x=T[i]) ou de le modifier (avec T[i]=x).
Pour créer un tableau rempli de 0 de taille n, on pourra utiliser [0]*n. Un autre moyen de construire un nouveau tableau est de créer un tableau vide (T=[]) et de le remplir progressivement avec la méthode append : après la séquence d’instructions T.append(4) ; T.append(7) ; T.append(2), le tableau T est maintenant égal à [4,7,2].
2.1 Chiffrement de César
Ce chiffrement est un des plus rudimentaires. Il a été utilisé par Jules César pour certaines de ses correspondances. Le principe est de décaler les lettres de l’alphabet vers la gauche d’une ou plusieurs positions, la clé de chiffrement étant la valeur du décalage. Par exemple, en décalant les lettres d’une 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 chiffrement du texte informatique en utilisant un décalage de 5 ?
Question 2. Écrire la fonction chiffrementCesar(t,d) qui prend en arguments le tableau t et un entier d, et qui retourne un tableau de même taille que t contenant le texte t décalé de d positions.
>>> chiffrementCesar([0, 21, 4, 2, 4, 18, 0, 17],1) #correspond à avecesar, qu'on décale de 1. [25, 20, 3, 1, 3, 17, 25, 16]
Question 3. Écrire de même la fonction dechiffrementCesar(t,d) prenant les mêmes arguments mais qui réalise le décalage dans l’autre sens.
>>> dechiffrementCesar([25, 20, 3, 1, 3, 17, 25, 16],1) #déchiffrement de zudbdrzq [0, 21, 4, 2, 4, 18, 0, 17]
Pour réaliser la cryptanalyse, il faut découvrir la valeur du décalage, qu’on va essayer de deviner automatiquement. L’approche la plus couramment employée est de regarder la fréquence d’apparition de chaque lettre dans le texte chiffré. 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) qui prend en argument un tableau t représentant le texte chiffré, et qui retourne un tableau de taille 26 dont la case d’indice i contient le nombre d’apparitions du nombre i dans t (avec 0 ≤ i < 26).
>>> frequences([1, 14, 18, 20, 20, 2, 16, 8, 8, 20, 3, 16]) [0, 1, 1, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 0, 0, 0, 0]
Question 5. Écrire une fonction indice_max(T) prenant en entrée un tableau d’entiers T et retournant l’indice du maximum du tableau.
>>> indice_max([0,7,8,10,1]) 3
Question 6. Écrire la fonction dechiffrementAuto(t) qui prend en argument le tableau t représentant le texte chiffré, et qui retourne le tableau correspondant au texte d’origine (en calculant la clé pour que la lettre e soit la plus fréquente dans le texte déchiffré).
>>> dechiffrementAuto([1, 14, 18, 20, 20, 2, 16, 8, 8, 20, 3, 16]) [11, 24, 2, 4, 4, 12, 0, 18, 18, 4, 13, 0]
Dans l’exemple précédent, on retrouve le tableau correspondant au texte lyceemassena, ce qui n’est pas étonnant : la lettre e est celle qui apparaît le plus.
2.2 Chiffrement de Vigenère
Au XVIème siècle, Blaise de Vigenère a modernisé le chiffrement 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é (de petite taille) qui donne une suite de décalages. Prenons par exemple la clé mpsi. Pour chiffrer un texte, on code la première lettre en utilisant le décalage qui envoie le a sur le m (la première lettre de la clé). Pour la deuxième lettre, on prend le décalage qui envoie le a sur le p, de même pour la troisième et la quatrième lettre avec s et i. Puis, pour la cinquième, on reprend la clé à partir de sa première lettre. Sur l’exemple lyceemassena avec la clé mpsi, on obtient le tableau qui suit. La première ligne donne le texte, la seconde la lettre de la clé utilisée pour le décalage et la troisième le texte chiffré. Ici le nombre de lettres de la clé divise la taille du texte, mais c’est fortuit.
| l | y | c | e | e | m | a | s | s | e | n | a |
|---|---|---|---|---|---|---|---|---|---|---|---|
| m | p | s | i | m | p | s | i | m | p | s | i |
| x | n | u | m | q | b | s | a | e | t | f | i |
Question 7. Donner le chiffrement du texte promenade en utilisant la clé de chiffrement nice.
Question 8. Écrire la fonction chiffrementVigenere(t,c) qui prend comme arguments un tableau d’entiers t représentant le texte à chiffrer, et un tableau d’entiers c donnant la clé servant au chiffrement, et qui retourne un tableau de même taille que t contenant les entiers correspondant au texte chiffré.
>>> #chiffrement de lyceemassena par la cle mpsi >>> chiffrementVigenere([11, 24, 2, 4, 4, 12, 0, 18, 18, 4, 13, 0],[12,15,18,8]) [23, 13, 20, 12, 16, 1, 18, 0, 4, 19, 5, 8]
Maintenant, on suppose disposer d’un texte t assez long (xnumqbsaetfi n’est pas un exemple pertinent !) chiffré par la méthode de Vigenère, et on veut retrouver le texte d’origine t0. Pour cela, on doit trouver la clé c ayant servi au chiffrement. On procède en deux temps :
- détermination de la longueur k de la clé c,
- détermination des lettres composant c.
La première étape est la plus difficile. On remarque que deux lettres identiques dans t0 espacées de p×k caractères (où p 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 t0.
Pour éviter ce problème, on recherche les répétitions non pas d’une lettre mais de séquences de ` lettres dans t puisque deux séquences de lettres répétées dans t0, dont les premières lettres sont espacées par p × k caractères, sont aussi chiffré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 5 en supposant que toute répétition d’une séquence de 5 lettres dans t provient exclusivement d’une séquence de 5 lettres répétée dans t0. Ainsi, la distance séparant ces répétitions donne des multiples de k. La valeur de k est obtenue en prenant le PGCD (plus grand diviseur commun) 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. La fonction suivante, que l’on pourra utiliser librement, donne le PGCD de deux entiers positifs a et b (avec P GCD(a, b) = P GCD(b, a) = a si b = 0).
def PGCD(a,b): m,n=a,b while n!=0: m,n=n,m%n return(m)
On définit le PGCD de plusieurs entiers comme le plus grand diviseur commun de tous ces entiers. Il peut être calculé en appliquant plusieurs fois la fonction PGCD ci-dessus.
Question 9. Écrire la fonction pgcdDesDistancesEntreRepetitions(t,i) qui prend en argument le texte chiffré t et un entier i (0 ≤ i ≤ n−5) 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 5 lettres t[i:i+5] dans la suite du texte t[i+5], t[i+6],..., t[n-1]. Cette fonction retourne 0 s’il n’y a pas de répétition. Pour tester l’égalité de deux séquences de longueur 5 démarrant aux indices j et k, on pourra utiliser t[j:j+5]==t[k:k+5].
Question 10. Écrire la fonction longueurDeLaCle(t) qui prend en argument le texte chiffré t ; et qui retourne la longueur k de la clé de chiffrement.
Question 11. Une fois la longueur de la clé connue, écrire la fonction dechiffrementVigenere(t,k) prenant en entrée le texte à déchiffrer et la longueur de la clé, et retournant le texte d’origine.
Indication : il suffit de faire une variante de l’algorithme proposé pour déchiffrer un texte chiffré par la méthode de César, mais il y a un décalage différent pour chaque lettre de la clé.
Question 12. Enfin, écrire la fonction dechiffrementAutoVigenere(t) permettant de déchiffrer de manière automatique un texte chiffré par la méthode de Vigenère.
FAQ
Qu'est-ce que le chiffrement de César ?
Le chiffrement de César est une méthode de chiffrement où chaque lettre du texte est décalée d'un certain nombre de positions dans l'alphabet.
Comment fonctionne le chiffrement de Vigenère ?
Le chiffrement de Vigenère utilise une clé de chiffrement pour décaler chaque lettre du texte d'un nombre de positions différent, basé sur la position de la lettre dans la clé.
Quelle est la différence entre le chiffrement de César et le chiffrement de Vigenère ?
Le chiffrement de César utilise un décalage unique pour toutes les lettres du texte, tandis que le chiffrement de Vigenère utilise une clé de chiffrement pour appliquer des décalages différents à chaque lettre.