clef

TP1-PROG-11 : Introduction à la cryptographie#

Objectifs#

  • Modéliser une scytale

    • comprendre et modéliser un chiffrement par décalage

    • intégrer une attaque en force brute

  • Implémenter le fonctionnement de la scytale:

    • chiffrer un texte clair avec connaissance de la clef

    • déchiffrer un texte crypté avec connaissance de la clef

  • Pour aller plus loin : Déchiffrer un texte crypté sans connaissance de la clef

    • attaque par force brute

    • reconnaissance de la langue

    • élagage des solutions peu probables

Modélisation d’une scytale#

La scytale est l’un des premiers dispositifs permettant de chiffrer ou déchiffrer un message. La méthode de chiffrement se fait par transposition.

Concrètement, le message à crypter est écrit sur un rouleau de papier ou de cuir enroulé sur la scytale (ou Bâton de Plutarque) :

       | u | n | e | s | c | y |
       | t | a | l | e | . | . |
   | c | e | c | i | e | s |
   | t | u | n | m | e | s |
   | s | a | g | e | e | c |
   | r | i | t | s | u | r |

Une fois déroulé, le message devient :

c t s r u t e u a i n a c n g t e l i m e s s e e e e u c . s s c r y .

Le clé de codage, c’est à dire le décalage sur la scytale vaut : clef = 6. Cette clef permet de chiffrer et déchiffrer le message clair et codé.

Décalage#

Le décalage (lié à la clef de codage/décodage) est lié au nombre de lettres que l’on peut inscrire sur le périmètre de la scytale. Par conséquent, la clef est directement liée au rayon de la scytale.

Attaque en force brute#

Si on ne connaît pas la clef de codage/décodage, le seul moyen de décoder le message est de tester toutes les possibilités de décalage des lettres et de reconnaître un éventuel message clair.

C’est la technique de la force brute.

Exercice 1 : déclarer les phrases claires#

  • Ouvrez l’IDE Python et créez un nouveau fichier crypto.py.

  • choisissez une phrase en clair (un texte_clair) en anglais ou en français

phrase_a_1 = "Arise, you have nothing to lose but your barbed wire fences!"
phrase_a_2 = "If privacy is outlawed, only outlaws will have privacy"
phrase_a_3 = "Show me a person who has nothing to hide, and I’ll show you a person who is either exceedingly dull or an exhibitionist"
phrase_a_4 = "One of the best ways to achieve justice is to expose injustice"
phrase_a_5 = "I am a future-hacker ; I am trying to get root access to the future. I want to ride its system of thought"
phrase_a_6 = "Girls need modems"

phrase_f_1 = "La valeur d’un trésor réside dans son secret"
phrase_f_2 = "La cryptographie est la forme la plus aboutie de l’action directe non-violente"
phrase_f_3 = "L’argent c’est du temps, sauf si vous n’avez pas l’un ou l’autre"
phrase_f_4 = "Un téléphone portable émet des signaux de localisation. Lorsqu’on a un téléphone portable, le réseau sait toujours où l’on se trouve"
phrase_f_5 = "Si vous possédez une bibliothèque et un jardin, vous avez tout ce qu’il vous faut"
phrase_f_6 = "Combien de vous n’ont pas violé de loi ce mois-ci ?"
phrase_f_7 = "Si vous surveillez tout le monde, vous ne surveillez personne"

Boucles : formalisme des algorigrammes - programme Python#

Une boucle for est une construction où un test conditionnel est fait de manière implicite. En effet, en Python on écrit une boucle de la façon suivante :

for var in range(longueur):
    instruction 1
    instruction 2
    etc..

Signifie que la variable var va successivement prendre les valeur décrites dans la liste retournée par la fonction range(borneSup) (où borneSup n’est pas compris). Par exemple :

for var in range(5):

la fonction range(5) va retourner la liste [0,1,2,3,4]. La variable var va donc successivement prendre ces valeurs. Lorsqu’elle atteindra la valeur 5, le test conditionnel sera faux et le programme va sortir de la boucle.

On peut décrire une boucle for avec l’algorigramme suivant :

boucle_for

Exercice 2 : Construction de la fonction de chiffrement#

La signature de la fonction de chiffrement est la suivante :

# Fonction permettant de chiffrer un texte en clair
# Argument 1 : le texte clair
# Argument 2 : la clef de chiffrage
# Retour     : le texte chiffré
def chiffre(texte_clair,saut):

Elle prend en paramètre le texte clair à chiffrer ainsi que le clef de chiffrement. Et le retourne la phrase chiffrée. L’algorithme est donc :

  1. POUR toute lettre du texte_clair faire

    1. calculer la position chiffrée pos_c : pos_c = pos_c + clef

    2. SI on a atteint la fin du texte_clair l, alors incrémenter : if (pos_c > l-1)

      1. dec = dec + 1

      2. la position dans le texte chiffré devient la valeur de l’incrément : pos_c = dec

    3. Ajouter la lettre chiffrée à la position pos_cdans le texte_chiffre : texte_chiffre = texte_chiffre + texte_clair[pos_c]

  2. retourner texte_chiffre : return texte_chiffre

Nous avons donc une boucle for qu’il s’agit de reconnaître dans algorigramme suivant:

chiffrement

Afin de tester votre algorigramme avec une feuille de papier, et avant de vous lancer dans l’implémentation :

  • prenez une feuille de papier

  • codez le mot BONJOUR avec clef = 2

  • analysez chacune des étapes dans un tableau qui contient :

Valeur de pos

Valeur de pos_c

Valeur de dec

0

0

0

1

2

0

2

4

0

etc…

  • le mot BONJOUR chiffré avec clef = 2 vaut BNOROJU

# Fonction permettant de chiffrer un texte en clair
# Argument 1 : le texte clair
# Argument 2 : la clef de chiffrage
# Retour     : le texte chiffré
def chiffre(texte_clair,clef):
    texte_chiffre = ''
    # la variable pos contient l'index (la position) dans le texte clair
    pos = 0
    # la variable dec contient l'incrément négatif lorsque la longueur du texte clair est atteinte
    dec = 0
    # la variable pos_c contient l'index (la position) dans le texte chiffré
    pos_c = 0
    # la variable l contient la longueur du texte clair
    l = len(texte_clair)
    # A REMPLIR ICI

    return texte_chiffre

Exercice 3 : Test de la fonction#

  • Pour tester votre fonction, appelez-la sur la phrase que vous avez choisie à l’exercice 1.

  • Testez plusieurs valeurs de clef

Exercice 4 : Construction de la fonction de déchiffrement#

La fonction de déchiffrement est parfaitement équivalente à la fonction de chiffrement. La seule différence est qu’elle prend en paramètre le texte_chiffre et que la position chiffrée pos_c devient la position dans le texte clair.

Attention : on travaille ici avec une liste ret pour recréer le texte clair et initialisée à la longueur du texte chiffré, puisqu’il n’est pas possible de changer un caractère dans une chaîne. Le retour s’effectue avec la fonction ''.join(ret) qui transforme une liste en chaîne de caractères.

# Fonction permettant de déchiffrer un texte crypté
# Argument 1 : le texte crypté
# Argument 2 : la clef de chiffrage
# Retour     : le texte déchiffré
def dechiffre(texte_chiffre,clef):
    # la variable l contient la longueur du texte chiffré
    l = len(texte_chiffre)
    # la variable pos continent l'index (la position) dans le texte chiffré
    pos = 0
    # la varibale pos_c contient l'index (la position) dans le texte clair
    pos_c = 0
    # la variable dec contient la valeur de l'incrément positif
    dec = 0
    # la variable ret est une liste de longueur l qui est vide et que l'on va remplir avec les lettre du texte chiffré
    ret = ['' for _ in range(l)]

    ## A REMPLIR ICI
    
    # on retourne une chaîne de caractères (''.join(ret) retourne la transformation de la liste en chaîne de caractères)
    return ''.join(ret)

Exercice 5 : Chiffrer et déchiffrer#

  • testez vos deux fonctions chiffrer(texte_clair,clef) et dechiffre(texte_chiffre, clef) sur la phrase choisir

  • vous devriez obtenir la phrase clair

Exercice 6 : Force brute#

  • Choisissez une valeur pour la variable clef

  • chiffrez une phrase de votre crû à l’aide de votre fonction de chiffrement et cette clef

  • Testez l’ensemble des possibilités par la force brute pour retrouver la phrase en clair.

Répondez aux questions suivantes :

  1. Combien de clef maximum devez-vous tester ?

  2. Quelles sont les difficultés que vous rencontrez ?

Pour aller plus loin#

Une fois que vous avez les deux fonctions de chiffrement et déchiffrement, il vous manque un élément pour être capable de casser une phrase chiffrée sans connaissance préalable de la clef de chiffrement.

Analyse de la langue utilisée#

Pour pimenter la difficulté, les messages sont écrit dans des langues différentes. Dans ce TP, nous utiliserons le français et l’anglais. La question devient donc : si l’on ne connaît pas la clef, comment faire comprendre à l’ordinateur qu’une phrase décryptée est peut-être la solution de décodage ?

Deux possibilités existent pour ce faire :

  1. Une analyse fréquentielle : on compare la fréquence de chaque lettre du message codé avec la fréquence d’utilisation des lettres de chacune des langues. On prend la plus proche.

  2. Une analyse par apparition des mots les plus courants des deux langues.

Créer des sets de données dans différentes langues#

Afin de tester l’analyse de la langue, il s’agit d’avoir deux datasets (l’un en anglais et l’autre en français). Ces sets de données comprennent l’entier des phrases déclarées à l’exercice 1

Exercice 7 : Créez les datasets#

Ces ensembles de données permettront de tester les différentes fonctions de chiffrement et de déchiffrement

  • déclarez l’ensemble des phrases en français et en anglais

  • crééez les deux sets de données tel que ci-dessous

dataset_a = [phrase_a_1,phrase_a_2,phrase_a_3,phrase_a_4,phrase_a_5,phrase_a_6]
dataset_f = [phrase_f_1,phrase_f_2,phrase_f_3,phrase_f_4,phrase_f_5,phrase_f_6,phrase_f_7]

Exercice 8 : Analyse linguistique du texte déchiffré#

Lorsqu’on a un très grand texte chiffré, la difficulté humaine lorsqu’on utilise la méthode de la force brute, est de devoir lire tous les résultats. Il peut y en avoir énormément et cela prend du temps. On peut demander à l’ordinateur de le faire à notre place.

  1. Analyser chaque sous-chaîne de caractère du texte décrypté

  2. Comparer avec un ensemble de mot très couramment utilisé dans les langues cibles.

  3. Si “peu” de mots apparaissent, la clef n’est probablement pas la bonne, sinon, on conserve la solution possible

La fonction analyse_langue(texte) a la signature suivante :

# Fonction permettant de retourner la langue d'un texte donné en paramètre
# sur la base d'une analyse de certains mots clefs
# La liste des mots clefs est basée sur les classements internationaux (comme COCA)
# Argument 1 : le texte clair
# Retour     : une liste qui contient : [la langue possible, le nombre d'occurences des mots-clefs] 
def analyse_langue(texte):

elle doit permettre de trouver si le texte est en français ou en anglais, sans garantie d’exactitude. Il s’agit d’abord de définir une suite des mots les plus utilisés en français et en anglais. Une recherche internet devrait vous y aider.

    mots_clefs_f = ['le','la','les','un','une','de','des','il','elle','et','non','est','on','vous','nous','se','pas','leur']
    mots_clefs_a = ['the','be','to','of','and','in','that','have','it','for','not','is','if']

L’idée ensuite est d’analyser l’ensemble de la chaîne de caractère passée en paramètre texte et de compter les occurences de chacun des mots-clefs en français nbr_f, puis en anglais nbr_a. La méthode texte.startwith(sousChaine,i) permet de retourner True si la sous-chaîne de caractères sousChaine à rechercher dans la chaîne texte à l’index i:

if texte.startwith(mot_clefs_f[i],position) :
    # on incrémente le nombre d'occurences françaises de 1
    nbr_f = nbr_f + 1

On compare ensuite les deux valeurs :

if (nbf_f == nbr_a):
#    on ne peut pas discriminer les deux langues, on retourne NULL:
    langue = 'NULL'
    retour = [langue,nbr_a]
elif (nbr_f > nbr_a):
#    le texte est en français
    langue = 'FRA'
    retour = [langue,nbr_f]
else:
#    le texte est en anglais
    langue = 'ENG'
    retour = [langue,nbr_a]

on retourne finalement la valeur de la liste avec le nombre d’occurences:

return retour

# Fonction permettant de retourner la langue d'un texte donné en paramètre
# sur la base d'une analyse de certains mots clefs
# La liste des mots clefs est basée sur les classements internationaux (comme COCA)
# Argument 1 : le texte clair
# Retour     : une liste qui contient : [la langue possible, le nombre d'occurences des mots-clefs] 
def analyse_langue(texte):
    mots_clefs_f = ['le','la','les','un','une','de','des','il','elle','et','non','est','on','vous','nous','se','pas','leur']
    mots_clefs_a = ['the','be','to','of','and','in','that','have','it','for','not','is','if']
    retour = ['',0]
    l = len(texte)
    nbr_f = 0
    nbr_a = 0
    for mot_clef in mots_clefs_f:
        ## A REMPLIR ICI
        
    for mot_clef in mots_clefs_a:
        ## A REMPLIR ICI

    if nbr_f == 0 and nbr_a == 0:
        ## A REMPLIR ICI
        
    return retour

  Input In [6]
    for mot_clef in mots_clefs_a:
    ^
IndentationError: expected an indented block

Exercice 9 : Chiffrement et déchiffrement des datasets français et anglais#

Pour chiffrer et déchiffrer, nous choisissons des clefs de codage aléatoirement avec le module Python random. Il s’agit d’importer ce module en tout début de programme :

import random

Pour tirer un entier au hasard, on utilise la fonction

random.randint(debut, fin)

où debut est la borne inférieure, fin la borne supérieure (non comprise). Ainsi :

random.randint(3,100)

va tirer un entier au hasard compris entre 3 et 100

import random
random.randint(3,100)

5

# Création des phrases chiffrées aléatoirement
# Et déchiffrement SANS élagage
for phrase in dataset_a:
    longueur = len(phrase)
    clef = random.randint(3,int(longueur/2))
    texte_chiffre = chiffre(phrase,clef)
    print('[Cyphered] '+str(clef)+"   : "+texte_chiffre)
    texte_dechiffre = dechiffre(texte_chiffre,clef)
    print('  [ANALYSED '+str(clef)+']   : '+texte_dechiffre)

[Cyphered] 24   : Atwroii rsleeo ,sf eey nobcuue tsh !ayvoeu rn obtahribnegd  
  [ANALYSED 24]   : Arise, you have nothing to lose but your barbed wire fences!
[Cyphered] 12   : Iso rf nwi olivpuylart lcilo yvauhawtacelvydae ,w i sp
  [ANALYSED 12]   : If privacy is outlawed, only outlaws will have privacy
[Cyphered] 31   : Sgpyh e otrdwosu  olmhnlei   dwoaehr ,o p  aeainrns sd eo exnIih ’tiwlhbhleio rt s ihheoaoxnswci  esnyetoodtuih niagn l
  [ANALYSED 31]   : Show me a person who has nothing to hide, and I’ll show you a person who is either exceedingly dull or an exhibitionist
[Cyphered] 27   : Oinnejevu eso tfji uctsehtei cbee sits  wtaoy se xtpoo saec hi
  [ANALYSED 27]   : One of the best ways to achieve justice is to expose injustice
[Cyphered] 21   : I;rti  outaIorsm te  a .sama y  cIsftc turewetysamuisn rn toegt f- ot ht otaot hc hrokgeiuee dgrtfeh  u t
  [ANALYSED 21]   : I am a future-hacker ; I am trying to get root access to the future. I want to ride its system of thought
[Cyphered] 8   : Gesidr lmso dneem
  [ANALYSED 8]   : Girls need modems

Exercice 10: Application de la force brute#

A partir de la boucle précédente, calculer toutes les possibilités et clefs associées, c’est-à-dire sans connaître la clef a priori

Exercice 11 : Décrypter un très long texte chiffré#

A l’aide des trois fonctions chiffre(texte_clair,clef), dechiffre(texte_chiffre,clef) et analyse_langue(texte), déchiffrez la phrase suivante :

phrase_chiffree = "Lemasp  lccerr yycppottnoonggurr aadppehh iiceqr,uy eplsta o pgsrrciaimpeihnticieev  eudste i ellxi iséséctera iipteounurtre   dpdareno stc éolgd eeArsn  tdeietqs u diietn éfc oheritmf,af tràie omunensn  tccseo rnptfoaiuidrne  nudtneiege rlcélo,em sml uadn aiptcleau tpdiaeor nt3   sd5ée0cs0u  rcaiinsvséi ele,in sveaistrtio onln. s u Unan n dcseicser niénbleeés m mesénestmosbp lopetrnaitmn icaeivnpo airurex c eoauuy raraneitct o ruàer nsld auà   cplroays psctirobyglpreta oplgh’riiaenp vhpeioneut.ri  oLdnei  sdrseeismm pucllraeycrpe tmuoen-nemt o fndonera misueylsme b eodtle e d,ge lsla açb ulfrooecr kmdceeh  alpiaon tspe lrmuiosed ,eé rlunétemisel.ni tsLaéeiesr  est uedrce h dnceirsqy uptetasob glcreratyptphetisoe g,dr  aaapprhpgiaiqrluaeeî.st  uàt illai sféoeiss  aduajnosu rlde sh uéic rsiotnst  écgeyppetnideannst  alnet ifqruueist  edt  umnées olpoontgaumei ehniss.t oLier ep ldues  daénvceileonp peexmeemnptl.e  Dceopnunius  dle  Acnet itqyupiet éd,e  lcar ycprtyopgtroagprhaipeh iae  épteér mterto udveé  tdraannss mleat ttroem bdee sd  iunnf onrombaltei oéngsy pdtei emna nnioèmrmeé  sKéhcnuurmihsoétee.p  VIoIi,c iq uli’ hviisvtaoiitr ei lf ays cai neannvtier odne  3l a9 0c0r yapntso.g r aLpeh iree mqpulia cae mceonntd udiet  sayumxb omléetsh oddaenss  alv’ainncsécersi petti osno pdhei sKtnihquuméheost eupt inl’ias épeass  ppoouurr  loeb jcercytpitfa gdee  nduimsésriimquulee rm oddeesr nien.f o r mLaetsi ornasc,i nmeasi sa ndcei ernennefso rdcee rl al ecurry pattotgrraaipth ilei n gOuni sstaiiqtu eq.u eL el epsr etmeicehrn ieqxue"

phrase_chiffree = "Lemasp  lccerr yycppottnoonggurr aadppehh iiceqr,uy eplsta o pgsrrciaimpeihnticieev  eudste i ellxi iséséctera iipteounurtre   dpdareno stc éolgd eeArsn  tdeietqs u diietn éfc oheritmf,af tràie omunensn  tccseo rnptfoaiuidrne  nudtneiege rlcélo,em sml uadn aiptcleau tpdiaeor nt3   sd5ée0cs0u  rcaiinsvséi ele,in sveaistrtio onln. s u Unan n dcseicser niénbleeés m mesénestmosbp lopetrnaitmn icaeivnpo airurex c eoauuy raraneitct o ruàer nsld auà   cplroays psctirobyglpreta oplgh’riiaenp vhpeioneut.ri  oLdnei  sdrseeismm pucllraeycrpe tmuoen-nemt o fndonera misueylsme b eodtle e d,ge lsla açb ulfrooecr kmdceeh  alpiaon tspe lrmuiosed ,eé rlunétemisel.ni tsLaéeiesr  est uedrce h dnceirsqy uptetasob glcreratyptphetisoe g,dr  aaapprhpgiaiqrluaeeî.st  uàt illai sféoeiss  aduajnosu rlde sh uéic rsiotnst  écgeyppetnideannst  alnet ifqruueist  edt  umnées olpoontgaumei ehniss.t oLier ep ldues  daénvceileonp peexmeemnptl.e  Dceopnunius  dle  Acnet itqyupiet éd,e  lcar ycprtyopgtroagprhaipeh iae  épteér mterto udveé  tdraannss mleat ttroem bdee sd  iunnf onrombaltei oéngsy pdtei emna nnioèmrmeé  sKéhcnuurmihsoétee.p  VIoIi,c iq uli’ hviisvtaoiitr ei lf ays cai neannvtier odne  3l a9 0c0r yapntso.g r aLpeh iree mqpulia cae mceonntd udiet  sayumxb omléetsh oddaenss  alv’ainncsécersi petti osno pdhei sKtnihquuméheost eupt inl’ias épeass  ppoouurr  loeb jcercytpitfa gdee  nduimsésriimquulee rm oddeesr nien.f o r mLaetsi ornasc,i nmeasi sa ndcei ernennefso rdcee rl al ecurry pattotgrraaipth ilei n gOuni sstaiiqtu eq.u eL el epsr etmeicehrn ieqxue"

Exercice 12 : Envoyer un message crypté#

Envoyez un email contenant un message chiffré à un ou une camarade de classe présent dans la salle sans lui dévoiler la clef et demandez-lui de le déchiffrer.