Chiffre de César

  On étudie dans ce TD le chiffre de César, ainsi appelé parce que Jules César l'aurait utilisé.

I) Cryptographie, chiffrage

1) Cryptographie

  La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de clés.   Son objectif est de rendre un message ou un fichier inintelligible à tout autre que qui-de-droit.
  Lorsque le message est un fichier informatique, on dit chiffrer au lieu de crypter.

2) Chiffrer, déchiffrer

  Chiffrer un fichier "en clair" F1 c'est le transformer, avec une clé de chiffrage, en un fichier "incompréhensible" F2.
Déchiffrer ce fichier F2 c'est, avec une clé de déchiffrage, le ramener à F1. Cette seconde clé peut être connue (si on est le destinataire du texte) ou "découverte" (si on a intercepté le fichier F2 avec de mauvaises intentions et si on est suffisamment doué...).

3) Principaux systèmes de chiffrement (Wikipédia)

Un système de chiffrement est dit :
    (1) symétrique quand il utilise la même clé pour chiffrer et déchiffrer.
    (2) asymétrique quand il utilise des clés différentes : une paire composée d'une clé publique, servant au chiffrement, et d'une clé privée, servant à déchiffrer. Le point fondamental soutenant cette décomposition publique/privée est l'impossibilité calculatoire de déduire la clé privée de la clé publique.

  Les méthodes les plus connues sont le DES, le triple DES et l'AES pour le chiffrement symétrique, et le RSA pour le chiffrement asymétrique, aussi appelé chiffrement à clé publique.

  L'utilisation d'un système symétrique ou asymétrique dépend des tâches à accomplir. La cryptographie asymétrique présente deux intérêts majeurs : elle supprime le problème de transmission sécurisée de la clé, et elle permet la signature électronique. Elle ne remplace cependant pas les systèmes symétriques car ses temps de calcul sont nettement plus longs et la cryptographie asymétrique est de par sa nature même plus vulnérable.

II) Chiffre de César

  C'est un système de chiffrage par simple décalage.

  Un fichier T est ici une suite d'octets de {0,...,255}.  Le chiffre de César est un système (très simple) de chiffrement symétique par translation. La clé est un entier C .
  On notera f C : { 0 , ... , 255 } { 0 , ... , 255 } l'application définie par f C ( n ) = n + C [ 256 ] ( f C est la translation de C modulo 256).  Le chiffrage du fichier T = [ t [ 0 ] , ... , t [ n - 1 ] ] avec la clé C est le fichier T ' = f C ( T ) = [ f C ( t [ 0 ] ) , ... , f C ( t [ n - 1 ] ) ] .
  Pour déchiffrer un texte T ' chiffré avec la clé C , il suffit de translater en sens inverse: T = f - C ( T ' )

Par exemple, Si T = [10, 100, 200] et C = 150, alors T' = [160, 250, 94] car 94 = 350 [256]

III) Lecture et écriture d'un fichier

  Un fichier informatique est une suite ordonnée d'octets enregistré sur un support. Pour travailler plus lisiblement ces octets seront convertis en entiers de {0,1,...,255}. Les entiers de {0,...,255} seront souvent dans la suite appelés des octets.

On donne les fonctions suivantes:

# -*- coding: UTF-8 -*
import os                    # Module contenant des fonctions utiles

##print(os.getcwd())        # Affiche le répertoire courant de travail
# Pour Changer (s'il le faut) le répertoire courant de travail, on utilise os.chdir()
# Par exemple:
##os.chdir(“C:/Users/Eric/Documents/Algorithmique/2013 Informatique Exercices/Fichiers”)

def lire_fichier(nom_fichier):
    """ Liste d'octets contenus dans fichier appelé nom_fichier convertis en
    une liste d'entiers de {0,...,255}"""
    with open(nom_fichier, "rb") as fich:   # Ouverture en lecture de fichier
         octets = fich.read()              # lecture du contenu de fichier
    return list(octets)                    # Conversion en une liste d'entiers

def enregistrer_fichier(nom_fichier, contenu):
    """Enregistrement du contenu dans le fichier appelé nom_fichier.
    contenu est une liste d'entiers de {0,...,255} qui est convertie en octets
    avant l'enregistrement"""
    octets = bytes(contenu)                # Conversion en liste d'octets
    with open(nom_fichier, "wb") as fich:  # Ouverture en écriture du fichier
        fich.write(octets)                 # Enregistrement

def conversion_vers_octets(mot):
    """ Conversion de la chaîne de caractères mot en une liste d'entiers de
    {0,...,255}.  mbcs est la norme d'encodage par défaut de Windows"""
    return  list(bytes(mot, "mbcs"))

def conversion_vers_mot(octets):
    """ Conversion de la liste d'entiers de {0,...,255} vers une chaîne de
     caractères. mbcs est la norme d'encodage par défaut de Windows"""
    return str(bytes(octets),  encoding='mbcs')

Un fichier est dans la suite une liste d'entiers (d'octets) de {0,...,255}. Les fonctions données ci-dessus permettent de travailler avec des vrais fichiers informatiques.

  Les fichiers de données pour le chiffre de César sont disponibles dansce répertoire

IV) Algorithmes de chiffrage et de déchiffrage en connaissant la clé

Q1) Ecrire une fonction f(n, c) (avec  n ∈ Z et c ∈ N * ) telle que f(n, c) = n + c [256]
Par exemple, f(200, 150) = 94  et f(-50, 33) = 239

Q2) Ecrire une fonction chiffrer(T, c) chiffrant la liste d'entiers T avec la clé c (un entier) avec le chiffre de César.

Q3) Ecrire une fonction chiffrer_fichier(nom_fichier, c) chiffrant le fichier nommé nom_fichier avec la clé c (un entier) avec le chiffre de César et l'enregistrant sous le nom cc_nom_fichier.

Q4) Ecrire une fonction dechiffrer_fichier(nom_fichier, c) déchiffrant le fichier nommé nom_fichier ayant été chiffré avec la clé c (c ∈ N * ) avec le chiffre de César et l'enregistrant sous le nom dc_nom_fichier.

Q5) Faire des essais de chiffrage et déchiffrage avec le fichier perrette.txt, dans le répertoire Cesar. Constater par exemple que si l'on exécute:

chiffrer_fichier("perrette.txt", 99)
dechiffrer_fichier("cc_perrette.txt", 99)

alors le fichier dc_cc_perrette.txt est identique au fichier perrete.txt.

V) Algorithme de déchiffrage sans connaître la clé

  On veut déchiffrer un fichier chiffré par l'algorithme de César, mais dont on ne connait pas la clé.
  Comme il y a 256 clés possibles, une première éventualité (un peu brutale...) est de le déchiffrer avec les 256 clés et de chercher celui qui veut dire quelque chose dans le lot.

Q6) Ecrire une fonction dechiffrage_brutal(nom_fichier) affichant les 256 déchiffrages possibles du fichier nommé nom_fichier. On utilisera la fonction conversion_vers_mot(octets) pour voir le contenu du fichier en clair.
Déchiffrer les fichier cesar1.txt,  cesar2.txt,  cesar3.txt.

  Une façon plus délicate de déchiffrer le fichier est de repérer l'octet le plus fréquent N et de se dire qu'il est probablement associé à un espace (octet 32) ou à un e (octet 101). La clé de chiffrage est alors C = N - 32 [256] ou C = N - 101 [256].
En effet en français, la fréquence moyenne d'apparition de l'espace est de 17 %, celle du e est de 14 %. Ensuite on trouve le s avec 7 %, etc...

Q7) Ecrire une fonction frequence_max(T) (avec T liste d'octets) calculant l'entier N le plus fréquent de la liste T. Le coût de cette fonction doit être en O(nT), avec nT la longueur de T.

Q8) Ecrire une fonction dechiffrage_delicat(nom_fichier, car) déchiffrant le fichier chiffré par l'algorithme de César et nommé nom_fichier en postulant que le caractère le plus fréquent est car (du type str)  (en pratique, commencer par car = “ ” , puis car = “e”, etc...). Le fichier déchiffré doit être enregistré sous le nom dcd_nomfichier .
L'octet correspondant au carctère car est ord(car).
Déchiffrer les fichiers cesar3.txt,  cesar4.txt,  cesar5.txt.

  Cette méthode de déchiffrement peut aussi fonctionner avec des fichiers qui ne sont pas des fichiers textes, mais qui contiennent beaucoup de texte écrit en français.

Q9) Déchiffrer le fichier cesar6.pdf .

© 2015 - Eric Obermeyer      Powered by      Corrigé