Aller au contenu
  • Société
    • Qui sommes-nous
    • Nos valeurs
    • Nos partenaires
    • Entreprise citoyenne
    • Régions
  • Services
    • Expertise
    • Formation
    • Développement
    • Migration
    • Infogérance
  • Join the Team
  • Actualités
  • Blog
    • Blog easyteam.fr
    • Blog Cloud Natives
  • Formations
  • Rugb’Easyteam
  • Contact
Menu
  • Société
    • Qui sommes-nous
    • Nos valeurs
    • Nos partenaires
    • Entreprise citoyenne
    • Régions
  • Services
    • Expertise
    • Formation
    • Développement
    • Migration
    • Infogérance
  • Join the Team
  • Actualités
  • Blog
    • Blog easyteam.fr
    • Blog Cloud Natives
  • Formations
  • Rugb’Easyteam
  • Contact
Inscrivez-vous à la newsletter

Inscrivez-vous à la newsletter

Abonnez-vous maintenant et nous vous tiendrons au courant.
Nous respectons votre vie privée. Vous pouvez vous désabonner à tout moment.

Bienvenue sur le Blog d'EASYTEAM (ex ArKZoYd)

  • Accueil
  • Actualités
  • Cloud
  • Infrastructure
  • Données / Sécurité
  • Intégration
  • Dev / DevOps
  • SAM / FinOps
Menu
  • Accueil
  • Actualités
  • Cloud
  • Infrastructure
  • Données / Sécurité
  • Intégration
  • Dev / DevOps
  • SAM / FinOps
  • le 03/07/2020
  • hatim amrani
  • Développement

Décryptage des textes avec chaînes de Markov

Partager sur linkedin
LinkedIn
Partager sur twitter
Twitter
Partager sur facebook
Facebook

Présentation

L’histoire du chiffrement des textes ne date pas d’aujourd’hui, puisque des recherches indiquent que 2000 ans avant J.C, les égyptiens ont employé des hiéroglyphes non conformes à la langue sur les pierres tombales, afin de masquer l’identité des morts. Au début, le cryptage et la cryptanalyse n’étaient l’affaire que des militaires, mais aujourd’hui, c’est devenu également le problème des banques, des informaticiens et on peut dire de pratiquement tout le monde, surtout avec le développement d’internet et tous ce qu’il engendre en termes de la protection de la vie privée.

 

Chiffrement Simple par décalage

Le but de cet exercice est de décrypter une phrase cryptée avec un chiffrement de César.
Ce chiffrement consiste à opérer un décalage sur les lettres de l’alphabet selon un pas donné. Pour un pas 2 on trouve par exemple : a ==> c et  w ==> y.
On crée alors une fonction (Dans un langage de programmation approprié) qui permet de faire toutes les permutations possibles.
Après avoir lancé toutes les permutations possibles, on retrouve la phase décryptée à partir de la phrase initialement cryptée.

Phrase cryptée : LD L CFWP, XPY HZCCJ XZCP LMZFE HSLE ESPJ NLYYZE DPP ESLY LMZFE HSLE ESPJ NLY. UFWTFD NLPDLC

Phrase décryptée: AS A RULE, MEN WORRY MORE ABOUT WHAT THEY CANNOT SEE THAN ABOUT WHAT THEY CAN. JULIUS CAESAR

Remarque : La méthode est assez simple puisque le nombre de cas à tester est petit (25 façons de chiffrer), on choisit ainsi le chiffrement qui donne un sens à la phrase (citation).

 

Chiffrement par permutation

Une méthode de chiffrement plus solide consiste à appliquer une permutation sur les lettres de l’alphabet. Avoir la clef du code c’est donc connaitre la permutation qui a été utilisée.
Afin de trouver toutes les permutations possibles on a besoin de 26! permutations. D’où l’impossibilité d’utiliser l’approche citée dans la partie précédente. Pour pallier ce problème, on simule des permutations avec des algorithmes de Monte Carlo et des chaînes de Markov (l’algorithme de Metropolis Hastings).

Pour implémenter cette méthode, nous avons besoin d’un texte assez long qui nous servira de base d’apprentissage. On s’intéresse aux fréquences d’apparition d’une lettre après une autre en calculant la matrice des fréquences d’apparition d’un symbole après l’autre (alphabet + espace). On essaie, avec ce calcul, d’avoir une matrice représentative de la langue de l’apparition d’un symbole après un autre.

Nous définissons après la vraisemblance d’un texte ‘w’, formé par la succession des caractère xi, comme suit :

L(w)=Π𝐴(𝑥𝑖,𝑥𝑖+1) , avec ‘A’ la matrice des fréquences d’apparition.

D’après l’écriture de cette vraisemblance, on peut déduire que plus un texte a une grande vraisemblance, plus il a de chance d’être un texte correct dans la langue en question. Donc notre objectif pour le décryptage serait de maximiser cette vraisemblance.

L’idée générale de l’algorithme et de partir d’une permutation aléatoire représentant l’état X0 pour la chaîne de Markov, et de simuler dans chaque itération une nouvelle permutation aléatoire,  et de l’accepter si elle permet d’améliorer la vraisemblance du texte traduit.

Après un certain nombre d’itérations, la vraisemblance devient stationnaire et maximale, car on n’accepte plus les nouvelles permutations. Ainsi, le chiffrement du texte est celui relatif à la dernière permutation acceptée par l’algorithme.

A noter que d’autres paramètres peuvent être ajoutés dans l’algorithme pour gagner en efficacité.

 

Conclusion

Les résultats obtenus nous montrent l’efficacité de l’utilisation des chaînes de Markov.
En effet, le décryptage par simulation donne le bon résultat après un nombre optimal d’itérations aux alentours de 3000 (Pour un texte d’environ ).

 

hatim amrani
hatim amrani
Voir tous ses articles
Partager sur linkedin
LinkedIn
Partager sur twitter
Twitter
Partager sur facebook
Facebook

Laisser un commentaire Annuler la réponse

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Les derniers articles

  • Oracle Database 18c : Clonage Point-In-Time de PDBs dans ASM 12/04/2021
  • Provisioning sur OCI : Utiliser Resource Manager (1/2) 05/04/2021
  • Chargement des données Météo depuis une API public ERA5 vers le Cloud AWS 02/04/2021
  • Coloriez et décoloriez vos ordres SQL Oracle 29/03/2021
  • Partie 1 : Architecture Google Kubernetes Engine (GKE) 22/03/2021

Les derniers commentaires

  • chaimaa dans Docker pour les débutants (Partie 1)
  • Guillaume dans [AWS] Coût d'une solution Serverless d'analyse vidéo temps réel
  • Ali Ait-Bachir dans Partie 1 : Architecture Google Kubernetes Engine (GKE)
  • zineb lidya dans Installer/désinstaller 10g en ligne de commande
  • PEDRO dans Contention du listener : Comment désactiver la notification ?
Espace Membres
Mot de passe perdu ?
EASYTEAM

Tour Nova, 71 Boulevard National,
92250 La Garenne-Colombes
Tél. 0800 40 60 40
contact@easyteam.fr

Facebook
Linkedin
Twitter
Navigation
  • Accueil
  • Qui sommes-nous
  • Entreprise citoyenne
  • Nos valeurs
  • Régions
  • Partenaires
  • Contact
  • Support
Menu
  • Accueil
  • Qui sommes-nous
  • Entreprise citoyenne
  • Nos valeurs
  • Régions
  • Partenaires
  • Contact
  • Support
Services
  • Développement
  • Migration
  • Infogérance
  • Expertise
  • Formation
Menu
  • Développement
  • Migration
  • Infogérance
  • Expertise
  • Formation
Blog
  • Cloud
  • Infrastructures
  • Data
  • Intégration
  • Dev / DevOps
  • SAM / FinOps
  • Applications
Menu
  • Cloud
  • Infrastructures
  • Data
  • Intégration
  • Dev / DevOps
  • SAM / FinOps
  • Applications
Copyright 2021 - EASYTEAM, Tous droits réservés
Mentions légales et Politique de confidentialité