miércoles, 2 de septiembre de 2015

Números primos y códigos secretos

Primos muy grandes

Inevitablemente todos tendremos estudiantes bostezando en clase, con ganas de hacer un chiste y perder clase o mostrando sincero interés, que nos harán la terrible pregunta de para qué sirven las matemáticas; sin dudarlo mucho, maestros y maestras del mundo acudimos a algunos ejemplos clásicos: sin las matemáticas no tendrías tu celular ni tu facebook, sin las matemáticas se te cae el puente, con matemáticas le ganas al casino y ganas millones, etcétera. Uno de los ejemplos más populares son los números primos y su uso en la criptografía, la base de nuestra comunicación en línea; hay quienes -me incluyo- incluso hablamos de cómo hay compañías que te compran números primos muy grandes en una millonada. 

Lo de la millonada puede no ser cierto; sí hay ciertas fundaciones que pagan decenas o hasta cientos de miles de dólares por números primos que rompan ciertos récords: el equipo que descubrió el primer número primo de más de diez millones de cifras se repartió 100,000 dólares. Actualmente, el mayor primo conocido tiene 17 millones de cifras y feria. La búsqueda de estos números primos gigantes está en gran medida acaparada por GIMP: Great Internet Mersenne Prime search que usa recursos compartidos para buscar primos de Marsenne verdaderamente monstruosos. (Un primo de Mersenne es un número primo de la forma 2^p - 1, donde p es un número primo; por ejemplo 3, 7, 31 y 127 son todos primos de Mersenne para p = 2, 3, 5 y 7. Actualmente conocemos 48 de ellos y GIMP ha descubierto del 35 en adelante, con un gigantesco esfuerzo computacional.)


La otra parte, la de los números primos jugando un papel fundamental en nuestras comunicaciones secretas del internet es completamente cierta. Y, pese a años de citarla como ejemplo, la verdad es que realmente no sabía cómo funcionaba... pero ahora ya sé y de eso vamos a hablar hoy. 

Criptografía viene del griego cryptos, que significa "oculto", y grafé, que significa "escritura". Has hecho criptografía desde que te pusiste de acuerdo con tus amigos de la primaria para "mover" tu alfabeto cierta cantidad de letras, para que sus mensajes estuvieran secretos; ese es un tipo específico de código donde cada caracter se sustituye por otro. (Mis amigos y yo teníamos uno un poco más complicado donde usábamos únicamente la primera letra de cada palabra; así, por ejemplo "Hoy olotes languidecieron acuáticamente" dice, sencillamente "hola". Y digo teníamos porque ahora que lo hice público, ya no podemos seguir usándolo.)


Primero, si viste The Imitation Game (2014), seguro te queda clara la necesidad de comunicaciones cifradas: compartir mensajes en un código que únicamente el que envía y el que recibe conozcan es fundamental en tiempos de guerra, en el salón de clases, en tu celular en caso de que tu mamá tenga acceso a tu whatsapp, etcétera. Internet no es realmente distinto: nuestros mensajes se transmiten por canales públicos, pero deseamos que únicamente el receptor pueda descifrarlo; piensa en tu información bancaria, tus contraseñas, etcétera. 

Segundo, si no viste The Imitation Game, te estás perdiendo de una excelente película.
Ve a verla ahora, aquí espero. 


Ahora, para poder entender el papel de los números primos en la criptografía, vamos a necesitar todo lo siguiente que puedes encontrar en casa. Si lo necesitas, pide ayuda a mamá, papá, o un amigo de confianza. Necesitas:
Todo lo anterior se cubre en un curso básico de Teoría de Números de Olimpiada, por ejemplo en nuestro Diminuto Curso de Teoría de Numeros; acá algunas pruebas importantes también. Como ves, confío bastante en la Wikipedia. Entiendo que no es poca información pero intentaremos dejarlo en términos sencillos y accesibles. No necesitas conocer todo lo anterior para ver cómo funciona el algoritmo de encriptación-decriptación, lo necesitas para entender por qué funciona. 

Vamos a discutir public-key cryptography, o criptografía asimétrica. En una criptografía simétrica, tanto el que envía como el que recibe tiene la misma llave; es decir el mensaje se escribe y se descifra usando la misma llave, que ambos conocen. Piensa, por ejemplo, en un código de sustitución simple donde A es D, B es E, C es F, D es G, etcétera. Si bien este código puede ser seguro en tu salón de clases, con computadoras tardarías relativamente poco en descifrarlo, incluso si usas fuerza bruta; por eso, una criptografía simétrica hace esto mismo con códigos de 56, 128, 256 bits, que te dan quintillones de combinaciones posibles, descartando la viabilidad de la fuerza bruta. 


La criptografía asimétrica usa dos llaves: una llave pública y una privada. La idea básica es la siguiente: tu llave pública es un código que cualquiera puede usar para escribirte un mensaje; sin embargo, esta llave no guarda el secreto para decodificar el mensaje. Así, si tu mensaje es interceptado, de todos modos no puede ser leído sin tu llave secreta, incluso entre aquellos que conocen la llave pública -que es cualquiera, en realidad. En una red cada usuario tiene su llave pública y su llave privada; si A y B se están comunicando, A le escribe a B usando la llave pública de B, B recibe el mensaje y lo lee usando su clave privada, B le escribe a A usando la llave pública de A, A recibe el mensaje y lo lee usando su clave privada, etcétera. 

Esto es, de manera resumida, la public-key cryptography.


¿Cómo se hace?

Aquí es donde vamos a empezar a hablar de números primos. Vamos a hacer un ejemplo con números pequeños, esperando que sea comprensible. Vamos a trabajar con ASCII 256, que son códigos de 8bits. Para cuestiones de seguridad, se pueden usar códigos tan grandes como 128 o 256 bits, es decir 2^256, que es terriblemente grande.  

  1. Supongamos que yo quiero enviarle un mensaje secreto a Yareli. Dicho mensaje secreto consiste únicamente Ü, la u mayúscula con diéresis, que en ASCII es 154. Para ello, yo, que envío el mensaje, necesito conocer la llave pública de Yareli, quien además tiene una llave privada.
  2. Esto es lo que hace Yareli para construir sus dos llaves. Primero, escoge dos números primos p y q. Como estamos usando ASCII 256, necesitamos que pq > 256, por lo que sus primos no pueden ser tan pequeños. Escoge 17 y 29, sin razón aparente; ya tiene la primera parte de su llave pública que es n = pq = 493. Por los teoremas que vamos a usar, necesitamos puros números que sean primos relativos con n, que son en total m = (p-1)(q-1) = 448. Yareli escoge un r, 1 < r < 448 que, además, sea primo relativo con 448. Ella elige r = 11.
  3. Yareli ya construyó su llave pública: (493, 11). Esa es la llave que me da para codificar el mensaje. Todavía no terminamos la llave privada de Yareli, pero con esto es suficiente para que yo codifique el mensaje y se lo envíe. Ahora, es importante tener en mente que, como 493 es bastante pequeño, es también bastante sencillo calcular su factorización en primos y así conocer p y q; no sería igual de fácil con números de millones de cifras.
  4. Yo quiero mandar 154. Lo que yo voy a mandar es la congruencia de (154)^11 módulo 493, que son los dos números de la clave pública de Yareli. Vamos a usar wolframalpha para calcular semejante número, porque una computadora hace eso sin mucho problema. El número que yo envío es 341.
  5. Cuando Yareli recibe 341, necesita usar su llave privada para leer el mensaje. Primero, como r es primo relativo con 448, existe un número s -único- tal que rs = 1 módulo m. (El número s se llama inverso multiplicativo de r, módulo m. En una de las notas demostramos que todo número primo relativo con el módulo tiene inverso multiplicativo.) Ese número es s = 163.
  6. Lo que tiene que hacer Yareli para leer mi mensaje es sencillamente tomar el número que yo le mandé y elevarlo a la s-potencia, calculando su residuo módulo n. Es decir, (341)^163 mod 493. El resultado, por supuesto, es 154.

Más que mostrar por qué funciona esto, quise ejemplificar el algoritmo que se sigue para la encriptación-desencriptación de mensajes usando public-key. Si ya conoces el Teorema de Euler-Fermat, Pequeño Teorema de Fermat, etcétera, a lo mejor no se te complica imaginar por dónde van las demostraciones, por qué funciona el algoritmo, etcétera. 

Insisto, como 493 es un número pequeño, no resulta difícil encontrar p y q, calcular m, y usar esa información para encontrar s. Imagina ese mismo proceso si la llave pública fuera (2630492240413883318777134293253671517529, r). Claro, incluso ese número no es problema para wolframalpha, pero sería una pesadilla con papel y lápiz. (Haciendo algunos experimentos, wolfram ya batalla con producto de primos de 100 dígitos; imagínate primos de cientos de miles o millones de dígitos.)

Algunos puntos importantes: 
  • Es importante que mi mensaje (que en este caso fue 154) y n (que en este caso fue 493) sean primos relativos; cuando p y q son monstruosamente grandes, sería de verdad mucha suerte atinarle a un número que no sea primo relativo. 
    • Fíjate que aunque 493 es pequeño, teníamos m = 448 posibles mensajes a transmitir; incluso así, la probabilidad de elegir un múltiplo de p o de q es de 0.091.
    • Si hubiéramos elegido p = 2017 y q = 287, tendríamos n = 578,879 y m = 576,576. Eso deja la probabilidad de elegir un mensaje no-codificable en 0.0039. Esta probabilidad se acerca a 0 conforme p y q crecen.
  • Observa, además, que los mensajes están doblemente codificados. Es decir, además de las llaves pública y privada, estamos usando el código ASCII para comunicar. Esto es porque nuestras computadoras -y todo el algoritmo criptográfico que estamos usando- transmiten números, hace falta interpretar esos números en un mensaje que podamos entender.
    • Entender esto hace que la observación anterior sobre la probabilidad de elegir números no-descodificables no sea tan importante.
  • El número s es parte importantísima de la llave privada y es posible encontrarlo conociendo p y q, pues eso nos permite conocer m. De nuevo, eso es casi imposible si p y q son suficientemente grandes, pues eso nos permite conocer m y ya conocemos r. Es decir, toda la seguridad se basa en lo complicado que es encontrar p y q.
  • El mensaje que transmití a Yareli fue 154. En 8bits, eso es 10011010. En 128 bits, por ejemplo, cada caracter que envío tiene un código de 128 unos y ceros -y se mandan números más grandes, claro-. Por supuesto, los mensajes son mucho más largos que nada más un caracter; si yo envío una oración de 100 caracteres, por ejemplo, enviaría en realidad 12800 ceros y unos pegados: la computadora sabe contar de 128 en 128 y así tomar cada "letra".
  • Un hackeo en donde se roban los datos personales de millones de usuarios -suena mucho el reciente ataque a Ashley Madison- no busca interceptar la comunicación y descifrar la clave privada. Lo que hacen es acceder a algunos de los nodos en una red -mediante virus, trojanos, etcétera- y desde ahí acceder a las bases de datos. De nuevo, estoy sobresimplificando un problema; hay que entender que nada de esto es tan fácil como en las películas. 



Para trabajar en casa:

Cornell Math tiene un par de retos de decodificación. No te preocupes, son códigos sencillos de sustitución y de transposición. Los de sustitución son más fáciles (y los discutimos brevemente al inicio). Puedes consultarlos aquí. En realidad no trabajamos a profundidad esos temas, por lo que no estaría mal si primero revisas la teoría. 

¿Podrías crear tu propia clave con tus amigas y amigos?


Lee más:

En esta entrada seguimos los siguientes textos, bastante útiles y sencillos de entender. Todas mis fuentes están en inglés, me disculpo. Los ponemos del más accesible al más formal, pero insistimos en que ninguno es complicado de seguir:
También puedes revisar las entradas de Wikipedia para public-key cryptography y para RSA (cryptosystem) que están bastante completas. 




Publicadas por a la/s

1 comentario:

Suscribirse a: Comentarios de la entrada (Atom)