M1 Cryptographie TD1 -- Exercice 2

On commence par lire tout le fichier sous forme d'une chaîne :

In [1]:
s = open('poly.txt').read()

On élimine les caractères non alphabétiques ...

In [2]:
t = ''.join([x for x in s if x.isalpha()])
In [3]:
print t[:80]
AEILBGASNNDUGRJZEKRLHGWPINTUQRKMVZJZFRVMSEGPPHWDCPUPQUAIRWXJSAKIAMJCSEKMOYPVIGUS

On code une petite fonction pour compter les occurences des lettres ..

In [4]:
def stats(w): 
    return {x:w.count(x) for x in set(w)}

... et une autre pour calculer l'indice de coincidence :

In [5]:
def ic(w):
    d = stats(w)
    n = float(sum([d[x] for x in d]))
    return sum(d[x]*(d[x]-1) for x in d)/(n*(n-1))

Comme dit explicitement dans le cours, pour trouver la longueur de la clef, le plus simple est de regarder les indices de coïncidence des chaines obtenues en prenant un caractère sur $k$ pour $k=2,3,4,\ldots$.

In [6]:
for i in range(2,25): print i, ic(t[::i])
2 0.0495057405422
3 0.0428588774946
4 0.0590089836995
5 0.0421831771329
6 0.0491834519891
7 0.0422746898399
8 0.077400883888
9 0.0432206642733
10 0.0482526432944
11 0.0432811656773
12 0.0530741482966
13 0.0441478826747
14 0.0470135043446
15 0.0410025062657
16 0.0794438502674
17 0.0453901622457
18 0.0477405115959
19 0.0433393610609
20 0.0593088071349
21 0.0423260949577
22 0.05058177117
23 0.0415561450044
24 0.0666024096386

La longueur de la clef est probablement celle qui donne la valeur la plus élevée, proche de celle du langage naturel. Ici, 8, 16 et 24 se ditinguent clairement. On essaie 8. On est donc ramené à 8 fois "Jules César". On suppose que dans chaque sous-chaîne t[i::8], la lettre la plus fréquente est le 'E' (si ça ne marche pas, on essaie avec la suivante).

Codons une petite fonction extrayant la lettre la plus fréquente d'un dictionnaire d'occurences :

In [7]:
def most_freq(d):
    dd = d.items()
    dd.sort(lambda x,y: y[1]-x[1])
    return dd[0][0]

K = [most_freq(stats(t[i::8])) for i in range(8)]
print K
['E', 'P', 'T', 'L', 'S', 'R', 'W', 'I']

Pour avoir la clef, il faut calculer les décalages (on voit que la première lettre de la clef doit être un A, puisque E est codé E.

In [8]:
K = ''.join([chr(ord(x)-ord('E')+ord('A')) for x in K])
K
Out[8]:
'ALPHONSE'

Il ne reste plus qu'à coder le système Vigenère (une version simple supposant que tout est en majuscules sans espaces ni ponctuation).

In [9]:
class Vigenere:
    def __init__(self,key):
        self.K = map(ord, key)
        self.m = len(self.K)
        
    def crypt(self, w):
        return("".join(
            [chr( ((ord(w[i])-65 +self.K[i%self.m]-65) % 26) +65)
                       for i in range(0,len(w))]))
    def uncrypt(self, w):
        return("".join(
            [chr( ((ord(w[i])-65 -self.K[i%self.m]-65) % 26) +65)
                       for i in range(0,len(w))]))

On crée une instance avec notre clef candidate (très plausible !)

In [10]:
v = Vigenere(K)

Et on déchiffre, en prenant soin de remettre la ponctuation en place ...

In [11]:
u = v.uncrypt(t)
texte=[]
i=0
for x in s:
    if x.isalpha():
        texte.append(u[i])
        i+=1
    else: texte.append(x)
texte = ''.join(texte)
print texte.lower()
--- attention : conservez cette licence si vous redistribuez ce fichier ---
license abu
-=-=-=-=-=-
version 1.1, aout 1999

copyright (c) 1999 association de bibliophiles universels
   http://abu.cnam.fr/
   abu@cnam.fr

la base de textes de l'association des bibliophiles universels (abu)
est une oeuvre de compilation, elle peut etre copiee, diffusee et
modifiee dans les conditions suivantes :

1.  toute copie a des fins privees, a des fins d'illustration de l'enseignement
    ou de recherche scientifique est autorisee.

2.  toute diffusion ou inclusion dans une autre oeuvre doit

     a) soit inclure la presente licence s'appliquant a l'ensemble de la
        diffusion ou de l'oeuvre derivee.

     b) soit permettre aux beneficiaires de cette diffusion ou de cette
        oeuvre derivee d'en extraire facilement et gratuitement une version
        numerisee de chaque texte inclu, muni de la presente licence.  cette
        possibilite doit etre mentionnee explicitement et de facon claire,
        ainsi que le fait que la presente notice s'applique aux documents
        extraits.

     c) permettre aux beneficiaires de cette diffusion ou de cette
        oeuvre derivee d'en extraire facilement et gratuitement la version
        numerisee originale, munie le cas echeant des ameliorations visees au
        paragraphe 6, si elles sont presentent dans la diffusion ou la nouvelle
        oeuvre. cette possibilite doit etre mentionnee explicitement et de
        facon claire, ainsi que le fait que la presente notice s'applique aux
        documents extraits.

   dans tous les autres cas, la presente licence sera reputee s'appliquer
   a l'ensemble de la diffusion ou de l'oeuvre derivee.


3. l'en-tete qui accompagne chaque fichier doit etre integralement 
   conservee au sein de la copie.

4. la mention du producteur original doit etre conservee, ainsi
   que celle des contributeurs ulterieurs.

5. toute modification ulterieure, par correction d'erreurs,
   additions de variantes, mise en forme dans un autre format, ou autre,
   doit etre indiquee.  l'indication des diverses contributions devra etre
   aussi precise que possible, et datee.

6. ce copyright s'applique obligatoirement a toute amelioration
   par simple correction d'erreurs ou d'oublis mineurs (orthographe,
   phrase manquante, ...), c'est-a-dire ne correspondant pas a
   l'adjonction d'une autre variante connue du texte, qui devra donc
   comporter la presente notice.

----------------------- fin de la licence abu --------------------------------

--- attention : conservez cet en-tete si vous redistribuez ce fichier ---
<ident tordre>
<ident_auteurs allaisa>
<ident_copistes thiriets>
<archive http://abu.cnam.fr/>
<version 1>
<droits 0>
<titre a se tordre>
<genre prose>
<auteur allais, alphonse>
<copiste serge thiriet>
<notesprod>
</notesprod>
----------------------- fin de l'en-tete --------------------------------

------------------------- debut du fichier tordre1 --------------------------------

a se tordre
histoires chatnoiresques
aphonse allais
(1891)

un philosophe

je m'etais pris d'une profonde sympathie pour ce grand flemmard de gabelou que me semblait l'image meme de la douane, non pas de la douane tracassiere des frontieres terriennes, mais de la bonne douane flaneuse et contemplative des falaises et des greves.
son nom etait pascal ; or, il aurait du s'appeler baptiste, tant il apportait de douce quietude a accomplir tous les actes de sa vie.
et c'etait plaisir de le voir, les mains derriere le dos, trainer lentement ses trois heures de faction sur les quais, de preference ceux ou ne s'amarraient que des barques hors d'usage et des yachts desarmes.
aussitot son service termine, vite pascal abandonnait son pantalon bleu et sa tunique verte pour enfiler une cotte de toile et une longue blouse a laquelle des coups de soleil sans nombre et des averses diluviennes (peut-etre meme antediluviennes) avaient donne ce ton special qu'on ne trouve que sur le dos des pecheurs a la ligne. car pascal pechait a la ligne, comme feu monseigneur le prince de ligne lui-meme.
pas un homme comme lui pour connaitre les bons coins dans les bassins et appater judicieusement, avec du ver de terre, de la crevette cuite, de la crevette crue ou toute autre nourriture traitresse.
obligeant, avec cela, et ne refusant jamais ses conseils aux debutants. aussi avions-nous lie rapidement connaissance tous deux.
une chose m'intriguait chez lui c'etait l'espece de petite classe qu'il trainait chaque jour a ses cotes trois garcons et deux filles, tous differents de visage et d'age.
ses enfants ? non, car le plus petit air de famille ne se remarquait sur leur physionomie. alors, sans doute, des petits voisins.
pascal installait les cinq momes avec une grande sollicitude, le plus jeune tout pres de lui, l'aine a l'autre bout.
et tout ce petit monde se mettait a pecher comme des hommes, avec un serieux si comique que je ne pouvais les regarder sans rire.
ce qui m'amusait beaucoup aussi, c'est la facon dont pascal designait chacun des gosses.
au lieu de leur donner leur nom de bapteme, comme cela se pratique generalement, eugene, victor ou emile, il leur attribuait une profession ou une nationalite.
il y avait le sous-inspecteur, la norvegienne, le courtier, l'assureur, et monsieur l'abbe.
le sous-inspecteur etait l'aine, et monsieur l'abbe le plus petit.
les enfants, d'ailleurs, semblaient habitues a ces designations, et quand pascal disait : " sous-inspecteur, va me chercher quatre sous de tabac ", le sous-inspecteur se levait gravement et accomplissait sa mission sans le moindre etonnement.
un jour, me promenant sur la greve, je rencontrai mon ami pascal en faction, les bras croises, la carabine en bandouliere, et contemplant melancoliquement le soleil tout pret a se coucher, la-bas, dans la mer.
- un joli spectacle, pascal !
- superbe ! on ne s'en lasserait jamais.
- seriez-vous poete ?
- ma foi ! non ; je ne suis qu'un simple gabelou, mais ca n'empeche pas d'admirer la nature.
brave pascal ! nous causames longuement et j'appris enfin l'origine des appellations bizarres dont il affublait ses jeunes camarades de peche.
- quand j'ai epouse ma femme, elle etait bonne chez le sous-inspecteur des douanes. c'est meme lui qui m'a engage a l'epouser. il savait bien ce qu'il faisait, le bougre, car six mois apres elle accouchait de notre aine, celui que j'appelle le sous-inspecteur, comme de juste. l'annee suivante, ma femme avait une petite fille qui ressemblait tellement a un grand jeune homme norvegien dont elle faisait le menage, que je n'eus pas une minute de doute. celle-la, c'est la norvegienne. et puis, tous les ans, ca a continue. non pas que ma femme soit plus devergondee qu'une autre, mais elle a trop bon coeur. des natures comme ca, ca ne sait pas refuser. bref, j'ai sept enfants, et il n'y a que le dernier qui soit de moi.
- et celui-la, vous l'appelez le douanier, je suppose ?
- non, je l'appelle le cocu, c'est plus gentil.
l'hiver arrivait ; je dus quitter houlbec, non sans faire de touchants adieux a mon ami pascal et a tous ses petits fonctionnaires. je leur offris meme de menus cadeaux qui les comblerent de joie.
l'annee suivante, je revins a houlbec pour y passer l'ete.
le jour meme de mon arrivee, je rencontrais la norvegienne, en train de faire des commissions.
ce qu'elle etait devenue jolie, cette petite norvegienne !
avec ses grands yeux verts de mer et ses cheveux d'or pale, elle semblait une de ces fees blondes des legendes scandinaves. elle me reconnut et courut a moi. 
je l'embrassai : 
- bonjour, norvegienne, comment vas-tu ? 
- ca va bien, monsieur, je vous remercie. 
- et ton papa ? 
- il va bien, monsieur, je vous remercie. 
- et ta maman, ta petite soeur, tes petits freres ? 
- tout le monde va bien, monsieur, je vous remercie. le cocu a eu la rougeole cet hiver, mais il est tout a fait gueri maintenant... et puis, la semaine derniere, maman a accouche d'un petit juge de paix.



In [11]: