Cryptoland

Cryptograms, puzzles, programming and other challenges.

http://twitter.com/#!/cryptoland

Búsqueda de Patrones en Cifrados de Sustitución

Cuando se realiza el criptoanálisis de un cifrado de sustitución monoalfabética, suele ser necesario encontrar palabras que encajen en ciertos patrones de letras. Por ejemplo, en un patroón como AACBBDA encajarían palabras como arrollar, guerrillero o  encarrillar. Muchas veces, para encontrar estas palabras no es suficiente con nuestra imaginación y conocimiento de la lengua, por lo que suele ser útil recurrir al ordenador.

A continuación, pego un programa que permite realizar este tipo de búsquedas de forma muy sencilla.

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

void remove_nl(char *str)
{
   if(str[strlen(str)-1]=='\n')
      str[strlen(str)-1]=0;
}

int match_pattern(char *match, const char *pattern, size_t pattern_len)
{
   int i,j;

   for(i=0; i<pattern_len; i++)
   {
      for(j=i; j<pattern_len; j++)
      {
         if(pattern[i]==pattern[j])
            if(match[i]!=match[j])
               return 0;

         if(pattern[i]!=pattern[j])
            if(match[i]==match[j])
               return 0;
      }
   }

   return 1;
}

int main(int argc, char *argv[])
{
   char word[64];
   char *pattern = NULL;
   int pattern_len = 0;

   if(argc!=3)
   {
      printf("Usage: %s [word list] [crypto-pattern]\n\n", argv[0]);
      return 0;
   }

   pattern = argv[2];
   pattern_len = strlen(pattern);

   FILE *file = fopen(argv[1], "r");
   if(!file)
   {
      perror("fopen()");
      exit(0);
   }

   while(!feof(file))
   {
      fgets(word, sizeof(word), file);
      remove_nl(word);

      char *substr = word;

      while(strlen(substr)>=pattern_len)
      {
         if(strlen(substr)<pattern_len)
            break;

         char match[pattern_len];
         strncpy(match, substr, pattern_len);
         match[pattern_len]=0;

         if(match_pattern(match, pattern, pattern_len))
            printf("%s\n", word);

         substr++;
      }
   }


   fclose(file);

   return 0;
}

Para el patrón del ejemplo bastarí con compilar el programa con:

$ gcc pattern.c -o pattern

Y ejecutarlo con:

$  ./pattern ../dict/spanish AACBBDA
acurrullar
aporrillarse
arrollar
arrullar
aturrullar
barrillar
barrillera
barrillero
carrillera
cerrillar
churrillera
churrillero
churrullera
churrullero
corrillera
corrillero
desarrollar
descarrillar
emborrullarse
emparrillar
encarrillar
guerrillero
marrullera
marrulleria
marrullero
pantorrillera
zarzaparrillar

Espero que os sirva para vuestros cripoanalisis!

The General Number Field Sieve

Actualmente, el algoritmo de factorización más rápido que existe. Dejo aquí mi colección de papers.

Antecedents
- The Factorization of the Ninth Fermat Number , A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard (1993).
- The Number Field Sieve , A. K. Lenstra, M. S. Manasse, J. M. Pollard (1990).

Introduction to the GNFS algorithm
- An Introduction to the General Number Field Sieve , Matthew E. Briggs (1998).
- A Beginner's Guide To The General Number Field Sieve , Michael Case.
- The Number Field Sieve , Peter Stevenhagen.
- The Number Field Sieve , Steven Byrnes.

Polynomial Selection
- Polynomial Selection for the Number Field Sieve Factorisation Algorithm , Brian Murphy (1999).
- On quadratic polynomials for the number field sieve , Brian Murphy and Richard P. Brent (1998).
- Rotations and Translations of Number Field Sieve Polynomials Jason Gower (2003).
- The multiple-lattice number field sieve , Daniel J Bernstein.

Sieve
- Continued Fractions and Lattice Sieving , Jens Franke, Thorsten Kleinjung.

Filtering
- Strategies in filtering in the number field sieve , S. Cavallar (2000).

Linear Algebra
- Solving Large Sparse Linear Systems over Finite Fields , B. A. LaMacchia and A. M. Odlyzko (1991).
- A Block Lanczos Algorithm for Finding Dependencies over GF(2) , Peter L. Montgomery.
- Solving large sparse linear systems over finite fields , B. A. Lamacchia, A. M. Odlyzko (1991).

Square Root
- A Montgomery-like square root for the Number Field Sieve , Phong Nguyen, Ecole Normale Superieure (1998).
- Computing a Square Root for the Number Field Sieve , Jean-Marc Couveignes (1993).
- Square Roots of Products of Algebraic Numbers , Peter L. Montgomery.

Cómo diferenciar entre cifrados de transposición y de sustitución

  
En criptoańalisis de cifrados clásicos, el primer problema con el que se enfrenta el criptoanalista es el desconocimiento del tipo de cifrado usado en el criptograma.
  

En criptografía clásica existen dos grandes grupos de sistemas de cifrado: los cifrados de sustitución y los cifrados de transposición.
  

Los primeros son aquellos en los que cada letra es sustituida por otra letra o símbolo. En los segundos, en cambio, no hay sustitución, pues solo se realiza una mezcla de las letras.
  

Mientras que en el caso de los cifrados de sustitución, nuestro objetivo será averiguar que símbolo corresponde a cada letra, en los cifrados de transposición tendremos que encontrar el patrón de 'mezcla' utilizado.


  

Características del Texto Cifrado:

Dado que en los cifrados de transpoción, únicamente se mezclan letras, en el resultado cifrado tendremos las misma letras que en el mensaje en claro. Así pues se mantendrán los porcentajes de vocales y de consonantes de la lengua usada.

Sin embargo, en los cifrados de sustitución, cada símbolo será sustituido por otro, de manera que no se mantendrá la distribución de vocales y consonantes.


 

Técnicas disponibles:

Las características del texto cifrado nos ofrecen dos técnicas para distinguir entre  cifrados de sustitución y cifrados de transposición: El porcentaje de vocales y el análisis de frecuencias.

El porcentaje de vocales en castellano, ronda el 47%. Así pues, si contamos las vocales y las consonantes del criptograma y nos encontramos con un procentaje similar, sabremos que no se han realizado sustituciones y que con alta probabilidad nos encontramos ante un cifrado de transposición.
  

Si, por otra parte, los porcentajes que obtenemos están lejos del 47%, probablemente se trate de un cifrado de sustitución.
  

Para afiinar un poco más realizaremos un análisis de frecuencias. Sabemos que, por ejemplo, en castellano, las letras más frecuentes son la 'a' y la 'e'. Si estas se corresponden con la 'a' y la 'e' del criptagrama, más probabilidades a favor del cifrado por transposición. Si por el contrario, las más frecuentes son letras de baja frecuencia en castellano, como la 'x' o la 'k', dificilmente se tratará de un cifrado de transposición.  Podremos suponer entonces que letras de aparición frecuente han sido sustituidas por 'x' y 'k'.

Ejemplos de Criptogramas Anteriores:

Vamos a apoyar la información expuesta con algunos criptogramas  propuestos anterioremente. 

Criptograma 28/03/09:
  

OTUOBLBNOA LIERYBHAEO ATAMSIEOYS AHRNPIRMUI URNPBENCIP

NIMOAUNEAR UJALBREAUN EAEZUNSVUA RLTQETABAM ASTCASAESA

SHSOBUVNAA IZCUAAEDON SONOBAUNYA UORALMNVES XDETOOSLNO

CORDDSTOAN RAAOTODHD

El porcentaje de vocales es del 45%.

Las letras más frecuentes son la 'a', la 'o', la 'n', la 'e' y la 's'.

Así pues, queda claro que se trata de un cifrado de transposición.

Criptrograma del 2008:
  

ADZMO YHADG TIYMM ZCAUG CZYJA DYJTG LKSKM DKOZJ
OKEIG JHKAC EZSGQ HYZOG EZMVG HAZSG MYJOZ MNJEG
SZENH GHEIZ JHKDG COMKS ZCCAB IYFAJ GSZMY JOGMN
JZEON FNHGH CNACO ZEYME GHADY JABNT KVZHY VGEAM
DYEMA YMPIA YCOZD ARKCC NYCOG DARKC ZSGMY JOZMP
IACYA COGEY MEZSK JAMEY UKCSG MZGOM ZAMGD YJABN
TKTKD SYZMG DAJYB NTKEI ZJHKA COGHY CKMHA JZHKS
MYSGM ZMCAE KJOMG YDEIZ JHKAC OGCYT IMKAJ OKHZC
SGMOY CAFNO ZMDYH IMGJO AIJON YBSKE IZJHK ACBGC
XIYMO ACNOI KSKJY JOAON YJAIJ OYBSA MZBYJ OKEKD
AMNEK NJOYJ OGNMM NOZMD ACNYC GMMKT ZJOAO MGOZH
YXKBA JOGMC IYTKO NCBKC NDZCO MKSGC AJYBN TZCCA
VGDDZ JUNYJ SMASG MZHGC OMZCI JGMYK MTZJN QGENK
JNJOA JOZHY CKMHA JGMDZ CCNYC OGJIJ NHZCC NABUM
GDZHN CYJCN KJAJO MYCIC XNDGC ZOGEZ GDAJY BNTKE
IZJHK JKACO GSMYS ZMGHK WZSGM AEYEI ZJHKJ KOAYC
SAMGY COZCC KJDGC EDZFA CHYDG FNEOK MNZSG MZADY
COMGO ATZCI JOQIY DGMOA HYDZT IAMMG

  
El porcentaje de vocales es del 23%.

Las letras más frecuentes son la 'm', la 'z', la 'g', la 'y' y la 'a'.

Así pues, queda claro que se trata de un cifrado de sustitución.