Archi Chiffrement

Identification

Infoforall

14 - Chiffrement symétrique


Nous avons vu que le Web utilise principalement deux protocoles :

  1. le protocole HTTP où les paquets IP transitent de routeurs en routeurs en clair. N'importe qui possédant des droits sur les routeurs peut lire la communication s'il en a envie. Pas terrible pour les transmissions sensibles comme les mots de passe ou les numéros de carte bancaire.
  2. le protocole HTTPS où les paquets IP transitent de routeurs en routeurs en étant chiffrés("cryptés"). Cette fois, même en étant interceptés, les paquets IP ne peuvent pas être compris. Ils peuvent être lus mais le contenu semblera totalement aléatoire et incompréhensible.

Dans cette partie, nous allons nous intéresser à ces techniques de chiffrement.

Evaluation ✎ : -

Documents de cours PDF : .PDF

Sources latex : .TEX, entete.tex et licence.tex

1 - Le code de César

Le code de César n'est plus utilisé pour chiffrer (ou "crypter") les communications. Il est beaucoup trop simple à déchiffrer une fois qu'on connaît le principe.

Cette technique est basée sur un simple décalage des lettres.

Par exemple, on décale les lettres de 1 position vers la droite.

A devient B, B devient C... jusqu'à Z qui devient ... A.

Pourquoi César ?

César aurait utilisé un tel chiffrement pour sa correspondance.

Il utilisait un décalage de 3 lettres vers la droite en utilisant l'alphabet ... grec. Deux niveaux de difficultés pour les gens qui cherchaient à intercepter ses courriers.

Appliqué à notre alphabet, le décalage de 3 lettres donne ceci :

César

Commençons par voir comment nous pourrions décaler les lettres simplement avec un tableau contenant notre séquence de lettres.

01° Créer la fonction trouve_indice() qui renvoie l'indice de l'élément recherché dans le type construit fourni (un tableau, un tuple, un string). Si plusieurs éléments identiques se trouvent dans le tableau, on renvoie le plus petit. Si l'élément n'est pas présent, la fonction renvoie None.

Voici le prototype :

1
trouve_indice(element:str, sequence:str|list|tuple) -> int|None

Exemple avec le tableau ALPHABET que vous pouvez visualiser en ligne 1.

>>> trouve_indice('A', ALPHABET) 0 >>> trouve_indice('B', ALPHABET) 1

Principe de l'algorithme : pour chaque valeur d'indice, lire l'élément correspondant. S'il correspond à l'élement cherché, on renvoie l'indice actuel.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
ALPHABET = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] def trouve_indice(element, sequence): """Renvoie l'indice de element dans l'itérable sequence :: param element(str) :: l'élément qu'on cherche à trouver :: param sequence(str|list|tuple) :: un itérable contenant des éléments :: return (int|None) :: l'indice de l'élément (ou None) >>> lettres = ['A', 'B', 'C', 'D', 'E', 'F'] >>> trouve_indice('A', lettres) 0 >>> trouve_indice('C', lettres) 2 >>> trouve_indice('Z', lettres) """ pass if __name__ == '__main__': import doctest doctest.testmod()

Notez bien que dans le dernier exemple, la lettre Z n'apparaît pas dans la variable lettres. C'est pour cela que la fonction ne renvoie rien.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
ALPHABET = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] def trouve_indice(element, sequence): """Renvoie l'indice de element dans l'itérable sequence :: param element(str) :: l'élément qu'on cherche à trouver :: param sequence(str|list|tuple) :: un itérable contenant des éléments :: return (int|None) :: l'indice de l'élément (ou None) >>> lettres = ['A', 'B', 'C', 'D', 'E', 'F'] >>> trouve_indice('A', lettres) 0 >>> trouve_indice('C', lettres) 2 >>> trouve_indice('Z', lettres) """ for i in range(len(sequence)): if sequence[i] == element: return i if __name__ == '__main__': import doctest doctest.testmod()

On utilise un for associé à un return. Algorithmiquement, il aurait fallu plutôt utiliser un while. Mais le for+return rend le code plus intuitif à comprendre.

Voici la version avec un while :

1 2 3 4 5 6 7 8 9 10 11 12 13
ALPHABET = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] def trouve_indice(element:str, sequence:'str|list|tuple') -> 'int|None': """Renvoie l'indice de element dans l'itérable sequence""" i = 0 while i < len(sequence) and sequence[i] != element: # TQ l'indice existe et ne contient pas l'élément voulu i = i + 1 # passe à la case suivante if i < len(sequence): # si le i final est valide return i # si on arrive ici, c'est qu'on a dépassé la dernière case, on renvoie None

Comme la recherche d'un élément dans un tableau est une chose courante et que les tableaux sont des objets en Python, il existe déjà une méthode qui fait ce que nous venons de réaliser... Le but de la NSI est néanmoins de parvenir à construire vos propres fonctions avant d'utiliser trop de "boîtes noires" créées par d'autres personnes. Cette méthode n'est donc pas au programme. Pas plus que remove(), pop(0), sort()...

02° Tester les instructions suivantes pour vous persuader que la méthode des lists index() permet de faire (presque) la même chose que la fonction que nous venons de construire. Attention, ALPHABET devra être en mémoire lors de ce test.

>>> ALPHABET.index('A') 0 >>> ALPHABET.index('B') 1 >>> ALPHABET.index('Z') 25 >>> ALPHABET.index('a')

Questions :

  1. avez-vous trouvé la différence qui existe entre cette façon de faire et la fonction que nous avions conçue ?
  2. (hors programme) Comment pourrions-nous créer la fonction trouve_indice() en utilisant à l'interne la méthode index() ?

...CORRECTION...

La méthode index() déclenche une erreur si l'élément n'existe pas.

1 2 3 4 5 6 7 8 9 10 11
ALPHABET = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] def trouve_indice(element:str, sequence:'str|list|tuple') -> 'int|None': """Renvoie l'indice de element dans l'itérable sequence""" try: # Tente reponse = sequence.index(element) # d'utiliser index() except: # et si cela déclenche une exception reponse = None # affecte reponse avec None return reponse

Une fois qu'on a trouvé l'indice de la lettre dans l'alphabet, il suffit de rajouter la clé et on obtient alors le chiffrement qui remplace cette lettre.

Ainsi avec une clé de 3 et une lettre B : l'indice de B est 1, on lui ajoute 3 et on obtient ainsi l'indice 4. Il suffit de renvoyer la lettre située à cet indice : E.

Comme nous allons toujours travailler à priori avec le tableau constant ALPHABET, j'ai rajouté ,en ligne 1 ci-dessous, cette valeur par défaut à ce paramètre. Cela nous évitera de le fournir à chaque fois.

03° Tester maintenant la fonction decale() qui renvoie une lettre présente dans alphabet en la décalant de cle position vers la droite.

Laissez les variables et fonctions précédentes dans script.

PRECONDITION : l'élément est bien présent dans la séquence.

1 2 3 4 5
def decale(element, cle, sequence=ALPHABET): """Renvoie la lettre chiffrée en décalant de cle case vers la droite (element doit être présent dans sequence)""" indice = trouve_indice(element, sequence) indice_decale = indice + cle return sequence[indice_decale]

Vous pourriez tester des appels comme ceux-ci :

>>> decale(element='A', cle=3) >>> decale(element='B', cle=3) >>> decale(element='C', cle=3) >>> decale(element='W', cle=3) >>> decale(element='X', cle=3)

Qu'est-ce qui provoque l'erreur qui survient parfois ?

...CORRECTION...

La fonction semble bien fonctionner sauf pour X et plus...

Pourquoi ? Simplement car l'indice de X vaut 23. Or 23 + 3 = 26.

Notre tableau n'ayant des indices valides que dans l'intervalle [0, 25], les lettres X, Y et Z provoquent une demande hors indice.

Pour éviter ce problème, il faut parvenir à faire comprendre à la machine qu'après l'indice 25, on veut l'indice 0.

Ainsi, si on obtient l'indice 23 du 'X' et qu'on rajoute 3, on obtient 26 mais on veut en réalité obtenir 0 pour 'A'.

Pour 'Y' (24), on obtient 24+3=27 mais on veut 'B' (indice 1).

Comment faire ? Utiliser le modulo !

Rappel :

>>> 24 % 26 24 >>> 25 % 26 25 >>> 26 % 26 0 >>> 27 % 26 1 >>> 28 % 26 2

04° Modifier decale() pour qu'elle gère bien les recherches dépassant l'indice maximum.

>>> decale(element='W', cle=3) 'Z' >>> decale(element='X', cle=3) 'A' >>> decale(element='Y', cle=3) 'B'

...CORRECTION...

1 2 3 4 5
def decale(element, cle, sequence=ALPHABET): """Renvoie la lettre chiffrant la lettre element en décalant de cle case vers la droite""" indice = trouve_indice(element, sequence) indice_decale = (indice + cle) % len(sequence) return sequence[indice_decale]

Le problème du code de César est qu'il ne gère pas tous les caractères : on ne travaille qu'avec des lettres majuscules non accentuées ou autres. On acceptera certains caractères de ponctuation qu'on ne modifiera pas d'ailleurs.

05° Expliquer de la façon la plus précise possible comment fonctionne la fonction filtre(). On rappelle que le string Python est une structure de données non mutable et qu'on doit donc recréer un string lorsqu'on veut en "modifier" un.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
# Constantes ALPHABET = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] PONCTUATION = [' ', '.', '!', '?', ',', "'", ' '] # Déclaration des fonctions def filtre(message:str) -> str: """Renvoie un string où les lettres sont toutes en majuscules""" message = message.upper() # Méthode des strings qui renvoie les lettres en majuscules reponse = '' # on va créer un string de réponse progressivement : on l'initialise for caractere in message: if caractere in ALPHABET or caractere in PONCTUATION : reponse = reponse + caractere # on ne le garde que s'il fait partie d'un des 2 tableaux return reponse # Instructions du programme principal if __name__ == '__main__': message = "L'épreuve est au mois de mars, vraiment ?"

Expliquer ensuite pourquoi on obtient la réponse suivante en lançant la fonction avec la variable message.

>>> message "L'épreuve est au mois de mars, vraiment ?" >>> mess_filtre = filtre(message) >>> mess_filtre "L'PREUVE EST AU MOIS DE MARS, VRAIMENT ?"

Nous allons maintenant nous intéresser au chiffrement de la chaîne de caractères filtrée qui ne contient donc que des caractères compatibles avec la fonction chiffrement().

Voici le code du projet en l'état. Il reprend les fonctions réalisées plus haut (trouve_indice(), decale() et filtre()) mais rajoute la fonction chiffrement() qui va permettre d'agir sur toute une chaîne de caractères, pas uniquement sur un seul caractère à la fois.

Pour gagner quelques lignes, j'ai décidé d'utiliser la forme de documentation courte pour les trois fonctions déjà étudiées.

06° Mettre le code ci-dessous en mémoire. Utiliser les instructions suivantes pour visualiser son fonctionnement.

>>> message "L'épreuve est au mois de mars, vraiment ?" >>> message = filtre(message) >>> message "L'PREUVE EST AU MOIS DE MARS, VRAIMENT ?" >>> mc = chiffrement(message, 3) >>> mc "O'SUHXYH HVW DX PRLV GH PDUV, YUDLPHQW ?" >>> mc = chiffrement(message, 3, debug=True) L devient O P devient S R devient U E devient H U devient X V devient Y E devient H E devient H S devient V T devient W A devient D U devient X M devient P O devient R I devient L S devient V D devient G E devient H M devient P A devient D R devient U S devient V V devient Y R devient U A devient D I devient L M devient P E devient H N devient Q T devient W
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
"""Permet de gérer le chiffrement par code de César. Fonctions --------- 1 :: trouve_indice(element:str, sequence:list=ALPHABET) -> int 2 :: decale(element:str, cle:int, sequence:list=ALPHABET) -> str 3 :: filtre(message:str) -> str 4 :: chiffrement(message:str, cle:int, sequence:list=ALPHABET, ponctuation:list=PONCTUATION, debug:bool=False) """ # Constantes ALPHABET = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] PONCTUATION = [' ', '.', '!', '?', ',', "'", ' '] # Déclarations des fonctions def trouve_indice(element:str, sequence:list=ALPHABET) -> 'int|None': """Renvoie l'indice de element dans le tableau sequence """ for indice in range(len(sequence)): if sequence[indice] == element: return indice def decale(element:str, cle:int, sequence:list=ALPHABET) -> str: """Renvoie la lettre chiffrée en décalant de cle case vers la droite (element doit être présent dans sequence)""" indice = trouve_indice(element, sequence) indice_decale = (indice + cle) % len(sequence) return sequence[indice_decale] def filtre(message:str) -> str: """Renvoie un string où les lettres sont toutes en majuscules""" message = message.upper() # Méthode des strings qui renvoie les lettres en majuscules reponse = '' # on va créer un string de réponse progressivement : on l'initialise for caractere in message: if caractere in ALPHABET or caractere in PONCTUATION : reponse = reponse + caractere # on ne le garde que s'il fait partie d'un des 2 tableaux return reponse def chiffrement(message, cle, sequence=ALPHABET, ponctuation=PONCTUATION, debug=False): """Renvoie un string en décalant les lettres majuscules de cle rangs vers la droite :: param message(str) :: un string filtré ne contenant que des majuscules ou de la ponctuation :: param cle(int) :: la valeur entière du décalage vers la droite pour crypter :: param sequence(list) :: la séquence des caractères cryptables :: param ponctuation(list) :: la séquence des caractères inchangées lors du chiffrement :: return (str) :: le string crypté :: exemple :: >>> chiffrement("ABCé D,XYZ", 3) 'DEF G,ABC' """ reponse = '' for caractere in message: if caractere in ponctuation: reponse = reponse + caractere elif caractere in sequence: crypte = decale(caractere, cle) reponse = reponse + crypte if debug: print(f"{caractere} devient {crypte}") return reponse # Instructions du programme principal if __name__ == '__main__': import doctest doctest.testmod() message = "L'épreuve est au mois de mars, vraiment ?"

07° Expliquer de la façon la plus précise possible comment fonctionne la fonction chiffrement(). On rappelle que le string est en Python une structure de données non mutable et qu'on doit donc recréer un string lorsqu'on veut en "modifier" un.

08° Réaliser la fonction dechiffrement() qui doit pouvoir retrouver le texte de base si on lui fournit le texte chiffré et la clé de chiffrement en entrée.

PRECONDITION : le message chiffré ne doit contenir que des caractères présents dans les paramètres sequence et ponctuation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
def dechiffrement(message, cle, sequence=ALPHABET, ponctuation=PONCTUATION, debug=False): """Renvoie un string en décalant les lettres majuscules de cle rangs vers la droite :: param message(str) :: un string chiffré ne contenant que des majuscules ou de la ponctuation :: param cle(int) :: la valeur entière du décalage vers la droite pour crypter :: param sequence(list) :: la séquence des caractères chiffrables :: param ponctuation(list) :: la séquence des caractères inchangées lors du chiffrement :: return (str) :: le string crypté :: exemple :: >>> dechiffrement('DEF G,ABC', 3) 'ABC D,XYZ' """ pass

Exemple d'utilisation (mc veut dire message crypté et md message décrypté)

>>> message = filtre(message) >>> message "L'PREUVE EST AU MOIS DE MARS, VRAIMENT ?" >>> mc = chiffrement(message, 3) >>> mc "O'SUHXYH HVW DX PRLV GH PDUV, YUDLPHQW ?" >>> md = dechiffrement(mc, 3) >>> md "L'PREUVE EST AU MOIS DE MARS, VRAIMENT ?"

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
def dechiffrement(message, cle, sequence=ALPHABET, ponctuation=PONCTUATION, debug=False): """Renvoie un string en décalant les lettres majuscules de cle rangs vers la droite :: param message(str) :: un string chiffré ne contenant que des majuscules ou de la ponctuation :: param cle(int) :: la valeur entière du décalage vers la droite pour crypter :: param sequence(list) :: la séquence des caractères cryptables :: param ponctuation(list) :: la séquence des caractères inchangées lors du chiffrement :: return (str) :: le string crypté :: exemple :: >>> dechiffrement('DEF G,ABC', 3) 'ABC D,XYZ' """ reponse = '' for caractere in message: if caractere in ponctuation: reponse = reponse + caractere elif caractere in sequence: crypte = decale(caractere, -cle) reponse = reponse + crypte if debug: print(f"{caractere} devient {crypte}") return reponse
chiffrement symétrique

Une méthode de chiffrement est dite symétrique lorsqu'on a besoin de la même clé pour chiffrer ou déchiffrer le message. Les deux personnages voulant communiquer doivent donc partager une clé commune.

Si quelqu'un intercepte la communication, il ne pourra lire que le message chiffré.

symétrique

Il est possible qu'on doive utiliser différemment cette clé lors de la phase de chiffrement et lors de la phase de déchiffrement mais la clé est bien la même dans les deux cas.

Initialisation

Les deux personnes qui désirent communiquer doivent donc partager cette clé à un moment ou à un autre AVANT de pouvoir communiquer de façon chiffrée.

Si cet échange se fait physiquement, les deux personnes pourront alors communiquer à distance en utilisant cette clé.

Deux problèmes émergent donc avec cette technique de chiffrement symétrique :

  • Le chiffrement doit être assez complexe pour qu'on ne puisse pas retrouver le message d'origine en un temps raisonnable (soit par force brute, soit en utilisant une faille permettant de limiter le vrai nombre de clés valides). Ce n'est pas le cas par exemple avec le code de César puisqu'il n'y a que 25 permutations possibles.
  • On ne peut pas initier une telle communication à distance entre deux inconnus : ils devraient se mettre d'accord à distance sur la clé en la communiquant en clair : on pourrait alors très bien intercepter la clé envoyée en clair puis continuer à écouter les messages chiffrés en les déchiffrant puisqu'on connaît la valeur de la clé, interceptée en clair !
  • échange d'une clé symétrique en clair ?

L'échange en clair d'une clé symétrique est donc dangereux et stupide : le but est de garantir la confidentialité de l'échange. S'il suffit d'écouter le premier échange pour parvenir à pénétrer la protection... Autant ne rien faire.

Nous verrons dans la prochaine activité comment parvenir à échanger cette clé symétrique de façon sécurisée.

09° Le chiffrement de César est-il une solution symétrique ou asymétrique. Justifier.

...CORRECTION...

Symétrique puisqu'on utilise la même clé pour la fonction de chiffrement et la fonction de déchiffrement.

10° Combien de clés sont-elles possibles ici ? Ce système est-il résistant à une recherche par force brute ?

...CORRECTION...

Il n'y a que 26 combinaisons avec nos 26 lettres : on peut décaler de 0 à 25 cases. Et encore, le cas 0 est un peu stupide : on ne décale pas...

Bref, 25 valeurs de clé à tester. Non, ce système n'est pas utilisable pour un chiffrement réel.

Chiffrement ou cryptage ?

Puisqu'on stocke tout sous forme d'octets, on parle en réalité plutôt de chiffrement puisqu'on peut toujours interpréter un octet comme un nombre compris entre 0 et 255.

Rappel : un octet correspond à 8 bits.

Il y a donc 28 valeurs possibles (256).

Un octet permet donc d'obtenir des entiers naturels compris entre 0 et 255.

Chiffrement est donc synonyme de cryptage puisqu'on transforme en réalité une donnée en nombre et qu'on transforme ce nombre.

Si on prend le code de César, on pourrait utiliser la simple table ASCII :

  • A encodé en octet valant 65. Le 65 est transformé en 65 + 3 = 68.
  • Lors du déchiffrement, on récupère le 68 et on obtient 68 - 3 = 65. Un A.

2 - XOR bit à bit

Intéressons nous maintenant à une méthode permettant d'obtenir une meilleure résistance à la force brute.

Imaginons qu'on désire transmettre le message "ABC".

Ce n'est pas cette chaîne de caractères qui transite sur les routeurs mais uniquement la représentation en octets de celle-ci.

Voici la table ASCII complète, en version hexadécimale. Comme je ne suis pas méchant, vous pouvez visualiser la valeur décimale d'un caractère en stabilisant la souris au dessus du caractère.

Table ASCII en version hexadécimale
_0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _A _B _C _D _E _F
0_ NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI _0
1_ DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US 1_
2_ ! " # $ % & ' ( ) * + , - . / 2_
3_ 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 3_
4_ @ A B C D E F G H I J K L M N O 4_
5_ P Q R S T U V W X Y Z [ \ ] ^ _ 5_
6_ ` a b c d e f g h i j k l m n o 6_
7_ p q r s t u v w x y z { | } ~ DEL 7_
_0_1_2_3_4_5_6_7_8_9_A_B_C_D_E_F

11° Répondre aux questions suivantes :

  1. Donner la valeur des trois octets qui encodent notre message, en décimal.
  2. Idem en hexadécimal.
  3. Réaliser à la main la conversion de A de l'hexadécimal en décimal pour vous convaincre qu'il s'agit bien de la même valeur représentée de deux façons différentes.
  4. Demander à Python de convertir la valeur hexadécimale de A en décimal.
  5. Demander à Python de convertir la valeur décimale de A en hexadécimal.

...CORRECTION...

  1. En décimal : 65 pour A, 66 pour B et 67 pour C.
  2. En hexadécimal : 41 pour A, 42 pour B et 43 pour C.
  3. 4116 = 4*16 + 1*1 = 65.
  4. En Python : hexadécimal vers décimal
  5. >>> 0x41 65
  6. En Python : décimal vers hexadécimal
  7. >>> hex(65) '0x41'

Nous allons donc envoyer trois octets : 65, 66 et 67 en base 10.

12° Exprimer maintenant vos octets sous forme binaire : donner la suite de bits qui sera envoyé.

...CORRECTION...

65 donne 0100 00012, soit 64 + 1.

66 donne 0100 00102, soit 64 + 2.

67 donne 0100 00112, soit 64 + 2 + 1.

Pour obtenir cette décomposition avec Python :

>>> bin(65) '0b1000001'

Zut, il y a un 0b au début de la réponse...

Pour supprimer les deux premiers caractères (0b) :

>>> bin(65)[2:] '1000001'

Zut, il n'y a pas 8 caractères.

Pour imposer 8 caractères :

>>> f"{bin(65)[2:]:8}" '1000001 '

Zut, il y a 8 caractères mais justifiés à gauche...

Pour justifier à droite :

>>> f"{bin(65)[2:]:>8}" ' 1000001'

Zut, il y a 8 caractères justifiés à droite mais avec un espace. Je veux mon 0 moi...

Pour justifier à droite ET rajouter les 0 nécessaires à gauche :

>>> f"{bin(65)[2:]:0>8}" '01000001'

Enfin...

Maintenant que nous avons notre message binaire, regardons comment le chiffrer.

13° Compléter (vous pouvez cliquer sur les cases notées ?) la table de vérité du ET(AND), du NON-ET(NAND), du OU(OR) et du NON-OU(NOR) :

Rappel :

  • ET est évalué à VRAI si toutes les conditions sont vraies
  • OU est évalué à VRAI si l'une des conditions est vraie

NAND et NOR sont juste des inversions des réponses du AND et du OR.

a b a ET b a NAND b
FAUX FAUX ? ?
FAUX VRAI ? ?
VRAI FAUX ? ?
VRAI VRAI ? ?

Pour le ET, cela revient à chercher cela avec Python :

a and b

Cela revient à chercher cela avec Javascript, C, C++ :

a && b
a b a OR b a NOR b
FAUX FAUX ? ?
FAUX VRAI ? ?
VRAI FAUX ? ?
VRAI VRAI ? ?

Pour le OU, cela revient à chercher cela avec Python :

a or b

Cela revient à chercher cela avec Javascript, C, C++ :

a || b

...CORRECTION...

Pour le AND et le NAND

a b a ET b a NAND b
FAUX FAUX FAUX VRAI
FAUX VRAI FAUX VRAI
VRAI FAUX FAUX VRAI
VRAI VRAI VRAI FAUX

Pour le OU et le NOR :

a b a OR b a NOR b
FAUX FAUX FAUX VRAI
FAUX VRAI VRAI FAUX
VRAI FAUX VRAI FAUX
VRAI VRAI VRAI FAUX

14° Compléter la table de vérité du XOR (OU eXclusif) en utilisant simplement le rappel suivant : un OU eXclusif diffère du OU car il n'est évalué à VRAI que si l'une des expressions est VRAIE. Si deux expressions sont vraies, il est évaluée à FAUX.

a b a XOR b
0 0 ?
0 1 ?
1 0 ?
1 1 ?

...CORRECTION...

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

Nous allons utiliser le XOR entre les bits de nos messages et les bits de la clé commune choisie. Vous allez voir qu'on obtient alors un chiffrement efficace et que le déchiffrement se fait avec la même clé.

Imaginons que notre message soit "ABC" (65-66-67) et notre clé soit "D" (68, donc 0100 0100).

Voici le contenu binaire du message, suivi du contenu binaire de la clé.

Message m : 01000001 01000010 01000011 Cle c : 01000100

Pour obtenir le message crypté mc à partir du message et de la clé, nous allons simplement écrire m XOR c entre chacun des bits de m et de c.

Pour rappel, voici la table du XOR.

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

Premiers bits : 0 XOR 0 donne 0 car il n'y a pas une condition unique vraie.

Message m : 01000001 01000010 01000011 Cle c : 01000100 Message crypté mc = m XOR c : 0

Les bits suivants : 1 XOR 1 donne 0 car deux conditions vraies : on en veut une seule.

Message m : 01000001 01000010 01000011 Cle c : 01000100 Message crypté mc = m XOR c : 00

Les bits suivants : 1 XOR 1 donne 0 car deux conditions vraies : on en veut une seule.

Message m : 01000001 01000010 01000011 Cle c : 01000100 Message crypté mc = m XOR c : 000

15° Trouver les bits du premier octet du message chiffré. Que vaut-il ? Si on ouvrait le fichier chiffré comme un simple fichier texte en ASCII, à quel caractère correspond-t-il ?

...CORRECTION...

Message m : 01000001 01000010 01000011 Cle c : 01000100 Message crypté mc = m XOR c : 00000101

On obtient donc un octet "valant" 5.

Cela correspondrait à un caractère non imprimable exprimant une demande sur le réseau (ENQ, ENQUIRY).

Comment faire avec les octets suivants ? La clé n'est pas assez longue...

La solution retenue est simple : on copie-colle la clé autant de fois que nécessaire.

Message m : 01000001 01000010 01000011 Cle c : 01000100 01000100 01000100 Message crypté mc = m XOR c : 00000101

16° Déterminer maintenant le message chiffré complet, sous forme binaire puis en exprimant chaque octet en décimal.

...CORRECTION...

Message m : 01000001 01000010 01000011 Cle c : 01000100 01000100 01000100 Message crypté mc = m XOR c : 00000101 00000110 00000111

On obtient le message crypté suivant :

00000101 00000110 00000111

5 6 7

L'émetteur veut donc envoyer "ABC", qui correspond aux bits 01000001 01000010 01000011 (65-66-67) mais il va envoyer 00000101 00000110 00000111 (5-6-7).

Comment fait alors le récepteur pour décoder le message crypté ? C'est là toute la beauté du chiffrement en XOR : il suffit de refaire la même chose : on applique un XOR bit à bit entre le message chiffré et la clé.

17° Vous êtes le récepteur. Vous venez de recevoir le message indiqué. Vous savez que la clé commune est 0000 0101. Déchiffrer le message émis. Retrouve-t-on le 'ABC' initial en utilisant la même valeur de clé pour le déchiffrement et le chiffrement ?

Message crypté mc : 00000101 00000110 00000111 Cle c : 01000100 Message m = mc XOR c :

...CORRECTION...

Message crypté mc : 00000101 00000110 00000111 Cle c : 01000100 01000100 01000100 Message m = mc XOR c : 01000001 01000010 01000011

On retrouve bien la suite 65 - 66 - 67.

S'il s'agit d'un texte en ASCII, c'est bien "ABC".

18° La technique de chiffrement par XOR est-elle un chiffrement symétrique ou asymétrique ? La clé est-elle commune, partagée entre émetteur et récepteur.

...CORRECTION...

Même clé pour chiffrer/crypter/coder et déchiffrer/décrypter/décoder.

Il s'agit donc d'un chiffrement symétrique.

Par définition même, la clé est donc commune ou partagée.

19° Si votre clé fait 8 bits, combien y-a-t-il de combinaisons possibles à tester ? Si votre clé fait 128 bits, combien chiffrement peut-il résister à une recherche par force brute ?

...CORRECTION...

8 bits : 28 possibilités : soit 256 clés à tester.

128 bits : 2128 possibilités : soit 340282366920938463463374607431768211456 clés à tester.

20° Choisir une valeur-clé de 5 bits avec un autre étudiant. Transmettez lui un message codé 3 caractères-octets (48 bits) chiffré avec votre clé. Vérifier que les deux parties parviennent bien à communiquer correctement.

Pourquoi 5 bits et 48 bits? Car vous allez devoir faire un copier-coller non complet de la clé sur le dernier octet. Ce n'est pas grave.

Exemple avec un message de 12 bits et un clé de 5 bits.

Message m : 01000001 0100 Cle c : 11001 Message crypté mc = m XOR c :
Message m : 01000001 0100 Cle c : 11001110 0111 Message crypté mc = m XOR c :

Vous allez voir qu'à la main, c'est long... D'où le prochain mini-projet.

...CORRECTION...

Message m : 01000001 0100 Cle c : 11001110 0111 Message crypté mc = m XOR c : 10001111 0011

On envoie donc sur le réseau le message crypté suivant : 10001111 0011.

Le récepteur reçoit ce message sur sa machine.

Il doit alors utiliser un XOR bit à bit entre le message crypté et la clé partagée.

Message m : 10001111 0011 Cle c : 11001110 0111 Message crypté mc = m XOR c : 01000001 0100

Le message décrypté est bien identique au message initial.

3 - FAQ

Nous avions vu que créer un string par concaténation successive ce n'est pas très malin...

C'est vrai !

Le coût de la création par concaténation est linéaire par rapport à n, le nombre de caractères.

Et donc, si vous concaténer ici un caractère à la fois à votre string qui devient peu à peu de plus en plus grand, cela donne ce coût :

𝞗(1 + 2 + 3 +.... n) opérations.

Il faut alors se souvenir de la formule d'Euler :

Formule de la série

On peut également écrire cette formule ainsi :

Formule de la série

𝞗(1 + 2 + 3 +.... n)

= 𝞗( n*(n+1) / 2 )

= 𝞗( n*(n+1) )

= 𝞗( n*n )

= 𝞗( n2 )

Le coût est donc QUADRATIQUE en n, le nombre final de caractères.

Et on fait comment alors ?

  1. On transtype le string en tableau avec la fonction list(). Cette phase a un coût linéaire.
  2. On modifie les éléments du tableau, à coût constant pour chaque case puisque le tableau est mutable. Si on modifie toutes les cases, on obtient alors un coût linéaire pour cette phase.
  3. On transtype le tableau en string avec la méthode join(), ce qui se fait à coût linéaire.

3 phases linéaires, donc une transformation globale à coût linéaire.

Quelques exemples d'utilisation de tout cela avant de vous montrer la nouvelle fonction filtre() :

>>> caracteres = list("Bonjour") >>> caracteres ['B', 'o', 'n', 'j', 'o', 'u', 'r'] >>> valeurs = [ord(c) for c in caracteres] >>> valeurs [66, 111, 110, 106, 111, 117, 114] >>> "*".join(caracteres) 'B*o*n*j*o*u*r' >>> "".join(caracteres) 'Bonjour' >>> "...".join(caracteres) 'B...o...n...j...o...u...r'

Voici une fonction de filtrage linéaire et non plus quadratique :

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
# Constantes ALPHABET = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] PONCTUATION = [' ', '.', '!', '?', ',', "'", ' '] # Déclaration des fonctions def filtre(message:str) -> str: """Renvoie un string où les lettres sont toutes en majuscules""" # 1 - On place tout le message en majuscules (linéaire) message = message.upper() # 2 - Transtype str -> list en ne gardant que les caractères acceptés (linéaire) caracteres = [c for c in message if c in ALPHABET or c in PONCTUATION] # 3 - Transtype list -> str (linéaire) return "".join(caracteres) # Instructions du programme principal if __name__ == '__main__': message = "L'épreuve est au mois de mars, vraiment ?" mess_filtre = filtre(message) print(mess_filtre)

Activité publiée le 02 10 2020
Dernière modification : 02 10 2020
Auteur : ows. h.