sábado, 12 de marzo de 2011

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.

30 comentarios:

  1. Interesante entrada. Esperaremos ansiosos esas otras de las que hablas ;)

    ResponderEliminar
  2. ¡Súper interesante!

    Muy claro y ameno, pero hay una cosa que no termino de entender del todo. ¿Por qué como cifrador elegimos un primo y no uno normal? Es decir, no termino de ver la relación entre el número primo y que sea mayor la fuerza bruta que tengamos que utilizar para alcanzar la clave (mayor número de veces `prueba-error´) que si lo hiciéramos con un número divisible por otro.

    Me interesa además lo que apuntas al final en una futura entrada de espionaje. ¿Te refieres a la famosa máquina Enigma? Con ella los alemanes (al menos hasta que se coscaron los aliados) dominaron el océano y hundían barcos a su antojo y se comunicaban de forma segura.

    No me deja de resultar paradójico que muchos avances tecnológicos y científicos (radar, cifrado, mejoras aeronáuticas...) tengan su lugar en las guerras. Sé que resultaré ingenuo y utópico, pero la Ciencia debería estar sólo enfocada al hallazgo de la paz y progreso humano. Además, los alemanes históricamente con un paso por delante tanto en ingenieros como en sus aplicaciones bélicas...una pena.

    Otra cosa es lo que se entienda por progreso humano...que es muy discutible.

    Abrazos.

    ResponderEliminar
  3. La razón es bien sencilla: si multiplico mi texto por un número que no sea primo eliminamos el problema de la factorización (que es la base sobre la que se fundamente la fortaleza de este tipo de cifrados además de la longitud del número primo).

    Supongamos que en lugar de multiplicar por 727, lo hacemos por ejemplo por 14.619.150. El 14.619.150 es incluso 5 órdenes de magnitud mayor, con lo que cabría suponer un aumento de la dificultad a la hora de hacer cada uno de los cálculos (¡si fuese primo desde luego así sería! :p), ¿no? Pues resulta que la factorización de ese número es 2×3^3×5^2×7^2×13×17, con lo que el cifrado con este número tiene una fortaleza equiparable a si lo hubiésemos encriptado con un número primo de 2 cifras (ese 17 que figura en último lugar).

    Realmente la teoría sobre esto no la conozco (ya decía que no se tanto sobre estas cosas), pero mi razonamiento es el siguiente:

    El ordenador empieza a dividir por números (primero, por los números primos que él conoce; debe tener una lista o un algoritmo para obtener los más básicos y ahorrar tiempo) 2,3,5,7,11,13,17...
    Estas divisiones no son nada difíciles para cualquier ordenador que te puedas encontrar hoy. Cuestión de milisengundos.
    Desde luego, la más complicada de las divisiones es por 17, pero si añadiésemos por ejemplo el 727 utilizado en la entrada, sin duda sería el número por el que más le costaría dividir.

    La cosa es que por cada factorización que hace (por cada primo que encuentra que le da resto 0 en la división) obtiene un problema nuevo más sencillo que el anterior, y lo que pudiera haber sido dividir por números primos hasta llegar a primos de 8 cifras, ha resultado ser varios problemas en los que la solución era un número primo de hasta 2 cifras.

    Quizá, uno podría pensar ¿y si en lugar de utilizar un primo de 8 cifras utilizo varios de menos cifras? Pues la respuesta es la misma que acabo de dar: reduciríamos el problema a que encontrase números primos menores (con los que se trabaja con más facilidad) y cada vez que factorizase, la cantidad a dividir sería menor, con el consecuente ahorro de tiempo de cálculo.

    Espero que eso aclare tu duda :p

    ResponderEliminar
  4. Siento el tocho. Aunque "La razón es bien sencilla", los ejemplos alargan mucho la respuesta jeje

    ResponderEliminar
  5. Gracias elfio,

    Es cierto que los ejemplos alargan la explicación, pero la hace más gráfica y se "ve", se agradece el interés.

    Ahora sí lo entendí, ¡qué primo soy! ;)

    No tenía ni idea de los ordenadores cuánticos, me tuve que ir a la Wiki a ver qué era eso.

    ResponderEliminar
  6. Los ordenadores cuánticos van a ser una locura...

    Ahora mismo hay uno en un centro de investigación de nuestro campus (Reina Mercedes) que realiza el producto 3x5 (=15 :p) más rápido que ningún otro.

    Quizá no sea la concepción que se tiene normalmente de un computador, pero su función es esa: computar, calcular cosas. Sus funciones no van más allá de ese simple producto, pero tiempo al tiempo... :D

    Y los sistemas de encriptación cuántica y se comercializan... ¡y se hackean! sí así es. Resulta que, una vez más, lo invulnerable ha sucumbido al ingenio del hombre. Resulta que introduciendo ciertas fluctuaciones en el suministro eléctrico, se consigue engañar a los ordenadores creyendo que la información se ha perdido en el camino por causas eléctricas, pero en realidad lo que ha ocurrido es que las fluctuaciones eran lo suficientemente grandes como para que creyese eso, pero no como para que los datos se perdiesen, con lo que se pudieron copiar sin problema.

    Estas cosas aun tienen que mejorar bastante, pero lo que parecía infalible (encriptación cuántica) no lo es tanto...

    Un saludo! :D

    ResponderEliminar
  7. No tiene mucho que ver, pero una vez escuché que cuando son pillados los mejores hackers (los que entran en los sitios más protegidos solo para firmar y esas cosas) las agencias de protección pagan sus fianzas y los contratan para que los protejan de otros hackers.

    Paradójicamente, la empresa a la que has puteado es para la que vas a trabajar simplemente por hablerla puteado y, además, porque eres el mejor haciéndolo y para evitar que otros lo hagan.

    Muchas paradojas :)

    ResponderEliminar
  8. Hay que diferenciar entre hackers y crackers.

    Los primeros son de buenas intenciones y lo que hacen es por el bien de la seguridad, mientras que los segundos tienen intenciones no buenas (que no tienen por que ser malas :p)

    ResponderEliminar
  9. Mmmm... no entiendo muy bien la diferencia ¿Tienes algún ejemplo?

    ResponderEliminar
  10. Un hacker puede demostrar (y de hecho lo hace) en público sus habilidades sin que le pase nada malo, y un cracker si se dedica a publicar lo que hace lo empapelan en -1.

    Ejemplos:
    http://es.engadget.com/2008/03/27/concurso-de-hackers-termino-tan-pronto-como-empezo-2-minutos-pa/

    http://www.lifeboxset.com/tecnologia/facebook-2011-hacker-cup/

    http://www.noticias24.com/tecnologia/noticia/710/solo-linux-sobrevivio-al-concurso-de-hackers-pwn-2-own/

    Esas son cosas de hackers, pero los crackers son anónimos bajo sus nicks y si los encuentran normalmente o los meten en la cárcel o les ofrecen trabajar para los 'buenos' (como cualquier hacker)
    :p

    ResponderEliminar
  11. Qué guay lo de concursos de hackers.

    Elfio, ¿por qué no te presentas a alguno? :P

    ResponderEliminar
  12. Podría ir a alguno... pero sólo para ver :p

    ResponderEliminar
  13. Por cierto Elfio, has comentado algo sobre "ordenadores cuánticos" ¿Podrías explicar así por encima qué son? Porque supongo que no son ordenadores muy pequeñitos :)

    ResponderEliminar
  14. Venga...! ese liumeg y sus mini chistes!

    Pues quizá me entere mejor de cómo están hechos y tal y escriba algo :p

    ResponderEliminar
  15. Una pregunta de tontos...

    Si un ordenata cuántico es capaz de resolver al instante una contraseña (llamémosla "contraseña clásica"), al menos sobre la teoría, nuestra privacidad ha pasado a mejor vida (Seguro que los de Google están detrás del desarrollo de esta tecnología, ¿no, elfio?). Digo sobre la teoría porque sobre la práctica aún no hay muchos computadores de estos....(¿afortunadamente?).

    El caso es, la pregunta digo, si sobre computación clásica se inventaron claves "seguras"...ahora con esta nueva tecnología incipiente ¿se inventaran contraseñas "seguras" de acuerdo a estas nuevas "normas"?

    Otra cosa que se queda en el tintero (¿o era teclado?) y no me gustaría que pasara desapercibida elfio, me seguiría gustando mucho leer algo sobre lo que apuntabas al principio de la entrada, lo del cifrado en el mundo del espionaje y si puede ser explica algo de la máquina Enigma.

    Abrazos.

    ResponderEliminar
  16. En absoluto es una pregunta tonta... bueno, puede ser una pregunta en apariencia simple, pero en cualquier caso es importante. En efecto, si cualquiera de nosotros tuviera un ordenador cuántico en su casa, no habría contraseña que se nos resistiera (recordemos que es capaz de probar todas las posibilidades en un instante de tiempo). Para ello se concibe la criptografía cuántica (mas info: http://es.wikipedia.org/wiki/Criptograf%C3%ADa_cu%C3%A1ntica)

    La verdad es que no se cómo va, pero sin duda la privacidad no se irá al traste ;)
    Quizá, la antigua privacidad quede al descubierto, pero confiemos en que se hará una conversión de todo jeje

    Por ahora no hay de qué preocuparse. Los computadores cuánticos que existen hoy día no responden a lo que comunmente se entiende por ordenador. El que hay en el campus de Reina Mercedes (en el CICA) sólo es capaz de multiplicar 3x5. El día en que exista un computador cuántico capaz de ejecutar programas, creo que nos enteraremos :p

    ResponderEliminar
  17. En cuanto a lo de la máquina Enigma y el espionaje, tengo que informarme un poco más y ahora mismo no dispongo de mucho tiempo, así que deberá esperar. Creo que no se me olvidará jeje

    Un saludo!

    ResponderEliminar
  18. Ya está Altair dinamizando esto con esas preguntas que ponen de manifiesto su espíritu de fisikillo.

    Te echábamos de menos Altair!!

    ResponderEliminar
  19. Veréis,

    Es que soy de esos bichos raros que ve La 2, y si bien no en directo, en la emisión, pues a través de la web. Y resulta, que viendo esta entrevista me ha recordado a Liumeg acercándonos la Física. Y también a elfio, con sus ordenadores cuánticos (he de decir, que hasta que elfio no puso esta entrada, para mi estos ordenadores ni existían).

    http://www.rtve.es/alacarta/videos/para-todos-la-2/para-todos-2-fisica-cuantica/1102821/

    La entrevista en realidad no desvela nada, pero apunta un libro que habrá que echarle un ojillo.

    Por cierto, a la pregunta “¿Qué es la Física Cuántica?” a pie de calle…ostras, paletismo total eh. Eso sí, si preguntan con cuantas se ha liao el Rafa pelón ese de Tele5…la cosa seguro que cambia.

    Abrazos.

    ResponderEliminar
  20. Buen aporte el vídeo, eh. Se nota que la tía es física y no dice gilipolleces aunque el presentador la lía un poquillo de vez en cuando, pero vamos, es normal.

    El vídeo me ha dado muchas ideas para hacer entradas, de hecho, me puede servir de guión/base para explicar algunas cosillas que ya tenía en mente, en plan "lo de que la materia pueda estar en varios sitios a la vez se debe a que..." o algo así.

    Ahora no tengo tiempo porque estoy de exámenes, pero cuando vuelva a la carga creo que me basaré en este vídeo para explicar unas cuantas cosillas que considero muy interesantes y a la vez, muy incomprensibles y cercanas a la magia, como lo de que las partículas puedas atravesar paredes (efecto túnel).

    Así que nada, el vídeo ya está guardado en favoritos para poder retomarlo a su debido tiempo, que en su momento dije que iba a explicar las bases de la física cuántica y aún conservo ese objetivo.

    Saludos!

    ResponderEliminar
  21. Hola elfio y gentecilla de por aquí.

    A lo mejor te interesa este documental:

    http://www.rtve.es/m/alacarta/videos/la-noche-tematica/noche-tematica-fabrica-espias/1193839/?media=tve

    ...y a lo mejor te dejas caer otro interesante artículo sobre el tema.

    Ese elfio!

    ResponderEliminar
  22. Le echaré un vistazo :p

    P.D.: si se quita la 'm'
    http://www.rtve.es/m/alacarta...
    http://www.rtve.es/alacarta...

    Se accede a la versión web habitual en lugar de a la versión móvil ;)

    ResponderEliminar
  23. oyeron hablar de La Rosa Polar?
    solaristica.blogspot.com

    ResponderEliminar
  24. La verdad es que no, y además, en el blog que indicas tampoco es que venga mucha información, ¿qué es?

    ResponderEliminar
  25. He estado mirando en wikipedia y al parecer es un tipo de familia matemática de curvas. Las curvas de las funciones de esa familia (r(alfa)=Cos(k·alfa)) dibujan una especie de flor con pétalos al ser representada. En función del parámetro K, la flor tendrá más pétalos o menos.

    Para más información: http://es.wikipedia.org/wiki/Rosa_polar

    ResponderEliminar
  26. Me resulta curioso que en el blog que indicas se utilice ese título con la foto de una expresión matemática, pero que no sea realmente la que define la rosa polar (aunque tenga una exponencial imaginaria que daría lugar a senos y cosenos, no hay ninguna variable;es una constante que ni siquiera es imaginaria (-1))

    ResponderEliminar
  27. Hola Elfio, Queria hacerte una pregunta, la cual estoy intentando averiguar en internet, pero no encuentro nada.
    He visto que has comentado esto

    "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.".

    Queria saber si conoces alguna empresa, o algun sitio donde pueda informarme, que vendan y compren estos números?

    Muchas gracias por toda la información

    ResponderEliminar
  28. LA TIENDITA SE LLAMA EL PRIMO NÚMERO.

    ResponderEliminar
  29. EN UNA OCASIÓN LLEGÓ PEPITO A LA TIENDA DE DON VENANCIO.
    PEPITO LE DICE A DON VENANCIO:
    -DON VENANCIO, DICE MI MÁMA QUE SI TIENE HUEVOS LE MANDE 20 EUROS.
    DON VENANCIO LE ENTREGA 20 MONEDAS DE UN EURO CADA UNA Y LE CONTESTA INDIGNADO A PEPITO:
    -TOMA PEPITO LLEVASELOS A TU MAMÁ Y DILE QUE NO SON MANERAS DE PEDIR FAVORES.

    ResponderEliminar