Ce chapitre contient plusieurs pages:

• introduction au chiffrement et nombres premiers
• sécuriser les communications: Lien 2
• chiffrement asymetrique: Lien 3
• TP sur les nombres premiers: Lien 4
• Projet sur le hack ethique et le chiffrement RSA: Lien 5

Chiffrements symétriques

du chiffrement de Cesar à celui de la machine Enigma…

Vocabulaire

• Chiffrer: transformer les caractères d’un texte pour le rendre incompréhensible, sauf pour celui qui possède la clé de chiffrement.
• Déchiffrer: transformer le texte chiffré en texte clair à l’aide de la clé de chiffrement
• Décrypter: transformer le texte chiffré en texte clair sans posséder la clé.
• Cryptologie: science du secret: possède deux branches
  • cryptographie: étude de l’art du chiffrement
  • cryptanalyse: analyse des méthodes de chiffrement pour les casser (décrypter)

à quoi sert le chiffrement?

Le chiffrement a pour but de protéger nos données, nos communications, mais aussi de signer nos messages et de s’assurer que l’on communique bien avec la bonne personne:

• Authentification: L’authentification est la procédure qui consiste, pour un système informatique, à vérifier l’identité d’une entité (personne, programme, machine).
• L’intégrité des données désigne le fait que les données ne soient pas modifiées au cours d’une communication ou de leur stockage. Ainsi, si vous envoyez un texte chiffré sur un canal non sécurisé, le texte chiffré pourra être intercepté et altéré par un attaquant avant d’atteindre son destinataire. Pour contrôler cette intégrité, on associe au message une valeur de contrôle.
• La confidentialité: Le chiffrement permet de protéger la confidentialité de vos données à l’aide d’une clé secrète.

Chiffrement symétrique - definition

Le chiffrement symétrique utilise la même clé (ou la même table) pour chiffrer et déchiffrer le message. L’algorithme peut être connu par l’adversaire. Mais le secret repose sur celui de la clé.

Le chiffrement par décalage, ou chiffre de Caesar

Le chiffre de César fonctionne par décalage des lettres de l’alphabet.

Compléter l’algorithme du chiffrement de César. On suppose qu’il existe une clé c correspondant au décalage utilisé. Le message clair est m et le message chiffré est m_chiffre

m = ""
Pour chaque lettre l du message m:
  l_chiffre = ...
  m_chiffre = ...

On peut utiliser les fonctions numero(l:str)->int et caractere(n:int)->str

Facilité du décryptage

monosubstitution par décalage ou par substitution: Une lettre du message clair va t-elle donner différentes lettres chiffrées, ou une seule?

Décryptage par FORCE BRUTE: Combien y-a-t-il de clés possibles à essayer pour celui qui réalise le décryptage? Conclure.

Un chiffrement par substitution monoalphabetique

Le chiffrement par substitution monoalphabetique utilise une fonction avec modulo:

$$x \rightarrow x + cle ~[26]$$

Mais il peut y avoir d’autres fonctions plus complexes utilisées. Voire, même aucune fonction, mais une table de correspondance entre lettre en clair et symbole chiffré. La clé aurait alors la longueur de l’alphabet.

Le chiffrement par monosubstitution a été également utilisé par différentes méthodes utilisant une table.

Vous trouvez cette méthode de chiffrement trop simpliste? Regardez alors sa déclinaison avec le chiffrement de Playfair

Decryptage par analyse fréquentielle

Le code issu du carré de Polybe a été utilisé par les prisonniers, qui transmettaient leur message en tapant sur les murs Tap code Le problème avec ce type de chiffrement monoalphabetique, est qu’il est possible de repérer comment sont transformées certaines lettres à partir de l'analyse fréquentielle du message chiffré.

On peut alors utiliser la frequence des lettres pour dechiffrer et comparer avec la frequence moyenne dans une langue. (200 caracteres suffisent). Il y a aussi tout un tas de statistique, comme les lettres uniques, doubles lettres, finales, etc… C’est un marqueur suffisant pour savoir comment le code est fait.

Une amélioration: Substitution polyalphabétique

L’analyse des fréquences est moins pertinente lorsque le message a été chiffré avec un chiffrement polyalphabétique (qui tend à rendre aléatoire la fréquence des lettres).

Polyalphabetique: Se dit d’un chiffre où un groupe de n lettres est codé par un groupe de n symboles. Le chiffrement Playfair, vu plus haut s’apparente à une substitution polyalphabetique, puisqu’il substitue des digrammes (groupes de 2 lettres) dans le texte d’origine.

Contrairement aux chiffrements monoalphabetiques, qui sont des chiffrements par flot (caractères transformés un à un), les chiffrements polyalphabetiques réalisent un chiffrement par blocs (plusieurs caractères transformés en une fois).

L’exemple suivant montre une polysubstitution simple avec une clé de longueur 3 qui va décaler les lettres de l’alphabet :

On définit la clé ‘123’ qui indique que le premier caractère sera décalé d’une position, le second de 2 et le troisième de 3 positions, etc.

Le mot : WIKIPEDIA donne donc dans ce cas XKNJRHEKD.

Mais si on chiffre le mot : AAAAAAAAA cela donnera BCDBCDBCD. La lettre A ne donne pas toujours la même correspondance chiffrée. Mais on peut analyser la périodicité et en déduire la longueur de la clé. La connaissance de la longueur de la clé est essentielle pour pouvoir pratiquer l’analyse frequentielle.

Une même lettre ne donne pas toujours le même caractère chiffré, sauf si on connait la longueur de cette clé. (voir aussi le chiffrement de Vigenère) qui utilise ce principe de décalage à partir d’une clé exprimée par un mot.

La machine Enigma

Des branchements permettent d’ajouter des permutations des caractères.

Tout ceci modifie l’alphabet chiffré et augmente sérieusement la complexité.

Comme tout chiffrement symétrique, déchiffrer se fait avec la même machine, à condition d’utiliser la même clé.

Son utilisation la plus célèbre fut celle faite par l’Allemagne nazie, avant et pendant la Seconde Guerre mondiale, la machine étant réputée inviolable selon ses concepteurs.

Le principe de la machine Enigma était connu. Le concepteur savait à l’avance que certains modèles pourraient être volés par les alliés. Ce qui fit son efficacité, c’est le nombre immense de combinaisons possibles pour les réglages initiaux de la machine et le choix de la clef brute du message.

Les cryptanalystes britanniques, dont Alan Turing

Exercices

Substitution monoalphabétique: Code de César

• Question 1: Quelle clé a été utilisée pour chiffer ce texte (avec l’algorithme de César)?

$$jyfwavnyhwopl hwwspxbll$$

• Question 2: Décrypter ce message.

• Question 3: Proposer un programme en python qui chiffre un message clair m en un message codé selon la clé numérique c.

Aide:

• La fonction ord('x') retourne un entier correspondant à la position d’un caractère dans la table ascii. Par exemple, ord('A') retourne 65, ord('B') retourne 66,…

• La fonction chr(N) retourne le caractère de rang N: chr(65) retourne ‘A’.

Substitution polyalphabétique: Chiffrement de Playfair

A partir des explications données dans la video:

• Question 1: Construisez la matrice pour l’algorithme de Playfair avec la clé estienne.
• Question 2: Chiffrer le message: ACTIONREACTION
• Question 3: S’agit-il d’une méthode utilisant la substitution monoalphabetique, ou polyalphabetique?
• Question 4: Avec cette méthode, le decryptage est-il possible par analyse fréquentielle?

Frequences des lettres dans un texte

La fonction suivante retourne une liste de 26 valeurs de type float, donnant dans l’ordre de l’alphabet, la frequence pour chaque lettre dans un texte:

def freq(m):
    frequences = [0]*26
    n = len(m)
    for c in m:
    ...

• Question 1: Compléter le script de la fonction freq.

Soient les deux textes chiffrés suivants:

a.

DGFHTMOMEIAMTLMFGOKFGOKEGDDTRWEIAKZGFGFSTEKGOMLASTTIFGFOSTLMFTFGOKMGWMFGOKRTSAJWTWTAWDTFMGFDAOLTWMOSSAFGOKETWKRWFDTEIAFMROAZSGMOFKOTFFTXAWMLARGWETWKJWAFROSDOAWSTAWDAMOFHGWKDTSTEITKSADAOF

b.

YOHGMVMFCBRBGWFNIZZPSURWFUOIPUWYITFANIETGGDOCKACPQEBEWPMXEMKVGRAILKWWXZOCILGPMQOVCGEGMYEBQRYACJMWXULFRVQMDCYLZFYZMYTPCRFDCRJNSFIHIQGRZEPRCVWMDILKGYDQORVFMXMCRCNIMUGRBKRBOOIUGPQCBVZNEYACE

• Question 2: L’un des 2 a été chiffré avec un algorithme de substitution mon-alphabetique, et l’autre, poly-alphabétique. Lequel est mono-alphabétique?

• Question 3: Tracer un histogramme à partir du texte chiffré en mono-substitution. On donne un exemple de script ci-dessous pour réaliser le graphique:

import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_axes([0, 0, 1, 1])

etiquettes = ['a', 'b', 'c', 'd', 'e']
valeurs = [23, 17, 35, 29, 12]

# Affichage des données
ax.bar(etiquettes, valeurs)

plt.title("Histogramme")  # Titre du graphique
plt.ylabel('Nombre')  # Titre de l'axe y
plt.xlabel('alphabet')
plt.show()  # Affichage d'une courbe

Chiffrement symétrique par la fonction XOR

exercice inspiré de la page sur le chiffrement de glassus.github.io

• Question 1: La fonction XOR est la fonction du OU EXCLUSIF.

Donner la table de vérité de la fonction XOR

• Question 2: A partir des lignes suivantes, vérifier que l’opérateur ^ en python réalise la fonction XOR sur 2 nombres écrits en valeur décimale:

> 3 ^ 4
7
> 4 ^ 5
1

• Question 3: Programmer la fonction xor en python qui retourne le resultat de XOR appliqué aux 2 paramètres a et b.

Exemple:

>>> xor(0,1)
1
>>> xor(53,23)
34
>>> xor(34,23)
53

• Question 4: Peut-on utiliser la fonction XOR pour chiffrer PUIS dechiffrer un message, avec la MEME clé de chiffrement? Expliquer à partir de l’exemple ci-dessus.

• Question 5: On s’interresse maintenant à la programmation de la fonction XOR pour chiffrer un message à partir d’un masque:

$$message = “CETTEPHRASEESTVRAIMENTTRESTRESLONGUEMAISCESTFAITEXPRES”$$

Le masque (correspond à la clé) aura une longueur inférieur au message. On utilise le masque selon la méthode de chiffrement polyalphabetique vue en cours.

Le chiffrement demande de faire correspondre les caractères avec des nombres entiers. On utilisera pour cela un alphabet de 32 caractères ($2^5$). Chaque lettre de l’alphabet correspondra alors à un nombre compris entre 0 et 31.

• Question 6: Lorsque l’on place 2 entiers inférieurs à 32 dans la fonction XOR, celle-ci retourne un entier également inférieur à 32. Pourquoi? (Representer ces nombres en binaire, sur un octet, et verifier cette affirmation)

• Question 7: Compléter la fonction chiffre(message, masque) qui chiffre message en le XORant avec masque.

Cette fonction doit pouvoir aussi servir à déchiffrer le message chiffré.

alphabet=[chr(i+ord('A')) for i in range(26)] + ['*','/','@','&','!','à']
def chiffre(message, masque):
    assert len(message)>=len(masque)
    message_chiffre = ""
    for i in range(len(message)):
        indice_lettre = alphabet.index(message[i])
        indice_masque = ...
        val = xor(...,...)
        message_chiffre+=alphabet[val]
    return ...

• Question 8: Utiliser la fonction chiffre pour effectuer le chiffrement puis le dechiffrement du message.

• Question 9: Pensez vous que cette méthode de chiffrement est assez resistante face à une attaque de cryptoanalyse? Si oui, pourquoi?

Liens

• Suite du cours: chiffrement asymétrique

Documentation, sitographie

• Chiffrement : notre antisèche pour l’expliquer à vos parents article de NextImpact
• chiffrement de Vigenère: wikipedia
• Interstices : coder et decoder. La machine Enigma
• sécurisez vos données avec la cryptographie openclassroom