Algorithme de bruteforce

Bonjour,
j'ai récemment programmé un algorithme "brute force" en C++ pour générer toutes les chaines possibles jusqu'à qu'il trouve celle voulue.
Cependant j'ai un problème, le temps pour la recherche est trop élevé :
Les données de temps :

Citation:

---

~0.0001 secondes pour trouver 9
~0.0014 secondes pour trouver 99
~0.0657 secondes pour trouver 999
2.84972 secondes pour trouver 9999
122.367 secondes pour trouver 99999
4922.98 secondes pour trouver 999999

---

Au dessus je n'ai pas encore réussi à avoir un résultat.

Je vais donc tenté de vous expliquer l'algorithme de ma création utilisé pour cela, tout cela sans communiquer de code car les modérateurs me l'ont formellement interdit :cry: dans le respect de la législation et des règles du forum.

Pour situer l'utilisation voici l'header de la classe (sans le code de brute force) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

class BruteForce { public: BruteForce(std::string scope = "abcdefghijklmnopqrstuvwxyz0123456789", std::string startCombination = "", int increaseEach = 1); ~BruteForce(); std::string GetNext(); // Call this method to get the next combination   private: std::string m_scope; std::string m_combination; vector<int> m_values; int m_increaseEach; };

---

Pour récupérer la combinaison suivante j'appelle donc GetNext(), grâce à une boucle, qui renvoie donc une chaine (par exemple : "aaz").


Algorithme :
J'utilise trois tableaux de variable, un tableau de caractères pouvant prendre tous les caractères du deuxième (le tableau des caractères à tester) et un troisième tableau de nombres qui sauvegarde la valeur (l'index) de chaque caractère de chaque emplacement de la chaine de caractère.

Ensuite dans "GetNext()", je boucle en partant de la dernière case de mon tableau de nombres et je l'incrémente si il ne dépasse pas le caractère maximal du tableau des caractères à tester, sinon je le remet à zéro et j'incrémente le suivant. Ceci jusqu'à la fin (tant que cela est nécessaire). Durant cette boucle, je vérifie si tous les caractères sont égaux à la valeur maximal du tableau des caractères à tester.
Une fois la boucle fini, si tous les caractères sont égaux à la valeur maximal du tableau des caractères à tester, je les remets tous à zéro et j'ajoute une case que je met, elle aussi, à zéro. (je pourrais générer la chaine en même que je boucle plus haut mais même avec cela, je ne pense pas que cela rendrait mon algorithme complètement optimisé)

Une fois cela fait je génère la chaine que je renvoi à la fin de "GetNext()".

Voila pour l'algorithme. J'ai précédemment cherché sur le net des codes, des algorithme, mais il sont rares et ceux que j'ai trouvé je n'ai pas réussi à comprendre leur fonctionnement et à les adapté à ma situation (appelé grâce à une boucle la fonction pour récupérer la prochaine valeur).


Je poste uniquement mon problème algorithmique, et ceci dans un but pédagogique pour progresser dans l'algorithmique et dans la sécurité informatique ainsi que dans des concepts mathématiques nouveau pour moi.

Je vous remercie donc pour l'aide que vous pourrez m'apporter ainsi que pour le temps que vous avez consacré à la lecture de ces lignes.

Merci d'avance.

Citation:

---

Envoyé par Amybond

Bonjour,
j'ai récemment programmé un algorithme "brute force" en C++ pour générer toutes les chaines possibles jusqu'à qu'il trouve celle voulue.
Cependant j'ai un problème, le temps pour la recherche est trop élevé :
Les données de temps :

Citation:

---

~0.0001 secondes pour trouver 9
~0.0014 secondes pour trouver 99
~0.0657 secondes pour trouver 999
2.84972 secondes pour trouver 9999
122.367 secondes pour trouver 99999
4922.98 secondes pour trouver 999999

---

Au dessus je n'ai pas encore réussi à avoir un résultat.

---

Te rends-tu compte que c'est justement le problème des algorithmes qui utilisent la force brute ?

Pour obtenir 999 999 tu as du testé une combinaison de 6 caractères à 36 possibilités chaque, soit 2 176 782 336 possibilités au total. En considérant que chaque possibilité te coûte 2 millionièmes de secondes, tout tester te coûte 4353,564672 secondes.

Rien d'étonnant dans tes résultats donc.

Ton algorithme se comporte normalement : il est complètement inefficace par nature. Si tu veux mieux, tu ne peux passer par la force brute qui énumère tout. Tu dois faire des stratégies de recherches, réduire ton alphabet, etc. C'est-à-dire ce qu'on fait en cryptanalyse.

Pourtant j'ai testé en parallèles un autre algorithme de bruteforce (qui n'es pas de moi) et celui ci etait à vue d'oeils plus rapide (seulement 756 secondes pour trouver une chaine de 6 caractères "999999")

Comment cela ?
Pourrais tu m'en dire plus stp ? M'orienter vers des tutoriels ?

Merci d'avance

Bonjour,

Comme l'a dit Garulfo, tu ne peux pas obtenir de biens meilleurs résultats par brute-force.
L'algo plus rapide que tu as trouvé ne le sera probablement plus pour des chaines encore plus longues et plus diversifiées.

Une solution est donc en cryptanalyse, la méthode du dictionnaire en complément de la force brute car cette méthode ne marche que lorsque le mot de passe utilisé pour le chiffrement est contenu dans le dictionnaire.

Ok merci à vous deux.

Bonjour,

Citation:

---

Envoyé par Amybond

Comment cela ?
Pourrais tu m'en dire plus stp ? M'orienter vers des tutoriels ?

---

rien ne dit que cela provienne de l'algorithme lui même. C'est peut être certaines couches natives et autres optimisations.
De toute façon comme on vient de te l'expliquer, le bruteforce n'a pas d'avenir car sinon la cryptographie n'existerait pas ;)

Ok merci, mais j'ai réussi à améliorer les temps de calcul :

Citation:

---

//~0.0002 seconds to find 9 : Divised by 0.5
//~0.0007 seconds to find 99 : Divised by 2
//~0.0181 seconds to find 999 : Divised by ~3.63
//0.63311 seconds to find 9999 : Divised by ~4.5
//22.6032 seconds to find 99999 : Divised by ~5.41
//831.549 seconds to find 999999 : Divised by ~5.92

---

++

tu peux toujours améliorer de quelques milisecondes mais cela reste une complexité exponentielle ;) plus ton code à déchiffrer sera long ou composé de caractère spéciaux, plus ce sera long