Cifrado de clave pública

Criptografía de clave pública

A diferencia de la criptografía de clave simétrica, no encontramos un uso histórico de la criptografía de clave pública. Es un concepto relativamente nuevo.

La criptografía simétrica era adecuada para organizaciones como gobiernos, militares y grandes corporaciones financieras involucradas en la comunicación clasificada.

Con la expansión de redes informáticas más inseguras en las últimas décadas, se sintió una necesidad genuina de utilizar la criptografía a mayor escala. Se descubrió que la clave simétrica no era práctica debido a los desafíos que enfrentaba para la administración de claves. Esto dio lugar a los criptosistemas de clave pública.

El proceso de cifrado y descifrado se muestra en la siguiente ilustración:

Las propiedades más importantes del esquema de cifrado de clave pública son:

  • Se utilizan diferentes claves para el cifrado y el descifrado. Esta es una propiedad que establece este esquema diferente al esquema de cifrado simétrico.

  • Cada receptor posee una clave de descifrado única, generalmente conocida como su clave privada.

  • El receptor necesita publicar una clave de cifrado, a la que se hace referencia como su clave pública.

  • En este esquema se necesita cierta garantía de la autenticidad de una clave pública para evitar la falsificación por parte del adversario como receptor. Generalmente, este tipo de criptosistema involucra a un tercero confiable que certifica que una clave pública en particular pertenece a una persona o entidad específica únicamente.

  • El algoritmo de cifrado es lo suficientemente complejo como para prohibir al atacante deducir el texto sin formato del texto cifrado y la clave de cifrado (pública).

  • Aunque las claves públicas y privadas están relacionadas matemáticamente, no es factible calcular la clave privada a partir de la clave pública. De hecho, una parte inteligente de cualquier criptosistema de clave pública consiste en diseñar una relación entre dos claves.

Hay tres tipos de esquemas de cifrado de clave pública. Los discutimos en las siguientes secciones:

Criptosistema RSA

Este criptosistema es uno del sistema inicial. Sigue siendo el criptosistema más empleado incluso hoy en día. El sistema fue inventado por tres eruditosRon Rivest, Adi Shamir, y Len Adleman y por lo tanto, se denomina criptosistema RSA.

Veremos dos aspectos del criptosistema RSA, en primer lugar la generación de un par de claves y, en segundo lugar, los algoritmos de cifrado y descifrado.

Generación de par de claves RSA

Cada persona o parte que desee participar en la comunicación mediante cifrado debe generar un par de claves, a saber, clave pública y clave privada. El proceso seguido en la generación de claves se describe a continuación:

  • Generate the RSA modulus (n)

    • Seleccione dos números primos grandes, py q.

    • Calcule n = p * q. Para un cifrado fuerte e irrompible, sea n un número grande, normalmente un mínimo de 512 bits.

  • Find Derived Number (e)

    • Número e debe ser mayor que 1 y menor que (p - 1) (q - 1).

    • No debe haber un factor común para e y (p - 1) (q - 1) excepto para 1. En otras palabras, dos números e y (p - 1) (q - 1) son coprimos.

  • Form the public key

    • El par de números (n, e) forman la clave pública RSA y se hace pública.

    • Curiosamente, aunque n es parte de la clave pública, la dificultad para factorizar un número primo grande asegura que el atacante no pueda encontrar en tiempo finito los dos primos (p & q) usados ​​para obtener n. Ésta es la fuerza de RSA.

  • Generate the private key

    • La clave privada d se calcula a partir de p, qye. Para dados nye, existe un número único d.

    • El número d es el inverso de e módulo (p - 1) (q - 1). Esto significa que d es el número menor que (p - 1) (q - 1) tal que cuando se multiplica por e, es igual a 1 módulo (p - 1) (q - 1).

    • Esta relación se escribe matemáticamente de la siguiente manera:

ed = 1 mod (p − 1)(q − 1)

El algoritmo euclidiano extendido toma p, qye como entrada y da d como salida.

Ejemplo

A continuación se ofrece un ejemplo de generación de un par de claves RSA. (Para facilitar la comprensión, los números primos p & q tomados aquí son valores pequeños. Prácticamente, estos valores son muy altos).

  • Sean dos primos p = 7 y q = 13. Por lo tanto, módulo n = pq = 7 x 13 = 91.

  • Seleccione e = 5, que es una elección válida ya que no hay ningún número que sea factor común de 5 y (p - 1) (q - 1) = 6 × 12 = 72, excepto 1.

  • El par de números (n, e) = (91, 5) forma la clave pública y se puede poner a disposición de cualquiera que deseemos para poder enviarnos mensajes cifrados.

  • Ingrese p = 7, q = 13 y e = 5 en el algoritmo euclidiano extendido. La salida será d = 29.

  • Compruebe que la d calculada sea correcta calculando -

de = 29 × 5 = 145 = 1 mod 72

  • Por lo tanto, la clave pública es (91, 5) y la clave privada es (91, 29).

Cifrado y descifrado

Una vez que se ha generado el par de claves, el proceso de cifrado y descifrado es relativamente sencillo y computacionalmente sencillo.

Curiosamente, RSA no opera directamente en cadenas de bits como en el caso del cifrado de clave simétrica. Opera en números módulo n. Por tanto, es necesario representar el texto llano como una serie de números menores que n.

Cifrado RSA

  • Suponga que el remitente desea enviar un mensaje de texto a alguien cuya clave pública es (n, e).

  • El remitente luego representa el texto sin formato como una serie de números menores que n.

  • Para cifrar el primer texto plano P, que es un número módulo n. El proceso de cifrado es un simple paso matemático como:

C = Pe mod n

  • En otras palabras, el texto cifrado C es igual al texto llano P multiplicado por sí mismo e veces y luego reducido módulo n. Esto significa que C también es un número menor que n.

  • Volviendo a nuestro ejemplo de generación de claves con texto sin formato P = 10, obtenemos texto cifrado C -

C = 105 mod 91

Descifrado RSA

  • El proceso de descifrado de RSA también es muy sencillo. Supongamos que el receptor del par de claves públicas (n, e) ha recibido un texto cifrado C.

  • El receptor eleva C a la potencia de su clave privada d. El resultado módulo n será el texto plano P.

Plaintext = Cd mod n

  • Volviendo de nuevo a nuestro ejemplo numérico, el texto cifrado C = 82 se descifraría al número 10 usando la clave privada 29 -

Plaintext = 8229 mod 91 = 10

Análisis RSA

La seguridad de RSA depende de los puntos fuertes de dos funciones independientes. El criptosistema RSA es el criptosistema de clave pública más popular, cuya fuerza se basa en la dificultad práctica de factorizar números muy grandes.

  • Encryption Function - Se considera una función unidireccional de convertir texto plano en texto cifrado y solo se puede revertir con el conocimiento de la clave privada d.

  • Key Generation- La dificultad de determinar una clave privada a partir de una clave pública RSA es equivalente a factorizar el módulo n. Por tanto, un atacante no puede utilizar el conocimiento de una clave pública RSA para determinar una clave privada RSA a menos que pueda factorizar n. También es una función unidireccional, pasar de los valores p & q al módulo n es fácil, pero no es posible invertirlo.

Si se demuestra que alguna de estas dos funciones no es unidireccional, RSA se romperá. De hecho, si se desarrolla una técnica para factorizar de manera eficiente, RSA ya no será seguro.

La fuerza del cifrado RSA disminuye drásticamente contra los ataques si el número pyq no son números primos grandes y / o la clave pública elegida e es un número pequeño.

Criptosistema ElGamal

Junto con RSA, se proponen otros criptosistemas de clave pública. Muchos de ellos se basan en diferentes versiones del problema del logaritmo discreto.

El criptosistema ElGamal, llamado variante de curva elíptica, se basa en el problema del logaritmo discreto. Deriva la fuerza del supuesto de que los logaritmos discretos no se pueden encontrar en un marco de tiempo práctico para un número dado, mientras que la operación inversa de la potencia se puede calcular de manera eficiente.

Veamos una versión simple de ElGamal que trabaja con números módulo p. En el caso de las variantes de curvas elípticas, se basa en sistemas numéricos bastante diferentes.

Generación del par de claves ElGamal

Cada usuario del criptosistema ElGamal genera el par de claves de la siguiente manera:

  • Choosing a large prime p. Generalmente se elige un número primo de 1024 a 2048 bits de longitud.

  • Choosing a generator element g.

    • Este número debe estar entre 1 y p - 1, pero no puede ser ningún número.

    • Es un generador del grupo multiplicativo de enteros módulo p. Esto significa que por cada entero m coprimo ap, hay un entero k tal que g k = a mod n.

      Por ejemplo, 3 es el generador del grupo 5 (Z 5 = {1, 2, 3, 4}).

norte 3 n 3 n mod 5
1 3 3
2 9 4
3 27 2
4 81 1

  • Choosing the private key. La clave privada x es cualquier número mayor que 1 y menor que p − 1.

  • Computing part of the public key. El valor y se calcula a partir de los parámetros p, gy la clave privada x de la siguiente manera:

y = gx mod p

  • Obtaining Public key. La clave pública de ElGamal consta de tres parámetros (p, g, y).

    Por ejemplo, suponga que p = 17 y que g = 6 (Se puede confirmar que 6 es un generador del grupo Z 17 ). La clave privada x puede ser cualquier número mayor que 1 y menor que 71, por lo que elegimos x = 5. El valor y se calcula de la siguiente manera:

y = 65 mod 17 = 7

  • Por tanto, la clave privada es 62 y la clave pública es (17, 6, 7).

Cifrado y descifrado

La generación de un par de claves ElGamal es comparativamente más simple que el proceso equivalente para RSA. Pero el cifrado y el descifrado son un poco más complejos que RSA.

Cifrado ElGamal

Supongamos que el remitente desea enviar un texto sin formato a alguien cuya clave pública de ElGamal es (p, g, y), entonces -

  • El remitente representa el texto sin formato como una serie de números módulo p.

  • Para cifrar el primer texto plano P, que se representa como un número módulo p. El proceso de cifrado para obtener el texto cifrado C es el siguiente:

    • Genere aleatoriamente un número k;
    • Calcule dos valores C1 y C2, donde -
C1 = gk mod p
C2 = (P*yk) mod p

  • Envíe el texto cifrado C, que consta de dos valores separados (C1, C2), enviados juntos.

  • En referencia a nuestro ejemplo de generación de claves de ElGamal dado anteriormente, el texto sin formato P = 13 se cifra de la siguiente manera:

    • Genere un número aleatoriamente, digamos k = 10
    • Calcule los dos valores C1 y C2, donde -
C1 = 610 mod 17
C2 = (13*710) mod 17 = 9

  • Envíe el texto cifrado C = (C1, C2) = (15, 9).

Descifrado de ElGamal

  • Para descifrar el texto cifrado (C1, C2) utilizando la clave privada x, se siguen los dos pasos siguientes:

    • Calcule el inverso modular de (C1) x módulo p, que es (C1) -x , generalmente conocido como factor de descifrado.

    • Obtenga el texto sin formato utilizando la siguiente fórmula:

C2 × (C1)-x  mod p = Plaintext

  • En nuestro ejemplo, para descifrar el texto cifrado C = (C1, C2) = (15, 9) usando la clave privada x = 5, el factor de descifrado es

15-5  mod 17 = 9

  • Extrae texto plano P = (9 × 9) mod 17 = 13.

Análisis ElGamal

En el sistema ElGamal, cada usuario tiene una clave privada x. y tienethree components de clave pública - prime modulus p, generator g, and public Y = gx mod p. La fuerza de ElGamal se basa en la dificultad del problema del logaritmo discreto.

El tamaño de la clave segura es generalmente> 1024 bits. Hoy en día se utilizan incluso claves de 2048 bits. En el frente de la velocidad de procesamiento, Elgamal es bastante lento, se utiliza principalmente para protocolos de autenticación de claves. Debido a la mayor eficiencia de procesamiento, las variantes de curva elíptica de ElGamal son cada vez más populares.

Criptografía de curva elíptica (ECC)

Criptografía de curva elíptica (ECC) es un término utilizado para describir un conjunto de herramientas y protocolos criptográficos cuya seguridad se basa en versiones especiales del problema del logaritmo discreto. No utiliza números módulo p.

ECC se basa en conjuntos de números que están asociados con objetos matemáticos llamados curvas elípticas. Existen reglas para sumar y calcular múltiplos de estos números, al igual que las hay para los números módulo p.

ECC incluye variantes de muchos esquemas criptográficos que fueron diseñados inicialmente para números modulares como el cifrado ElGamal y el algoritmo de firma digital.

Se cree que el problema del logaritmo discreto es mucho más difícil cuando se aplica a puntos en una curva elíptica. Esto solicita el cambio de números módulo p a puntos en una curva elíptica. También se puede obtener un nivel de seguridad equivalente con claves más cortas si usamos variantes basadas en curvas elípticas.

Las claves más cortas dan como resultado dos beneficios:

  • Facilidad de gestión de claves
  • Computación eficiente

Estos beneficios hacen que las variantes del esquema de cifrado basadas en curvas elípticas sean muy atractivas para aplicaciones en las que los recursos informáticos están limitados.

Esquemas RSA y ElGamal: una comparación

Comparemos brevemente los esquemas RSA y ElGamal en los diversos aspectos.

RSA ElGamal
Es más eficiente para el cifrado. Es más eficaz para el descifrado.
Es menos eficiente para el descifrado. Es más eficaz para el descifrado.
Para un nivel de seguridad particular, se requieren claves largas en RSA. Para el mismo nivel de seguridad, se requieren claves muy cortas.
Es ampliamente aceptado y utilizado. Es nuevo y no muy popular en el mercado.