Développement et optimisation d’un système cryptographique basé sur les principes de décomposition et de NP-complétude de la théorie des graphes

Abstract

Dans le cadre du travail réalisé, nous nous sommes intéressés à la conception et au développement des nouvelles approches de sécurité informatique en s’appuyant sur les propriétés de la théorie des graphes. Dans ce contexte, différentes techniques développées dans la littérature souffrent de certaines lacunes selon la nature des données traitées, la précision, la robustesse et le temps de calcul. Dans ce travail, l’objectif principal porte sur l’intégration et l’exploitation des concepts liés à la théorie des graphes dans la conception des systèmes cryptographiques. Dans notre première contribution, nous avons proposé un nouveau système de chiffrement par blocs (BC-GT) qui met en jeu les concepts fondamentaux de la théorie des graphes afin de faciliter les manipulations des données brutes. Le principe s’articule sur la génération des graphes pondérés à partir d’un nouvel usage des circuits Hamiltoniens. Concernant la génération des sous-clés, nous avons fait appel à un générateur de sous-clés très particulier qui a été soigneusement conçu pour produire les clés de chiffrement conformément aux spécifications du système. Les résultats expérimentaux obtenus démontrent que notre système de chiffrement est robuste contre les attaques statistiques. Quant à la deuxième contribution, nous avons proposé une nouvelle variante améliorée du premier système. Notre proposition est en fait un nouveau système de chiffrement par blocs qui procède par la représentation des messages en clair à l’aide des circuits hamiltoniens disjoints, puis les traite sous forme d’une matrice d’adjacence dans une phase de pré-chiffrement. Les résultats expérimentaux obtenus démontrent que notre nouveau système de chiffrement est aussi robuste contre les attaques statistiques, à travers le test de DIEHARD, et présente à la fois une bonne confusion et diffusion.