Un concierto con un catastrófico sistema de validación de
boletos es el argumento del tercer desafío criptográfico con el que EL PAÍS
reta a sus lectores.
 |
| BEL MARTÍN |
―¡Carlos, Carlos! ¡Espera un momento!― gritó Paula a través de la ventana del primer piso del instituto ―Notición: nos vamos al concierto de SUPERSTAR.
Carlos miró a Paula con escepticismo.
―Paula, perdona, el concierto se suspendió. Algo de entradas duplicadas, o se pasaron con el aforo… no sé.
―¡Exacto!― gritó Paula―. Lo han aplazado hasta la semana que viene. Y en el Aula de Tecnología han puesto en marcha un concurso. Hay que contestar tres preguntas y ¡el premio son dos entradas!
A Carlos le encantaba SUPERSTAR, así que se sentó pacientemente mientras Paula soltaba emocionada un torrente de información.
―El concierto se suspendió porque tuvieron varios problemas con la validación de entradas. Verás, cada entrada tiene un número, y para validarlas más rápido, ese número se resumía a través de una transformación que se llama función hash o función resumen. En la puerta del estadio tenían un lector que comparaba el resumen de cada entrada con la lista de resúmenes válidos, para autorizar o no el paso.
―Me está empezando a dar pereza…― protestó Carlos. ―¿Qué es eso de función resumen?
Paula prosiguió, implacable. ―Una función resumen es una función matemática que toma un valor, por ejemplo una ristra de números de cualquier longitud, como el número de una entrada, y te devuelve un resumen, es decir, una secuencia de números corta. Este proceso es irreversible, es decir, si te dan el resumen no puedes volver atrás y recuperar la secuencia de partida. Por otro lado, con la misma entrada, la función te devuelve siempre la misma salida. Paula pintaba dos círculos con puntos y unas flechas en la tierra del paseo, representando lo que estaba explicando.
Estos resúmenes se usan para muchas cosas. Por ejemplo, para detectar y corregir errores al transcribir un número grande; justo ese es el papel de la letra de nuestro DNI, que es un resumen de los dígitos que la preceden. También sirven para detectar si alguien añade un virus a un programa que te bajas de internet: puedes comprobar si el resumen del código que te has bajado coincide con el que está publicado en la web de quien te ofrece el programa. Si no es así, alguien ha modificado el archivo mientras viajaba por la red.
―Y eso no es bueno…― interrumpió Carlos.
―No. Mala señal. Otras veces, se usan los resúmenes para, por ejemplo, acelerar procesos, imagínate que en lugar de llamarnos en el instituto usando nuestro número entero de matrícula, usaran sólo los dos últimos dígitos.
―Pues menudo lío montarían— saltó Carlos - porque seguro que hay varios que tenemos esos dos dígitos iguales.
―¡Eso es!— dijo Paula— ¡Si la función resumen es mala, hay coincidencias, que se llaman colisiones, y no deben usarse… justo eso les ha pasado a los del concierto! Te lo explico, es bastante sencillo. Cada entrada tenía un número identificativo, cuyo resumen se determinaba usando la función CUTREHASH, que divide el número original por 1.024 y toma como resumen el resto de esa división.
―¿Y por qué justo el 1.024?
―Ummm. Eso no es relevante para resolver el problema, pero interesará a quienes recuerden las secuencias binarias. Como validar las entradas ha de ser rápido, ambos números se representan en binario (con unos y ceros), para que puedan leerse fácilmente con un lector óptico. Como 1.024 es 2 elevado a 10, así nos aseguramos que el número resumen va a poder representarse como mucho con 10 cifras (10 bits).
―No veo el problema— dijo Carlos - lo tenían todo muy bien pensado.
―Bueno… no del todo… —sonrío Paula— para empezar, el aforo del estadio era de 10.900 personas, con lo que los identificadores correctos de partida deberían ser números entre 1 y 10.900. Pero con la fórmula elegida hay muchos menos resúmenes que números de entradas, entonces ¡no podía haber un resumen diferente para cada identificador! ¿Recuerdas el Principio del Palomar que vimos en clase? Si tienes más palomas que palomares, algunas han de compartir cama…y justo eso les pasó. En un momento dado, empezaron a llegar personas con entradas válidas y resúmenes que ya habían sido validados por el lector de la puerta, con lo que les denegaron el acceso.
―Madre mía, qué desastre— Carlos parecía preocupado – y, ¿tardaron mucho en darse cuenta?
― En realidad no, Carlos, piénsalo… Esa es la primera pregunta del concurso. ¿Cuánta gente como máximo y como mínimo había entrado en el estadio cuando llegó la primera persona con un resumen repetido?
― Venga, lo pienso. Pero, si no tardaron tanto en darse cuenta, podrían haber celebrado el concierto un poco más tarde ¿no?
―Intentaron hacerlo. Al comprobar que usar solo el resumen era un mal método, decidieron validar las entradas de otra forma, comprobando dos cosas: que el identificador no hubiera sido utilizado antes y que su resumen estuviera bien calculado (usando así el hash para corregir posibles errores de impresión). Pero tampoco funcionó. Unos maleantes, conocedores del defectuoso sistema de validación, habían falsificado miles de entradas con sus correspondientes resúmenes, desde la que llevaba el identificador 10.901, hasta la numerada con el 99.999. ¡Y de eso solo se dieron cuenta cuando claramente los asistentes desbordaron el aforo!
Y ahora vienen el resto de preguntas del desafío. La segunda es fácil: ¿Podrías encontrar el número de una entrada válida cuyo resumen dé el mismo valor que la entrada con identificador 4.410? Y la tercera, más complicada: ¿Cuántas entradas válidas y cuántas en total, contando las falsificadas, tenían el mismo resumen que esa numerada con el 4.410? ¡Tenemos que darnos prisa, el premio son dos entradas de las buenas!
―Pues, ¡al lío!— ahora sí que Carlos estaba convencido — ¡Vamos a ir al concierto de SUPER STAR fijo!
Los desafíos criptográficos se publicarán cada 15 días. Los lectores pueden dejar sus soluciones y debatir sobre el problema en los comentarios de esta página, por lo que se recomienda a quien quiera resolverlo por sí mismo no leerlos hasta haber descifrado el enigma. También pueden enviar sus respuestas al correo desafioscriptograficos@gmail.com. En cada nuevo desafío publicaremos la solución del anterior, acompañada de un comentario con algunas ideas originales o inspiradoras que hayamos recibido.
Ana Isabel González Tablas Ferreres, @aigtf, es Doctora en Informática y profesora e Investigadora del grupo COSEC de la Universidad Carlos III de Madrid.
Fuente: El País
/cloudfront-us-east-1.images.arcpublishing.com/elespectador/EJXU4SPL55DW7INGB6ZI5DYFEA.jpg)
.jpg)