Mecanismo de encapsulación clave

Un mecanismo de encapsulación de claves, para transportar de forma segura una clave secreta de un remitente a un receptor, consta de tres algoritmos: Gen, Encap y Decap. Los círculos sombreados en azul (la clave pública del receptor y la encapsulación ) pueden revelarse de forma segura a un adversario, mientras que los cuadros sombreados en rojo (la clave privada del receptor y la clave secreta encapsulada) deben mantenerse en secreto. ${\displaystyle k}$ ${\displaystyle pk}$ ${\displaystyle c}$ ${\displaystyle sk}$ ${\displaystyle k}$

En criptografía , un mecanismo de encapsulación de claves , o KEM , es un criptosistema de clave pública que permite a un remitente generar una clave secreta corta y transmitirla a un receptor de forma segura, a pesar de las escuchas e interceptaciones de los adversarios. ^{[1] [2] [3] [4]}

Un KEM permite a un remitente que conoce una clave pública generar simultáneamente una clave secreta aleatoria corta y una encapsulación o texto cifrado de la clave secreta mediante el algoritmo de encapsulación del KEM . El receptor que conoce la clave privada correspondiente a la clave pública puede recuperar la misma clave secreta aleatoria de la encapsulación mediante el algoritmo de decapsulación del KEM . ^{[1] [2] [3]}

El objetivo de seguridad de un KEM es evitar que cualquier persona que no conozca la clave privada recupere información sobre las claves secretas encapsuladas, incluso después de espiar o enviar otras encapsulaciones al receptor para estudiar cómo reacciona. ^{[1] [2] [3]}

Diferencia con el cifrado de clave pública

Un esquema de cifrado de clave pública.

La diferencia entre un esquema de cifrado de clave pública y un KEM es que un esquema de cifrado de clave pública permite al remitente elegir un mensaje arbitrario de un espacio de mensajes posibles, mientras que un KEM elige una clave secreta corta al azar para el remitente. ^{[1] [2] [3]}

El remitente puede tomar la clave secreta aleatoria producida por un KEM y utilizarla como clave simétrica para un cifrado autenticado cuyo texto cifrado se envía junto con la encapsulación al receptor. Esto sirve para componer un esquema de cifrado de clave pública a partir de un KEM y un cifrado autenticado de clave simétrica en un criptosistema híbrido . ^{[1] [2] [3] [5]}

La mayoría de los esquemas de cifrado de clave pública, como RSAES-PKCS1-v1_5 , RSAES-OAEP y Elgamal, se limitan a mensajes pequeños ^{[6] [7]} y, de todos modos, casi siempre se utilizan para cifrar una clave secreta aleatoria corta en un criptosistema híbrido. ^{[8] [9] [5]} Y aunque, a la inversa, un esquema de cifrado de clave pública se puede convertir en un KEM eligiendo una clave secreta aleatoria y cifrándola como un mensaje, es más fácil diseñar y analizar un KEM seguro que diseñar como base un esquema seguro de cifrado de clave pública. Por lo tanto, la mayoría de los esquemas modernos de cifrado de clave pública se basan en KEM y no al revés. ^{[10] [5]}

Definición

Sintaxis

Un KEM consta de tres algoritmos: ^{[1] [2] [3] [11] [12]}

1. La generación de claves no requiere entradas y devuelve un par de claves públicas y privadas . ${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$ ${\displaystyle {\mathit {pk}}}$ ${\displaystyle {\mathit {sk}}}$
2. La encapsulación toma una clave pública , elige aleatoriamente una clave secreta y regresa junto con su encapsulación . ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$ ${\displaystyle {\mathit {pk}}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle c}$
3. La decapsulación toma una clave privada y una encapsulación y devuelve una clave secreta encapsulada o falla, a veces se indica con un retorno (llamado ' inferior '). ${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$ ${\displaystyle {\mathit {sk}}}$ ${\displaystyle c'}$ ${\displaystyle k'}$ ${\displaystyle \bot }$

Exactitud

Un KEM es correcto si, para cualquier par de claves generado por , desencapsular una encapsulación devuelta por con alta probabilidad produce la misma clave , es decir, . ^{[2] [3] [11] [12]} ${\displaystyle ({\mathit {pk}},{\mathit {sk}})}$ ${\displaystyle \operatorname {Gen} }$ ${\displaystyle c}$ ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$ ${\displaystyle k}$ ${\displaystyle \operatorname {Decap} ({\mathit {sk}},c)=k}$

Seguridad: IND-CCA

La seguridad de un KEM se cuantifica por su indistinguibilidad frente a un ataque de texto cifrado elegido , IND-CCA, que es, en términos generales, cuánto mejor puede hacer un adversario que lanzar una moneda al aire para saber si, dada una clave aleatoria y un encapsulado, la clave está encapsulada por esa encapsulación o es una clave aleatoria independiente. ^{[2] [3] [11] [12]}

Específicamente, en el juego IND-CCA:

1. El algoritmo de generación de claves se ejecuta para generar . ${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$
2. ${\displaystyle {\mathit {pk}}}$se revela al adversario.
3. El adversario puede consultar encapsulaciones arbitrarias de su elección. ${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$ ${\displaystyle c'}$
4. El algoritmo de encapsulación se ejecuta para generar aleatoriamente una clave secreta y encapsulación , y se genera otra clave secreta de forma aleatoria e independiente. ${\displaystyle (k_{0},c):=\operatorname {Encap} ({\mathit {pk}})}$ ${\displaystyle k_{1}}$
5. Se lanza una moneda justa y se obtiene un resultado . ${\displaystyle b\in \{0,1\}}$
6. La pareja se revela al adversario. ${\displaystyle (k_{b},c)}$
7. El adversario puede volver a consultar encapsulaciones arbitrarias de su elección, excepto . ${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$ ${\displaystyle c'}$ ${\displaystyle c}$
8. El adversario devuelve una respuesta y gana el juego si . ${\displaystyle b'\in \{0,1\}}$ ${\displaystyle b=b'}$

La ventaja IND-CCA del adversario es , es decir, la probabilidad más allá de un lanzamiento justo de moneda de distinguir correctamente una clave encapsulada de una clave elegida al azar de forma independiente. ${\displaystyle \left|\Pr[b'=b]-1/2\right|}$

Ejemplos y motivación

RSA

El cifrado RSA tradicional , con módulos de bits y exponente , se define de la siguiente manera: ^{[13] [14] [15]} ${\displaystyle t}$ ${\displaystyle e}$

• Generación de claves ,: ${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$

1. Generar un semiprimo de bits con satisfacción aleatoria , donde está la función Carmichael . ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle 2^{t-1}<n<2^{t}}$ ${\displaystyle \gcd(e,\lambda (n))=1}$ ${\displaystyle \lambda (n)}$
2. Calcular . ${\displaystyle d:=e^{-1}{\bmod {\lambda }}(n)}$
3. Devuelve como clave pública y como clave privada. (Hay muchas variaciones disponibles en algoritmos de generación de claves y formatos de claves privadas. ^[16] ) ${\displaystyle {\mathit {pk}}:=n}$ ${\displaystyle {\mathit {sk}}:=(n,d)}$

• Cifrado de mensaje de bits a clave pública , dando : ${\displaystyle (t-1)}$ ${\displaystyle m}$ ${\displaystyle {\mathit {pk}}=n}$ ${\displaystyle c:=\operatorname {Encrypt} ({\mathit {pk}},m)}$

1. Codifique la cadena de bits como un número entero con . ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle 0\leq r<n}$
2. Devolver . ${\displaystyle c:=r^{e}{\bmod {n}}}$

• Descifrado de texto cifrado con clave privada , dando : ${\displaystyle c'}$ ${\displaystyle {\mathit {sk}}=(n,d)}$ ${\displaystyle m':=\operatorname {Decrypt} ({\mathit {sk}},c')}$

1. Calcular . ${\displaystyle r':=(c')^{d}{\bmod {n}}}$
2. Decodifica el número entero como una cadena de bits . ${\displaystyle r'}$ ${\displaystyle m'}$

Este enfoque ingenuo es totalmente inseguro. Por ejemplo, dado que no es aleatorio, no puede ser seguro ni siquiera contra ataques de texto plano conocido : un adversario puede saber si el remitente está enviando el mensaje ATTACK AT DAWNo el mensaje ATTACK AT DUSKsimplemente cifrando esos mensajes y comparando el texto cifrado.

Incluso si siempre es una clave secreta aleatoria, como una clave AES de 256 bits , cuando se elige para optimizar la eficiencia como , el mensaje se puede calcular a partir del texto cifrado simplemente tomando raíces cúbicas de números reales, y existen muchos otros ataques contra claves simples. RSA . ^{[13] [14]} Se han ideado varios esquemas de relleno aleatorio en intentos (a veces fallidos, como RSAES-PKCS1-v1_5 ^{[13] [17] [18]} ) de hacerlo seguro para mensajes cortos arbitrarios . ^{[13] [14]} ${\displaystyle m}$ ${\displaystyle e}$ ${\displaystyle e=3}$ ${\displaystyle m}$ ${\displaystyle c}$ ${\displaystyle m}$

Dado que el mensaje es casi siempre una clave secreta corta para un cifrado autenticado de clave simétrica utilizado para cifrar un mensaje de cadena de bits arbitrario, un enfoque más simple llamado RSA-KEM es elegir un elemento de al azar y usarlo para derivar una clave secreta usando una función de derivación de clave , aproximadamente como sigue: ^{[19] [8]} ${\displaystyle m}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle H}$

• Generación de claves : como arriba.
• Encapsulación de una clave pública , dando : ${\displaystyle {\mathit {pk}}=n}$ ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$

1. Elija un número entero uniformemente al azar. ${\displaystyle r}$ ${\displaystyle 0\leq r<n}$
2. Regresar y como su encapsulación. ${\displaystyle k:=H(r)}$ ${\displaystyle c:=r^{e}{\bmod {n}}}$

• Decapsulación con clave privada , dando : ${\displaystyle c'}$ ${\displaystyle {\mathit {sk}}=(n,d)}$ ${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$

1. Calcular . ${\displaystyle r':=(c')^{d}{\bmod {n}}}$
2. Devolver . ${\displaystyle k':=H(r')}$

Este enfoque es más sencillo de implementar y proporciona una reducción más estricta del problema RSA que los esquemas de relleno como RSAES-OAEP . ^[19]

Elgamal

El cifrado tradicional de Elgamal se define sobre un subgrupo multiplicativo del campo finito con generador de orden de la siguiente manera: ^{[20] [21]} ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle g}$ ${\displaystyle q}$

• Generación de claves ,: ${\displaystyle (pk,sk):=\operatorname {Gen} ()}$

1. Elija uniformemente al azar. ${\displaystyle x\in \mathbb {Z} /q\mathbb {Z} }$
2. Calcular . ${\displaystyle y:=g^{x}{\bmod {p}}}$
3. Devuelve como clave privada y como clave pública. ${\displaystyle {\mathit {sk}}:=x}$ ${\displaystyle {\mathit {pk}}:=y}$

• Cifrado de un mensaje a clave pública , dando : ${\displaystyle m\in \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle {\mathit {pk}}=y}$ ${\displaystyle c:=\operatorname {Encrypt} ({\mathit {pk}},m)}$

1. Elija uniformemente al azar. ${\displaystyle r\in \mathbb {Z} /q\mathbb {Z} }$
2. Calcular: $${\displaystyle {\begin{aligned}t&:=y^{r}{\bmod {p}}\\c_{1}&:=g^{r}{\bmod {p}}\\c_{2}&:=(t\cdot m){\bmod {p}}\end{aligned}}}$$
3. Devuelve el texto cifrado . ${\displaystyle c:=(c_{1},c_{2})}$

• Descifrado de un texto cifrado para una clave privada , dando : ${\displaystyle c'=(c'_{1},c'_{2})}$ ${\displaystyle {\mathit {sk}}=x}$ ${\displaystyle m':=\operatorname {Decrypt} ({\mathit {sk}},c')}$

1. Falla y regresa si o si , es decir, si o no está en el subgrupo generado por . ${\displaystyle \bot }$ ${\displaystyle (c'_{1})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$ ${\displaystyle (c'_{2})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$ ${\displaystyle c'_{1}}$ ${\displaystyle c'_{2}}$ ${\displaystyle g}$
2. Calcular . ${\displaystyle t':=(c'_{1})^{x}{\bmod {p}}}$
3. Devolver . ${\displaystyle m':=t^{-1}c'_{2}{\bmod {p}}}$

Esto cumple con la sintaxis de un esquema de cifrado de clave pública, restringido a mensajes en el espacio (lo que lo limita a mensajes de unos pocos cientos de bytes para valores típicos de ). Al validar los textos cifrados durante el descifrado, se evita la filtración de bits de la clave privada a través de textos cifrados elegidos maliciosamente fuera del grupo generado por . ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle g}$

Sin embargo, esto no logra lograr la indistinguibilidad del ataque de texto cifrado elegido . Por ejemplo, un adversario que tenga un texto cifrado para un mensaje desconocido puede descifrarlo trivialmente consultando al oráculo de descifrado para obtener el texto cifrado distinto , obteniendo el texto sin formato relacionado , del cual se puede recuperar mediante . ^[20] ${\displaystyle c=(c_{1},c_{2})}$ ${\displaystyle m}$ ${\displaystyle c':=(c_{1},c_{2}g)}$ ${\displaystyle m':=mg{\bmod {p}}}$ ${\displaystyle m}$ ${\displaystyle m=m'g^{-1}{\bmod {p}}}$

El cifrado tradicional de Elgamal se puede adaptar a la configuración de curva elíptica, pero requiere alguna forma de codificar mensajes de forma reversible como puntos en la curva, lo cual es menos trivial que codificar mensajes como números enteros mod . ^[22] ${\displaystyle p}$

Dado que el mensaje es casi siempre una clave secreta corta para un cifrado autenticado de clave simétrica utilizado para cifrar un mensaje de cadena de bits arbitrario, un enfoque más sencillo es derivar la clave secreta y prescindir de él por completo, como un KEM, utilizando una derivación de clave . función : ^[1] ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle m}$ ${\displaystyle c_{2}}$ ${\displaystyle H}$

• Generación de claves : como arriba.
• Encapsulación de una clave pública , dando : ${\displaystyle {\mathit {pk}}=y}$ ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$

1. Elija uniformemente al azar. ${\displaystyle r\in \mathbb {Z} /q\mathbb {Z} }$
2. Calcular . ${\displaystyle t:=y^{r}{\bmod {p}}}$
3. Regresar y como su encapsulación. ${\displaystyle k:=H(t)}$ ${\displaystyle c:=g^{r}{\bmod {p}}}$

• Decapsulación con clave privada , dando : ${\displaystyle c'}$ ${\displaystyle {\mathit {sk}}=x}$ ${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$

1. Falla y regresa si , es decir, si no está en el subgrupo generado por . ${\displaystyle \bot }$ ${\displaystyle (c')^{(p-1)/q}\not \equiv 1{\pmod {p}}}$ ${\displaystyle c'}$ ${\displaystyle g}$
2. Calcular . ${\displaystyle t':=(c')^{x}{\bmod {p}}}$
3. Devolver . ${\displaystyle k':=H(t')}$

Cuando se combina con un cifrado autenticado para cifrar mensajes de cadenas de bits arbitrarios, la combinación es esencialmente el Esquema de cifrado integrado . Dado que este KEM solo requiere una función de derivación de clave unidireccional para codificar elementos aleatorios del grupo sobre el que está definido, en este caso, y no una codificación reversible de mensajes, es fácil extenderlo a grupos de curvas elípticas más compactos y eficientes para La misma seguridad, que en el ECIES, Elliptic Curve Integrated Encryption Scheme . ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

Referencias

1. Galbraith, Steven (2012). "§23.1.1: El paradigma KEM/DEM". Matemáticas de la criptografía de clave pública . Prensa de la Universidad de Cambridge. págs. 471–478. ISBN 978-1-107-01392-6.
2. Shoup, Victor (mayo de 2000). Preneel, Bart (ed.). Uso de funciones hash como protección contra el ataque de texto cifrado elegido. Avances en criptología - EUROCRYPT 2000. Apuntes de conferencias sobre informática. vol. 1807. Brujas, Bélgica: Springer. págs. 275–288. doi : 10.1007/3-540-45539-6_19 . ISBN 978-3-540-67517-4.
3. Cramer, Ronald ; Shoup, Víctor (2003). "Diseño y análisis de esquemas prácticos de cifrado de clave pública seguros contra ataques de texto cifrado elegidos adaptativamente". Revista SIAM de Computación . 33 (1). Sociedad de Matemáticas Industriales y Aplicadas : 167–226. doi :10.1137/S0097539702403773.
4. FIPS 203 (borrador): Estándar de mecanismo de encapsulación de claves basado en celosía de módulo (PDF) , Instituto Nacional de Estándares y Tecnología , 2023-08-24, doi : 10.6028/NIST.FIPS.203.ipd
5. Barnes, R .; Bhargavan, K.; Lipp, B.; Wood, C. (febrero de 2022). Cifrado de clave pública híbrida. Grupo de Trabajo de Ingeniería de Internet . doi : 10.17487/RFC9180 . RFC 9180.
6. Kaliski, B .; Jonsson, J.; Rusch, A. (noviembre de 2016). Moriarity, K. (ed.). PKCS #1: Especificaciones de criptografía RSA Versión 2.2. Grupo de Trabajo de Ingeniería de Internet . doi : 10.17487/RFC8017 . RFC 8017.
7. Menezes, Alfred J .; van Oorschot, Paul C .; Vanstone, Scott A. (octubre de 1996). "8. Cifrado de clave pública". Manual de criptografía aplicada (PDF) . Prensa CRC. págs. 283–319. ISBN 0-8493-8523-7.
8. Ferguson, Niels ; Kohno, Tadayoshi ; Schneier, Bruce (2010). "12. RSA". Ingeniería de Criptografía . Wiley. págs. 195-211. ISBN 978-0-470-47424-2.
9. Callas, J .; Donnerhacke, L.; Finney, H .; Shaw, D.; Thayer, R. (noviembre de 2007). Formato de mensaje OpenPGP. Grupo de Trabajo de Ingeniería de Internet . doi : 10.17487/RFC4880 . RFC 4880.
10. "Criptografía poscuántica: preguntas frecuentes". Instituto Nacional de Estándares y Tecnología . 2024-07-19. Archivado desde el original el 26 de junio de 2024 . Consultado el 20 de julio de 2024 .
11. Dent, Alexander W. (2002), Guía del diseñador de KEM, Cryptology ePrint Archive, Asociación Internacional para la Investigación Criptológica
12. Hofheinz, Dennis; Hövelmanns, Kathrin; Kiltz, Eike (noviembre de 2017). Kalai, Yael; Reyzin, Leonid (eds.). Un análisis modular de la transformación Fujisaki-Okamoto. Teoría de la criptografía - TCC 2017. Apuntes de conferencias en informática. vol. 10677. Baltimore, MD, Estados Unidos: Springer. págs. 341–371. doi : 10.1007/978-3-319-70500-2_12 . ISBN 978-3-319-70499-9.
13. Aumasson, Jean-Philippe (2018). "10. RSA". Criptografía seria: una introducción práctica al cifrado moderno . Sin prensa de almidón. págs. 181-199. ISBN 978-1-59327-826-7.
14. Stinson, Douglas R. (2006). "5. El criptosistema RSA y la factorización de números enteros". Teoría y práctica de la criptografía (3ª ed.). Chapman y Hall/CRC. págs. 161-232. ISBN 978-1-58488-508-5.
15. Rivest, RL ; Shamir, A .; Adleman, L. (1 de febrero de 1978). «Un método para la obtención de firmas digitales y criptosistemas de clave pública» (PDF) . Comunicaciones de la ACM . 21 (2). Asociación de Maquinaria Informática: 120–126. doi : 10.1145/359340.359342 .
16. Švenda, Petr; Nemec, Matúš; Sekan, Peter; Kvašňovský, Rudolf; Formánek, David; Komárek, David; Matyáš, Vashek (agosto de 2016). La pregunta del millón de claves: investigación de los orígenes de las claves públicas RSA. 25º Simposio de Seguridad USENIX. Austin, TX, Estados Unidos: Asociación USENIX. págs. 893–910. ISBN 978-1-931971-32-4.
17. Bleichenbacher, Daniel (agosto de 1998). Krawczyk, Hugo (ed.). Ataques de texto cifrado elegidos contra protocolos basados ​​en el estándar de cifrado RSA PKCS #1. Avances en criptología - CRYPTO '98. Apuntes de conferencias sobre informática. vol. 1462. Santa Bárbara, CA, Estados Unidos: Springer. págs. 1–12. doi : 10.1007/BFb0055716 . ISBN 978-3-540-64892-5.
18. Corón, Jean-Sébastien; Joye, Marc; Naccache, David ; Paillier, Pascal (mayo de 2000). Preneel, Bart (ed.). Nuevos ataques al cifrado PKCS#1 v1.5. Avances en criptología - EUROCRYPT 2000. Apuntes de conferencias sobre informática. vol. 1807. Brujas, Bélgica: Springer. págs. 369–381. doi : 10.1007/3-540-45539-6_25 . ISBN 978-3-540-67517-4.
19. Shoup, Victor (2001), Propuesta de un estándar ISO para el cifrado de clave pública (versión 2.1), Cryptology ePrint Archive, Asociación Internacional para la Investigación Criptológica
20. Galbraith, Steven (2012). "§20.3: Cifrado Elgamal de libros de texto". Matemáticas de la criptografía de clave pública . Prensa de la Universidad de Cambridge. págs. 471–478. ISBN 978-1-107-01392-6.
21. Elgamal, Taher (agosto de 1984). Blakeley, George Robert ; Chaum, David (eds.). Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos. Avances en criptología - CRYPTO 1984. Apuntes de conferencias sobre informática. vol. 196. Santa Bárbara, CA, Estados Unidos: Springer. págs. 10-18. doi : 10.1007/3-540-39568-7_2 . ISBN 978-3-540-15658-1.
22. Koblitz, Neal (enero de 1987). "Criptosistemas de curva elíptica" (PDF) . Matemáticas de la Computación . 48 (177). Sociedad Estadounidense de Matemáticas : 203–209. doi : 10.1090/S0025-5718-1987-0866109-5 .

Ver también

• Envoltura de llaves
• Relleno de cifrado asimétrico óptimo
• Criptosistema híbrido