El Blog de Daniel Lerch

Criptograma 16/07/09

2009-07-16T01:08:00.001+02:00

HOLAB UHODE MIMAH OLASI TUMAC ETUNA NATUB IMICI RUTUM
AHOCE HOMAS IMIRU SIMIR EFAHO DOTUB LNATU MACIB IHOLA
RUHOS STUMA NATUL ABIFA BITUL ABIHO GRUXR UUXSI UXGUT
UBUHO RUSIH ORRMA MIFAY YMIBU TUMAY YXXXX

Comandos útiles para Vim

2009-07-09T08:27:00.006+02:00

# las funciones de autocompletado buscan en los directorios indicados

: set path=/usr/include, /usr/local/include

# Habilita el coloreado de sintaxis

: syntax on

# habilita el auto indentado

: set autoindent

# habilita el auto indentado inteligente

: set smartindent

# Define 3 espacios para el indentado

:set shiftwidth=3

# Convierte tabulados en espacios. Deshabilitar con :set noexpandtab

: set expantab

# Hace que los tabuladores sean de tres espacios

: set tabstop=3

# Plega bloques delimitados por {{{ }}}

: set fdm=marker

# Plega blouqe segun la sintaxis. No necesita marcas, como en el caso anterior.

: set fdm=syntax

# Establece los nivels de anidamiento para plegar código.

: set foldnestmax=1

# Cierra un bloque delimitado por {{{ }}}.
# Se abre pulsando el espacio sobre el bloque.
: foldclose

# Marca el parentesis/llave que abre y el que cierra al situarse encima.

: set showmatch

# La marca habilitada con 'showmatch' dura un segundo.
: set matchtime=1

# Aparecen indicadores con el numero de linea, de columna, etc.

: set ruler

# Cuando se abre un archivo coloca el cursor en su posicion del ultimo cierre

if has("autocmd")

au BufReadPost * if line("'\"") > 0 && line("'\"") <= line("$")

\| exe "normal! g'\"" | endif

endif

# Entra en modo insercion a continuacion de la posicion actual
a

# Entra en modo insercion en la posicion actual
i

# Deshace los cambios
u

# Rehace los cambios

:redo

# Guarda los cambios

:w!

# Guarda los cambios en el fiechero 'file'
:w! file

# Sale sin guardar

:q!

# Mueve el cursor al final del fichero
G

# Mueve el cursor al principio del fichero

# Mueve el cursor a la linea N

N G

# Entra en modo visual. Seleccion a nivel de columnas.

ctrl + v

# Entra en modo visual. Seleccion de todo el texto.

ctrl + v v

# Corta/borra el texto seleccionado

# Copia el texto seleccionado

# Pega el texto del portapapeles

# Sustituye from por to, pidiendo confirmacion
:%s/from/to/gc

# Sustituye from por to, pidiendo confirmacion de un texto seleccionado.

:'<,'>s/from/to/gc

# Ir al principio de la linea

# Ir al final de la linea

# Ir a la palabra siguiente

# Pinta los resultados de la busqueda

: set hlsearch

# Busca palabras como la situada debajo del cursor

# Abre la pagina man de la función sobre la que se encuentra el cursor

# Salta a la definición/declaración de la variable sobre la que se encuentra el cursor

# Salta al parentesis/llave asociado al parentesis/llave sobre el que se encuentra el cursor

# Abre una pestaña con el fichero 'file'

: tabnew file

# Salta de una pestaña a otra

# Divide la ventana en dos abriendo el fichero 'file'

: split file

# Salta de una ventana a otra

Ctrl+w w

# Autocompleta la palabra

Ctrl + p

Ctrl + n

Estamos dentro de VMWare?

2009-07-06T07:31:00.000+02:00

A continuacion dejo un programa que permite detectar si nuestro servidor se encuentra dentro de una maquina virtual VMWare. Utiliza una tecnica descubierta por Ken Kato que consiste en encontrar el Backdoor I/O port. Este puerto es el que utiliza VMWare para comunicarse con la maquina virtual. Como dicho puerto no existe en un servidor normal su deteccion indica que nos encontramos bajo VMWare.

/*
 * 4tphi-vmchk.c
 * Detects if you are in a VMWare virtual machine.
 *
 * Written by Andrew Hintz 
 * and AAron Walters
 * Fortify Research Laboratories 
 *
 * "Oft at the hives of his tame bees
 * They would their sugary thirst appease."
 *
 * This program is based on info and code from:
 * http://chitchat.tripod.co.jp/vmware/
 * by chitchat_at_lycos.jp
 *
 * Notes:
 * The program can be run as a normal user.
 * We tested the program only in x86 Linux.
 * The m4dn3ss lives on!
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/signal.h>

#if __INTSIZE == 2 /* 16 bit environment */
typedef unsigned int uint16;
typedef unsigned long uint32;
#else /* 32 bit environment */
typedef unsigned short uint16;
typedef unsigned int uint32;
#endif /* __INTSIZE */

void segfault()
{
  printf("Not running inside VMware.\n");
  exit(1);
}

int main()
{
  uint32 verMajor, verMinor, magic, dout;

  signal(SIGSEGV, segfault);

  __asm__ __volatile__ 
   (
   "mov $0x564D5868, %%eax; /* magic number */"
   "mov $0x3c6cf712, %%ebx; /* random number */"
   "mov $0x0000000A, %%ecx; /* specifies command */"
   "mov $0x5658, %%edx; /* VMware I/O port */"
   "in %%dx, %%eax;"
   "mov %%eax, %0;"
   "mov %%ebx, %1;"
   "mov %%ecx, %2;"
   "mov %%edx, %3;"
    : "=r"(verMajor), "=r"(magic), "=r"(verMinor), "=r"(dout)
    );

  if (magic == 0x564D5868) 
  {
    printf("Running inside VMware. ");
    printf("(Version %lu,%lu)\n", verMajor, verMinor);
    /* I'm not really sure what the versions mean. */
  }

  return 0;

}

OpenDomo visto desde un iPod touch

2009-06-17T23:40:00.004+02:00

Dejo una foto de un sistema OpenDomo controlado desde un iPod Touch, en el se accede al sistema de videovigilancia.
Cortesía de Isidro, uno de los desarrolladores principales de OpenDomo.

Enlace original:
http://www.opendomo.com/drupal/node/55

Control de sensores e interruptores con OpenDomo

2009-06-17T23:28:00.001+02:00

Recientemente he publicado un manual en OpenDomo que explica como controlar sensores e interruptores.
Por fin opendomo puede usarse en sistemas reales, aunque esté todavía en fase alpha.

Dejop un enlace al manual:

¿Cómo controlar sensores e interruptores con OpenDomo y Micropik PS3X8?

Criptograma 11/04/09: Solución

2009-06-12T07:31:00.004+02:00

Se trataba de un autocifrado, cuya clave era nada más y nada menos que "AUTOCIFRADO" ;)

Aquí tenéis un ejemplo de como se hace el cifrado:

SIHEVISTOMASLEJOSESPORQUEESTOYSENTADOSOBREHOMBROSDEGIGANTESISAACNEWTON

AUTOCIFRADOSIHEVISTOMASLEJOSESPORQUEESTOYSENTADOSOBREHOMBROSDEGIGANTES

======================================================================

SCASXQXKOPOKTLNJAWLDARIFINGLSQHSEJUHSKHPPWLBFBUCKRFXMNOZUVGAVEGKTEJMSF

y un ejemplo de como se descifra:

SCASXQXKOPOKTLNJAWLDARIFINGLSQHSEJUHSKHPPWLBFBUCKRFXMNOZUVGAVEGKTEJMSF

AUTOCIFRADO

===========

SIHEVISTOMA

           SIHEVISTOMA

           ===========

           SLEJOSESPOR

                      SLEJOSESPOR

                      ===========

                      QUEESTOYSEN

                                 QUEESTOYSEN

                                 ===========

                                 TADOSOBREHO

                                            TADOSOBREHO

                                            ===========

                                            MBROSDEGIGA

                                                       MBROSDEGIGA

                                                       ===========

                                                       NTESISAACNE

                                                                  NTES

                                                                  ====

                                                                  WTON

Habéis perdido el interés o es que era muy difícil?! :)

Librerías para Visión Artificial

2009-06-07T22:27:00.001+02:00

Excelente colección de código que implementa diferentes técnicas de visión artificial. Desde algoritmos 'sueltos' hasta librerías completas.

http://www.cs.cmu.edu/~cil/v-source.html

OpenBSD en el escritorio

2009-05-13T22:56:00.007+02:00

OpenBSD es un Sistema Operativo centrado en la seguridad. Es muy apreciado en el mundo de los servidores no tan solo por su seguridad, si no por su gran estabilidad y su política de 'corrección' del código.

Desde hace algún tiempo he ido viendo posts de gente que lo usaba como entorno de escritorio. lo que me ha llevado a hacer mis propias pruebas. Esta no es su mejor baza, ni mucho menos. Pero si se quiere una roca como Sistema Operativo, hay que tenerla en cuenta.

En este post explico el procedimiento para instalar OpenBSD en el escritorio. No es Ubuntu, así que no esperéis nada parecido, pero tampoco resulta excesivamente complicado. Usaré OpenBSD 4.5 (la última en el momento de escribir el post) en una arquitectura AMD64. El que tenga otra arquitectura solo tendrá que sustituir en las URL amd64.

Instalación del sistema base

Descargamos la imagen y la quemamos en un CD:

ftp://ftp.openbsd.org/pub/OpenBSD/4.5/amd64/install45.iso

Arrancamos desde el CD y seguimos los pasos que se nos indican. En general, aunque es unainstalación en modo texto, no supone mucho problema: configuración de teclado, red, etc.

Lo que sí puede resultar difícil si no se está acostumbrado es el particionado de disco. Si no se sabe lo que se esta haciendo lo mejor es usar el disco entero para OpenBSD, o la pérdida de datos estará garantizada.

Esta parte está explicada en detalle en el siguiente enlace, en el punto 4.5.2:

http://www.openbsd.org/faq/faq4.html

Selección de paquetes

Durante la instalación se nos solicitarán los paquetes que queremos instalar. Los seleccionaremos todos, o como mínimo, los paquetes relacionados con las X.

Ejecutando las X

En estos momentos tenemos un sistema base con las X, las cuales podemos ejecutar mediante el comando startx. Si no funcionan correctamente tendremos que revisar /etc/X11/xorg.conf y adaptarlo a nuestro sistema.

Instalando GNOME

Habrá quien quiera instalar KDE. Googlead un poco, no creo que sea muy diferente. Aquí instalaremos GNOME.

Para poder instalar binarios de forma cómoda tendremos que establecer la variable de entorno PKG_PATH. Lo haremos añadiendo:

export PKG_PATH=ftp://ftp.openbsd.org/pub/OpenBSD/4.5/packages/amd64/

en el fichero ~/.profile. Así quedara configurada al reiniciar.

Ahora, para instalar GNOME haremos:

$ pkg_add gnome-session

Y para que GNOME arranque al iniciar el sistema pondremos en /etc/rc.local
/usr/local/bin/gdm -nodaemon

Creación de usuarios

Ejecutaremos:
$ adduser

Este nos irá preguntando lo típico: nombre de usario, shell a usar, contraseña, etc.

Si queremos que el usuario se pueda convertir en root con el comando 'su' necesitaremos añadirlo al grupo wheel. Lo haremos con:

$ moduser -G wheel usuario

Y con esto, ya tenemos un espléndido OpenBSD en nuestro escritorio.

Solo faltará instalar los paquetes que creamos necesarios como:

$ pkg_add openoffice-3.0.1p2
$ pkg_add firefox-i18n-es-ES-3.0.6

etc.

Factorización en tiempo polinómico!?

2009-05-12T12:50:00.001+02:00

Claus P. Schnorr ha presentado en el Eurocrypt 2009 "Average Time Fast SVP and CVP Algorithms: Factoring Integers in Polynomial Time".

Habría que ver el impacto que puede tener este documento en la criptografía de clave pública. Pero si es correcto, podría representar el fin de RSA.

Se ha iniciado un hilo de discusión en sci.crypt.research.

Free Mathematics Books

2009-05-09T23:18:00.003+02:00

Estupenda colección de libros de matemáticas distribuidos gratuitamente:

http://www.e-booksdirectory.com/mathematics.php

The P-versus-NP page

2009-05-07T23:42:00.004+02:00

Dejo un enlace a una página estupenda que recopila todos los intentos de demostrar el problema P?=NP.

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Después de todo, hay un suculento premio para el que lo consiga.

Criptograma 11/04/09

2009-05-05T00:56:00.000+02:00

Pista: Autocifrado

 SCASXQX KOPOKTL NJAWLDA RIFINGL SQHSEJU 

HSKHPPW LBFBUCK RFXMNOZ UVGAVEG KTEJMSF

  

Criptograma 07/04/09: Solución

2009-04-23T20:00:00.000+02:00

Una combinación de transposición y sustitución. Primero había que transponer las letras del criptograma:

TRJVMFPTTFIEPFNCCFSFFTTDIVBDOIOBBSDZJNEJPSDBPSOEEPPTTWPFKDP
FTTEBPOTUPFSTFEKFBITBZCVMOBBSTNPBMEBBMNFFOEHFVTBFFWTJQHPOSF

Cogiendolas con un periodo de dos: una si, una no, ... Obteníamos:

TJMPTIPNCSFTIBOOBDJEPDPOEPTPKPTEPTPSFKBTZVOBTPMBMFOHVBFTQPS
RVFTFEFCFFTDVDIBSZNJSBSEPTWFDFTBOUFTEFIBCMBSNBEBNFEFTFWJHOF

Finalmente con un desplazamiento de una letra en el abecedario inglés:

SILOSHOMBRESHANNACIDOCONDOSOJOSDOSOREJASYUNASOLALENGUAESPOR
QUESEDEBEESCUCHARYMIRARDOSVECESANTESDEHABLARMADAMEDESEVIGNE

Evitar timeouts en conexiones ssh

2009-04-22T14:05:00.002+02:00

echo "ServerAliveInterval 60" >> ~/.ssh/config

Y se acabaron los timeouts por inactividad.

Gracias Jordi!

Criptograma 05/04/09: Solución

2009-04-21T20:00:00.001+02:00

Observando los números con atención se veía que 'todos' se podían descomponer en, únicamente, dos números primos. Dado que había un total de 26 números primos, se podía deducir que había un primo por letra del abecedario inglés.

La asignación era la siguiente:

A: 002, B: 003, C: 005, D: 007, E: 011, F: 013, G: 017, 

H: 019, I: 023, J: 029, K: 031, L: 037, M: 041, N: 043, 

O: 047, P: 053, Q: 059, R: 061, S: 067, T: 071, U: 073, 

V: 079, W: 083, X: 089, Y: 097, Z: 101

El problema añadido del criptograma, era que al asignar cada letra a su número primo correspondiente las letras podían quedar desordenadas, pues dependía del orden en que se colocaban los dos factores. Aun así, después de la sustitución, no ser dificil finalizar el criptograma.

Despues de factorizar los números originales quedaba como:

37  2  5  23  11  43  5  23  2  43  47  43  47  67  19  2

11  43  67  11  43  2  7  47  2  73  43  67  23  37  2  37

47  5  73  61  2  11  67  47  43  47  37  47  41  2  67  67

73  3  37  23  41  11  7  11  37  2  23  43  71  11  37  23

17  11  43  5  23  2  11  7  17  2  61  2  37  37  2  43

53  47  11 101

Y finalmente, después de sustituir:

LACIENCIANONOSHAENSENADOAUNSILALOCURAESONO

LOMASSUBLIMEDELAINTELIGENCIAEDGARALLANPOEX

Catástrofe!!

2009-04-20T17:39:00.000+02:00

Oracle compra Sun Microsystems, y con ella MySQL, Java, OpenOffice, OpenSolaris, VirtualBox, ...

Esta noche voy a tener pesadillas.

Criptograma 26/03/09: Solución

2009-04-19T20:00:00.001+02:00

Volvíamos con Kasiski, esta vez con una clave un poquito más larga...

VRBCI UGJZB JMCJK EVMBF ZSCNX
NIWAN CEGYI UVIQV FRWUZ ANWEH
VLPAT EUQUH RPIIW ONWQB EWXXX
RCVAN CCDHH PKMBF FTJYL HCKSE
EMCAN NFIBB HYTLB EPLCI ZZXLY
UGZOQ VPGYU APWBB RPPAX NVMBB
XYHNT QWMIA FXTHZ AUCDE FTXUY
EPWOY RKTHM EPWUH JXPKN EWVCG
VRVUL URZCC ZEUYM OFWGG FHDMF
EOQFN EQPFL ANDCY FWRCX GQASF
EEIOK ANIPP UIUAA ILSZZ FTFLL

CLAVE: REPUTACION

ENMIP UEBLO SINPR ETENS IONTE
NGOMA LAREP UTACI ONHAG ALOQU
EHAGA ESIGU ALTOD OLOCO NSIDE
RANMA LYONO PIENS OPUES HACER
NINGU NDANO QUERI ENDOV IVIRF
UERAD ELREB ANONO ALAGE NTENO
GUSTA QUEUN OTENG ASUPR OPIAF
ENOAL AGENT ENOGU STAQU EUNOT
ENGAS UPROP IAFET ODOST ODOSM
EMIRA NMALS ALVOL OSCIE GOSES
NATUR ALABC DEFGH IJKLM OPQRS

Criptograma 20/03/09: Solución

2009-04-17T20:00:00.002+02:00

Como ya se decía en la pista del criptograma se trataba de un cifrado Vigenere susceptible al ataque Kasiski.

BEAOSERIPMXAQUTLXTDMTLDDTCXABIEAEABEAOSIYEGOCMJCWAHVTCTS

NLDOAVXDPBPMJCWAHMPSIRPBPJPNXNDNDTTPXECSTSFUTSXNSICEGOKI

KIGAHJJNIATLTSUUTROONEAAWOGRDAQRTTTPPSDYPVTRPSROBOAAKISA

IESEEAGAQUTNDSBOBECTDSIEPLOAGAHSDBGEAOHPDBGEHYBEOQJICOHQ

JECOWACSPBXDDDTSROALPRBEAOSERIPMXAQUTLXTDMTLDDTCXABIEAEA

BEAOSIYEGOCMJCWAHVTCTSNLDOAVXDPBPMJCWAHMPSAAKISATSAURHPD

TSEIPDPDPNPDXEIEPYJDPAHICOBAHYHIIUHOAOCOPDTLPNIAHTTIGACD

TJPNSOPTGAHAIRPSPNSABURHPCWOSAAESUGOAAIITRGAIOSATLHOAITL

BAGSDNEAGAPQJEALDSFUTHPNHAQISOHECTPRHEHOQRTLDSSEBAHMTLDD

TCXABIPBJEAIIOBEAOSERIPMXPPPPMTLDDXJTRDNBURHPSKEREHYAOWE

DLKISASOHITMERTMPSYOHEPGJSIICGDYIIHOAOPBRDTFVHXJZLBNDPFR

CLAVE : PAPA

MELODECIAMIABUELITOMELODECIAMIPAPAMELODIJERONMUCHASVECES

YLOOLVIDABAMUCHASMASTRABAJANINONOTEPIENSESQUESINDINEROVI

VIRASJUNTAELESFUERZOYELAHORROABRETEPASOYAVERASCOMOLAVIDA

TEDEPARABUENOSMOMENTOSTEALZARASSOBRELOSPOBRESYMEZQUINOSQ

UENOHANSABIDODESCOLLARMELODECIAMIABUELITOMELODECIAMIPAPA

MELODIJERONMUCHASVECESYLOOLVIDABAMUCHASMASLAVIDAESLUCHAD

ESPIADADANADIETEAYUDAASINOMASYSITUSOLONOADELANTASTEIRAND

EJANDOATRASATRASANDAMUCHACHODALEDUROLATIERRATODAELSOLIEL

MARSONPARAAQUELLOSQUEHANSABIDOSENTARSESOBRELOSDEMASMELOD

ECIAMIABUELITOMELODECIAMIPAPAMELODIJERONMUCHASVECESYLOHE

OLVIDADOSIEMPREMASJOSEAGUSTINGOYTISOLOABCDEFGHIJKLMNOPQR

Vectores Dinámicos en C

2009-04-13T00:07:00.008+02:00

Si queremos usar vectores dinámicos en C necesitamos recurrir a funciones de manejo de memoria de la familia *alloc(). En este post explico cómo hacerlo de forma sencilla y añado algunas macros que facilitan la tarea.

Para empezar necesitaremos declarar el vector. Lo haremos como apuntador a NULL, creando así, un vector vacío. Necesitaremos también una variable que almacene el tamaño del vector, es decir, la cantidad de elementos que contiene.

Como ejemplo crearemos un vector de números enteros.

int *v = NULL;
size_t v_size = 0;

Tenemos un vector vacío, por lo que el siguiente paso no puede ser otro que añadir elementos. Lo haremos mediante realloc(), función que permite reasignar el tamaño reservado en memoria.

v_size++;
v = realloc(v, sizeof(int)*v_size);
v[v_size-1] = 5;

De esta manera podemos añadir tantos elementos como creamos oportuno. El acceso a ellos se realizará mediante la tradicional indexación de vectores v[i], donde i es el índice del vector. Así podremos acceder al contenido de las diferentes posiciones del vector tanto para leerlas como para escribir en ellas.

Finalmente, tendremos que liberar la memoria asignada al vector mediante la función free().

free(v);

A continuación pego un ejemplo completo del uso de vectores dinámicos con las sentencias comentadas anterioremente. Añado tambien un ejemplo de uso de la función qsort() que permite ordenar el vector.

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


int cmp(const void *a, const void *b)
{
   int *ia, *ib;

   ia = (int *) a;
   ib = (int *) b;

   return (*ia - *ib);
}

int main()
{
   /* Declaracion del vector y de su tamaño */
   int *v = NULL;
   size_t v_size = 0;


   /* Añade un elemento al vector con valor 5 */
   v_size++;
   v = realloc(v, sizeof(int)*v_size);
   v[v_size-1] = 5;

   /* Añade un elemento al vector con valor 3 */
   v_size++;
   v = realloc(v, sizeof(int)*v_size);
   v[v_size-1] = 3;

   /* Añade un elemento al vector con valor 1 */
   v_size++;
   v = realloc(v, sizeof(int)*v_size);
   v[v_size-1] = 1;

   /* Mofifica el valor del primer elemento del vector */
   v[0] = 2;

   /* Ordena el contenido del vector */
   qsort(v, v_size, sizeof(int), cmp);

   /* Muestra los elementos del vector */
   int i;
   for(i=0; i<v_size; i++)
      printf("%d ", v[i]);
   printf("\n");

   /* Libera la memoria asignada */
   free(v);

   return 0;
}

La sintaxis usada es un poco engorrosa, principalmente cuando se trata de añadir elementos a un vector. Esto puede solucionarse mediante el uso de macros. A continuación pego un ejemplo usando macros. En el puede verse también cómo pasar un vector como parámetro a una función.

#define VECTOR(v_var,v_size_var,type) \
   type *v_var = NULL; \
   size_t v_size_var = 0;

#define VECTOR_ADD(v_var,v_size_var,type,value) \
   (v_size_var)++; \
   v_var = realloc(v_var, sizeof(type)*(v_size_var)); \
   v_var[v_size_var-1] = value;
   
#define VECTOR_FREE(v_var) if(v_var) free(v_var);


void add_elements(int *v, size_t *v_size)
{
   VECTOR_ADD(v, *v_size, int, 3);
   VECTOR_ADD(v, *v_size, int, 5);
   VECTOR_ADD(v, *v_size, int, 7);
}  

int main()
{
   VECTOR(v, v_size, int);
   VECTOR_ADD(v, v_size, int, 2);
   
   add_elements(v, &v_size);

   int i;
   for(i=0; i<v_size; i++)
      printf("%d ", v[i]);
   printf("\n");
   
   VECTOR_FREE(v);

   return 0;
}

Para finalizar, solo recordar que el punto fuerte de los vectores es el acceso directo a los elementos (solo es necesaria una operación - O(1) ). Esto permite por ejemplo ordenar los elementos del vector a gran velocidad.

Por el contrario son costosas las inserciones de elementos. Pueden añadirse con facilidad al final, pero insertar un elemento en el medio, obliga a recolocar todos los demás elementos. Si se requiere una estructura de datos que permita estas operaciones es mejor recurrir a las listas dinámicas.

Criptograma 01/04/09: Solución

2009-04-10T00:43:00.004+02:00

Se trataba de un cifrado de sustitución homofónica que usaba dos valores para cada letra. A contnuación, la solución propuesta por Izzec.

Mis felicitaciones, Izzec!

dEbo decir que soy un priNcipiante en esto, y que a pesar de Haberme informadO sobRe Algunos aspectos de la criptografía tengo que decir que no tengo aún una haBilidad adqUirida. aún así mE gusta, y con coNstancia, en mi tiempo libre le dedico lo suficiente pAra intentar saber semana tras semana (aunque siemPre se nOs adelante altaiR) que nos escondes en los cripTogramas, daniel.
    bUeno el método que seguí fue Bastante sencilLo la verdad. en primera instancia hice una lectura rápida de los númerOs, y me di cuenta que todos eran curiosamente impares. alGo me Hizo pensar en esE momento que serían números impares sustituidos por letras. así que me puse a contar caDa númEro impar las veces que aparecía en dicho criptograma (esto no me serviría de mucho más adelante). hecho esto los clasifique por orden ascendente 002 (el único que no era impar) -003-005, etc. y me di cuenta que eran primos.así que los reordené todos de forma ascendente de tal forma que quedasen cuadrados con el alfabeto (sin utilizar la ñ). adjunto eJemplo;

    002   A     003   b    005   c     007   D   011   e     013   f     017   g    019   h    023   i      029   j      ¿? k         037   l

    041   m    043   n    047 O     053   p    059   q    061   r     067 s      071   t     073   U    ¿? v         ¿? w        089 x

    097 y     ¿? z         103 a      107 b     109 c      113 d     127 e      ¿?   f        ¿? g        139 h      149 i       ¿?   j

    ¿?   k      163 l        167 m      173 N      179 o      ¿? p        191 q     193 r      197 s      199 t      211 u     ¿?   v

    ¿? w      ¿? x       233 y     ¿?   z      241 a      ¿?   b     257 C     263 d     269 e      ¿? f       ¿? g      ¿? h

    283 i       ¿?   j       ¿? k       311 l       313 m     317 n     331 o     ¿? p        ¿? q       349 R      353 s      359 t

    367 u

Y luego lo demás fue cambiar las cifras Por las leTras. El texto queda así:

l a d i f e r e N c

    i a q u e e x i s t

    e e n t r e l o s h

    o M b r e s n e c I

    o s y l o s h o m B

    r e s d e t a L e n

    t O s u e l e s e r

    q u e l o s p r i m

    e r o s d i c e n n

    e c e d a d e s y l

    o s s e G u n d o s

    l a s c o m e t e n

    m a r i a n o j o s

    e d e l a r r a

Lo habéis leído con atención? ;)

Búsqueda de Patrones en Cifrados de Sustitución

2009-04-08T00:56:00.002+02:00

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!

Criptograma 07/04/09

2009-04-07T22:41:00.002+02:00

TRJVMFPTTFIEPFNCCFSFFTTDIVBDOIOBBSDZJNEJPSDBPSOEEPPTTWPFKDP
FTTEBPOTUPFSTFEKFBITBZCVMOBBSTNPBMEBBMNFFOEHFVTBFFWTJQHPOSF

Criptograma 05/04/09

2009-04-05T23:44:00.000+02:00

0074 0115 0473 0115 0086 2021 3149 0038 0473 0737 0086
0329 0146 2881 0851 0074 0235 4453 0022 3149 2021 1739
0082 4489 0219 0851 0451 0077 0074 0989 0781 0621 0187
0215 0046 0077 0034 0122 1369 0086 2491 1111

Podéis enviar vuestro procedimiento de solución a dlerch (en gmail) o publicar un comentario.

The General Number Field Sieve

2009-04-05T22:53:00.001+02:00

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

2009-04-03T12:58:00.010+02:00

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.