Mecanismo de encapsulación clave

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

1. Generación de claves ,${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$No requiere ninguna entrada y devuelve un par de claves públicas.${\displaystyle {\mathit {pk}}}$y una clave privada${\displaystyle {\mathit {sk}}}$.
2. Encapsulación ,${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$, requiere una clave pública${\displaystyle {\mathit {pk}}}$elige aleatoriamente una clave secreta${\displaystyle k}$y devuelve${\displaystyle k}$junto con su encapsulación${\displaystyle c}$.
3. Desencapsulación ,${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$, requiere una clave privada${\displaystyle {\mathit {sk}}}$y una encapsulación${\displaystyle c'}$y devuelve una clave secreta encapsulada.${\displaystyle k'}$o falla, a veces indicado por un retorno${\displaystyle \bot }$(llamado " fondo ").

En el contexto asintótico de la criptografía teórica, todos los algoritmos son probabilísticos de tiempo polinomial en un parámetro de seguridad.${\displaystyle \lambda }$y la longitud de la clave secreta${\displaystyle k}$es una función del parámetro de seguridad${\displaystyle \lambda }$. ^{[ 1 ] [ 2 ]}

En criptografía práctica, la clave secreta${\displaystyle k}$Por lo general, tiene una longitud fija para cada algoritmo. Por ejemplo, ML-KEM siempre utiliza claves secretas de 256 bits, ^{[ 4 ] : § 3.3, p. 16} mientras que los algoritmos en RFC 9180 varían entre claves secretas de 256, 384 y 512 bits; ^{[ 5 ] : § 7.1} se pueden derivar claves secretas de longitud arbitraria de ${\displaystyle k}$mediante una función de derivación clave . ^{[ 13 ] : § 5.3 [ 5 ]}

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

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

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${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$para encapsulaciones arbitrarias${\displaystyle c'}$de la elección del adversario.
4. El algoritmo de encapsulación se ejecuta para generar aleatoriamente una clave secreta y una encapsulación.${\displaystyle (k_{0},c):=\operatorname {Encap} ({\mathit {pk}})}$y otra llave secreta${\displaystyle k_{1}}$se genera de forma independiente y aleatoria.
5. Se lanza una moneda justa , obteniendo un resultado.${\displaystyle b\in \{0,1\}}$.
6. La pareja${\displaystyle (k_{b},c)}$se revela al adversario.
7. El adversario puede volver a preguntar${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$para encapsulaciones arbitrarias${\displaystyle c'}$de la elección del adversario, excepto${\displaystyle c}$.
8. El adversario devuelve una suposición${\displaystyle b'\in \{0,1\}}$y gana el juego si${\displaystyle b=b'}$.

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

Se puede utilizar un mecanismo de encapsulación de clave junto con un cifrado simétrico autenticado para construir un esquema de cifrado de clave pública para mensajes arbitrarios. El requisito de seguridad para el cifrado simétrico, denominado mecanismo de encapsulación de datos o DEM , es la indistinguibilidad frente a ataques de texto cifrado elegido para un único mensaje cifrado por el remitente. ^{[ 15 ] [ 11 ] [ 16 ]}

Dado un KEM seguro con algoritmos Gen/Encap/Decap y un DEM seguro${\displaystyle E_{k}(m)}$, el siguiente esquema de cifrado híbrido de clave pública también es seguro contra ataques adaptativos de texto cifrado elegido en el entorno de clave pública: ^{[ 1 ] [ 2 ] : § 7.2, Teorema 7.3 [ 13 ] : § 6.2.1}

• Generación de claves: Igual que la del KEM.
• Para cifrar un mensaje${\displaystyle m}$para una clave pública${\displaystyle {\mathit {pk}}}$:
  1. Dejar${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$.
  2. Dejar${\displaystyle \sigma$ :=E_{k}(m)} .
  3. Enviar${\displaystyle (c,\sigma )}$como el texto cifrado.
• Para descifrar un texto cifrado${\displaystyle (c',\sigma ')}$con clave privada${\displaystyle {\mathit {sk}}}$:
  1. Dejar${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$o fallar si falla.
  2. Devuelve el mensaje${\displaystyle E_{k'}^{-1}(\sigma ')}$o fallar si falla.

Cabe señalar que , al igual que con cualquier cifrado de clave pública por sí solo , esto no autentica al remitente: cualquiera que posea la clave pública puede enviar un mensaje a un destinatario con la clave privada. Para que el remitente demuestre su identidad al receptor, es necesario utilizar otros métodos criptográficos, como las firmas digitales , en un protocolo. ^{[ 17 ]}

No obstante, en este esquema de cifrado de clave pública anónimo se requiere el uso de un cifrado simétrico autenticado para cumplir con la seguridad IND-CCA. Si se utilizara un cifrado no autenticado , seguro solo contra ataques de texto plano elegido (IND-CPA), un adversario podría modificar selectivamente un mensaje a través de su texto cifrado en tránsito, lo que no solo invalida la seguridad IND-CCA por un tecnicismo ^{[ 18 ]} , sino que también puede comprometer la confidencialidad en la práctica, como en EFAIL ^{[ 19 ]} .

Un KEM también puede utilizarse en un protocolo de acuerdo de clave autenticado como TLS con secreto directo para una sesión en línea, haciendo que el cliente y el servidor generen pares de claves KEM e intercambien encapsulaciones firmadas utilizando esos pares de claves, que luego borran al final de la sesión. ^{[ 13 ]}

Los distintos KEM se basan en diferentes problemas matemáticos para su seguridad. Por ejemplo, la seguridad de Rabin-KEM se basa en la dificultad de la factorización de enteros ^{[ 11 ]} , que se ha estudiado durante siglos, pero se sabe que es vulnerable a las computadoras cuánticas capaces de ejecutar el algoritmo de Shor . En cambio, la seguridad de ML-KEM se basa en la dificultad del aprendizaje con errores ^{[ 4 ]} , que solo se ha estudiado durante décadas, pero no se sabe que sea vulnerable ni siquiera a un adversario con una computadora cuántica capaz de ejecutar Shor.

Un combinador KEM es un esquema para combinar dos KEM, KEM ₁ y KEM ₂ con sus respectivos algoritmos de encapsulación KEM ₁ .Encap y KEM ₂ .Encap, y así sucesivamente, en un KEM combinado que es seguro si KEM 1 _o KEM 2 _es seguro. ^{[ 20 ]}

Un KEM que combina un KEM vulnerable a la computación cuántica, como DH-KEM usando X25519 , con un KEM post-cuántico , como ML-KEM, a veces se denomina híbrido , ^{[ 21 ] [ 10 ] [ 22 ]} que no debe confundirse con un criptosistema híbrido que combina criptografía de clave pública con criptografía de clave simétrica .

Cifrado RSA tradicional , con${\displaystyle t}$Módulos y exponentes de -bits${\displaystyle e}$, se define de la siguiente manera: ^{[ 23 ] [ 24 ] [ 25 ]}

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

1. Generar un${\displaystyle t}$semiprimo de -bit${\displaystyle n}$con${\displaystyle 2^{t-1}<n<2^{t}}$al azar satisfactorio${\displaystyle \gcd(e,\lambda (n))=1}$, dónde${\displaystyle \lambda (n)}$es la función de Carmichael .
2. Calcular${\displaystyle d:=e^{-1}{\bmod {\lambda }}(n)}$.
3. Devolver${\displaystyle {\mathit {pk}}:=n}$como clave pública y${\displaystyle {\mathit {sk}}:=(n,d)}$como clave privada. (Existen muchas variaciones de algoritmos de generación de claves y formatos de clave privada. ^{[ 26 ]} )

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

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

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

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

Este enfoque ingenuo es totalmente inseguro. Por ejemplo, al no ser aleatorio, no puede protegerse ni siquiera contra ataques de texto plano conocido : un adversario puede determinar si el remitente envía un mensaje ATTACK AT DAWNo uno falso ATTACK AT DUSKsimplemente cifrando esos mensajes y comparando el texto cifrado.

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

Desde el mensaje${\displaystyle m}$es casi siempre una clave secreta corta para un cifrado autenticado de clave simétrica utilizado para encriptar un mensaje de cadena de bits arbitrario, un enfoque más simple llamado RSA-KEM es elegir un elemento de${\displaystyle \mathbb {Z} /n\mathbb {Z} }$de forma aleatoria y usar eso para derivar una clave secreta usando una función de derivación de clave.${\displaystyle H}$, aproximadamente como sigue: ^{[ 15 ] [ 8 ] [ 16 ]}

• Generación de claves : Como se indicó anteriormente.
• Encapsulación para una clave pública${\displaystyle {\mathit {pk}}=n}$, donación${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$:

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

• Desencapsulación de${\displaystyle c'}$con clave privada${\displaystyle {\mathit {sk}}=(n,d)}$, donación${\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 precisa al problema RSA que los esquemas de relleno como RSAES-OAEP . ^{[ 15 ]}

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

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

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

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

1. Elegir${\displaystyle r\in \mathbb {Z} /q\mathbb {Z} }$uniformemente al azar.
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${\displaystyle c'=(c'_{1},c'_{2})}$para una clave privada${\displaystyle {\mathit {sk}}=x}$, donación${\displaystyle m':=\operatorname {Decrypt} ({\mathit {sk}},c')}$:

1. Fallar y regresar${\displaystyle \bot }$si${\displaystyle (c'_{1})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$o si${\displaystyle (c'_{2})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$, es decir, si${\displaystyle c'_{1}}$o${\displaystyle c'_{2}}$no está en el subgrupo generado por${\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${\displaystyle \mathbb {Z} /p\mathbb {Z} }$(lo que lo limita a un mensaje de unos pocos cientos de bytes para valores típicos de${\displaystyle p}$Al validar los textos cifrados durante el descifrado, se evita la filtración de bits de la clave privada.${\displaystyle x}$a través de textos cifrados elegidos maliciosamente fuera del grupo generado por${\displaystyle g}$.

Sin embargo, esto no logra la indistinguibilidad contra un ataque de texto cifrado elegido . Por ejemplo, un adversario que tenga un texto cifrado${\displaystyle c=(c_{1},c_{2})}$para un mensaje desconocido${\displaystyle m}$puede descifrarlo trivialmente consultando al oráculo de descifrado para obtener el texto cifrado distinto.${\displaystyle c':=(c_{1},c_{2}g)}$, lo que produce el texto plano relacionado${\displaystyle m':=mg{\bmod {p}}}$, de la cual${\displaystyle m}$puede ser recuperado por${\displaystyle m=m'g^{-1}{\bmod {p}}}$. ^{[ 29 ]}

El cifrado Elgamal tradicional se puede adaptar al entorno de curva elíptica, pero requiere algún método para codificar mensajes de forma reversible como puntos en la curva, lo cual es menos trivial que codificar mensajes como números enteros módulo${\displaystyle p}$. ^{[ 31 ]}

Desde el mensaje${\displaystyle m}$es casi siempre una clave secreta corta para un cifrado autenticado de clave simétrica utilizado para encriptar un mensaje de cadena de bits arbitrario, un enfoque más simple , llamado Elgamal-KEM o DH-KEM , es derivar la clave secreta de${\displaystyle t}$y prescindir de${\displaystyle m}$y${\displaystyle c_{2}}$En conjunto, como un KEM, utilizando una función de derivación clave${\displaystyle H}$: ^{[ 1 ] [ 5 ]}

• Generación de claves : Como se indicó anteriormente.
• Encapsulación para una clave pública${\displaystyle {\mathit {pk}}=y}$, donación${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$:

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

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

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

Cuando se combina con un cifrado autenticado para encriptar mensajes de cadena 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 aplicar hash a elementos aleatorios del grupo sobre el que está definido,${\displaystyle \mathbb {Z} /p\mathbb {Z} }$En este caso, y no se trata de una codificación reversible de mensajes, es fácil extenderla a grupos de curvas elípticas más compactos y eficientes para la misma seguridad, como en las instancias de ECIES, Elliptic Curve Integrated Encryption Scheme o RFC 9180 DHKEM(...).