IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme de bruteforce


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2007
    Messages
    240
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2007
    Messages : 240
    Par défaut 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 :
    ~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 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  2. #2
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 60
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Par défaut
    Citation Envoyé par Amybond Voir le message
    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 :
    ~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.

  3. #3
    Membre éclairé
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2007
    Messages
    240
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2007
    Messages : 240
    Par défaut
    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

  4. #4
    Membre expérimenté Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Par défaut
    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.

  5. #5
    Membre éclairé
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2007
    Messages
    240
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2007
    Messages : 240
    Par défaut
    Ok merci à vous deux.

  6. #6
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    Citation Envoyé par Amybond Voir le message
    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
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  7. #7
    Membre éclairé
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2007
    Messages
    240
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2007
    Messages : 240
    Par défaut
    Ok merci, mais j'ai réussi à améliorer les temps de calcul :
    //~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
    ++

  8. #8
    Membre expérimenté Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme qui simule du bruteforcing.
    Par abdeljaouad dans le forum C
    Réponses: 3
    Dernier message: 28/04/2011, 20h03
  2. Algorithme de bruteforce
    Par sloshy dans le forum Général Python
    Réponses: 37
    Dernier message: 04/07/2010, 15h59
  3. Algorithme de randomisation ... ( Hasard ...? )
    Par Anonymous dans le forum Assembleur
    Réponses: 8
    Dernier message: 06/09/2002, 14h25
  4. Recherche de documentation complète en algorithmes
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 29/03/2002, 12h09
  5. Algorithme génétique
    Par Stephane.P_(dis Postef) dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/03/2002, 17h14

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo