INTRODUCCIÓN A LA CRIPTOGRAFÍA DE CLAVE PÚBLICA

Parte I

Introducción:

Hasta ahora estareis acostumbrados a encontrar programas y algoritmos que encriptan cosas. Os piden un password, se lo dais, y ya está, os encriptan lo que sea. Luego, cuando quereis recuperar la información necesitais el mismo password para poder desencriptar. Estos programas se basan en criptografia de clave simétrica, o sea, la clave que necesitas para encriptar y para desencriptar es la misma. Afortunadamente, estos no son los únicos tipos de algoritmos de encriptación que existen. Existen otros algoritmos de encriptación en los que la clave que necesitas usar para encriptar y la que necesitas usar para desencriptar no son la misma, y además no puedes calcular una a partir de la otra si no dispones de datos adicionales. Este tipo de algoritmos son los llamados algoritmos de clave pública.

Utilidad y funcionamiento:

Si tú quieres comunicarte con un amigo que vive lejos usando un canal no seguro (por ejemplo, internet, donde cualquiera te puede sniffar la conexion y ver los datos que circulan) te puede interesar enviar las cosas encriptadas. Que pasa si encriptas los datos a enviar con una clave simétrica? Pues que tu amigo necesita conocer esta misma clave para poder desencriptar los datos que le lleguen... y... cómo le haces llegar la clave de forma segura? :-? La única forma sería que se la dieras tú en persona, así seguro que nadie la chafardea... pero muchas veces eso no es posible (por ejemplo, a tus amigos del IRC no los ves nunca en persona). Por eso se han desarrollado estos otros algoritmos de clave pública. En este caso, tu amigo te enviaría su clave pública, tú encriptarias los datos con la clave pública, y se los enviarías. Nadie, salvo quien tiene la clave privada correspondiente a esa clave pública será capaz de desencriptar los datos. Estos algoritmos se construyen de forma que dada una clave pública sea IMPOSIBLE obtener la clave privada correspondiente. Así que si tu amigo se ha guardado la clave privada bien guardada, los datos que tú le envies encriptados con su clave pública sólo los podrá leer él, que es el único que tiene la clave privada correspondiente. Con esto ya aseguras que sólo el destinatario (tu amigo) puede leer lo que tú has encriptado para él. Y que pasa si alguien captura la clave pública cuando tu amigo te la enviaba a ti? pues nada, sólo podra enviar info encriptada a tu amigo pero a partir de la clave pública no podrá calcular la clave privada y, por tanto, no podrá desencriptar los datos que tú envíes a tu amigo. De esta forma, cualquiera que tenga la clave pública de tu amigo (por ejemplo tú) le puede enviar datos sin temor a que alguien los pueda chafardear, ya que el único que podrá ver los datos será tu amigo... Y no necesitas un canal seguro para obtener la clave, ya que la clave que te envia tu amigo sólo sirve para encriptar, y aunque la capturen no podrán leer los datos que tú le envias a tu amigo... 

Base Matemática:

Ahora os voy a presentar un mundo un poco extraño, donde las matemáticas que conoceis no funcionan como esperais... Es un mundo donde vamos a trabajar siempre "módulo n", o sea, un mundo donde se cuenta 0, 1, 2, 3, 4, ..., n-2, n-1, 0, 1, 2, 3, ... Como se opera en este mundo? Pues fácil: 

(n-1) + 1 == n == 0
2 * (n-2) == 2n-4 == (n-4)
4 - 8 == -4 == (n-4)
42 == 16
(23)2 == 2(3*2) == 26 == 64

Si os fijais, operar en este mundo es como hacerlo normalmente con los números enteros sólo que cuando el número da más grande que n-1 o da más pequeño que 0, pues se le suma o se le resta n tantas veces como sea necesario hasta que salga un número comprendido en el rango [0..n-1]. Las propiedades de las operaciones +,-,*,/,^ se cumplen igualmente. Ah! y n es un número entero que fijaremos al principio. Si no fijamos n no podemos hacer gran cosa ya que el mundo no estará completamente definido... Este maravilloso mundo tiene un problema, y es... cómo se divide? :-? imaginemos que queremos dividir 4/2... esto es sencillo, da 2. Pero las cosas se complican si dividimos 4/3. Cuanto da eso? Pues bien, la forma habitual de entender la división en este mundo es tratarla como el producto por el inverso... el qué? el inverso, sí... el inverso de un número es aquel otro número tal que el producto de ambos da 1. Por ejemplo, el inverso de 1 (yo lo escribiré 1-1) es 1 ya que 1*1==1 pongamos que queremos encontrar el inverso de 3 módulo 10... pues será aquel número t tal que (3 * t) mod 10 = 1 ... veamos... mmmmm... t = 7! Comprobemoslo: 3*7==21==11==1 sip! 7 es 3-1 en el mundo "módulo 10"... Si en este mundo queremos hacer 4/3 sólo hemos de hacer 4*(3-1) o sea, 4*7=28=18=8... así que 4/3 en este mundo da 8. Quien lo iba a imaginar, eh? Ahora faltaria que 8*3 diera 4 para que se cumplan las propiedades que conocemos... a ver... 8*3==24==14==4 anda, pues sí! 

Vale, ya sabemos dividir... bueno, siempre que sepamos calcular el inverso de un número... mmmmm... calcular inversos parece un problema complicado... realmente lo es? pues... depende de las circunstancias... El inverso de un número depende del mundo en el que estemos trabajando, o sea de la n del mundo "módulo n" en el que juguemos... Para cada n, el inverso de un número puede variar. Además, para calcular el inverso de un número en un mundo de estos, la cosa puede ser muy muy complicada, ya que hasta el momento sólo se sabe calcular el inverso de un número módulo n si n es primo o si sabemos escribir n como producto de números primos. En cada mundo "módulo n" existe un número f(n) tal que cualquier número en el rango [0..n-1] elevado a f(n) es igual a 1, o sea, que para todo x se tiene que xf(n) == 1 mod n. Si nos fiajmos, tenemos que x * xf(n)-1 == 1, así que parece que si multiplicamos x por xf(n)-1 obtenemos 1... y eso es precisamente lo que ha de cumplir un inverso! :-) Así que si somos capaces de calcular f(n) podemos calcular el inverso de cualquier número simplemente haciendo xf(n)-1... Qué fácil, nop? :-) Pues bien, en caso de que n sea un número primo, no es difícil calcular f(n). Simplemente, f(n)=n-1. Si n lo podemos escribir como producto de números primos, hay un teorema (el teorema chino de los restos) que nos permite obtener el inverso a partir de calcular el inverso en cada uno de los mundos "módulo qi" donde qi son los factores primos de n. Por ejemplo, si n = p * q, se llega a que f(n)=(p-1)*(q-1). Sólo hemos de conocer la descomposición de n en factores primos para calcular f(n) y poder así calcular el inverso de cualquier número en ese mundo "módulo n". En caso de que no sepamos factorizar n, la única forma de encontrar el inverso de un número "módulo n" es provando todos los números entre el 2 y el (n-1) a ver cuál de ellos cumple que multiplicado por el número original el resultado sea 1 mod n.

Hasta aquí os gusta el mundo?? ... no?? pues los algoritmos de clave pública existen gracias a este mundo y otros similares. Ya que os habeis tragado todo este rollo matemático voy a explicaros un algoritmo que funciona en ese mundo para conseguir que la clave con la que encriptas y la clave con la que desencriptas sean diferentes. 

De las matemáticas a la encriptación:

Suponte que cojes un número (m) y lo elevas a otro número (e): 

me == c mod n (n es primo)

c es el resultado de esa operacion. A partir de c, como obtienes m?? pues veamos: 

sabemos que (me)d == m(e*d) vale, pues a partir de esto, si encontramos un d tal que e*d==1 mod n ya tenemos la forma de desencriptar: cd == (me)d == m(e*d) == m1 == m mod n o sea, elevamos c a d y obtenemos m... y d y e son dos números tal que e*d==1 mod n, pero no tienen por que ser iguales. Si m fuera un trozo de un mensaje que queremos encriptar, el mensaje encriptado obtenido (c) se consigue usando una clave (e) distinta de la clave que necesitamos para recuperar el mensaje original (d). 

Así que en este caso, m serian los datos a enviar, {e,n} la clave pública, {d,n} la clave privada, y c lo que envias por internet a tu amigo, o sea, el mensaje encriptado! :-) Como ves, d y e no son iguales! Así que aunque tu amigo te envie e y alguien lo vea, no pasa nada, porque no podrá obtener m a partir de tener c, e y n... necesita d! :-) y como calculamos d?? pues... en este caso es fácil: e*d == 1, o sea, d == 1/e, es decir, d == 1*(e-1) == e-1 si podemos calcular el inverso de e ya tenemos d... y el inverso de d se puede calcular fácilmente porque n es primo! :-) vaya... pero... yo sólo he necesitado n y e para calcularlo... así que... cualquiera lo puede calcular! :-( Eso no es lo que yo queria... Parece que cualquiera que pueda ver e podrá calcular d y entonces podrá descifrar mi mensaje c! :-( Eso no es lo que dije antes, verdad?? Dije que teniendo e no se tenia que poder calcular d... Así que todo lo que hemos hecho no sirve para nada?? Deberiamos tratar de arreglar un poco esto para que no sea tan fácil calcular d a partir de e! Y cómo hacemos para que sea más difícil el cálculo de d?? pues... haciendo que n no sea primo... :-) Hagamos que n sea realmente el producto de dos números primos p y q, y que nadie más que la persona que ha de recibir el mesaje conozca p y q... a partir de n sólo se puede encontrar p y q si factorizas, pero factorizar es un problema también muy difícil del que luego hablaré un poco. Ahora veamos cómo queda modificado el algoritmo que teníamos si n deja de ser primo:

como n no es primo, ya no es cierto que f(n)=n-1, y en su lugar, lo que se cumple es que f(n)=(p-1)*(q-1), así que suponiendo que c==me, hemos de conseguir un d tal que cd==m, o sea, que (me)d==m, o lo que es lo mismo, que m(e*d)==m, o sea, que e*d==f(n)+1 Y como obtenemos d?? pues fácil, e*d==1 mod f(n), así que d==1/e==e-1 mod f(n), y para calcular d ahora necesitamos pode calcular f(n)=(p-1)*(q-1), o sea, necesitamos conocer p y q, cosa que sólo conoce el receptor, ya que aunque n=p*q nadie es capaz de factorizar un número muy grande en sus dos factores, y si no te lo crees, intenta factorizar este pequeño n de sólo 20 cifras, y obtener sus dos factores p y q... ;-) 

66024717357306257987

Por cierto, el hecho de que se use un n producto de sólo dos números primos es porque cuantos más factores tenga n, más fácil es de factorizar. Me explico, si n=p*q se sabe que o bien p o bien q estará por debajo de sqrt(n) (o sea, raíz cuadrada de n), en cambio si n=p*q*r lo que se sabe es que alguno de los tres factores está por debajo la raiz cúbica de n, que es un número aún menor que sqrt(n). Así que para factorizar n basta con probar a dividirlo por números más pequeños que ese límite que se conoce. Y el límite preferible es sqrt(n), que es mayor que la raiz cúbica y, por tanto, obliga a hacer más pruebas para factorizar n. Es por eso que se usa un n compuesto únicamente de dos factores primos p y q. 

Otra cuestión respecto a los números primos escogidos para generar n es que han de estar muy separados, o sea, que (p-q) sea un número grande ya que sino existen ataques que permiten factorizar n. También es importante que p-1 y q-1 sean números que tengan ambos por lo menos un factor primo muy grande ya que, en caso contrario, también es muy sencillo factorizar n.

Un algoritmo que se basa en todo eso: RSA

RSA es uno de estos algoritmos de clave pública que se basan en lo que os he explicado en el apartado anterior. Su funcionamiento es muy simple: 

  1. Se eligen 2 números primos, llamemosles p y q.

  2. Se calcula n=p*q.

  3. Se escoge un número e en el rango [2..n-1] que cumpla ciertas cosas. Para que el inverso de e sea difícil de calcular, e no puede valer 1 (el inverso de 1 es 1) ni tampoco puede ser múltiplo de (p-1)*(q-1), ya que calcularemos d como e-1 en el mundo "módulo (p-1)*(q-1)", y si e es múltipo de (p-1)*(q-1) tendriamos que e==0 en ese mundo, así que no podríamos calcular su inverso! :-( [dime un número que multiplicado por 0 de 1 en el mundo módulo (p-1)*(q-1), o lo que es lo mismo, dime cuanto vale 1/0 en ese mundo...].

  4. Ahora se calcula d == e-1 mod ((p-1)*(q-1)). Como os dije antes, hay un teorema que permite calcular esta d sin problemas, sólo que necesitamos conocer p y q.

La clave pública es {n,e} y la privada es {p,q,d} Así que tú le pides a tu amigo, al que quieres enviar datos, su clave pública, y él te envia {n,e} a tí... Tú ahora, codificas tu mensaje como una tira de números entre 0 y n-1 y a cada número m le aplicas c = me mod n y envias cada uno de esos números c después de aplicarles la operación. Ahora tu amigo recibe cada número y hace m = cd mod p*q (o sea, mod n ya que n=p*q) y obtiene los números originales entre 0 y n-1 que son en realidad tu mensaje desencriptado. Supongamos que en este proceso alguien captura lo que circula por la red, o sea, {n,e} y c. Qué puede hacer?? :-? Pues realmente nada: Necesita d para poder desencriptar los datos c, y para calcular d necesita tener e y saber los 2 factores en los que se descompone n. O sino, puede intentar calcular m como la raiz e-ésima de c módulo n, pero eso también es un problema muy difícil. Así que, este sistema, en qué basa su seguridad?? pues en 2 cosas: 

Pues bien, este algoritmo que os he explicado es el RSA. Es un algoritmo que está patentado en USA (o sea, que para implementarlo y usarlo has de pagar derechos), pero que es libre en el resto del mundo, es decir, que si no vives en USA puedes usarlo sin problemas. Este algoritmo se lo inventaron tres señores cuyos apellidos eran Rivest, Shamir y Adleman, así que le pusieron de nombre las iniciales de sus apellidos: RSA. Como veis, eran muy poco originales! :-)

Programas:

Hay varios programas que se basan en todo esto que he explicado para encriptar/desncriptar. El más popular es probablemente el PGP. PGP es un programa que te permite encriptar algo con la clave pública de los receptores a los que va destinado y desencriptar con la clave secreta si es que tú eres el receptor de un mensaje cifrado. Encriptar usando algoritmos de clave pública tiene 2 inconvenientes: 

Estos dos inconvenientes se pueden solucionar fácilmente, tal y como lo hace el PGP. En lugar de encriptar el mensaje con un algoritmo de clave pública, lo encripta con un algoritmo de clave simétrica usando como clave simétrica algo absolutamente aleatorio e impredecible. A continuación, encripta la clave simétrica que ha generado para encriptar usando las claves públicas de los destinatarios. El resultado es un mensaje encriptado con una clave que nadie conoce, seguido de esa clave, pero encriptada con la clave pública del destinatario. Si hay más de un destinatario, se añanade la clave simétrica encriptada tantas veces como destinatarios haya, encriptandola cada vez con la clave pública de uno de los destinatarios del mensaje. Con esto, uno de los destinatarios del mensaje puede desencriptar la clave simétrica (una de las copias encriptadas que hay va destinada a él así que está encriptada con su clave pública) y con la clave simétrica puede desencriptar el mensaje completo. De esta forma conseguimos acelerar el proceso (encriptar con clave simétrica es muy rápido, y con clave pública sólo se encripta la clave simétrica que es algo muy corto), y además permitimos que varias personas puedan desencriptar el mismo mensaje cifrado (ya que la clave simétrica necesaria para desencriptar el mensaje está encriptada con la clave pública de cada receptor, y añadida al final del mensaje encriptado). Así que un documento encriptado con PGP está formado por varias partes: 

mensaje original encriptado con IDEA, usando una clave K generada aleatoriamente en el momento de encriptar el mensaje.

K encriptada con la clave pública RSA del receptor 1.

K encriptada con la clave pública RSA del receptor 2.

Ahora, si os fijais, la seguridad del sistema no sólo depende de que no se pueda hayar la clave privada de alguno de los receptores del mensaje sino también de que no se pueda encontrar K. Para ello, el algoritmo de clave simétrica que usemos ha de ser robusto y seguro, y lo que usa PGP 2.6.x (es decir, IDEA) lo es... al menos de momento. Y también ha de ser realmente impredecible la K, es decir, hemos de poder generar números realmente aleatorios para formar la clave K y que esos números no sean predecibles. Respecto a las claves públicas, existen métodos para factorizar un n de forma rápida, basados en propiedades matemáticas extrañas. De todas formas, aumentando el tamaño del número n se consigue hacer que estos métodos sean muy muy lentos. Por eso se recomiendan claves públicas en las que n sea un número de 512 bits, 768 bits, 1024 bits, o incluso 2048 bits si usas PGP 2.6.3i. Mi recomendación es que useis una clave de 2048 bits, ya que actualmente se han conseguido factorizar números de 129 digitos (512 bits aprox.) y se espera que pronto caigan los de 768 bits. En realidad, es posible que alguna agencia en USA ya sea capaz de factorizar 768 bits, ya que todas ellas invierten millones de dollares en investigación sobre estos temas cada año, y, al contrario que en las universidades, no comparten sus resultados con el resto del mundo. A nivel civil, se cree que se podrán factorizar números de 1024 bits en el 2004, y de 2048 bits en el 2014 si es que no se descubre nada nuevo que suponga una revolución en este campo... Es de suponer que los militares, la CIA, el FBI, etc... nos llevan ventaja, así que ponerse una clave de 2048 es bastante recomendable. 

Consideraciones finales:

A ver, he intentado mantener a las matemáticas lo más alejadas posible de este documento, así que no os he hablado de ciertas cosas y no os he demostrado algunas propiedades, ya que lo que me interesa es que entendais la idea de cómo y porqué funciona, no que saqueis un 10 en las asignturas de álgebra o matemática discreta. Eso quiere decir que me he comido algunos detalles y que no he justificado ciertas cosas. Entre los detalles que no he mencionado es la forma en la que hemos de escoger p y q. No cualquier pareja de números primos nos sirve, ya que si se cumplen ciertas cosas, es fácil factorizar n... :-( Así que ya sabeis, si queréis conocer más detalles, leed libros serios sobre criptografía en los que no se ahorren esos detalles, o sino, haced la carrera de matemáticas! X-D 

Por último, deciros que últimamente han salido por ahí PGP 5.0 y 5.5, que no son compatibles con 2.6.x ya que no usan los mismo métodos de encriptación que 2.6.x (o sea, no usan ni IDEA ni RSA). En su lugar usan un problema conocido como "El Gamal" y encima no lo hacen en el mundo que os he explicado ("módulo n") sino en un mundo montado sobre Curbas Elípticas. Esto les permite conseguir la misma seguridad que antes pero usando claves más cortas (de menos bits). Además, este algoritmo no está patentado así que se puede usar en cualquier sitio sin pagar derechos a nadie. El problema es que el mundo de las Curbas Elípticas no está aún muy estudiado, y cualquier día descubriremos que es más fácil moverse en ese mundo de lo que ahora parece, y los métodos criptográficos basados en ese mundo dejarán de ser seguros. Se le han encontrado algunos problemas a las Curbas Elípticas, pero hasta ahora nada serio que comprometa la seguridad de los algoritmos de encriptación... de todas formas, se llevan estudiando demasiado poco tiempo como para asegurar que no tienen truco, por lo que de momento creo que es preferible usar PGP 2.6.3i mejor que PGP 5.0 o 5.5 ya que RSA ha soportado muchos y muy variados ataques que se han probado, y el mundo de los cuerpos finitos está mucho más estudiado y se conoce mucho más a fondo y desde hace más tiempo. Además, la seguridad de "El Gamal" no reside en la imposibilidad de factorizar un número o en el cálculo de raices e-ésimas sino en que no sabemos calcular el logaritmo discreto de un número en ese mundo. El problema de calcular un logaritmo discreto se supone igual de difícil que el problema de factorizar, pero en el caso del logaritmo discreto se sabe que existen funciones en ciertos mundos que tranforman ese cálculo en calcular simplemente un inverso, cosa muy sencilla, ya que aquí no hay que factorizar nada, con lo que hay que escoger el cuerpo sobre el que se trabaja de forma muy cuidadosa para no sea posible hallar una de esas funciones. Y el cuerpo que se ha escogido es uno que no conocemos mucho, o sea, uno sobre una Curva Elíptica... así que saca tú tus propias conclusiones sobre la seguridad que te puede ofrecer PGP 5.x. 
 

Y como siempre, las sugerencias, consultas o críticas destructivas que tengais las podéis enviar a z3b4l@iname.com. Y aquí teneis mi clave pública PGP 2.6.3i de 2048 bits por si me quereis enviar algo encriptado para que solamente yo pueda desencriptarlo.

Tipo Bits/Clave    Fecha      Identificador

pub  2048/4AE73665 1998/07/19 Zebal <z3b4l@iname.com>

 

-----BEGIN PGP PUBLIC KEY BLOCK-----

Version: 2.6.3i

 

mQENAzWyABwAAAEIALS8PuClNEaEnhAfUxaM+sh8mgZGpJTNXvWGBC/J4VrNvDlC

IDDoYLbRkG5Fbf6fNG89oUI3SiottK7FJysKI28ZR3D4mfy1KIEhuCchlsW8ll+5

uHbEcn9exlJ5VXQYuxCRXkMsNurK5b0TSzvcejuFo55kNCpua8/pqv3o7WS12DS6

kuhCArRyfRMbS34T3IxLpvKPb8bXvW4iaA9Hnp3jlYotVdryQovJzfoOmSU7r/ZB

tbAy/2zNInNasgNwFnH5IjxrKkNlb3kVcHSAfoPrHjuusuBagoJRUJEwm4vAQ9MD

cEkejAwgS8rNkpoc+I2q9YQMLu5EqqhHzkrnNmUABRG0F1plYmFsIDx6M2I0bEBp

bmFtZS5jb20+iQEVAwUQNbIAHqqoR85K5zZlAQEJDwf/ZgFUK5rWGRZlF4Vlln6P

bbu7jSPySIiH08OJQzaV+W1oNK7ebGlmN60kypsr5h3FoDNxxhJ+hA0H10tMLOSY

b3pNxA2OOnQ6yh7KKWKSnySrP5xl4nuj9l3ZBPBGs8S8dtGQauNKPVhdVL0920KN

HtUCH1R28SHImnEI+KhNA3w07k384m8+8rQ8HLDuJgt3wK4PnLFdmXZX3w1kZ/Vt

ibqXW2eqsRoXTgwMLDORhDEpMxZmf6KYhlTMHEv9yyxq9yhzccZO4FjeUlGztZ2f

m2bDRYU5SfCUrXC1BBYWa2yOQyQ9qZ/FGl9wUWcv2mjHrPdjnhs64JRo89Bb7dJP

bA==

=/mJT

-----END PGP PUBLIC KEY BLOCK-----

(Hispahack 22-7-98) By Zebal