Listes et cryptographie


Dans cette feuille de calcul nous allons travailler sur les listes pour bien comprendre les mécanismes d'accès, de création, de modification des listes. Nous illustrons tout cela avec de la cryptographie, il faut bien se distraire.

Commençons par une distinction subtile. Python, Sage comme la plupart des langages de programmation connaissent les chaines de caractères. Ce sont presque des listes. Mais Python a choisi de les rendre immutables (immuables).

Commençons par une chaine de caractères.

message="FZCFRJXGNJSXSJJXQFAFQJZWSFYYJSIUFXQJSTRGWJIJXFSSJJX"

Essayons d'accéder aux caractères à l'intérieur:

print message[3]
In [0]:
 

Attention dans les chaines de caractères et les listes à l'indice 0 on trouve le premier caractère.

Faites une boucle pour afficher les dix premiers caractères de la liste

In [0]:
 

Il est indispensable d'accéder à la longueur de la chaine de caractère (ou de la liste):

len(message)

et de faire une boucle sur la liste:

for c in message:
    print c

ou bien

for i in range(len(message)):
   print c[i]

Essayez les deux boucles ci-dessus et utilisez le paramètre step de range pour parcourir la liste à l'envers.

In [0]:
 
In [0]:
 
In [0]:
 

Parcourez maintenant message pour trouver le nombre de 'J'. Puis le nombre de 'F'.

In [0]:
 
In [0]:
 

Attention aux effets de bords:

print len(message)
message[51]
In [0]:
 

Quelques mécanismes très efficaces:

  • On peut accéder directement à la fin d'une chaine de caractère ou une liste: message[-1]
  • On peut découper en tranche chaine de caractère ou une liste: message[2:7], mémorisez bien les effets de bord (le caractère en position 2 y est, mais pas celui en position 7)
In [0]:
 
In [0]:
 

Déchiffrons !


Le message ci-dessus est donc un message chiffré. La méthode de chiffrement est la plus simple possible: les lettres ont été décalé de 5 ainsi le 'F' du début correspond en clair à un 'A'.

Pour faire des opérations sur les lettres on dispose de leur place dans la table ascii donnée par ord() et de l'opération inverse char().

Essayez

print ord('A')
print ord('F')
print chr(67)
In [3]:
 

Parcourez les lettres du message et affichez la lettre obtenue en décalant de 5.

Attention à ne pas enlever 5 à 'A', sinon vous sortez de l'alphabet, utilisez plutôt les calculs modulo 26, et retournez au TP prise en main sur les nombres si vous avez oublié le modulo.

Vous pouvez dans un premier temps afficher le rang dans l'alphabet latin ord(c)-65.

In [0]:
 
In [0]:
 

Vous pouvez stocker le message décrypté dans une nouvelle chaine de caractère resultat, en effet si les chaines de caractères sont immuables on peut les concaténer.

result = ""
for c in message:
   result = result + char(((ord(c)-65)-5)%26+65)
In [0]:
 

Plus difficile !


Votre mission, maintenant, si vous l'acceptez est de décrypter le message suivant:

G LPKKNVAH RL BALYG RNAN LCLPO OFVWFVAH CNPKKN HVA 
RFP LCNZ VYN GNKPZLONHHN OAFM OPRFANN MFVA TVN WN 
YN ZAVHHN MLH TVN K NYHNRSKN GNH ZIFHNH TV FY YN 
GFPO MLH ULPAN NHO PYGPCPHPSKN NO TVN GNH WNVYNH 
UPKKNH TVP RLYTVNYO GN ANHMNZO L KL CPNPKKNHHN 
UVHHNYO OFVO G VY ZFVM LAANONNH MLA GNH HZAVMVKNH 
TVLYG PK H LBPO GN MKLPHPAH MKVH ONYOLONVAH TVN GN 
HLVONA MLA GNHHVH VY FZOFBNYLPAN

Vous pouvez commencer par créer une grande chaine de caractère message (en utilisant la somme des chaines de caractères pour ne pas les copier-coller toutes d'un coup).

In [0]:
 

Le seul indice dont vous disposez pour votre travail d'espion-ne est que le message est écrit en français sans accents, sans espaces et sans signes de ponctuation. Chaque lettre en clair correspond à une lettre cryptée

Et les linguistes (et les joueuses de scrabble) vous diront qu'en français la fréquence des lettres n'est pas du tout uniforme:

EASINTRLUODCPMVGFBQHXJYZKW
17,268,408,087,347,137,076,556,015,745,264,183,033,012,961,321,271,121,060,990,920,450,310,300,120,050,04

Les bigrammes les plus fréquents sont dans l'ordre décroissant :

ES DE LE EN RE NT ON ER TE EL AN SE ET LA AI IT ME OU EM IE



Quelle est la lettre la plus fréquente dans le message crypté ?

Vous pouvez commencer par tatonner. Ou bien vous pouvez faire une boucle pour afficher le nombre d'occurence (puis la fréquence)de chacune des 26 lettres de l'alphabet.

In [0]:
 
In [0]:
 

Essayez de remplacer la lettre la plus fréquente par des 'e' (minuscule pour bien voir la différence entre lettre cryptée et lettre en clair).

Comme les chaines de caractères sont immuables, c'est le moment d'utiliser les listes: message=list(message). Comme cela vous pouvez remplacer la la première lettre du message:

message[0]='m'

(oups je vous ai donné un indice).

Tiens, et pourquoi ne pas utiliser une liste pour se souvenir de la correspondance entre lettre cryptée et lettre en clair ?

In [0]:
 
In [0]: