Criptografía asimétrica

El cifrado asimétrico se caracteriza porque cada participante tiene 2 claves, normalmente llamadas: clave pública y clave privada. Ambas claves están relacionadas, es decir, al momento de generar una, se debe generar la otra. Sin embargo, una vez generadas es computacionalmente imposible pasar de una a otra por fuerza bruta. Normalmente, uno da a conocer la clave pública y resguarda la clave privada. A estas 2 claves se las denomina par de claves pública y privada.

Ambas claves están matemáticamente vinculadas. Un ejemplo de aplicación es, por ejemplo, que alguien cifre datos con la clave pública y solo aquel que tenga la clave privada podrá descifrala.

Si bien las claves están vinculadas, no se puede derivar una clave a partir de la otra con facilidad ya que son funciones unidireccionales. Una función unidireccional es una función fácil de computar cuando se le da entrada, pero difícil de invertir dada una imagen aleatoria de la función hablando en términos de la teoría de complejidad computacional, y bajo este principio radica la seguridad de este tipo de criptografía.

Es uno de los sistemas criptográficos asimétricos más utiizado. La seguridad de este algoritmo radica en el problema de la factorización de números enteros.

Los mensajes enviados se representan mediante números, y el funcionamiento se basa en el producto, conocido, de dos números primos grandes elegidos al azar y mantenidos en secreto.

En terminos prácticos de funcionamiento, como sabemos, necesitamos una clave privada y una pública, llamaremos “e" a la clave pública y “d” a la clave privada, también existe un número “n” el cual debe ser conocido por ambos participantes de la comunicación. Por último, tenemos el mensaje “M”, el cual será transformado a número.

Para generar un mensaje cifrado C, debemos elevar el número resultante del mensaje “M” al número de la clave pública “e” y obtener el resto de dividirlo por “n”.

C = M^e mod n

Para obtener de nuevo el mensaje M, debemos elevar el número resultante del mensaje cifrado “C” al número de la clave privada “d” y obtener el resto de dividirlo por “n”.

M = C^d mod n

Podemos ver claramente, que los números “e” y “d” que se utilizan como clave pública y privada se relacionarse entre sí por el número “n”, entonces, es lógico pensar que con obtener este número podemos vulnerar el sistema de encriptación porque con unos cuantos cálculos matemáticos nos permitirá obtener una clave a partir de la otra. En el número “n” radica la seguridad de este algoritmo, el mismo debe ser generado con algún mecanismo de forma que sea computacionalmente inabordable obtener una clave a partir de la otra.

También podemos darnos cuenta que en el proceso de desencriptado, para que la formula pueda darnos correctamente el numero correspondiente a nuestro mensaje, "n" debe ser mayor a todo mensaje posible (representado con números) que pueda llegar a ser encriptado por la utilización de la operacio mod. Esto es un limitante bastante grande, porque la obtención de claves basadas en un "n" excesivamente grande tardan mucho tiempo en ser generadas, por esto, en la práctica suele optarse por ir encriptando caracter por caracter, y si los mismos pertenecen al codigo ascii y utilizamos su numero de orden asociado para la representación del texto a números, con tener un "n" mayor a 255 podemos estar seguros de que nuestro algoritmo funcionará.

Pasos del algoritmo RSA

1. Elegir 2 números primos grandes y que sean coprimos. Los llamaremos p y q.
2. Calcular n=p*q.
3. Elegir un c tal que sea coprimo de (p-1)*(q-1)
4. Hasta acá ya hemos generado la clave privada denotada como: (c, n). Notar que la clave privada está compuesta por 2 números generados anteriormente.
5. Ahora vamos a generar la clave pública resolviendo la ecuación: c*d = 1 mod (n). La incógnita es la letra d.
6. La clave pública está compuesta por (d, n).

Referencias

Qué es la seguridad informática - Capítulo 4 - Hugo Scolnik.

• Calculemos también el número F=(p-1)*(q-1). El número n es público, pero p y q no lo son.

• La clave pública e será un número tal que F y e sean primos relativos. Con “primos relativos” queremos decir que no tengan divisores comunes, es decir, que su máximo común divisor sea uno. No tienen por qué ser primos ellos mismos.

• La clave privada d es un número que cumpla que e*d mod F = 1, se dice en este caso que d es el inverso (multiplicativo) de e módulo F. No siempre existe el inverso multiplicativo, y la condición necesaria para que exista inverso es que los números e y F sean primos relativos. Por eso le hemos exigido esa condición específica al número e.

• Confidencialidad

Uno de los usos que puedo darle al cifrado asimétrico es garantizar la confidencialidad del mensaje. La confidencialidad se logra aplicando la llave pública del receptor del mensaje, pues de esta forma nos aseguramos que el y solo él podrá desencriptar el mensaje.

Si el X1 y X2 quieren comunicarse utilizando encriptación asimétrica para mantener la confidencialidad de sus mensajes, deben intercambiar claves públicas. X1 le da su clave pública a X2, y X2 le da su clave pública a X1. Ahora X1 y X2 pueden enviarse mensajes de forma segura.

X1 puede tomar el documento y lo encripta con la clave pública de X2, quien usa su clave privada para desencriptar y leerlo, X2 es el único que puede leer ese documento.

El esquema para la confidencialidad sería:

X1 => Aplico(Mensaje, PúblicaX2) => X2.

• Certificación de origen

Otro uso importante es garantizar la certificación de origen del mensaje. La misma se logra aplicando mi llave privada antes de enviar el del mensaje, de esta forma estamos asegurándonos de que cualquiera que tenga mi llave pública pueda descifrarlo con la certeza de que yo fui quien envió el mensaje, de otra manera no hubiera podido obtener el mensaje en el caso que la llave pública que use para cifrar no esté asociado con la pública que se usó para descifrar.

Volviendo al ejemplo anterior, si X1 quiere asegurarse de que X2 este seguro de que él escribió el mensaje, lo encriptará con su clave privada antes de enviarlo.

El esquema para la certificación de origen sería:

X1 => Aplico(Mensaje, PrivadaX1) => X2

Ahora sabemos que el mensaje garantiza que fue escrito por X1, pero el mismo puede ser desencriptado por cualquier persona que tenga la clave pública asociada a la llave privada de X1. ¿Y si X1 quería que X2 esté seguro que él escribió mensaje pero también que X2 fuera el único receptor de ese mensaje? Para resolver esta situación, debemos utilizar un esquema mixto, X1 primero deberá cifrar con su clave privada para garantizar certificación de origen pero también deberá cifrar con la clave pública privada de X2 para que solo él pueda ser quien lo desencripte y así garantizar confidencialidad.

El esquema certificación de origen + confidencialidad sería:

X1 => Aplico(Aplico(Mensaje, PrivadaX1), PúblicaX2) => X2

• Integridad

Utilizando los métodos anteriormente mencionados, el mensaje fue enviado correctamente de X1 a X2, pero ahora, ¿cómo aseguro que el mensaje es íntegro y que no ha sido modificado a través del canal de comunicación? La solución es aplicar una función hash al mensaje, y concatenarlo al mismo mensaje. De esta forma, cuando X2 reciba el mensaje, puede aplicar la misma función hash al mensaje no hasheado, y comparar ese hash resultante con el que estaba concatenado y en el caso de que el mensaje sea íntegro deberían ser iguales.

Recordando el ejemplo, X1 quería enviar un mensaje a X2 asegurándose de que X2 tenga la certeza que X1 lo escribió, pero a demás, ahora utilizará la función hash para no solo asegurar certificación de origen sino también que el mensaje es íntegro y no sufrió modificaciones.

El esquema de certificación de origen + integridad sería:

X1 => Aplico(Mensaje + Hash(Mensaje), PrivadaX1) => X2

¿Y si X1 también quiere asegurarse de que solo X2 sea quien reciba el mensaje? Se deben aplicar los 3 conceptos aprendidos, primero X1 deberá hashear el mensaje y realizar la concatenación para asegurar integridad, luego encriptarlo con su clave privada para la certificación de origen, y más tarde encriptarlo con la clave pública de X2 para tener la certeza que será confidencial.

El esquema de integridad + certificación de origen + confidencialidad sería:

X1 => Aplico(Aplico(Mensaje + Hash(Mensaje), PrivadaX1), PúblicaX2) => X2