Cette thèse est consacrée au problème de la vérification automatique des protocoles cryptographiques d'un point de vue logique et calculatoire.<br />Dans une première partie, nous abordons la sécurité des protocoles dans le cadre logique (formel). Nous montrons comment spécifier différentes propriétés de sécurité des protocoles (secret, authentification, <br />résistance aux attaques par dictionnaire) au moyen d'un langage de processus et comment les analyser de manière automatique pour un nombre borné de sessions.<br />La seconde partie traite de la justification cryptographique des modèles logiques. Nous nous intéressons ici à la notion d'équivalence statique, appliquée en particulier au chiffrement et aux données vulnérables aux attaques par dictionnaire (par ex. des mots de passe). Dans ce cadre, nous montrons que sous certaines conditions simples, toute preuve logique d'équivalence statique implique d'indistinguibilité cryptographique des données modélisées.

La vérification des protocoles cryptographiques assure qu'il n'existe pas d'attaque possible lors d'une exécution du protocole face à un certain intrus ou permet de trouver une attaque. Nous affaiblissons "l'hypothèse de chiffrement parfait" : le seul moyen d'obtenir le contenu d'un message chiffré est de connaître la clef de déchiffrement. Si un protocole est prouvé sûr sous cette hypothèse, cela est insuffisant pour assurer qu'une information confidentielle échangée sur le réseau grâce à un protocole cryptographique entre deux participants reste secrète. Un des moyens pour affaiblir cette hypothèse de chiffrement parfait est de prendre en compte certaines propriétés algébriques dans le modèle de vérification afin d'analyser de manière plus réaliste les protocoles. Nous développons une approche formelle pour la vérification de la propriété de secret d'information pour les protocoles cryptographiques en présence de théories équationnelles et de l'homomorphisme.

Il existe de nombreux démonstrateurs automatiques qui effectuent des raisonnements modulo une théorie équationnelle, c'est-à-dire enconsidérant non pas des termes, mais des classes d'équivalence de termes. En général, les travaux accomplis dans ce domaine ont pour but de concevoir des techniques pour faire de la déduction modulo une théorie particulière. Dans [Avenhaus & Plaisted, 2001], Jürgen Avenhaus et David Plaisted ont cherché à déterminer des techniques qui pourraient être employées dans le traitement non plus d'une théorie particulière, mais de toute une classe de théories équationnelles: les théories permutatives. Les auteurs ont introduit les notions de terme stratifié et d'ensemble stratifié, et décrit les procédures qui devraient être implémentées dans un démonstrateur automatique basé sur ces termes stratifiés. Les propriétés de régularité de ces théories font qu'il est possible d'employer des techniques efficaces de théorie algorithmique des groupes pour les traiter. Les auteurs espéraient que l'efficacité de ces techniques contrebalancerait le nombre élevé de clauses qui pourraient être générées dans un démonstrateur automatique basé sur ces termes stratifiés. Cependant, les algorithmes proposés pour faire de la déduction avec des termes stratifiés sont basés sur une énumération explicite des éléments des groupes, et sont donc exponentiels. Dans ce mémoire, nous développons les travaux d'Avenhaus et Plaisted, et modifions leur formalisme pour pouvoir faire l'usage le plus intensif possible des techniques de théorie algorithmique des groupes.