Cet article est uneébauche concernant l’informatique.
Larecherche exhaustive ourecherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on consulte toutes les valeurs. Encryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette méthode.
Le principe de cet algorithme est d'essayer toutes les possibilités dans un intervalle. Un exemple courant est l'attaque par force brute des mots de passe. Si on sait que le mot de passe contient obligatoirement 4 chiffres, alors on essaie tous les nombres de 0000 à 9999 jusqu'à trouver le bon mot de passe.
Trouver A et B tels que pour unprédicat à deux arguments f la propriété f(A, B) soit vraie.
La recherche exhaustive est alors une méthode de recherche qui consiste à considérer l'ensemble des valeurs possibles pour A et B et à les tester toutes dans un ordre quelconque jusqu'à ce que la propriété soit vraie. Typiquement lesalgorithmes qui découvrentdynamiquement la structure des données pour optimiser leur calcul sont aussi considérés comme des algorithmes de recherche exhaustive. On peut citer SSS*,AlphaBeta, MinMax, A*,BackTrack, BackJump, BackMark, NC-AC(n), ForwardChecking…
Dans cette catégorie, on peut considérer que le terme « exhaustive » ne s'applique plus :
À supposer qu'il y a un problème et n variables dont il est possible d'obtenir une grandeur. Alors un objectif sera de découvrir les p variables significatives de ce problème. Pour cela, une des premièresméthodes de réalisation à envisager est la recherche exhaustive.
En effet, ce genre deproblème contient très souvent de nombreuses contraintes implicites liées à la structure propre du problème. Il suffit alors de construire l'hypergraphe descontraintes et en déduire les paramètres les plus influents. La méthode brutale la plus employée pour ce problème est la sélection séquentielle des p variables significatives. Cela consiste à entrainer un modèle sur une seule des n variables et d'ajouter unitairement celles restantes si et seulement si elles minimisent le score de perte tel que l'erreur quadratique moyenne pour une problématique de régression ou l'entropie croisée pour de la classification.
Cette recherche est très souvent réalisée enrobotique et entraitement automatique du langage naturel. Dans ces deux derniers, il est très courant que les contraintes soient entrées « à la main » via un expert. En effet, construire unprogramme qui découvre automatiquement les caractéristiques d'un robot ou d'une langue est très compliqué. Cependant, l'ordonnancement desparamètres les plus influents se fait souvent par recherche exhaustive sur des corpus obtenusempiriquement.
Attaque par force brute en cryptanalyse
