Crear bucle de fuerza bruta con rango de caracteres

[mamcx]

Pero tienes el rando de busqueda acotado, asi que no debe ser tan grande. Ademas con fuerza bruta tienes un algoritmo sequencial donde pagas lo mismo por cada vez que lo ejecutes. Solo es rapido si apuestas a que la respuesta esta al inicio del rango de busqueda. Ademas estas buscando integers. Eso se puede almacenar super-eficiente.

[[escafandra]]

Entiendo que aguml solo ha pretendido experimentar. Al principio no entendí bien lo que pretendía y escribí un código muy simple que evidentemente no era lo que él buscaba. Siguiendo con la causa original del hilo me permito aportar un código usando C, sin ayuda de cadenas estilo delphi, como él usa, mucho más eficiente.

He usado un serial como éste: FAB1AF04. La función de aguml ha dado con el resultado en 262,875 segundos, mientras que la función que propongo ha tardado 8,656 segundos en un i7. La diferencia es más que notable: 30 veces más rápido, y dedicándole un poco más de tiempo, seguro que se le puede hacer rendir algo más:

Código PHP:

bool FuerzaBruta(char* Serial, char* Salida, char* Rango)
{
  int L = strlen(Serial);
  int R = strlen(Rango);
  int n, i;
  bool Error = true;

  for(n=0; n<L; n++) Salida[n] = *Rango;
  Salida[n] = 0;
  int f;
  for(int r=0; ; r++){
    *Salida = Rango[r%R];
    //acarreo
    for(int c=0; Salida[c]==*Rango && r>1; c++){
      for(i=0; Rango[i] && Rango[i]!=Salida[c+1]; i++);
      Salida[c+1] = Rango[(i+1)%R];
    }
    if(!(Error = strcmp(Salida, Serial))) break;
  }
  return !Error;
} 


Saludos.

[aguml]

tengo que probarlo, se ve mas corto y con muy buena pinta.

[aguml]

Bueno, tuve que mirarlo y tracear porque a simple vista habia cosas que no tenia claras y luego de tracear me sorprendio los tiempos que obtenia y entonces pensé "claro, el empieza de izquierda a derecha el incremento y yo al contrario y como la palabra buscada era F1ACA pues el llegaba antes a la A que yo a la F" entonces decidí dar la vuelta a la cadena tal como ACA1F y mi sorpresa incrementa al ver que casi no cambió el tiempo ya que subió unos 100 milisegundos .
Con esto solo puedo felicitar al maestro Escafandra por un codigo tan bueno como este.

Una cosa mas, le vi un fallo y es que no tiene control de fin de busqueda y si no encuentra la cadena sigue incrementando hasta llegar a desbordar el array por lo que le hice algunos pequeños cambios, el principal para subsanar ese problema y otros para hacerlo mas entendible para mi.

Otra cosa, me dio por probar cambiar los for que inicializan la cadena de tope y la cadena inicial por dos memset y vi que los tiempos se incrementaban solo con eso asi que lo dejé con los for. Supongo que memset hace algo mas internamente que ralentiza un poco el proceso.

Aquí el código final:

Código PHP:

void __fastcall TForm1::Button1Click(TObject *Sender)
{
   AnsiString Rango = "0123456789ABCDEF"; //Rango de caracteres que se usará para la fuerza bruta
   AnsiString cadena = "KMK;P";//"P;KMK"; //Cadena a buscar. Le he aplicado un calculo usando la funcion CalculosSerial
   bool retval;
   double tiempoInicial, tiempoFinal;
   char *Salida = new char[cadena.Length()+1];
   memset(Salida,'\n',(cadena.Length()+1));

   Form1->WindowState = wsMinimized; //Minimizamos el form para que el usuario no pueda pulsar el boton ni nada

   tiempoInicial = GetTickCount(); //Obtenemos el tiempo de entrada

   retval = FuerzaBruta(cadena.c_str(), Salida, Rango.c_str());

   if(retval == false){ //Si no se encontró avisamos
      ShowMessage("No se encontró el valor");
   }else{
      tiempoFinal = GetTickCount(); //obtenemos el tiempo de salida

      ShowMessage( AnsiString().sprintf( "Valor hexadecimal: %s\n"
                                         "Se han tardado %s segundos en encontrarlo.",
                                         Salida, FormatFloat("0.000",(tiempoFinal - tiempoInicial) /1000)));
   }
   Form1->WindowState = wsNormal; //volvemos a restaurar el form
   delete [] Salida;
}
//---------------------------------------------------------------------------

bool FuerzaBruta(char* Serial, char* Salida, char* Rango)
{
   int largoSerial = strlen(Serial); //Obtengo el largo de la cadena del serial
   int largoRango = strlen(Rango); //Obtengo el largo de la cadena del rango
   int n; //Es usado como un contador auxiliar para rellenar inicialmente la cadena de salida y la de tope
   int posEnRango; //Es usada para obtener la posicion en el rango
   bool retval = false; //El valor que contenga esta variable será lo que retornemos al salir
   bool salir = false; //La uso para indicar cuando debo salir del bucle de fuerza bruta
   char *CadenaFinal; //Es la cadena obtenida de aplicarle calculos a la cadena de salida
   char *CadenaTope; //Esta cadena contendrá el tope de busqueda y si llegamos a ella y no encontramos el valor bueno saldremos con false

   //Reservamos memoria para la cadena final y ponemos el valor de fin de cadena al final de esta
   CadenaFinal = new char[largoSerial+1];
   CadenaFinal[largoSerial]=0;

   //Reservamos memoria para la cadena tope
   CadenaTope = new char[largoSerial+1];

   //Para inicializar la cadena de salida la rellenamos con el primer valor del rango y la cerramos con el caracter de fin de cadena
   for(n=0; n<largoSerial; n++) Salida[n] = *Rango;
   Salida[n] = 0;

   //Para inicializar la cadena de tope la rellenamos con el ultimo valor del rango y la cerramos con el caracter de fin de cadena
   for(n=0; n<largoSerial; n++) CadenaTope[n] = Rango[largoRango-1];
   CadenaTope[n] = 0;

   //Bucle de fuerza bruta
   for(unsigned int contador=0; salir != true; contador++){
      *Salida = Rango[contador % largoRango];

      //Aqui realizamos el acarreo cuando se ha llegado al ultimo valor del rango en la columna
      for(int columna=0; Salida[columna]==*Rango && contador>1; columna++){

         //Recorremos el bucle hasta que encontramos el caracter de la siguiente columna de la cadena de salida en la cadena del rango
         //En posEnRango tendremos su posicion del caracter al salir
         for(posEnRango=0; Rango[posEnRango] && Rango[posEnRango]!=Salida[columna+1]; posEnRango++);

         //Aqui obtenemos el resto de dividir la posicion en el rango obtenida en el for + 1 entre el largo del rango
         //El resultado es el indice que usaremos para asignar el caracter de la siguiente columna
         //Si el caracter de la siguiente columna es el ultimo posible, i+1 será igual al largo del rango
         //con lo que el resto será 0 y asignariamos el valor del primer caracter del rango a la siguiente columna
         Salida[columna+1] = Rango[(posEnRango+1) % largoRango];
      }

      //Hacemos los calculos deseados con la cadena y obtenemos el resultado en CadenaFinal
      CalculosSerial(Salida, CadenaFinal);

      if(strncmp(CadenaFinal, Serial, largoSerial) == 0)
      { //Si CadenaFinal es igual a la cadena que estamos buscando salimos del bucle
         retval=true;
         salir = true;
      }
      else if(strncmp(Salida, CadenaTope, largoSerial) == 0)
      { //Si la cadena es igual al tope querrá decir que ya rrecorrimos todo y no se encontró así que salimos del bucle
         salir = true;
      }
   }

   //Liberamos la memoria
   delete [] CadenaFinal;
   delete [] CadenaTope;

   //Retornamos indicando si la busqueda tuvo exito o no
   return retval;
}
//---------------------------------------------------------------------------

//Aqui realizariamos los calculos necesarios con el serial
void CalculosSerial(char *Serial, char *Salida)
{
   int largo = strlen(Serial);

   //Yo simplemente le sumo 10 a cada caracter por ejemplo
   for(int x=0; x<largo; x++)
      Salida[x] = Serial[x] + 10;
}
//--------------------------------------------------------------------------- 


y una captura con todos los tiempos (los tres codigos que yo realicé y este ultimo que he llamado "prueba 4"):
Clic aqui para ver imagen

Alucinante la mejora.
Mil gracias amigos.

[aguml]

Otro posible (aunque no se hasta que punto probable) fallo. El contador que se usa en el for principal puede llegar a desbordarse (en mi maquina quizas en un par de eones jejeje) ya que incrementa continuamente y dependiendo de lo grande del serial a buscar podria ocurrir.
Lo he solucionado poniendo la siguiente linea al final del for que se encarga del acarreo:

Código PHP:

//Cada vez que llegamos aqui, contador llega siendo multiplo del largo del rango por lo que, para evitar un posible desbordamiento
//de la variable contador, cada vez que entre aquí le asignaremos el valor del largo del rango para curarnos en salud
contador = largoRango; 


Sinceramente no se en que interviene esto pero desde que lo hice los tiempos han mejorado algo mas.

[[escafandra]]

Empezado por aguml

Otro posible (aunque no se hasta que punto probable) fallo. El contador que se usa en el for principal puede llegar a desbordarse (en mi maquina quizas en un par de eones jejeje) ya que incrementa continuamente y dependiendo de lo grande del serial a buscar podria ocurrir.
Lo he solucionado poniendo la siguiente linea al final del for que se encarga del acarreo:

Código PHP:

//Cada vez que llegamos aqui, contador llega siendo multiplo del largo del rango por lo que, para evitar un posible desbordamiento
//de la variable contador, cada vez que entre aquí le asignaremos el valor del largo del rango para curarnos en salud
contador = largoRango; 


Sinceramente no se en que interviene esto pero desde que lo hice los tiempos han mejorado algo mas.

Incrementa la velocidad porque el módulo calculado es de números más pequeños. si obviamos el módulo en el bucle principal, como comenté arriba, descargamos de trabajo al procesador y aumenta el rendimiento en procesadores lentos. En mi i7 no se nota prácticamente, pero lo probé en un PC inferior y ganó 7 segundos (de 20 pasó a 13).


Saludos.

[aguml]

Pues si, yo la comprobacion de tope la dejaré por si alguna vez se mete un serial incorrecto pero con lo que me indicas te digo que ha pasado de 188 milisegundos a 156 en el mismo ejemplo que estaba viendo. O sea que en un serial mayor se notaria aun mas.

[[escafandra]]

La velocidad se consigue por el hecho de trabajar con cadenas estilo C y es independiente de si vas de izquierda a derecha o al revés. Si eliminas comprobaciones y condicionales superfluos también aceleras el proceso. El hecho de no comprobar que se terminaron las combinaciones de caracteres no es casual, ya que si la cadena cumple la condición de contener solo los caracteres existentes en Rango, el resultado lo encuentra sí o sí, por lo tanto no puene entrar en un bucle infinito y ganamos rendimiento.

Una cosa que hace perder rendimiento es usar el resto de la división en el bucle principal, que es el más largo. Si lo eliminamos, le procesador hará menos cálculos, perdemos un poco de elegancia en el código pero ganamos algo de tiempo. Como ejemplo pongo lo siguiente:

Código PHP:

bool FuerzaBruta(char* Serial, char* Salida, char* Rango)
{
  int L = strlen(Serial);
  int R = strlen(Rango);
  int n, i;

  for(n=0; n<L; n++) Salida[n] = *Rango; Salida[n] = 0;
  
  int r=0, f = 0;
  do{
    *Salida = Rango[r];
    //acarreo
    for(int c=0; Salida[c]==*Rango && f>0; c++){
      for(i=0; Rango[i] && Rango[i]!=Salida[c+1]; i++);
      Salida[c+1] = Rango[(i+1)%R];
    }
    f=1;
    r++; if(r==R) r=0;
  }while(strcmp(Salida, Serial));
  return true;
} 


Cambio el tipo de bucle a do while, lo que me obliga a incrementar el índice r y añado otra variable (f) para detectar que no es la primera vez que pasamos por el primer carácter de Rango. No compruebo que se terminaron las combinaciones porque encontraré el Serial obligatoriamente.

Un paso más puede ser escribirlo en asm, no lo he hecho pero es muy probable que incremente algo la velocidad