Aller au contenu

Exercices d'entraînement☘

Ces exercices doivent être utilisés pour vous entraîner à programmer. Ils sont généralement accompagnés d'aide et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

  • Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
  • Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
  • Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
  • Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
  • Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?
Rappels
  • Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
    Enregistrez ce fichier dans le dossier [C03-Securisation] avec le nom donné à l'exercice : ProgC03.51.py, ProgC03.52.py, etc...
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].
  • Le programme principal doit contenir un appel au module doctest : 
    ##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Jeux sérieux

Le concours Alkindi permet de s'initier et s'exercer à la cryptographie.

ProgC03.51 - Chiffrement de César☘

Vous allez appliquer le chiffrement de César à des messages constitués uniquement de lettres majuscules. Pour cela, vous vous réfèrerez uniquement à la chaîne alphabet définie en constante globale du programme.
En d'autres termes, l'usage des fonctions chr() et ord() n'est pas autorisé.

Copiez, collez et complétez la définition de la fonction crypt_cesar() en respectant ses spécifications.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def crypt_cesar(message, clef):
    """
    message - str, chaîne de caractères dont les lettres sont en majuscules
    clef - int, entier correspondant au décalage
    Sortie: str - chaîne de caractères cryptée selon l'algorithme de César
             avec un décalage de valeur clef
    >>> crypt_cesar("OK POUR CESAR ALLONS PLUS LOIN", -3)
    'LH MLRO ZBPXO XIILKP MIRP ILFK'
    >>> crypt_cesar("LH MLRO ZBPXO XIILKP MIRP ILFK", 3)
    'OK POUR CESAR ALLONS PLUS LOIN'
    """
Une piste

Vous pouvez effectuer un pré-traitement en associant à chaque lettre majuscule la lettre correspondante après le décalage.

Une solution
 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
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def crypt_cesar(message, clef):
    """
    message - str, chaîne de caractères dont les lettres sont en majuscules
    clef - int, entier correspondant au décalage
    Sortie: str - chaîne de caractères cryptée selon l'algorithme de César
             avec un décalage de valeur clef
    >>> crypt_cesar("OK POUR CESAR ALLONS PLUS LOIN", -3)
    'LH MLRO ZBPXO XIILKP MIRP ILFK'
    >>> crypt_cesar("LH MLRO ZBPXO XIILKP MIRP ILFK", 3)
    'OK POUR CESAR ALLONS PLUS LOIN'
    """
    n = len(alphabet)
    associe = {}
    for i in range(n):
        associe[alphabet[i]] = alphabet[(i+clef)%n]
    crypt = ""
    for lettre in message:
        if lettre in alphabet:
            crypt += associe[lettre]
        else:
            crypt += lettre
    return crypt

if __name__ == '__main__':
    import doctest
    doctest.testmod()

ProgC03.52 - Algorithme d'Euclide étendu☘

  1. Sur votre cahier, recherchez deux entiers u et v tels que 287 u + 29 v = 1.

  2. À partir de l'exercice réalisé en TD, complétez la définition de la fonction euclide_etendu() qui prend en paramètres deux entiers a et b. Cette fonction renvoie un triplet d'entiers (r, u, v) tels que :

    • r est le PGCD de a et b ;
    • u et v sont deux entiers tels que a*u + b*v = r
    1
2
3
4
5
6
7
8
    def euclide_etendu(a, b):
    """
    a, b - int, entiers strictement positifs
    Sortie: tuple - Triplet d'entiers (r, u, v) tels que
            r = pgcd(a, b) et a*u + b*v = r.
    >>> euclide_etendu(287, 29)
    (1, -10, 99)
    """
    Une solution

    Voici un exemple utilisant des dictionnaires, ce qui n'est pas nécessaire mais peut clarifier l'algorithme pour certains.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    def euclide_etendu(a, b):
    """
    a, b - int, entiers strictement positifs
    Sortie: tuple - Triplet d'entiers (r, u, v) tels que
            r = pgcd(a, b) et a*u + b*v = r.
    >>> euclide_etendu(287, 29)
    (1, -10, 99)
    """
    L1 = {'r': a, 'u': 1, 'v': 0}
    L2 = {'r': b, 'u': 0, 'v': 1}
    while L2['r'] != 0:
        q = L1['r']//L2['r']
        r = L1['r']-q*L2['r']
        u = L1['u']-q*L2['u']
        v = L1['v']-q*L2['v']
        L1['r'], L2['r'] = L2['r'], r
        L1['u'], L2['u'] = L2['u'], u
        L1['v'], L2['v'] = L2['v'], v
    return L1['r'], L1['u'], L1['v']

  3. Proposez une version récursive de la fonction précédente :

    1
2
3
4
5
6
7
8
9
    def euclide_etendu_rec(a, b, u0=1, u1=0, v0=0, v1=1):
    """
    a, b - int, entiers strictement positifs
    u0, u1, v0, v1 - int
    Sortie: tuple - Triplet d'entiers (r, u, v) tels que
            r = pgcd(a, b) et a*u + b*v = r.
    >>> euclide_etendu_rec(287, 29)
    (1, -10, 99)
    """
    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    def euclide_etendu_rec(a, b, u0=1, u1=0, v0=0, v1=1):
    """
    a, b - int, entiers strictement positifs
    u0, u1, v0, v1 - int
    Sortie: tuple - Triplet d'entiers (r, u, v) tels que
            r = pgcd(a, b) et a*u + b*v = r.
    >>> euclide_etendu_rec(287, 29)
    (1, -10, 99)
    """
    if b == 0:
        return a, u0, v0
    else:
        q = a//b
        r = a%b
        return euclide_etendu_rec(b, r, u1, u0-q*u1, v1, v0-q*v1)

ProgC03.53 - Chiffrement symétrique ECB☘

Pour renforcer les algorithmes de chiffrement symétrique, on peut utiliser le mode opératoire ECB (Electronic CodeBook) : le message est découpé en blocs puis on utilise l'algorithme de chiffrement sur chaque bloc.

Chiffrement par permutation☘

Une permutation peut-être représentée par un tableau contenant les n entiers de 0 à n-1. L'élément de valeur j et d'indice i sera ainsi placé à l'indice j après la permutation.

Exemple

Le tableau permut = [2, 0, 3, 1] signifie que, pour un bloc de taille 4 :

  • l'élément d'indice 0 ira à l'indice 2 ;
  • l'élément d'indice 1 ira à l'indice 0 ;
  • etc...

  1. On considère le bloc LISE de taille 4.
    Quel bloc obtient-on après application de la permutation représentée par le tableau permut = [2, 0, 3, 1] ?

    Une réponse

    On obtient le bloc IELS.

  2. Comment retrouver le bloc initial ?

    Une réponse

    En appliquant la permutation réciproque, c'est-à-dire la permutation représentée parle tableau permut_rec = [1, 3, 0, 2].

  3. Copiez, collez et complétez la définition de la fonction creer_permut() en respectant ses spécifications.

    1
2
3
4
5
    def creer_permut(n):
    """
    n - int, entier strictement positif
    Sortie: list - tableau contenant les entiers de 0 à n-1 permutés aléatoirement
    """

    Exemple de test

    >>> creer_permut(7)
[1, 3, 0, 4, 5, 2, 6]

>>> creer_permut(7)
[6, 4, 1, 0, 2, 5, 3]

>>> creer_permut(7)
[5, 2, 3, 6, 0, 1, 4]
    Une piste

    Pensez à importer un module permettant de simuler du hasard...

    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
    from random import shuffle

def creer_permut(n):
    """
    n - int, entier strictement positif
    Sortie: list - tableau contenant les entiers de 0 à n-1 permutés aléatoirement
    """
    tab = [i for i in range(n)]
    shuffle(tab)
    return tab

  4. Copiez, collez et complétez la définition de la fonction creer_permut_inverse() en respectant ses spécifications.

    1
2
3
4
5
6
7
8
9
    def creer_permut_inverse(tab):
    """
    tab - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: list - tableau correspondant à la permutation réciproque
    >>> permut = [2, 0, 3, 1]
    >>> depermut = creer_permut_inverse(permut)
    >>> depermut
    [1, 3, 0, 2]
    """

    Exemple de test

    >>> permut = creer_permut(7)
>>> permut
[4, 1, 0, 3, 5, 6, 2]

>>> creer_permut_inverse(permut)
[2, 1, 6, 3, 0, 4, 5]
    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def creer_permut_inverse(tab):
    """
    tab - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: list - tableau correspondant à la permutation réciproque
    >>> permut = [2, 0, 3, 1]
    >>> depermut = creer_permut_inverse(permut)
    >>> depermut
    [1, 3, 0, 2]
    """
    result = [0 for i in range(len(tab))]
    for i in range(len(tab)):
        result[tab[i]] = i
    return result

  5. Copiez, collez et complétez la définition de la fonction permut_bloc() en respectant ses spécifications.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def permut_bloc(permut, bloc):
    """
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    bloc - list, tableau contenant n, où n est la taille de permut 
    Sortie: list - tableau contenant les mêmes éléments que bloc, mais permutés
            selon la permutation représentée par permut
    >>> permut = [2, 0, 3, 1]
    >>> bloc = ['L', 'I', 'S', 'E']
    >>> permut_bloc(permut, bloc)
    ['I', 'E', 'L', 'S']
    """

    Exemple de test

    Attention de bien lever l'erreur d'assertion : 

    >>> permut = [2, 0, 3, 1]
>>> bloc = ['I', 'E', 'L', 'S']
>>> depermut = creer_permut_inverse(permut)
>>> depermut
[1, 3, 0, 2]

>>> permut_bloc(depermut, bloc)
['L', 'I', 'S', 'E']

>>> permut_bloc([2, 1, 6, 3, 0, 4, 5], ['L', 'I', 'S', 'E'])
AssertionError: Les deux tableaux n'ont pas la même taille

    Une piste

    Vous pouvez initialiser un « tableau de None ».

    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    def permut_bloc(permut, bloc):
    """
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    bloc - list, tableau contenant n, où n est la taille de permut 
    Sortie: list - tableau contenant les mêmes éléments que bloc, mais permutés
            selon la permutation représentée par permut
    >>> permut = [2, 0, 3, 1]
    >>> bloc = ['L', 'I', 'S', 'E']
    >>> permut_bloc(permut, bloc)
    ['I', 'E', 'L', 'S']
    """
    assert len(bloc) == len(permut), "Les deux tableaux n'ont pas la même taille"
    result = [None for i in range(len(permut))]
    for i in range(len(permut)):
        result[permut[i]] = bloc[i]
    return result

Chiffrement ECB☘

  1. Copiez, collez et complétez la définition de la fonction decoupe_en_blocs() en respectant ses spécifications.

    1
2
3
4
5
6
7
8
    def decoupe_en_blocs(message, n):
    """
    message - str, le message à découper en blocs
    n - int, entier strictement positif - longueur d'un bloc
    Sortie: list - tableau de chaînes de caractères de taille n,
            éventuellement complétées par un caractère aléatoire de code décimal
            ASCII compris entre 32 et 126 ou entre 161 et 255 (92 et 173 exclus).
    """

    Exemple de test

    >>> message = "Ceci est un exemple !"
>>> decoupe_en_blocs(message, 5)
['Ceci ', 'est u', 'n exe', 'mple ', '!+4d7']

>>> decoupe_en_blocs(message, 5)
['Ceci ', 'est u', 'n exe', 'mple ', '!kY3|']
    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    def decoupe_en_blocs(message, n):
    """
    message - str, le message à découper en blocs
    n - int, entier strictement positif - longueur d'un bloc
    Sortie: list - tableau de chaînes de caractères de taille n,
            éventuellement complétées par un caractère aléatoire de code décimal
            ASCII compris entre 32 et 126 (92 exclus).
    """
    result = []
    for i in range(0, len(message), n):
        temp = ""
        for k in range(n):
            if i+k < len(message):
                temp += message[i+k]
            else:
                code = randint(32, 126)
                while code == 92:
                    code = randint(32, 126)
                temp += chr(code)
        result.append(temp)
    return result

  2. Copiez, collez et complétez la définition de la fonction permute_chaque_bloc() en respectant ses spécifications.
    Cette fonction devra lever une assertion si la longueur des blocs ne correspond pas à la longueur de la permutation (cf. exemple).

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def permute_chaque_bloc(tab, permut):
    """
    tab - list, tableau de chaînes de caractères de taille n
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: list - tableau contenant les éléments de tab.
            Chaque chaîne de caractères voit caractères mélangés selon la
            permutation représentée par permut
    >>> tab = ['Ceci ', 'est u', 'n exe', 'mple ', '!+4d7']
    >>> permute_chaque_bloc(tab, [2, 4, 0, 3, 1])
    ['c Cie', 'tue s', 'eenx ', 'l mep', '47!d+']
    """

    Exemple de test

    >>> tab = ['Ceci ', 'est u', 'n exe', 'mple ', '!+4d7']
>>> permute_chaque_bloc(tab, [2, 0, 3, 1])
AssertionError: La longueur des chaînes ne correspond pas à la longeur de la permutation
    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    def permute_chaque_bloc(tab, permut):
    """
    tab - list, tableau de chaînes de caractères de taille n
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: list - tableau contenant les éléments de tab.
            Chaque chaîne de caractères voit caractères mélangés selon la
            permutation représentée par permut
    >>> tab = ['Ceci ', 'est u', 'n exe', 'mple ', '!+4d7']
    >>> permute_chaque_bloc(tab, [2, 4, 0, 3, 1])
    ['c Cie', 'tue s', 'eenx ', 'l mep', '47!d+']
    """
    assert len(tab[0]) == len(permut), "La longueur des chaînes ne correspond pas à la longeur de la permutation"
    result = []
    for mot in tab:
        temp = list(mot)
        temp = permut_bloc(permut, temp)
        mot = ""
        for carac in temp:
            mot += carac
        result.append(mot)
    return result

  3. Copiez, collez et complétez la définition de la fonction crypte_ECB() en faisant appel aux fonctions précédentes et en respectant ses spécifications.

    1
2
3
4
5
    def crypte_ECB(message, permut):
    """
    message - str, le message à découper en blocs
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: str - message crypté par le chiffrement ECB

    Exemple de test

    >>> message = "Ceci est un exemple !"
>>> crypte_ECB(message, [2, 4, 0, 3, 1])
'c Cietue seenx l mep32!1H'
    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def crypte_ECB(message, permut):
    """
    message - str, le message à découper en blocs
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: str - message crypté par le chiffrement ECB
    """
    n = len(permut)
    tab = decoupe_en_blocs(message, n)
    tab_crypte = permute_chaque_bloc(tab, permut)
    message_crypte = ""
    for mot in tab_crypte:
        message_crypte += mot
    return message_crypte

  4. Copiez, collez et complétez la définition de la fonction decrypte_ECB() en faisant appel aux fonctions précédentes et en respectant ses spécifications.

    1
2
3
4
5
6
7
8
9
    def decrypte_ECB(message_crypte, permut):
    """
    message_crypte - str, le message à décrypter
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: str - message décrypté par le déchiffrement ECB
    >>> message_crypte = 'c Cietue seenx l mep32!1H'
    >>> decrypte_ECB(message_crypte, [2, 4, 0, 3, 1])
    'Ceci est un exemple !H312'
    """
    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    def decrypte_ECB(message_crypte, permut):
    """
    message_crypte - str, le message à décrypter
    permut - list, tableau de taille n représentant une permutation des entiers de 0 à n-1
    Sortie: str - message décrypté par le déchiffrement ECB
    >>> message_crypte = 'c Cietue seenx l mep32!1H'
    >>> decrypte_ECB(message_crypte, [2, 4, 0, 3, 1])
    'Ceci est un exemple !H312'
    """
    n = len(permut)
    permut_inverse = creer_permut_inverse(permut)
    tab_crypte = decoupe_en_blocs(message_crypte, n)
    tab_decrypte = permute_chaque_bloc(tab_crypte, permut_inverse)
    message_decrypte = ""
    for mot in tab_decrypte:
        message_decrypte += mot
    return message_decrypte

  5. Vous recevez un message crypté et vous savez que le chiffrement utilisé est ECB. Quelle(s) méthode(s) pourriez-vous utiliser pour décrypter de message ?
    Appelez l'enseignant pour lui faire part de cette méthode avant de vous précipiter sur la solution...

    Une réponse

    1. On commence par déterminer la longueur de la permutation qui est un diviseur de la longueur du message.

    2. Pour chaque longueur possible, on extrait les deux ou trois premiers blocs de même longueur dans le message et on leur applique chacune des permutations possibles pour cette longueur.

Pour aller plus loin☘

On considère un message comportant des caractères aléatoires dont la représentation ASCII décimale est comprise entre 32 et 126.

Convertissez en premier lieu chaque caractère de ce message par l'octet correspondant (chaîne de '0' et de '1') puis appliquez les fonctions de cryptage et décryptage à cette chaîne de bits plutôt qu'à la chaîne de caractères.