Crypter un message – Bac théorique – Section informatique – 2019
Sujet (Algo et programmation - Bac 2019)
Parmi les méthodes de chiffrement utilisant un mot-clé, on cite celle décrite ci-après qui permet de crypter un message msg ne dépassant pas 18 caractères et formé uniquement de lettres minuscules, de chiffres et d'espaces :
Etape1 : Remplir aléatoirement une matrice carrée Ml de dimension 6x6 par toutes les lettres alphabétiques minuscules ainsi que tous les chiffres.
NB :Les indices des lignes et des colonnes de la matrice M1 sont les lettres A, B, C, D, E et F.
Etape2 : Générer un message intermédiaire msgi, en concaténant les résultats du chiffrement de chaque caractère du message msg. Le résultat du chiffrement d'un caractère est la concaténation de l'indice de la ligne avec J'indice de la colonne de la case contenant le caractère à chiffrer.
Le caractère espace ne sera pas chiffré.
Etape3 :Remplir une deuxième matrice M2 de taille 7x6 caractères en mettant dans :
la première ligne, les lettres d'un mot-clé formé de 6 lettres majuscules,
le reste des lignes, Je message msgi caractère par caractère en commençant par la première case de la deuxième
NB :Chaque case vide de la matrice M2 sera rem pl ie par le caractère espace.
Etape4 : Trier les éléments de la première ligne de M2 scion un ordre alphabétique croissant, sachant que tout déplacement d'un élément entraîne le déplacement de tous les éléments de la colonne correspondante.
Etape5 : Concaténer les lettres de la matrice M2, colonne par colonne en commençant par la 1ère colonne et sans considérer les éléments de la lere ligne, pour obtenir le message, chiffré final.
Exemple :
Pour msg = "promotion bac 2019" et le mot-clé "CHAISE"
Etape 1 :La matrice M1 est remplie aléatoirement comme suit :
Travail demandé
On se propose d'écrire un programme permettant :
- de saisir un message msg ne dépassant pas 18 caractères et formé uniquement de lettres minuscules, de chiffres et d'espaces.
- de saisir un mot-clé formé de 6 lettres
- de crypter le message msg selon la méthode de chiffrement décrite précédemment.
NB : On dispose d'un module Initialisation(Ml) qui permet de remplir aléatoirement la matrice carrée Ml comme décrit dans l'étape 1 et que le candidat peut appeler dans sa solution sans le développer.
1. Analyser le problème en le décomposant en modules.
2. Ecrire les algorithmes des modules envisagés.
Solution Algorithmique
Dans cet algorithme, On va utiliser six fonctions et quatre procédures:
- la procédure remplir_matrice_m1()
- la procédure afficher_matrice()
- la fonction verif_msg()
- la fonction saisie_msg()
- la fonction crypter_etape1()
- la fonction verif_cle()
- la fonction saisie_cle()
- la procédure remplir_matrice_m2()
- la procédure tri_matrice()
- la fonction crypter_etape2()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Algorithme cryptage_message Debut remplir_matrice_m1(m1) Ecrire('*** Matrice M1 ****') afficher_matrice(m1, 6, 6) msg <- saisie_msg() # saisie du message msg_crypte <- crypter_etape1(msg, m1) # cryptage étape 1 cle <- saisie_cle() # saisie de la clé remplir_matrice_m2(m1, m2, cle, msg_crypte) # remplissage de m2 Ecrire('*** Matrice M2 ****') afficher_matrice(m2, 7, 6) tri_matrice(m2) # tri de m2 selon la clé Ecrire('*** Matrice M2 triée ****') afficher_matrice(m2, 7, 6) Ecrire('***********************') Ecrire('message chiffré =', crypter_etape2(m2)) # cryptage étape 2 Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| m1 | matrice |
| msg | chaîne |
| msg_crypte | chaîne |
| cle | chaîne |
| m2 | matrice |
La procédure remplir_matrice_m1
Cette procédure sert à remplir une matrice carrée 6×6 (m1) avec des caractères alphanumériques choisis aléatoirement, sans répétition.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Procédure remplir_matrice_m1(m:matrice) ch <- 'abcdefghijklmnopqrstuvwxyz0123456789' # caractères possibles Pour i de 0 à 5 faire Pour j de 0 à 5 faire Si long(ch) != 1 alors indice <- Alea(0, long(ch)-1) # choix aléatoire m1[i][j] <- ch[indice] # assignation ch <- Sous_chaine(ch, 0 , indice) + Sous_chaine(ch , indice+1 , long(ch)) # suppression du caractère choisi Sinon m1[i][j] <- ch Fin si Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaîne |
| i | entier |
| j | entier |
La procédure afficher_matrice
Cette procédure permet d’afficher à l’écran une matrice m de taille l × c de manière lisible, ligne par ligne.
|
1 2 3 4 5 6 7 8 |
Procédure afficher_matrice(m:matrice;l:entier;c:entier) Pour i de 0 à l-1 faire Pour j de 0 à c-1 faire Ecrire(m[i][j],' ') Fin pour Ecrire() Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La fonction verif_msg
Cette fonction sert à vérifier la validité d’un message (chaîne de caractères) selon des règles bien précises.
Règles vérifiées :
- La longueur du message doit être comprise entre 1 et 18 caractères.
- Chaque caractère du message doit être : une lettre minuscule (a à z), ou un chiffre (0 à 9), ou un espace (' ').
|
1 2 3 4 5 6 7 8 9 10 11 |
Fonction verif_msg(ch:chaine):booleen Si 1 <= long(ch) <= 18 alors i <- 0 Tant que (i < long(ch)-1) et (('a' <= ch[i] <= 'z') ou ('0' <= ch[i] <= '9') ou ch[i] = ' ') faire i <- i + 1 Fin tant que retourner (('a' <= ch[i] <= 'z') ou ('0' <= ch[i] <= '9') ou ch[i] = ' ') Sinon retourner Faux Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction saisie_msg
Cette fonction permet de saisir un message valide auprès de l’utilisateur, en s’assurant qu’il respecte les règles définies par la fonction verif_msg.
|
1 2 3 4 5 6 7 8 9 |
Fonction saisie_msg():chaine Ecrire('donner un message valide : ') Lire(ch) Tant que Non (verif_msg(ch)) faire Ecrire('donner un message valide : ') Lire(ch) Fin tant que retourner ch Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaîne |
La fonction crypter_etape1
Cette fonction réalise la première étape du cryptage d’un message en utilisant une matrice 6×6 (m) contenant des caractères alphanumériques.
Cette fonction transforme chaque caractère du message en un couple de lettres (A–F) représentant sa position dans une matrice de chiffrement 6×6, tout en conservant les espaces.
|
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 26 27 |
Fonction crypter_etape1(msg:chaine, m:matrice):chaine msg_crypte <- '' Pour k de 0 à long(msg)-1 faire Si msg[k] != ' ' alors i <- 0 test <- Faux Tant que i <= 5 et test = Faux faire j <- 0 Tant que j <= 5 et test = Faux faire Si m[i][j] = msg[k] alors test <- Vrai Sinon j <- j + 1 Fin si Fin tant que Si test = Faux alors i <- i + 1 Fin si Fin tant que # Transformation du caractère en code à deux lettres (A..F) msg_crypte <- msg_crypte + chr(65+i) + chr(65+j) Sinon msg_crypte <- msg_crypte + ' ' Fin si Fin pour retourner msg_crypte Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| msg_crypte | chaîne |
| k | entier |
| i | entier |
| test | booléen |
La fonction verif_cle
Cette fonction permet de vérifier la validité d’une clé de chiffrement.
Règles vérifiées :
- La clé doit contenir exactement 6 caractères.
- Chaque caractère de la clé doit être une lettre majuscule (A à Z).
|
1 2 3 4 5 6 7 8 9 10 11 |
Fonction verif_cle(ch:chaine):booleen Si long(ch) = 6 alors i <- 0 Tant que (i < long(ch)-1) et ('A' <= ch[i] <= 'Z') faire i <- i + 1 Fin tant que retourner ('A' <= ch[i] <= 'Z') Sinon retourner Faux Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction saisie_cle
Cette fonction permet de saisir une clé de chiffrement valide auprès de l’utilisateur, en s’assurant qu’elle respecte les règles définies par la fonction verif_cle.
|
1 2 3 4 5 6 7 8 9 |
Fonction saisie_cle():chaine Ecrire('donner une cle valide : ') Lire(ch) Tant que Non (verif_cle(ch)) faire Ecrire('donner une cle message valide : ') Lire(ch) Fin tant que retourner ch Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaîne |
La procédure remplir_matrice_m2
Cette procédure sert à construire la matrice de chiffrement m2 (7 × 6) à partir de la clé et du message crypté.
Principe :
La matrice m2 est organisée ainsi :
1ʳᵉ ligne : la clé de chiffrement (6 lettres).
6 lignes suivantes : le message crypté, réparti ligne par ligne.
Le message est complété par des espaces si sa longueur est inférieure à 36 caractères.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Procédure remplir_matrice_m2(m1:matrice, m2:matrice, cle:chaine, msg:chaine) Tant que long(msg) != 36 alors # compléter le message crypté avec des espaces si nécessaire msg <- msg + ' ' Fin tant que Pour j de 0 à 5 faire m2[0][j] <- cle[j] # première ligne = clé Fin pour k <- 0 Pour i de 1 à 6 faire Pour j de 0 à 5 faire m2[i][j] <- msg[k] k <- k + 1 Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| k | entier |
La procédure tri_matrice
Cette procédure sert à trier les colonnes de la matrice m2 selon l’ordre alphabétique de la clé, qui se trouve dans la première ligne de la matrice.
Elle réorganise les colonnes de la matrice en fonction de la clé triée, ce qui constitue une étape classique du chiffrement par transposition.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Procédure tri_matrice(m:matrice) Pour k de 0 à 4 faire minimum <- k Pour j de k+1 à 5 faire Si m[0][minimum] > m[0][j] alors minimum <- j Fin si Fin pour Si minimum != k alors Pour i de 0 à 6 faire temp <- m[i][k] m[i][k] <- m[i][minimum] m[i][minimum] <- temp Fin pour Fin si Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| k | entier |
La fonction crypter_etape2
Cette fonction réalise la deuxième étape du cryptage en produisant le message crypté final à partir de la matrice m2.
Elle transforme la matrice triée en une chaîne de caractères en lisant les données verticalement, ce qui finalise le chiffrement par transposition.
|
1 2 3 4 5 6 7 8 9 |
Fonction crypter_etape2(m2:matrice):chaine msg_crypter <- '' Pour j de 0 à 5 faire Pour i de 1 à 6 faire msg_crypter <- msg_crypter + m2[i][j] Fin pour Fin pour retourner msg_crypter Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| msg_crypter | chaîne |
Solution en Python
|
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
from numpy import * import random # nécessaire pour la génération aléatoire # -------------------------------------------------- # Définition des dimensions maximales de la matrice # -------------------------------------------------- lignes = 50 # Nombre maximal de lignes de la matrice colonnes = 50 # Nombre maximal de colonnes de la matrice # -------------------------------------------------- # Création des structures de données # -------------------------------------------------- # Matrice m1 : sert à stocker les caractères pour le cryptage # Matrice m2 : sera utilisée pour l'étape 2 du cryptage m1 = array([[str] * colonnes] * lignes) m2 = array([[str] * colonnes] * lignes) # -------------------------------------------------- # Procédure qui remplit la matrice m1 avec des caractères # alphanumériques choisis aléatoirement # -------------------------------------------------- def remplir_matrice_m1(m): ch = 'abcdefghijklmnopqrstuvwxyz0123456789' # caractères possibles for i in range(6): for j in range(6): if len(ch) != 1: indice = random.randint(0, len(ch)-1) # choix aléatoire m1[i][j] = ch[indice] # assignation ch = ch[0:indice] + ch[indice+1:len(ch)] # suppression du caractère choisi else: m1[i][j] = ch # -------------------------------------------------- # rocédure qui affiche une matrice de taille l x c # -------------------------------------------------- def afficher_matrice(m, l, c): for i in range(l): for j in range(c): print(m[i][j], end=' ') print() # -------------------------------------------------- # Vérification de la validité d'un message # Le message doit être constitué de lettres minuscules, # de chiffres ou d'espaces, et sa longueur doit être 1..18 # -------------------------------------------------- def verif_msg(ch): if 1 <= len(ch) <= 18: i = 0 while (i < len(ch)-1) and (('a' <= ch[i] <= 'z') or ('0' <= ch[i] <= '9') or ch[i] == ' '): i = i + 1 return (('a' <= ch[i] <= 'z') or ('0' <= ch[i] <= '9') or ch[i] == ' ') else: return False # -------------------------------------------------- # Saisie d'un message valide # -------------------------------------------------- def saisie_msg(): ch = input('donner un message valide : ') while not verif_msg(ch): ch = input('donner un message valide : ') return ch # -------------------------------------------------- # Première étape du cryptage # Chaque caractère est transformé en deux lettres selon sa position dans m1 # -------------------------------------------------- def crypter_etape1(msg, m): msg_crypte = '' for k in range(len(msg)): if msg[k] != ' ': i = 0 test = False while i <= 5 and test == False: j = 0 while j <= 5 and test == False: if m[i][j] == msg[k]: test = True else: j = j + 1 if test == False: i = i + 1 # Transformation du caractère en code à deux lettres (A..F) msg_crypte = msg_crypte + chr(65+i) + chr(65+j) else: msg_crypte = msg_crypte + ' ' return msg_crypte # -------------------------------------------------- # Vérification de la validité de la clé # La clé doit contenir 6 lettres majuscules # -------------------------------------------------- def verif_cle(ch): if len(ch) == 6: i = 0 while (i < len(ch)-1) and ('A' <= ch[i] <= 'Z'): i = i + 1 return ('A' <= ch[i] <= 'Z') else: return False # -------------------------------------------------- # Saisie d'une clé valide # -------------------------------------------------- def saisie_cle(): ch = input('donner une cle valide : ') while not verif_cle(ch): ch = input('donner une cle valide : ') return ch # -------------------------------------------------- # Remplissage de la matrice m2 # La première ligne contient la clé # Les lignes suivantes contiennent le message crypté (avec des espaces pour compléter) # -------------------------------------------------- def remplir_matrice_m2(m1, m2, cle, msg): while len(msg) != 36: # compléter le message crypté avec des espaces si nécessaire msg = msg + ' ' for j in range(6): m2[0][j] = cle[j] # première ligne = clé k = 0 for i in range(1, 7): for j in range(6): m2[i][j] = msg[k] k = k + 1 # -------------------------------------------------- # Tri des colonnes de la matrice m2 en fonction de la clé (première ligne) # -------------------------------------------------- def tri_matrice(m): for k in range(5): minimum = k for j in range(k+1, 6): if m[0][minimum] > m[0][j]: minimum = j if minimum != k: for i in range(7): temp = m[i][k] m[i][k] = m[i][minimum] m[i][minimum] = temp # -------------------------------------------------- # Deuxième étape du cryptage # Lecture de la matrice m2 par colonnes pour générer le message final # -------------------------------------------------- def crypter_etape2(m2): msg_crypter = '' for j in range(6): for i in range(1, 7): msg_crypter = msg_crypter + m2[i][j] return msg_crypter # -------------------------------------------------- # Programme principal # -------------------------------------------------- remplir_matrice_m1(m1) print('*** Matrice M1 ****') afficher_matrice(m1, 6, 6) msg = saisie_msg() # saisie du message msg_crypte = crypter_etape1(msg, m1) # cryptage étape 1 cle = saisie_cle() # saisie de la clé remplir_matrice_m2(m1, m2, cle, msg_crypte) # remplissage de m2 print('*** Matrice M2 ****') afficher_matrice(m2, 7, 6) tri_matrice(m2) # tri de m2 selon la clé print('*** Matrice M2 triée ****') afficher_matrice(m2, 7, 6) print('***********************') print('message chiffré =', crypter_etape2(m2)) # cryptage étape 2 |
Exécution du programme
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
