[C] ALGORITHME BRUTE FORCE

cs_ptidiable

Messages postés: 16
Date d'inscription: dimanche 17 avril 2005
Statut: Membre
Dernière intervention: 21 mars 2007

- 21 mars 2007 à 08:31
MoonRaptorZ

Messages postés: 2
Date d'inscription: vendredi 21 octobre 2011
Statut: Membre
Dernière intervention: 21 octobre 2011

- 21 oct. 2011 à 17:44

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/41911-c-algorithme-brute-force

MoonRaptorZ

Messages postés: 2
Date d'inscription: vendredi 21 octobre 2011
Statut: Membre
Dernière intervention: 21 octobre 2011

21 oct. 2011 à 17:44

Je viens d'essayer ton code, il n'essaie pas toutes les combinaisons ! j'ai essayé avec 2 lettres et ça ne marche pas.

Voilà essaie de le corriger si tu peux ! ;o) sinon niveau vitesse c'est rapide !!

Zestyr

Messages postés: 466
Date d'inscription: mercredi 12 août 2009
Statut: Membre
Dernière intervention: 17 octobre 2011

24 févr. 2010 à 15:29

Salut,

Ca serait pas plus performant si on enregistrait toutes les possibilités dans un fichiers qu'on chargerait ensuite lorqu'on en aura besoin ?

Maintenant que le 4Go est aqui on pourrait dédier 2Go de mémoire à notre programme, ce qui nous permettrait de charger 100 millions de possibilités à la fois en imaginant que la chaine de caractères recherchée mesure pas plus de 20 octets !

Neo_Fr

Messages postés: 653
Date d'inscription: mardi 6 décembre 2005
Statut: Membre
Dernière intervention: 10 novembre 2014

2
8 mai 2007 à 12:27

Merci d'avoir corriger les bugs

BruNews

Messages postés: 21041
Date d'inscription: jeudi 23 janvier 2003
Statut: Modérateur
Dernière intervention: 21 août 2019

27
7 mai 2007 à 00:46

Me suis permis de réutiliser ton algo:
http://www.cppfrance.com/code.aspx?ID=42524
Voir comments en bas de source.

Neo_Fr

Messages postés: 653
Date d'inscription: mardi 6 décembre 2005
Statut: Membre
Dernière intervention: 10 novembre 2014

2
31 mars 2007 à 14:33

Merci de tes conseils lefauve,
- Pour les realloc je ne pensse pas qu'ils ralentissent vraiment
le prog etant donné que je l'appelle tres peu souvent, mais peut etre qu'un malloc, free a chaque fois serait plus rapide?

- J'ai légerement améliorer la boucle d'incrémmentation,
dès que je trouve un 0, je sort de la boucle...

- Que veut tu dire par "Tu aurais donc interet a calculer ce hash pendant que tu construis ta chaine." ?
Tu veut dire de faire la comparaison pendant la génération du mdp (a la place de printf), si c'est le cas c ce que j'ai fait

- Et sinon est-ce que tu pourrait m'expliquer l'histoire du tableau d'int, je vois vraiment pas comment je pourrais faire
pour récupérer le mdp "en clair" pour pouvoir le hasher ensuite.

Merci

LeFauve42

Messages postés: 239
Date d'inscription: vendredi 20 octobre 2006
Statut: Membre
Dernière intervention: 20 avril 2009

26 mars 2007 à 18:53

Salut,

C'est mignon ton code, mais je ne pense pas qu'en pratique ca permette de casser quelque chose de plus de 5 ou 6 caracteres dans un temps "raisonable" :o)

Ceci dit, c'est plutot bien ecrit.

Voici quelques astuces pour l'optimiser un peu:
- D'abord, les realloc() sont a proscrire. Dans ton cas tu ne l'appelles pas souvant, mais c'est tres couteux, et en plus tu n'en as pas besoin. Il te suffit d'allouer un buffer de taille max, et de le remplir de zeros et hop, tu peux l'utiliser pour toutes les tailles.
- Ta boucle de mise en cascade des retenues pourrait etre beaucoup optimisee: En effet, tu la parcours du dernier caractere au premier. C'est generalement une bonne habitude quand la valeur max est le resultat d'une fonction, mais ce n'est pas le cas ici. De plus, comme il s'agit d'une retenue, les valeurs ne changent pas aleatoirement. Je dirais meme que ce sera toujours uniquement les "n" premiers qui vont changer, mais des que tu arrives sur une case sans retenue, il n'est plus possible que d'autres cases changent.

Donc, au lieu de parcourir tout ton tableau, tu peux le parcourir en partant du debut uniquement tant qu'il y a des debordements (valeurs >= 107)

- Un autre truc qui ne gagnera rien en vitesse, mais tu devrais utiliser un truc genre sizeof(ALL)/sizeof(char) au lieu de 107 (eventuellement tu peux faire un #define) pour que ce soit plus lisible. Tu ne perds pas de temps car c'est calcule a la compilation

- Pour calculer la plupart des fonctions de hash, tu utilises les caracteres de ton mdp du premier au dernier. Tu aurais donc interet a calculer ce hash pendant que tu construis ta chaine. Si tu te debrouilles bien, tu peux stocker les valeurs intermediaires et les reutiliser (ex: apres avoir calcule hash('aaaaaaaaaa'), tu peux rapidement recalculer hash('aaaaaaaaab)').

Evidemment, ca rend le code beaucoup moins lisible, mais c'est aussi ca la force brute :o)

En fait, pour la plupart des trucs de hash, tu n'as pas besoin d'avoir ton mdp stocke en memoire sous forme claire. Ce qui peut te faire gagner du temps (mais du coup, ton prog d'exemple avec printf() ne serait plus possible). L'ideal serait d'avoir un tableau d'int au lieu de char. Ca prendrait plus de place, mais le proc adresserait alors des cases memoires multiples de 4 ce qui le ferait aller plus vite (les procs modernes n'aiment pas les adresses impaires).

Enfin, ce genre de progs est parmis les quelques programmes qui gagnent encore a etre ecris en assembleur, donc sorti de l'aspect "didactique", je te deconseillerais donc de l'utiliser dans le vrai monde.

Sinon pour repondre a ta question, tu ne gagnerais pas grand chose en faisant calculer les mdp par un thread et le hash par un autre.
L'ideal serait de couper le nombre de possibilites a tester en deux (ou plus si tu as plus de cores sur ton proc) et de donner a chaque thread une partie des calculs a effectuer.
Attention, sur un monocore, ca n'apportera rien, et ca prendra sans doute legerement plus de temps.

Comme tu affiches le temps, je suppose que tu as du noter les perfs de ton programme.
Je serais currieux de savoir combien l'optimisation de la boucle des retenues te fais gagner.

Bonne chance,
Eric

NB: Ca me rappelle ma jeunesse quand on se tappait la bourre pour les calculs de nombre premiers avec les potes :o)

Afficher les 20 commentaires