search

Accueil > TICE > TRAAM > Ah ! ... la famille > Ah !... la famille... Correction et commentaires...

Ah !... la famille... Correction et commentaires...

mercredi 7 janvier 2015

**Ah !... la famille... Correction et commentaires...

Ah ! ... la famille !
Arthur correspond par messagerie instantanée avec ses amis.
Il sait que son petit frère Maxime essaye régulièrement de lire ses messages car ils partagent le même ordinateur.
Afin de protéger sa vie privée tout en conservant l’historique de sa messagerie, Arthur décide de crypter ses conversations. Maxime qui est vexé mais plein de ressources, décide de jouer un mauvais tour à son frère...
Ayant entendu dire que lui et ses copains utilisent un cryptage affine, et après s’être documenté, il décide de percer leur code afin de déchiffrer leurs messages et pouvoir en envoyer en se faisant passer pour son frère sans se faire remarquer.
Ah ! ... la famille !

Document 1 : Message intercepté par Maxime :

***UHSAHYWZPBFBHGICHPUHBBZPBEHGEFIFSHAPTZEEHVH

Document 2 : Cryptage affine – Extrait Wikipédia

**Méthode de codage :

On commence par remplacer chaque lettre par son rang dans l’alphabet en commençant au rang 0
(certaines variantes commencent au rang 1) :

ABCDEFGHIJKLMNOPQRSTUVWXYZ
0 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

Deux entiers a et b sont choisis comme clef.
On considère la fonction définie par f(x)=ax+b.
Chaque lettre claire est d’abord remplacée par son équivalent numérique x puis chiffrée par le calcul du reste de la division euclidienne par 26 de l’expression affine ax+b
Ainsi pour chiffrer le mot CODE grâce au chiffre affine de clef (17,3),

  • il faut d’abord le transcrire en série de nombres
    C O D E → 2 ; 14 ; 3 ; 4
  • appliquer ensuite la fonction affine
    2 ; 14 ; 3 ; 4 → 37 ; 241 ; 54 ; 71
  • prendre les restes dans la division par 26
    37 ; 241 ; 54 ; 71 → 11 ; 7 ; 2 ; 19
  • puis retranscrire en lettres
    11 ; 7 ; 2 ; 19 → L H C T

Document 3 : Fréquence d’apparition des lettres dans la langue française –

Extrait Wikipédia :
Ah ! ... la famille !

Document 4 :

Si a et b sont deux nombres entiers alors il existe un unique couple d’entiers (q,r) tel que :
0<r<b et a=bq+r, avec r le reste de la division euclidienne de a par b.
La fonction mod() du tableur sert à déterminer ce reste : mod(a ;b)=r

**CORRECTION

I – Clef de codage

Commençons par une attaque statistique du cryptage et calculons les fréquences d’apparition de chaque lettre du message :
Ah ! ... la famille !
Commentaires  :
A la fin du cours précédent, les élèves ont rapidement pensé à comparer les fréquences d’apparition des lettres dans le message avec les données du document 3.
Le tableau ci-dessus était à réaliser pour le lendemain.
Les lettres H et B ont les plus grandes fréquences d’apparition dans le message.
On peut raisonnablement supposer à l’aide du document 3 qu’elles codent respectivement les lettres E et S.
On peut alors écrire à l’aide du document 2 que :

  • E → 4 → procédure de cryptage → 7 → H
  • S → 18 → procédure de cryptage → 1

Si f définie par f(x)=ax+b est la fonction de cryptage, alors on cherche le couple d’entiers (a,b) pour que :
mod(f(4) ;26)=7 et mod(f(18) ;26)=1
c’est à dire mod(4a+b ;26)=7 et mod(18a+b ;26)=1
Remarquons que pour que le codage ne prête pas à confusion il faut que les images des nombres compris entre 0 et 25 soient toutes distinctes.

Ah ! ... la famille !
a devra être choisi parmi les nombres premiers avec 26, soit dans l’ensemble 1 ;3 ;5 ;7 ;9 ;11 ;15 ;17 ;19 ;21 ;23 ;25 si nous le choisissons inférieur à 26.

Commentaires :

1- On peut faire l’impasse sur la démonstration et illustrer les propos par des exemples en invitant les élèves à tester des valeurs de a ayant un diviseur commun avec 26.
Ah ! ... la famille !
Avant d’élaborer la feuille de calcul de test, utilisons le tableur et la fonction mod() pour tester les couples (a,b) possibles
(15 min)

2 – Quel est le reste de la division de 487 par 63 ?
Ah ! ... la famille !
3 – Pour deux nombres quelconques a et b quel est le reste de la division de a par b ?
Ah ! ... la famille !
4 – Pour deux nombres quelconques a et b quel est le reste de la division de ax42 + b par 26 ?
Ah ! ... la famille !
5 – Elaboration de la feuille de calculs de test.

6 - Comme les coefficients étaient petits, certains élèves ont trouvé la solution après quelques essais en utilisant une feuille de calculs construite sur le modèle de la question 3, mais la plupart se sont découragés devant le grand nombre possibilités à tester.
Le nombre de valeurs de a à tester étant réduit, nous avons pris le parti de modifier les valeurs de a manuellement pour tester chacune d’entre elles avec les valeurs de b variant de 1 à 50 (construction dans un premier temps d’une feuille de calculs plus compliquée qui teste toutes les combinaisons en même temps mais lecture et élaboration trop difficile pour les élèves …).
Les erreurs sont presque toutes venues des problèmes d’adressages relatifs et absolus.
L’utilisation du formatage conditionnel permet une meilleure lecture des résultats.
Ah ! ... la famille !
Le couple (a=7, b=5) correspond à notre clef de codage

7- le manque de temps pour aller plus loin en classe (la clef de codage trouvée), entraîne la construction de la table et le décodage du message à la maison avec le tableur ou la calculatrice.

**Clef de codage

Utilisation du tableur pour construire la table de codage avec la fonction mod().
Ah ! ... la famille !
Cette feuille de calculs ne fait que coder les messages, il faudra donc décoder les messages à la main en utilisant cette table.

II – Décodage (pour aller plus loin...)

Pour créer une feuille de calculs de décodage il faudrait déterminer l’antécédent d’un nombre par l’application qui, à un entier x compris entre 0 et 25, associe le reste r de ax + b dans la division par 26.
Si ax+b=r+26q alors ax(r-b)+26q
Pour résoudre cette équation, on cherche un entier a’ tel que aa’=1+26q (a’ est l’inverse de a dans Z/26Z)
(remarquons que l’existence de cet entier est assuré par le théorème de Bachet-Bézout si PGCD(a,26)=1 )
Dans ce cas x=a’x(r-b) + 26k
Déterminons a’ dans notre exemple :
Si a=7 on cherche deux entiers k et a’ pour que 7a’-26q=1
avec l’algorithme d’Euclide :
Ah ! ... la famille !
Ainsi a’=-11 convient, on obtient la feuille de décodage ci-dessous.
Ah ! ... la famille !

III – Évaluation des compétences :

Ah ! ... la famille !

Messages