TARDÍGRADOS

Ciencia en español

¿Es posible comprimir 4 terabytes de datos en tan sólo 16 bytes?

Posted by Albert Zotkin en mayo 12, 2016

La respuesta a la pregunta del título es sí. Hola amigos de Tardígrados. Hoy voy a hablar de un método poco estándar de comprimir información binaria sin perdida. Este método es simplemente una curiosidad que se me ocurrió el otro día. Lo llamaré Compresión Estocástica de Datos Binarios, CEDaBit.

Supongamos que tenemos el siguiente archivo jpg de la Mona Lisa:

Mona_Lisa

que es una imagen de 560 pixels de ancho por 864 de alto. Es decir, sin comprimir, en total tenemos 483.840 pixels, y si cada pixel se puede describir por 3 bytes, tendremos en total una imagen de 1.451.520 bytes, y como cada byte consiste en 8 bits, tendremos una imagen de 11.612.160 bits. Pero esa imagen está codificada y comprimida en un archivo JPG, por lo tanto no son raw data (datos primarios), el tamaño es mucho menor. En dicho archivo existen también datos de cabecera y cola en los que se almacena más información. Si queremos “comprimir” en un CEDaBit todo el archivo JPG, debemos “comprimir” una cadena de 46.474 bytes. ¿Cömo lo haremos?.

Supongamos que queremos comprimir a un CEDaBit de 16 bytes. Para ello, lo primero que tenemos que hacer es calcular un hash de esos datos. Yo usaré un hash muy conocido llamado MD5, y para calcular dicho hash usaré una página online que posea una herramienta de cálculo, por ejemplo esta: Online MD5.

Subo el archivo a dicha página, y me calcula el siguiente hash para dicho archivo: 9E00544CEE3B677CA2E826980D9CF02A. Es decir, me da una cadena de 16 bytes, que es su MD5, es como la huella característica de ese archivo en concreto. Cada archivo de datos binarios posee un hash que casi es único, digo casi porque en realidad conjuntos de datos muy distintos pueden poseer el mismo hash, y a eso se le llama colisión. Pero, es muy probable que para ese archivo de ese tamaño que he usado no existan muchas colisiones de su hash MD5. Existen miles de páginas en internet y aplicaciones que calculan todo tipo de hashes para cadenas de bytes, pero no encontrarás ninguna que haga la tarea inversa. Es decir, calcular una cadena de bytes desde su hash no es trivial. De hecho, existen infinitas cadenas que resultarían de un mismo hash. ¿Cómo podemos saber cual es nuestro archivo al expandir un hash en una determinada cadena de bytes?. Tenemos que saber por otros medios cual es el tamaño del archivo que queremos recuperar. Por ejemplo el archivo jpg de la Mona Lisa de arriba sabemos que posee 46.474 bytes, ni uno más ni uno menos. Por lo tanto, tenemos 371792 bits, es decir, tenemos un número binario de 371792 bits. Así pues para recuperar nuestra Mona Lisa desde su Hash 9E00544CEE3B677CA2E826980D9CF02A, sólo tenemos que ir variando los ceros y los unos de esa cadena de 371792 bits y a cada paso calcular un hash y ver si coincide con el del archivo. ¿Cuántas variaciones de ceros y unos posee una cadena de 371792 bits?. Pues, precisa y exactamente posee tantas variaciones como representa ese mismo número binario. Por ejemplo, el número binario 111, que son 3 bits, representa al número 8, que es 23, y posee exactamente 8 variaciones de ceros y unos, es decir, 000, 001, 010, 011, 100, 101, 110, 111. Por lo tanto, nuestra Mona Lisa posee exactamente 2371792 variaciones de ceros y unos. Un número muy superior al de partículas subatómicas en nuestro universo observable. Supongamos que tenemos un superordenador capaz de calcular un trillón de esas variaciones binarias por segundos y de decidir a cada paso si ha encontrado una solución (coincidencia de hash). Incluso a esa velocidad de cálculo, tendríamos que esperar miles de trillones de veces la edad de nuestro universo (13 mil millones de años) para ver completadas todas las variaciones binarias, y poder afirmar con seguridad que hemos recuperado nuestra Mona Lisa desde su hash. El número 2371792 posee 111.921 dígitos en el sistema decimal, y por muy rápido y potente que sea nuestro super ordenador, la tarea de expandir ese hash en la cadena original de bytes es una tarea imposible. Pero, si nuestro ordenador es un ordenador cuántico de más de 371792 qubits, ese cálculo se podría hacer en unos pocos minutos, con lo cual, posiblemente, mediante esa computación cuántica, obtendríamos una carpeta de colisiones, con una serie de archivos de igual tamaño y todos con el mismo hash.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

 
A %d blogueros les gusta esto: