Zhentao Li's Homepage

email: firstname.lastname@ens.fr

 // home


Programmes vus en TP: q1.py q2.py q3.py

Exemple de programme pour le tri

Exercice - La crypto c'est rigolo

Cryptographie

  1. Dans un interpréteur Python créez la chaîne de caractères message contenant la valeur 'ceci est mon message a chiffrer'. A l'aide d'une boucle for sur cette chaîne, chiffrer la par un décalage de 3 (chiffre de César). Par exemple la lettre a sera chiffrée en la lettre d (et la lettre x en la lettre a).

    >>> message = 'ceci est mon message a chiffrer'
    >>> 
    >>> def decalage(caractere, valeur):
    ...     indice = ord(caractere) - ord('a')
    ...     nouvel_indice = (indice + valeur) % 26
    ...     return chr(nouvel_indice + ord('a'))
    ... 
    >>> chiffre=''
    >>> for lettre in message.lower():
    ...     if lettre.isalpha():
    ...         chiffre = chiffre + decalage(lettre, 3)
    ...     else:
    ...         chiffre = chiffre + lettre
    ... 
    >>> print chiffre
    fhfl hvw prq phvvdjh d fkliiuhu

    Visualiser l'exécution

  2. Écrire un script Python qui chiffre (ou déchiffre selon le choix de l'utilisateur) une chaîne de caractères entrée au clavier avec une clé (i.e.un décalage) choisi aussi par l'utilisateur. On définira les fonctions chiffrer et dechiffrer.

    def decalage(caractere, valeur):
        indice = ord(caractere) - ord('a')
        nouvel_indice = (indice + valeur) % 26
        return chr(nouvel_indice + ord('a'))
    
    def chiffrer(texte, cle):
        chiffre = ''
    
        for lettre in texte.lower():
            if lettre.isalpha():
                chiffre = chiffre + decalage(lettre, cle)
            else:
                chiffre = chiffre + lettre
        return chiffre
    
    def dechiffrer(texte, cle):
        return chiffrer(texte, 26-cle)
    
    message = raw_input("Entrer le texte a chiffrer/dechiffrer : ")
    cle = int(raw_input("Entrer le decalage (0 a 26) : "))
    operation = raw_input("Entrer 'c' pour chiffrer ou 'd' pour dechiffrer : ")
    
    if operation == 'c':
        print chiffrer(message, cle)
    elif operation == 'd':
        print dechiffrer(message, cle)
    else:
        raise Exception("Operation '%s' inconnue" % operation)

    Visualiser l'exécution

  3. Modifier le script précédent pour qu'il utilise la méthode de chiffrement de Vigenère : la clé est désormais une chaîne de caractères et le chiffrement se fait en décalant la i-ème lettre du message gràce à la i-ème lettre de la clé (on reprend au début de la clef quand on a fini de lire celle-ci) suivant la règle naturelle A=1,B=2,...,Z=26(=0).

    def decalage(caractere, valeur):
        indice = ord(caractere) - ord('a')
        nouvel_indice = (indice + valeur) % 26
        return chr(nouvel_indice + ord('a'))
    
    def chiffrer(texte, cle, mode):
        chiffre=''
    
        i = 0
        for lettre in texte.lower():
            if lettre.isalpha():
                clei = ord(cle[i]) - ord('a') + 1
                if mode == 'd':
                    clei = 26 - clei
                chiffre = chiffre + decalage(lettre, clei)
            else:
                chiffre = chiffre + lettre
            i = (i+1) % len(cle)
        return chiffre
    
    def alpha(cle):
        cle_alpha = ""
        for lettre in cle:
            if lettre.isalpha():
                cle_alpha += lettre.lower()
        return cle_alpha
    
    message = raw_input("Entrer le texte a chiffrer/dechiffrer : ")
    cle = raw_input("Entrer la cle : ")
    operation = raw_input("Entrer 'c' pour chiffrer ou 'd' pour dechiffrer : ")
    
    cle_alpha = alpha(cle)
    
    print chiffrer(message, cle_alpha, operation)
    
    nom_fichier = "Poe.txt"
    contenu_fichier = open(nom_fichier).read()
  4. Modifier le script précédent pour qu'il chiffre/déchiffre un fichier dont le chemin est entré par l'utilisateur. On pourra utiliser cette nouvelle de Edgar Poe pour tester le script.

    Pour obtenir le contenu d'un fichier a partir de son nom, vous pouvez utiliser. Nous verrons plus en détail les fonctions reliés aux fichiers au prochain cours.

    nom_fichier = "Poe.txt"
    contenu_fichier = open(nom_fichier).read()
    def decalage(caractere, valeur):
        indice = ord(caractere) - ord('a')
        nouvel_indice = (indice + valeur) % 26
        return chr(nouvel_indice + ord('a'))
    
    def chiffrer(texte, cle, mode):
        chiffre=''
    
        i = 0
        for lettre in texte.lower():
            if lettre.isalpha():
                clei = ord(cle[i]) - ord('a') + 1
                if mode == 'd':
                    clei = 26 - clei
                chiffre = chiffre + decalage(lettre, clei)
            else:
                chiffre = chiffre + lettre
            i = (i+1) % len(cle)
        return chiffre
    
    def alpha(cle):
        cle_alpha = ""
        for lettre in cle:
            if lettre.isalpha():
                cle_alpha += lettre.lower()
        return cle_alpha
    
    message = raw_input("Entrer le texte a chiffrer/dechiffrer : ")
    nom_fichier = raw_input("Entrer le nom du fichier cle : ")
    cle = open(nom_fichier).read()
    operation = raw_input("Entrer 'c' pour chiffrer ou 'd' pour dechiffrer : ")
    
    cle_alpha = alpha(cle)
    
    print chiffrer(message, cle_alpha, operation)

Cryptanalyse

Comme expliqué dans la nouvelle de E. Poe, les chiffrements par substitution alphabétique peuvent être casser facilement par une analyse fréquentielle. Par exemple, dans un texte écrit en langue française, la lettre la plus fréquente est généralement le "E" et puisqu'un chiffrement de César ne modifie pas les fréquences, la lettre qui apparaît le plus fréquemment dans le texte chiffré correspond vraisemblablement à "E" et si c'est le cas le décalage entre les deux lettres donne la clé et permet de retrouver l'intégralité du message clair.

  1. Écrire une fonction Python qui prenant en entrée une chaîne de caractères (ou un fichier texte) affiche la fréquence des caractères qui le composent.

  2. Modifier le programme précédent pour qu'il affiche la lettre qui apparaît le plus de fois.

    nom_fichier = raw_input("Entrer le nom du fichier : ")
    texte = open(nom_fichier).read()
    compteur = [0] * 26
    
    for lettre in texte.lower():
        if lettre.isalpha():
            compteur[ord(lettre) - ord('a')] += 1
    
    indice_max = 0
    for indice in range(26):
        print "'%s' apparait %s fois" % (chr(indice+ord('a')), compteur[indice])
        if (compteur[indice] > compteur[indice_max]): 
            indice_max = indice
    
    print "'%s' apparait le plus de fois" % chr(indice_max+ord('a'))
  3. Utiliser cette fonction pour créer une fonction qui prend en entrée un texte chiffré avec le chiffrement de César (mais pas la clé) et retourne un texte clair associé. On pourra demander à l'utilisateur de valider que ce texte est correct (et si ce n'est pas le cas proposer un nouveau texte clair probable).

    def decalage(caractere, valeur):
        indice = ord(caractere) - ord('a')
        nouvel_indice = (indice + valeur) % 26
        return chr(nouvel_indice + ord('a'))
    
    def chiffrer(texte, cle):
        chiffre=''
    
        for lettre in texte.lower():
            if lettre.isalpha():
                chiffre = chiffre + decalage(lettre, cle)
            else:
                chiffre = chiffre + lettre
        return chiffre
    
    def dechiffrer(texte, cle):
        return chiffrer(texte, 26-cle)
    
    def compte_lettres(texte):
        compteur = [0] * 26
        for lettre in texte.lower():
            if lettre.isalpha():
                compteur[ord(lettre) - ord('a')] += 1
    
        indice_max = 0
        for indice in range(26):
            if (compteur[indice] > compteur[indice_max]): 
                indice_max = indice
    
        return (compteur, indice_max)
    
    nom_fichier = raw_input("Entrer le nom du fichier : ")
    texte = open(nom_fichier).read()
    compteur, indice_max = compte_lettres(texte)
    
    indice_e = 4
    for indice in range(indice_max, 26) + range(0, indice_max):
        cle = (indice - indice_e) % 26
        print dechiffrer(texte, cle)
        print "Cle : %s" % cle
        verification = raw_input("Est-ce que ce texte semble etre le texte decrypte? Entrer 'o'ui ou 'n'on : ")
        if verification == "o" or verification == 'oui':
            break

    Exemple de lancement, supposant que nous avons écrit un message chiffré dans le fichier chiffre.

    $ cat chiffre
    fhfl hvw xq phvvdjh d fkliiuhu
    $ python dechiffreur-auto.py
    Entrer le nom du fichier : chiffre
    ceci est un message a chiffrer
    
    Cle : 3
    Est-ce que ce texte semble etre le texte decrypte? Entrer 'o'ui ou 'n'on : o
  4. **L'encyclopédie Wikipedia propose un article expliquant une méthode de cryptanalyse du chiffrement de Vigenère reposant sur les mêmes principes. Écrire une fonction Python qui prend un entrée un texte chiffré avec le chiffrement de Vigenère (mais pas la clé) et retourne un texte clair associé possible.


Website design modified from Sliqua taken from OSWD