By Zebal
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.
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...
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.
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.
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:
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! :-)
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 algorimto 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.
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 Curba 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 [email protected]. 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 <[email protected]> -----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-----