Crack-wifi.com FORUM

LE FORUM DU SITE

Wifi, Backtrack, crack WEP et WPA...

Vous n'êtes pas identifié(e).  

Annonce

Visitez la boutique Wifi-highpower.com, votre revendeur agr Alfa Network: du matriel Wifi slectionn, cartes Wifi USB Awus036h et Awus036nh, antennes omnis, yagis, panel, amplis wifi, accessoires...

#1 10-12-2011 23:44:59

antares145
Membre d'honneur
Inscription : 29-09-2009
Messages : 5 199
Site Web

Appel à compétences : codage en C (ou C++ ou Python)

Salut à tous !

Bon, chacun son truc, et moi la programmation rigoureuse en C c'est pas mon truc tongue
Pour un projet, j'ai besoin d'une fonction en C qui a les spécifications suivantes :
- entrée = chaîne ASCII (ou char array), d'une longueur N comprise entre 8 et 63 caractères
- sortie = char array (ou buffer) de longueur 8*N, qui est la représentation binaire de la chaîne d'entrée (chaque caractère d'entrée converti en 8 caractères 0 ou 1)

Exemple : "ABC" => "010000010100001001000011"

Je sais qu'il faut jouer avec les conversions et les pointeurs, mais c'est très loin pour moi tout ça (surtout les pointeurs). Une façon de faire est sans doute de calculer la représentation binaire d'un caractère à la fois et d'ajouter le résultat à un buffer (qui, au final, pointera vers la chaîne complète), mais s'il y a une façon plus optimisée de faire je dis tant mieux smile

Pourquoi du C et pas du C++ ou du Python ? L'objectif est la performance pure, donc je préfère un langage le plus bas-niveau possible. Évidemment, si quelqu'un a une implémentation en C++ (ou en Python, en Ruby,...) je prends aussi, la seule que j'ai pour l'instant est en Octave et c'est pas génial... hmm

Maintenant, la question que tout le monde se pose : pourquoi tout ceci ? Le but est d'intégrer ça à un programme qui est capable de calculer (enfin, estimer) la complexité d'une chaîne de caractères. Le programme en question permettrait de filtrer des clés WPA aléatoires pour éliminer les clés genre "aaaaaaaaa" qui ont une complexité faible.
Par extension, on peut calculer la complexité moyenne des clés WPA dont on dispose déjà (par exemple la liste des clés Livebox qu'on a récoltées pour d'autres projets) pour voir quelle est la complexité moyenne, et ne garder que les clés qui ont une complexité similaire smile
Pour que ça soit efficace, il faut pouvoir coupler ça à un bon générateur, comme Crunch ou le LiveBoxGenerator, qui sont capables de générer plusieurs milliers de clés par seconde. Si le filtre est trop lent, on perd tout l'avantage du générateur wink

Messieurs, à vos claviers !

PS : j'ai déjà le reste du code en C, je le publierai une fois qu'il sera complet

Hors Ligne

Annonce

Visitez la boutique Wifi-highpower.com, votre revendeur agr Alfa Network: du matriel Wifi slectionn, cartes Wifi USB Awus036h et Awus036nh, antennes omnis, yagis, panel, amplis wifi, accessoires...

#2 16-12-2011 20:37:57

antares145
Membre d'honneur
Inscription : 29-09-2009
Messages : 5 199
Site Web

Re : Appel à compétences : codage en C (ou C++ ou Python)

Bon, la question n'a pas l'air de susciter un enthousiasme débordant big_smile
En même temps ça se comprend, coder en C pur c'est tellement has been...

Voilà le reste de mon code si quelqu'un est intéressé, je n'aurai pas le temps d'y travailler à court ni moyen terme. Je n'ai pas beaucoup de mérite sur ce coup-là, j'ai juste adapté le code proposé ici smile
--> Kolmogorov Complexity - Matlab File Exchange

// Source : http://www.mathworks.com/matlabcentral/fileexchange/6886
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


int main(void){
char s[208];
scanf("%s", s );
//char s[]="0011000100110001010001100100010100110101010001010100010101000101001101110100010100110001001101110011010000110011001101000011001000110011001101010011001000111001001101000011001001000011010001000011011000111001";
int n=strlen(s);
int c=1;
int l=1;

int i=0;
int k=1;
int k_max=1;
int stop=0;

while (stop==0)
{
	if (s[i+k-1]!=s[l+k-1])
	{
        	if (k>k_max)
		{
            		k_max=k;
        	}
        	i=i+1;
        
	        if (i==l)
		{
        		c=c+1;
        		l=l+k_max;
        		if (l+1>n)
			{
        			stop=1;
			}
                    	else
			{
        	        	i=0;
                		k=1;
                		k_max=1;
             	    	}
		}
        	else
		{
            		k=1;
        	}
	}
	else
	{
        	k=k+1;
        	if (l+k>n)
		{
            		c=c+1;
            		stop=1;
        	}
	}
}
float b=n/log2f(n);
float complexity=c/b;
printf("Complexité : %d\n",complexity);
return 0;
}

Il se compile avec la commande [c]gcc complexity.c -lm -Wall -o complexity[/c] (le -lm est obligatoire à cause du logarithme) et il s'exécute de la façon suivante :

echo 0011000100110001010001100100010100110101010001010100010101000101001101110100010100110001001101110011010000110011001101000011001000110011001101010011001000111001001101000011001001000011010001000011011000111001 | ./complexity

(on peut aussi décommenter la séquence d'exemple dans le code)

Pour ceux qui connaissent le Matlab, voilà le programme équivalent en Octave (plus abouti mais beaucoup trop lent). Il faudra installer Octave pour le lancer (paquet octave-3.0)

#!/usr/bin/octave -q

% Fonction annexe, cfr. ligne 64 pour le code de base

%==========================================================================
% FUNCTION: kolmogorov.m
% DATE: 9th Feb 2005
% AUTHOR: Stephen Faul ([email protected])
%
% Function for estimating the Kolmogorov Complexity as per:
% "Easily Calculable Measure for the Complexity of Spatiotemporal Patterns"
% by F Kaspar and HG Schuster, Physical Review A, vol 36, num 2 pg 842
%
% Input is a digital string, so conversion from signal to a digital stream
% must be carried out a priori
function complexity=kolmogorov(s);
n=length(s);
c=1;
l=1;

i=0;
k=1;
k_max=1;
stop=0;
bla=0;

while stop==0
	if s(i+k)~=s(l+k)
	bla=bla+1;
        	if k>k_max
            		k_max=k;
        	end
        	i=i+1;
        
	        if i==l
        		c=c+1;
        		l=l+k_max;
        		if l+1>n
        			stop=1;
                    	else
        	        	i=0;
                		k=1;
                		k_max=1;
             	    	end
        	else
            		k=1;
        	end
	else
        	k=k+1;
        	if l+k>n
            		c=c+1;
            		stop=1;
        	end
	end
end

b=n/log2(n);
% a la Lempel and Ziv (IEEE trans inf theory it-22, 75 (1976), 
% h(n)=c(n)/b(n) where c(n) is the kolmogorov complexity
% and h(n) is a normalised measure of complexity.
complexity=c/b;
endfunction
%==============================================================

% Fonction principale
% Paramètres
source = "stdin";	% "file" ou "stdin"
infile = "target.txt";	% fichier contenant les clés si la source est "file"
outfile = "resultat.txt";	% fichier dans lequel le résultat sera sauvé

format long	% pour afficher + de décimales
switch (source)
	case "file"
		fid = fopen(infile, "r"); 
		% On lit le fichier d'entrée ligne par ligne pour construire la variable "keys"		
		keys=[];
		while( !feof(fid)) 
			keys=[keys;fscanf(fid,'%s\n',"C")];
		endwhile
		for i=1:size(keys,1)
			% On prend chaque clé ASCII et on convertit chaque caractère en binaire (en passant par son code ASCII)
			sBin=dec2bin(toascii(keys(i,:)),8);
			% On regroupe tout sous la forme d'une seule séquence continue de 0 et 1
			seq=reshape(sBin',1,prod(size(sBin)));
			% On calcule la complexité à l'aide de la fonction annexe
			C(i)=kolmogorov(seq);
		endfor
		if length(C) > 1
			fprintf("[%s] Moyenne : %1.4f, variance : %1.4f, min : %1.4f, max : %1.4f",infile,mean(C),var(C),min(C),max(C));
		else
			fprintf("Complexité : %1.6f\n",C);
		endif
	case "stdin"
		key=fscanf(stdin,'%s\n',"C");
		% On prend la séquence ASCII d'entrée et on convertit chaque caractère en binaire (en passant par son code ASCII)
		sBin=dec2bin(toascii(key),8);
		% On regroupe tout sous la forme d'une seule séquence continue de 0 et de 1
		seq=reshape(sBin',1,prod(size(sBin)));
		% On calcule la complexité à l'aide de la fonction annexe
		C=kolmogorov(seq);
		fprintf("Complexité : %1.6f\n",C);
endswitch
% On sauve la variable C (qui contient les valeurs de complexité) dans le fichier "outfile"
save("-text",outfile,"C");
% Fin du code

On sauve tout ceci dans un fichier "complexity.sh", on le rend exécutable (chmod +x complexity.sh) et suivant les réglages spécifiés dans le code, soit on lui envoie une séquence ASCII soit on l'appelle sans argument (le fichier source est alors précisé dans le code)

Voilà, maintenant vous savez tout, si quelqu'un est chaud pour réécrire ça en Python on peut voir ce que ça vaut, mais je reste convaincu qu'il faut une implémentation en C si on veut que le temps d’exécution reste raisonnable...

Bon amusement smile

Hors Ligne

#3 16-12-2011 21:43:38

noireaude
Membre d'honneur
Lieu : Chez le docteur
Inscription : 12-03-2010
Messages : 2 362
Site Web

Re : Appel à compétences : codage en C (ou C++ ou Python)

Je t'aurais bien aidé mais j'y capte rien en C, ni même en Python sad


L’écureuil conserve les noisettes par instinct et non par représentation, sans cela il aurait déjà bâti des congélateurs à noisettes. Karl Marx : 1818 - 1883

Ma seule certitude est d'être dans le doute. Pierre Desproges : 1939 - 1988  @lavachelibre

Hors Ligne

#4 17-12-2011 00:01:55

Squaks
Membre Irremplaçable
Inscription : 18-06-2009
Messages : 974

Re : Appel à compétences : codage en C (ou C++ ou Python)

Je vais essayer de jeter un coup d’œil d'ici lundi wink


Sharkoff

Hors Ligne

#5 17-12-2011 12:05:10

faptiem
Membre Indéboulonnable
Inscription : 29-04-2010
Messages : 127

Re : Appel à compétences : codage en C (ou C++ ou Python)

Salut, après une absence prolongée je n'avais pas vu ce post, je ne te promets rien car je suis assez débordé mais je vais essayer de consacrer un peu de temps à cette fonction.

Hors Ligne

#6 17-12-2011 17:41:39

faptiem
Membre Indéboulonnable
Inscription : 29-04-2010
Messages : 127

Re : Appel à compétences : codage en C (ou C++ ou Python)

Voilà le programme ci joint, il est pas vraiment optimisé car écrit de façon "éducative" mais a des performances pas trop dégueulasses :

real	0m0.003s
user	0m0.004s
sys	0m0.000s

pour une entrée de 63 caractères.

Code :

/* 
* realisé par faptiem pour le forum Crack-Wifi 
* se compile avec : gcc -lm -c -ansi -pedantic -W -Wall -Werror -g3 *.c 
* se link avec : gcc -lm *.o 
* indication sur les performances : time ./a.out
* le main n'est là qu'en guise de test
*/


#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char* getsinglebinary(char input);
char* binaryconv(char* in);

int main (void)
{
  char input[] ="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
  char* output = binaryconv(input);
  
  printf("valeur retournée :%s pour la chaine %s de taille %d\n",output, input ,strlen(input));
  
  free(output);
  
  return 0;
}

char* binaryconv(char* in)
{
  char* out;
  char* dizaine;
  char* unite;
  char valhexa[3];
  unsigned int i = 0;

  out = malloc(8*strlen(in)*sizeof(char));
  memset(out,0,8*strlen(in)*sizeof(char));
  memset(valhexa,0,3);

  if ((out == NULL) || (strlen(in) <= 0))
    return NULL;
  
  for (i = 0; i < strlen(in); i++)
  {
    /* recuperation valeur hexa */
    
    sprintf(valhexa,"%x",in[i]); 
  
    /* conversion de ces valeurs une par une */
    
    dizaine = getsinglebinary(valhexa[0]);
    unite = getsinglebinary(valhexa[1]);
    
    /* stockage dans le buffer de sortie */
    
    strcat(out,dizaine);
    strcat(out,unite);
    
    free(dizaine);
    free(unite);
  }
  
  return out;
}


char* getsinglebinary(char input)
{
  int i = 0;
  int temp = 0;
  int calculval = 0;
  char test = 0;
  char* returnvalue;


  returnvalue = malloc(5*sizeof(char));
  memset(returnvalue,0,5);
  
  /* conversion du caractere d'entree en valeur numérique correspondant à de l'hexa */
  
  if((input >= '0') && (input <= '9')) 
    calculval = atoi(&input);
  
  else if (input == 'a')
    calculval = 10;
  
  else if (input == 'b')
    calculval = 11;
  
  else if (input == 'c')
    calculval = 12;
  
  else if (input == 'd')
    calculval = 13;
    
  else if (input == 'e')
    calculval = 14;

  else if (input == 'f')
    calculval = 15;
  
  else
    return NULL;
  
  /* conversion du caractere en binaire grace a la valeur tiree precedemment */
  
  for (i = 3; i>=0; i--)
  {
    temp = calculval/(pow(2,i));
    sprintf(&test,"%d",temp);
    calculval -= (temp*(pow(2,i)));
    strcat(returnvalue,&test);
  }
  return returnvalue;
}

Edit : si tu as besoin de plus de performance / moins d'utilisation mémoire fait le savoir. De plus je suis ouvert à vos commentaires sur le code pour ceux qui s'y intéressent, j'ai écrit cela rapidement donc ce n'est pas parfait.

Dernière modification par faptiem (17-12-2011 18:05:31)

Hors Ligne

#7 24-12-2011 12:59:11

antares145
Membre d'honneur
Inscription : 29-09-2009
Messages : 5 199
Site Web

Re : Appel à compétences : codage en C (ou C++ ou Python)

Damn, j'avais oublié de te répondre, honte à moi ! pam

Merci pour la fonction, je vais essayer d'intégrer ça au reste pour voir ce que ça donne au niveau des performances. Je pense qu'il y a moyen de faire plus efficace pour [c]getsinglebinary[/c], ne fut-ce qu'avec un switch/case, mais la base est bonne.

De même, au niveau du code, on pourrait virer l'étape de normalisation avec le logarithme, c'est juste pour avoir une valeur rigoureuse de la complexité mais on en a pas besoin dans notre application. C'est toujours ça de gagné en temps processeur big_smile

Hors Ligne

#8 24-12-2011 14:02:50

faptiem
Membre Indéboulonnable
Inscription : 29-04-2010
Messages : 127

Re : Appel à compétences : codage en C (ou C++ ou Python)

Étant donné le nombre réduit d'éléments dans le if/else le passage à un switch/case sera, de mon avis, négligeable en termes de performance !
Je n'ai pas eu le courage de décortiquer ton code (trop de if etc imbriqués sans fonction intermédiaire c'est illisible big_smile) mais si tu veux VRAIMENT gagner de la performance une chose très simple est réalisable : ciao les scanf printf etc et bonjour les appels systèmes read et write !

Hors Ligne

#9 24-12-2011 14:11:41

antares145
Membre d'honneur
Inscription : 29-09-2009
Messages : 5 199
Site Web

Re : Appel à compétences : codage en C (ou C++ ou Python)

Alors ce n'est pas "mon" code mais une fonction que j'ai récupérée et que je n'ai pas cherché à comprendre non plus (par contre j'en ai ch*é pour mettre les accolades au bon endroit) big_smile

Le scanf est là pour lire l'entrée standard, je ne connais pas ses performances mais il y a moyen de faire plus rapide pour lire stdin via un "read"? Le but est de pouvoir piper directement un générateur vers le filtre ici sans devoir passer par l'écriture d'un fichier (qui pénaliserait l'ensemble, surtout si on ne peut pas le faire en RAM)...

[EDIT] Il semble que oui --> read (C System Call) - Code Wiki

Hors Ligne

#10 24-12-2011 15:13:22

koala
Membre d'honneur
Lieu : In the sky
Inscription : 03-09-2010
Messages : 2 316

Re : Appel à compétences : codage en C (ou C++ ou Python)

Étant donné le nombre réduit d'éléments dans le if/else le passage à un switch/case sera, de mon avis, négligeable en termes de performance !

@faptiem, tout dépend de ce que tu veux mettre entre les if/else, pourquoi ne pas utiliser une boucle while en début puis des for suivi de if/else, et des return pour vérif le tout? pour le read, tu peux définir un char de départ avant de le donner a read.Enfin je sais pas si je suis très clair.

Hors Ligne

#11 24-12-2011 16:27:34

Squaks
Membre Irremplaçable
Inscription : 18-06-2009
Messages : 974

Re : Appel à compétences : codage en C (ou C++ ou Python)

Pour lire sur l'entrée standard :

char key[26];
fgets(key,26,stdin);

Sharkoff

Hors Ligne

#12 24-12-2011 16:35:24

faptiem
Membre Indéboulonnable
Inscription : 29-04-2010
Messages : 127

Re : Appel à compétences : codage en C (ou C++ ou Python)

Oui voilà à quoi je voulais venir Antares, les fonctions telles que scanf et printf utilisent (forcément) des appels systèmes bas niveau tels que read et write, elles ne sont pas directement écrites en asm big_smile.

Donc étant donné que ce sont des fonctions ultra simplifiées convenant à tous les cas de lecture/écriture possibles cela implique un certain nombre de tests, vérifications etc pour écrire/lire sur la sortie standard.

Quand tu n'as besoin de lire qu'un certain type de données et que tu a cerné tes besoins (ainsi qu'avec un peu de temps devant toi) tu as tout à gagner à coder une fonction maison utilisant un appel système pour ton besoin spécifique, cela sera plus rapide si bien conçu (et j'ai entendu dire qu'il y avait des leaks de mémoire dans printf, rumeur que je n'ai pas encore vérifiée !)

Sinon Koala.. euh.. je n'ai pas compris ce que tu veux dire, et où cela s'appliquerait ? ahah

Concernant les performances jette un oeil sur google (j'ai checké quelques minutes) et tu pourras constater que les avis convergent vers un switch plus performant que des if else à partir d'un certain nombre de cas car dans ce cas là une hashtable est utilisée, ce qui rend le temps de check linéaire, contrairement au if/else dont le dernier élément met un temps bien plus long à être vérifié que les précédents (logique).

A première vue la hashtable est utilisée à partir de 5 éléments, or (démonstration) dans mon cas j'ai 16 éléments réunis en 7 vérifications.
On sait tous que le temps d'accès (de check) de la hashtable est plus long qu'un check normal dans un if else, MAIS quand tu tombes sur le cas n°15 par exemple, peut être que 7 itérations de if else seront plus longues qu'une vérif dans la hashtable, dans ce cas là c'est rentable. Malgré tout (important ici) la première itération que je réalise concerne en une seule fois 10 éléments ! Soit plus de la moitié de mes cas.
Donc dans plus de 50% des cas la vérification s'arrêtera à la première itération, qui est surement plus rapide qu'un accès à une hashtable.

Après quand t'as 1 000 000 000 éléments et que tu cherches l'élément 999 999 999, il vaut mieux faire un check de hashtable que 999 999 999 itérations big_smile

Hors Ligne

#13 15-06-2012 15:18:25

pilpoile
N00b
Inscription : 15-06-2012
Messages : 3

Re : Appel à compétences : codage en C (ou C++ ou Python)

Bonjour,

Je sais bien que ce poste date un peu, mais si ça peut aider j'ai fait une solution en python :
[Comme tout les acaracteres sont sur 7 bits j'ai juste ajouté un 0 devant]

def Atraduire(TInput):
        TOutput = ''
        for carac in TInput:
                temp = str(bin(ord(carac))).replace('0b','')
                TOutput = TOutput + '0' + temp
        return TOutput

print Atraduire("ABC")

++
Pilpoile
/*/ Windows XP - Python 2.6 /*/

Dernière modification par pilpoile (15-06-2012 15:22:56)

Hors Ligne

Annonce

Visitez la boutique Wifi-highpower.com, votre revendeur agr Alfa Network: du matriel Wifi slectionn, cartes Wifi USB Awus036h et Awus036nh, antennes omnis, yagis, panel, amplis wifi, accessoires...

Sujets similaires

Pied de page des forums


Le coin des bonnes affaires, achats informatiques:


|   Alfa 1000 mW AWUS036H   |    Linksys WRT54GL   |    Misco, informatique   |   
 |    Ebay   |    PC portables   |    PC Gamers & Tuning   |    Cles USB   |   
|   Disques durs externes 2 To   |   
|   Wifi-highpower.com   |   


Server Stats - [ Generated in 0.033 seconds ]   Forum Stat - [ Most users ever online on the forum was : 150 on 20-09-2009 17:06:59 ]