Encriptación y números primos (por Elfio)

Hola a todos.

Liumeg, tal y como me pediste voy a tratar de escribir una pequeña entrada en la que explicaré lo poco que sé sobre la parte más fundamental de un cifrado típico. Antes de nada, aclarar que mis conocimientos sobre el tema son bastante limitados. Si no os enteráis de mucho, después de los ejemplos explico algunos conceptos importantes :P

Para empezar, tenemos que pensar como si fuéramos un ordenador. Ellos sólo entienden de 0 y 1 (binario) y cualquier dato que tengamos en nuestro PC no será más que una combinación de esos dígitos. Una imagen, un archivo de texto, un número, un vídeo, o cualquier otro archivo no será más que una simple (más que simple, bastante larga) combinación de unos y ceros. Esto es fundamental para entender cómo funciona.

El método no puede ser más simple: se multiplica nuestro archivo (o número) por un número primo y ya tendremos nuestro archivo (que sigue siendo un número) encriptado. Para desencriptarlo no hay más que conocer el número primo por el que se multiplicó, y dividirlo por ese mismo número. De esta forma volveríamos a tener el archivo (o número) original.

Veamos un ejemplo: supongamos que ese archivo que queremos cifrar es, en el sistema decimal, el número 123456789 (en binario sería el 11110001001000000). Para que no sea difícil, tomaremos como número decimal el 727.

Si lo encriptamos (multiplicamos) nos queda: 89753085603 

(en binario 1010011100101101100110110011010100011)

Ahora el archivo puede viajar por cualquier parte sin que su contenido sea leído, ya que nadie sabe qué número primo hemos usado para su encriptación. Para revelar su contenido, no tenemos más que dividirlo por 727, con lo que nos quedaría de nuevo el número original: 123456789

Si quisiéramos realizar un intercambio de información entre dos personas, necesitaríamos dos números primos (sean a,b). Primero se envía la información multiplicada por el número a, viaja hasta su destino donde se multiplica por b. Ahora, vuelve hasta su origen para ser dividida por a, y de nuevo a su destino donde ya, una vez dividida por b es legible.

Para aclarar todo un poco, hay algunos detalles en los que creo que habría que profundizar un poco:

¿Qué es un número primo?. 

Los números primos son la clave del asunto y la razón de que así sea es porque no son factorizables. Las empresas se gastan verdaderas fortunas en comprar números primos lo suficientemente grandes (millones de cifras) para encriptar sus datos.

¿Qué quiere decir que un número sea factorizable?

Significa que, para que en una división dé como resto un número entero, sólo lo puedes dividir por él mismo y por 1. Si lo divides por cualquier otro número, te dará un número con decimales (o como se dice en el mundo de la informática un no entero, o con coma flotante).

La fortaleza del cifrado estriba en que cuanto mayor sea el número primo por el que multiplicamos nuestro archivo (o número), mucho mayor será la potencia de computación que hará falta para encontrar dicho número por fuerza bruta. La factorización de números enteros supone hoy día uno de los mayores problemas de las matemáticas en computación. Más info-> http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_enteros

La llegada de los ordenadores cuánticos amenaza los sistemas de encriptación actuales debido a que son capaces de factorizar de forma 'instantánea' cualquier número entero. Hay que tenerlos en cuenta, aunque aún quedan unos años para que sean funcionales. Con su llegada los sistemas de cifrado deberán cambiar a un sistema cuántico que ya se comercializa hoy día.

¿Qué es la fuerza bruta?

No es ni más ni menos que probar todas y cada una de las posibles combinaciones hasta dar con la acertada. Todos los cifrados se pueden romper por fuerza bruta, pero el tiempo necesario suele ser ingente. Un sistema de cifrado no se considera roto (ya no serviría más) hasta que no exista otro medio más rápido que la fuerza bruta para desencriptar el archivo.

Este es el sistema sobre el que se fundamenta todo, luego hay multitud de variaciones con sistemas matriciales, permutaciones, intercambios y un largo ectécera. Tradicionalmente se piensa que la fortaleza de un método de cifrado ha de residir en las claves utilizadas y nunca en el algoritmo, aunque como en todo, hay quien no piensa así.

Si queréis, en entradas futuras podría hablar del tema del cifrado más enfocado hacia el tema del espionaje, temas que están profundamente ligados. La Segunda Guerra Mundial y la posterior Guerra Fría fueron grandes caldos de cultivo para todas estas cosas.

¡Un saludo y espero que os haya gustado!:D

elfio.