Tenemos finalistas para el SHA-3

Los SHA (secure hash algorithm) son una serie de algoritmos establecidos por la Agencia Americana de Tecnología para la criptografía. Si no sabes mucho de criptografía, puedes aprender todo lo que hace falta saber en una hora. Parece ser que según van saliendo los algoritmos se van buscando sus fallos y, por ejemplo, ya te avisan de que no uses el SHA-1 y que vayas pasándote al SHA-2. Es probable que de aquí a poco también empiecen a aparecer grietas en este último por lo que es importante ir preparándose para el SHA-3.

El SHA-3 no está decidido aún, pero el concurso ha llegado a su final donde sólo quedan cinco candidatos posibles. Los nombres de los algoritmos son:

• BLAKE
• Grøstl
• JH
• Keccak
• Skein

Para los curiosos que quieran saber qué es lo que cuenta para que un algoritmo de hash criptográfico sea bueno, el informe de su evaluación está aquí.

Edit: El ganador fue Keccak. Así que ahora el SHA-3 es ese algoritmo.

Por qué no existe el compresor perfecto o los nidos de las palomas

Supongamos que existe un compresor que toma cualquier cadena de bits y la comprime en otra cadena con menos bits. Llamaremos [$c(x)$] al algoritmo compresor y [$d(x)$] al descompresor.

Está claro que

[$$c(0)=\epsilon$$]

Puesto que la cadena vacía [$\epsilon$] es la única cadena con menos longitud que la cadena [$0$]. ¡Pero también es inmediato para la cadena [$1$]!

[$$c(1)=\epsilon$$]

Entonces, ¿cuánto es [$ d(\epsilon) $]? Porque sólo podrá ser una de las dos cadenas iniciales, pero no las dos.

Esto es el llamado principio del palomar. Sólo tenemos una cadena de longitud cero para almacenar dos cadenas de longitud uno. Si en un palomar hay más pichones que nidos, en algún nido habrá dos pichones (y no podremos descomprimirlos).

Por tanto, no existe el compresor perfecto. Habrá cadenas que comprima y otras que expanda. El truco está en que comprima las cadenas más usadas y expanda las menos usadas.

Otra chuchería binaria

Sigo buscando y encontrando algoritmos curiosos para manipular bits. Éste cuenta el número de bits puestos a uno. Es decir, el peso de Hamming. Realmente hay muchísimas variantes y mejoras, pero esta es la más elegante desde mi punto de vista.

int bitcount (unsigned int n) {
   int count = 0 ;
   while (n) {
       count++ ;
       n &= (n - 1) ;  
   }
   return count ; 
}

De bits y binits

Estudiar y aprender es llevarse sopresas. Una de las sorpresas que nos llevamos al aprender teoría de la información es que un bit no es lo que crees que es un bit. Algo que está a uno o a cero, encendido o apagado, pasando corriente o cortándola, ¿no? Pues no. Un bit es algo que está a uno o a cero el 50% de las veces. Si no, no llega a bit. Será medio bit o un cuarto de bit.

La siguiente gráfica indica cuál es la entropía (información en bits) de un binit según la probabilidad de estar a uno o a cero. (Tomada de Wikipedia)

La idea es que el bit es una unidad de información y no de almacenamiento. La unidad de almacenamiento es el binit. Es un hueco donde poder guardar un uno o un cero. Si siempre se guarda un cero o siempre se guarda un uno la información es nula y por tanto ese binit guarda cero bits de información.

Hoy por hoy el concepto de binit se ha fusionado con el concepto de bit y hablamos de megabits por segundo en vez de megabinits por segundo lo cual permite a algunos hacer trampa y "comprimir la información" como si eso fuera posible. En todo caso comprimes la representación de la información. Los binits, no los bits. Pero eso ya son otras divagaciones de las que no vamos a hablar hoy.