Comment casser un algorithme de cryptage?

En voici une excellente question! Juste avant d'y répondre je tiens à préciser une chose:
 

Ce chapitre va vous montrer les aspects purement théoriques de ces techniques. Elles sont expliquées ici à des fins d'études et de compréhension de la sécurité des chiffrements en informatique. Elles ne doivent jamais être réalisées pour causer du mal, la perte ou destruction de données sans s'y limiter. De plus la loi punis sévèrement toute violation de la vie privée!

Que cela soit clair: Nous ne vous donnerons pas les outils nécessaires permettant de réaliser des attaques sur un système de chiffrement. Nous aborderons juste les aspects théoriques!

Les conditions étant posées, je vous propose de continuer normalement ce tutoriel

Nous disions donc: mais comment certains arrivent-ils à trouver des failles de sécurité dans des algorithmes alors que c'est super compliqué? @_@

Et bien ils utilisent, la plupart du temps, ces techniques:

-L'analyse fréquentielle.
-Attaque par brute-force.
-Attaque par dictionnaire.
-Attaque par table arc-en-ciel.
-Le vol de clé.
-L'attaque de l'homme du milieu.

Et bien d'autres comme l'attaque par collisions, par pseudo-collisions, attaque par préimage, etc....
Cependant elles sont trop complexes pour être abordées dans ce cours qui était initialement prévu pour les personnes commençant la cryptographie.


Nous allons commencer des plus simples pour aller progressivement vers les plus poussées. Nous allons tout de suite partir voir ... l'analyse fréquentielle avec notre bon vieux chiffrement de César


L'analyse fréquentielle:


Comme son nom l'indique, l'analyse fréquentielle permet de trouver la clé de chiffrement de certains algorithmes juste en analysant la fréquence d'apparition des lettres dans le texte crypté.
Car il faut savoir que dans chaque langue, il y a des lettres que vous utiliserez plus que d'autre. Nous allons prendre, ici, l'exemple du français mais cette technique fonctionne pour n'importe quelle langue mais avec un nombre très petit d'algorithmes!

L'algorithme de César est faillible à cette technique, c'est pourquoi nous allons tenter de casser ce mot de passe:

gvierix
 

Bien sur n'essayez même pas de tenter la même chose avec un algorithme actuel comme le MD5 ou le RSA, sa ne servirait à rien

Passons au cassage du texte "gvierix".

Nous avons déjà un indice super important: le texte chiffré l'est avec le chiffrement de César.
Ce qui veut dire qu'il nous suffit d'avoir la clé (le nombre qui permet de décaler les lettres) pour pouvoir déchiffrer le texte.

Nous allons pour cela utiliser cet histogramme:
 

Source: wikipédia

On peut y voir très nettement que le "e" est en première place dans le niveau d'apparition, suivi de près par le "s", etc...


Regardons maintenant de plus près le texte à déchiffrer:
 

gvierix

On y voit que la lettre le plus présente est le "i". Or dans la langue française on s'aperçoit que la lettre la plus présente est le "e".

Nous pouvons donc en conclure que le "i" du texte chiffré est en réalité un "e"!

Cela nous donne donc

gveerex

Les lettres vertes sont les lettres connues alors que celles en rouges sont celles encore "chiffrées".

Il ne nous reste plus qu'à "calculer" combien il y a d'écart entre le "e" et le "i" dans leur position dans l'alphabet. Il y en a 4. Donc la clé de chiffrement est tout simplement 4.

Tenez, on va s'amuser à déchiffrer le restant du texte:

g - 4 = c

v - 4 = r

e - 4 = a

r - 4 = n

x - 4 = t

Ce qui nous donne:

Creanet
 

Pas si robuste que ça cet algorithme

Ici nous avons testé le cassage avec un seul mot mais cela n'aurait peut être pas été possible! Prenez cet exemple de mot chiffré qui figure dans la langue française:

rgvot

et bien essayez de le casser avec la méthode que nous venons de voir
 

.....................................
 

Vous n'y arrivez pas (ou vous n'avez pas cherché :P)?

C'est normal, car toutes les lettres de ce mot ne sont présente qu'une seul fois!

C'est pour cela que pour casser un algorithme de substitution mono-alphabétique (algorithme qui remplace une lettre par une autre lettre) le mieux est d'avoir une phrase ou deux minimum de chiffrées avec l'algorithme.

Voilà, nous en avons fini avec l'analyse fréquentielle, qui était la méthode la plus simple. Nous allons maintenant rentrer dans des méthodes plus .... subtiles.

Au programme du chapitre suivant, nous verrons comment casser un algorithme de chiffrement par l'attaque brute-force, l'attaque au dictionnaire et l'attaque par tables arc-en-ciel


PS: Pour ceux qui aimerais savoir le mot qui est chiffré derrière "rgvot" il s'agit du mot "lapin" chiffré avec une clé de 6 :P


                                                                                                                                     
                                                                                                                                          Suite
 

 

v