Mecanismo De Proteccion

Calves Públicas

Para entender bien lo que trata una clave o llave pública es necesario entender el concepto de “Criptografía asimétrica”. La cual es un método que se usa un par de claves para el envío de mensajes. Ñas dos claves pertenecen a la misma persona que ha enviado un mensaje. Una clave es publica y se puede entregar a cualquier persona, la otra clave es privada y el propietario debe aguardar de modo que nadie tenga acceso a ella además, los métodos criptográficos garantizan que ese pareja de claves solo se pueden generar en vezm de modo que se pueda asumir que no es posible que dos personas hayan obtenido casualmente la misma pareja de claves.

Si el propietario del par de claves usa su clave privada para cifrar el mensaje, cualquiera puede descifrarlo utilizando su clave pública. En este caso se consigue por tanto la identificación y autentificación del remitente, ya que se sabe que sólo pudo haber sido él quien empleó su clave privada (salvo que alguien se la hubiese podido robar). Esta idea es el fundamento de la firma electrónica.

Los sistemas de cifrado de clave pública o sistemas de cifrado asimétricos se inventaron con el fin de evitar por completo el problema del intercambio de claves de los sistemas de cifrado simétricos. Con las claves públicas no es necesario que el remitente y el destinatario se pongan de acuerdo en la clave a emplear. Todo lo que se requiere es que, antes de iniciar la comunicación secreta, el remitente consiga una copia de la clave pública del destinatario. Es más, esa misma clave pública puede ser usada por cualquiera que desee comunicarse con su propietario. Por tanto, se necesitarán sólo n pares de claves por cada n personas que deseen comunicarse entre sí.

Sistema de clave publica

Los sistemas de encriptación de datos por clave publica han revolucionado el mundo de la criptografía y se han impuesto ampliamente en el mercado de las comunicaciones, la idea aunque sencilla recién surgió en la década del '70, los expertos en criptografía no logran ponerse de acuerdo en cual fue el motivo que demorara tanto el surgimiento de este tipo de sistema de encriptación.

La idea de los sistemas de clave pública es sencilla: cada usuario genera 2 (dos) claves: una publica y una privada, el usuario debe conservar su clave privada a salvo mientras que la clave pública es distribuida en forma masiva.

El juego de claves funciona de la siguiente forma: los mensajes que son encriptados con la clave pública de un usuario solo pueden ser des encriptados con la clave privada del mismo.

El algoritmo de encriptación es publico, de forma tal que cualquiera pueda encriptar un mensaje, el algoritmo de desencriptación debe de forma tal que sin la clave privada sea muy difícil desencriptar el código mientras que con la clave privada esto es una tarea sencilla. Todos los algoritmos de encriptación por clave publica se basan en algún problema en general de tipo matemático de cuyo tiempo de resolución no pueda establecerse una cota inferior.

KNAPSACKS.

El primer ejemplo sobre el cual presentaremos a los sistemas de clave publica esta basado en un problema de ingenio denominado 'el problema de la mochila'

'El problema de la mochila'

Se tiene una mochila con capacidad para "K" kilos. Además se cuenta con una lista de "n" objetos cuyos pesos se conocen y son (A1,A2,A3,...,AN). El problema consiste en seleccionar una cierta cantidad de objetos de la lista de forma tal que la mochila quede completamente llena.

Para resolver este problema no se conoce ningún método mejor que el ir probando las distintas combinaciones de objetos y ver si en alguna de ellas la mochila queda completamente llena. Si los pesos de los objetos están en un vector (A1,A2,A3,...,AN) una combinación puede escribirse como un numero binario de N bits en el cual un uno en la posición "i" indica que el elemento "i" debe estar en la mochila, un cero indica lo contrario.

Ej:

A=(3,45,6,7,21,12,9,90)

C1=(00000001)=90

C2=(10101010)=3+6+21+9=39

etc...

De esta forma se puede ver claramente que la cantidad de combinaciones a probar es 2^N siendo N el numero de elementos del vector, a este tipo de vectores lo denominaremos 'Knapsack'. Si N es un numero lo suficientemente grande (por ejemplo 300) la cantidad de combinaciones a probar es tan grande que resultaría imposible probarlas todas antes de que se termine el universo!.

Veamos como podemos construir un sistema de clave publica utilizando Knapsacks.

Empecemos por inventar un sistema de clave privada que utilice 'Knapsacks'

Dado un mensaje lo pasamos a binario y tomamos bloques de "N" bits de acuerdo al tamaño del Knapsack, sumamos los elementos del Knapsack que corresponden a los bits en 1 y el numero resultante es la codificación del bloque.

Ej: Con bloques de 8 bits y usando el código Ascii si el vector es: (3,45,6,7,21,12,9,90)

'H' = 01001000 = 45 + 21 = 66

'o' = 01101111 = 45 + 6 + 21 + 12 + 9 + 90 = 183

'l' = 01101100 = 45 + 6 + 21 + 12 = 84

'a' = 01100001 = 45 + 6 + 90 = 141

'Hola' = 66,183,84,141

Hasta ahora tenemos un método para encriptar un mensaje, la clave privada por el momento es el Knapsack, sin embargo este sistema tiene un problema: el receptor 'legal' del mensaje pese a poseer el Knapsack aun tiene que resolver el problema de la mochila para poder descifrar el mensaje, esto obviamente dista mucho de ser lo deseado. La solución consiste en simplificar el problema de la mochila utilizando un vector super-incrementante (super increasing, tradúzcanlo mejor si pueden). Un vector super-incrementante es aquel en el cual el elemento Ak es mayor a la sumatoria de todos los elementos con subíndice menor que él.

Ej: (1,3,5,11,21,44,87,175,349,701) es super-incrementante.

Con un vector super-incrementante resolver el problema de la mochila es fácil, para un cierto numero lo que hay que hacer es tomar el primer elemento del vector menor o igual al numero y poner su bit en 1, luego al número restarle el elemento y con el resultado repetir el procedimiento hasta que el número se hace cero.

Supongamos que tenemos el numero 734.

Para 734: Como 734 > 701 => el bit numero 10 es 1

734-701 = 33

Para 33: 33 > 21 => el bit 5 es 1

33-21 = 12

Para 12 : 12 > 11 => el bit 4 es 1

12-11 = 1

Para 1 : El bit 1 es 1

Luego 734=(1001100001) = 1+11+21+701

El algoritmo de desencriptado, como puede verse, es ahora muy sencillo. El problema es que el sistema sigue siendo de clave privada, conociendo el Knapsack se puede tanto encriptar como desencriptar cualquier mensaje.

Convirtiendo los Knapsacks en un sistema de clave pública

Lo que debemos lograr es identificar cual va a ser la clave privada y cual va a ser la clave publica, para ello una vez que tenemos un vector super-incrementante lo que se hace es elegir dos números t y m forma tal que t y m no tengan factores en común.

Al número t lo denominamos multiplicador.

Al número m lo denominamos modulo.

Además debemos encontrar un numero t' que sea el inverso multiplicativo de t usando aritmética modulo m.

Ejemplo: Sea m=1590 Verificar que 1590 y 43 no tienen factores en común

t=43 (43 es primo y 1590 no es divisible por 43)

1590 y 43 son relativamente primos.

Para el inverso de t hacemos 1591/43 = 37 luego t'=37

(37 * 43 = 1591, 1591 mod 1590 = 1)

Ahora lo que hacemos es aplicarle a cada elemento Ai del Knapsack la función

Ai'= Ai*t mod m

(1,3,5,11,21,44,87,175,349,701)=>(43,129,215,473,903,302,561,1165,697,1523)

Al vector que obtenemos una vez aplicada la función lo utilizaremos como clave publica (notar que el vector obtenido no es super-incrementante). Es decir que para encriptar un mensaje utilizaremos el método que ya hemos descripto utilizando la clave publica. Si el mensaje cifrado es interceptado el interceptor tiene que resolver el problema de la mochila para poder desencriptar el mensaje, y como sabemos este problema le va a llevar mucho mas que toda su vida.

La clave privada esta formada por t' y m, el receptor legal del mensaje primero convierte todos los números haciendo c*t' mod m y luego convierte el Knapsack de la misma forma, lo único que le resta hacer es resolver el problema de la mochila con un vector super-incrementante, lo cual es fácil.

Ejemplo:

Para el Knapsack ejemplo anterior la clave publica es (tomando solo 8 elementos para no hacer tantas cuentas, obviamente cuanto mayor es el vector mas seguro es el sistema)

P = (43,129,215,473,903,302,561,1165)

Supongamos que queremos encriptar 'Hola'

'H' = 01001000 = 129 + 903 = 1032

'o' = 01101111 = 129 + 215 + 903 + 302 + 561 + 1165 = 3275

'l' = 01101100 = 129 + 215 + 903 + 302 = 1549

'a' = 01100001 = 129 + 215 + 1165 = 1509

'Hola' = 1032,3275,1549,1509

Si este código es interceptado y sabiendo la clave publica no puede hacerse nada para desencriptar el mensaje pues la clave publica no es super-incrementante (aquí reside la gracia del asunto).

La clave privada es t'=37 m=1590

Para desencriptar usamos la clave privada:

1032 * 37 mod 1590 = 24

3275 * 37 mod 1590 = 335

1549 * 37 mod 1590 = 73

1509 * 37 mod 1590 = 183

A continuación se convierte el vector

...