Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 S. BOUKHEDOUMA USTHB Module ALGO Faculté d’électronique et d’informatique Ann

1 S. BOUKHEDOUMA USTHB Module ALGO Faculté d’électronique et d’informatique Année 2018/2019 Département d’informatique Section L2Acad-A Devoir Algorithmique et Programmation C Implémentation de quelques algorithmes de cryptage Objectifs du TP  Ecriture d’algorithmes, procédures et fonctions et traduction en langage C  Manipulation de tableaux, de chaînes de caractères et de bits en C  Ecriture et appel de fonctions en C  Utilisation d’un menu permettant à l’utilisateur de choisir un des algorithmes programmés.  Initiation des étudiants à la notion de complexité des algorithmes  Initiation des étudiants aux notions de cryptage/décryptage des textes Le travail demandé consiste à implémenter quelques algorithmes de cryptage décrits ci- dessous, il s’agit de programmer le cryptage et le décryptage (opération inverse) des textes (chaines de caractères). Le cryptage de données est un ensemble de techniques qui permettent de chiffrer un texte (le transformer pour le rendre incompréhensible), utilisé dans le domaine de la communication (envoi de messages), seule la personne qui saura déchiffrer le texte, pourra le lire correctement. Pour déchiffrer un texte (i.e retrouver le message en clair), il faudra connaître la technique avec laquelle il a été chiffré, pour pouvoir effectuer l’opération inverse. Cryptage (chiffrement) Décriptage (déchiffrement) Plusieurs algorithmes de cryptage existent, basés sur des mécanismes de substitution (remplacement de lettres du texte clair par d’autres), nous présentons dans ce qui suit quelques uns en expliquant le principe de fonctionnement de chacun d’eux. Algorithme1 : algorithme de César : Consiste à remplacer chaque lettre du texte par celle qui se situe à n positions plus loin dans l’alphabet, n étant un paramètre au choix. Exemple : Si n=3, a sera remplacé par d, b par e,…, z par c. Avec cet algorithme, le texte "bonjour" sera crypté en "erqmrxu" Algorithme2 : le carré de 25 C’est un système basé sur un carré de 25, chaque lettre peut être représentée par un groupe de 2 chiffres : celui correspondant à l’indice de sa ligne et celui correspondant à l’indice de sa colonne, ainsi a= 00, b= 01, h = 12… texte en clair (lisible) texte crypté (illisible) 2 S. BOUKHEDOUMA a b c d e deux lettres de l’alphabet seront confondues f g h i j généralement i avec j ou v avec w k l m n o elles auront le même code p q r s t u v x y z Avec cet algorithme le texte "bon" sera crypté en "012423" Algorithme 3 : carré de 25 avec clé C’est une variante de l’algorithme précédent, utilisant une clé secrète comme paramètre (elle peut changer d’une exécution à une autre), il faudra commencer par placer dans le carré, les lettres constituant la clé (sans répétitions), et continuer ensuite à placer les autres lettres de l’alphabet dans l’ordre. Pour décrypter le texte, il faudra connaitre la clé. Exemple : clé= "password" p a s w o deux lettres de l’alphabet seront confondues r d b c e ici, i avec j f g h i k l m n q t "merci" sera codé par : 3114101323 u v x y z Algorithme4 : chiffre de Playfair Basé sur le carré de 25, il remplace chaque paire de lettres du texte clair par une autre paire, on chiffre le texte par diagrammes. Chaque paire de lettres donne les coordonnées d’un rectangle dans la matrice, on remplace cette paire de lettres par les lettres formant les deux autres sommets du rectangle, si les deux lettres se trouvent sur la même ligne, elles seront remplacées par les deux situées à droite, si elles se trouvent sur la même colonne, elles seront remplacées par les deux en dessous. Exemple a b c d e f g h i j k l m n o p q r s t "merci" sera codé par : "cohxi" u v x y z Algorithme5 : algorithme de Vigenere On associe à chaque lettre un chiffre correspondant à sa position dans l’alphabet, a :1, b : 2,…z : 26, l’algorithme utilise une clé. Il s’agit de chiffrer le texte original en utilisant la clé qui sera répétée autant de fois que nécessaire dans le message : 3 S. BOUKHEDOUMA Exemple : soit la clé "bonjour" et soit le message suivant : "ceci est un texte secret" bonjour bonjour bonjou pour avoir une lettre du message chiffré , il faut prendre le code d’une lettre du message en clair et le code d’une lettre de la clé, faire leur somme modulo 26 code(y) = (code(x) + code( c))mod 26 pour déchiffrer le message, il faudra faire l’opération inverse code(x) = (code(y)-code(c)) mod 26 Algorithme 6 : algorithme du OU EXCLUSIF Dans cet algorithme, on effectue un codage au niveau bit. Comme l’algorithme précédent, on utilise une clé qu’il faudra répéter autant de fois que nécessaire sur toute la longueur du message, et effectuer une opération de ou exclusif + entre un bit du message et celui de la clé. Exemple : si le message = 1010100011 la clé = 1101 On aura 1010100011 + 1101110111 0111010100 message chiffré Pour retrouver le texte en clair, il faudra effectuer un autre ou exclusif entre le texte chiffré et la clé. Travail demandé  Ecrire les algorithmes (actions paramétrées) permettant d’implémenter chacune des méthodes de cryptage et décryptage sus-décrites (l’algorithme doit avoir le nom de la méthode associée).  Préciser la complexité de chacun des algorithmes en calculant la fonction C(…) ensuite en utilisant la notation de Landau.  Ecrire les programmes C, permettant d’implémenter chacun des algorithmes décrits ci- dessus, pour chacun d’eux il faudra implémenter la technique de cryptage et de décryptage, pour les textes on utilisera des chaînes de caractères (ne pas utiliser de chaîne intermédiaire pour les transformations)  L’interface de l’application devra se présenter sous forme d’un menu à choix multiples où l’utilisateur pourra sélectionner une des techniques programmées.  Proposer et implémenter un autre algorithme de cryptage. 1. Algorithme de Cesar 2. Carré de 25 6. OU exclusif 7. Autre algorithme 8. Quitter 4 S. BOUKHEDOUMA Travail à remettre Un compte rendu du travail réalisé doit comporter trois parties: Dans un fichier Word (.docx ou .doc) - Partie I : Les procédures/fonctions demandées (avec des commentaires) ainsi que l’algorithme principal. - Partie II : Un jeu de test de différentes exécutions (5 opérations au choix) avec des captures d’écran de résultats affichés. NB : Il est important de bien présenter les saisies et les affichages à l’écran. Dans un fichier WordPad - Partie III : Le code source (commenté) des différentes fonctions écrites en langage C NB : les noms de fichiers doivent comporter les noms des étudiants Important o Le travail doit être fait par binôme (ou monôme) o Les noms des étudiants et le titre du TP doivent être indiqués avant le début du programme et sur la couverture du compte rendu. o La date de remise du travail est fixée pour le 15/11/2018. o Le travail doit être envoyé à l’adresse électronique RecupSpace@gmail.com en précisant l’objet : DevoirAlgo- <noms-des-étudiants> o Aucun retard ne sera toléré par rapport à la date d’envoi du travail o Les cas de copiage seront sévèrement sanctionnés uploads/S4/ devoiralgo-2018.pdf