Criptosistema Cramer-Shoup

El sistema Cramer-Shoup es un algoritmo de encriptación de clave asimétrica, y fue el primer esquema eficiente que se comprobó que era seguro contra el ataque de texto cifrado elegido mediante el uso de suposiciones criptográficas estándar. Su seguridad se basa en la intratabilidad computacional (ampliamente asumida, pero no probada) de la suposición decisional de Diffie-Hellman. Desarrollado por Ronald Cramer y Victor Shoup en 1998, es una extensión del criptosistema ElGamal. En contraste con ElGamal, que es extremadamente maleable, Cramer-Shoup agrega otros elementos para asegurar la no maleabilidad incluso contra un atacante ingenioso. Esta no maleabilidad se logra mediante el uso de una función hash unidireccional universal y cálculos adicionales, lo que da como resultado un texto cifrado que es dos veces más grande que en ElGamal.

Ataque de texto cifrado adaptable

La definición de seguridad lograda por Cramer-Shoup formalmente se denomina "indistinguibilidad bajo ataque de texto cifrado adaptable" (IND-CCA2). Esta definición de seguridad es actualmente la definición más sólida conocida para un sistema criptográfico de clave pública: asume que el atacante tiene acceso a un oráculo de descifrado que descifrará cualquier texto cifrado utilizando la clave secreta de descifrado del esquema. El componente "adaptativo" de la definición de seguridad significa que el atacante tiene acceso a este oráculo de descifrado antes y después de observar un texto cifrado objetivo específico para atacar (aunque tiene prohibido usar el oráculo para simplemente descifrar este texto cifrado objetivo). La noción más débil de seguridad contra los ataques de texto cifrado no adaptativos elegidos (IND-CCA1) solo permite al atacante acceder al oráculo de descifrado antes de observar el texto cifrado objetivo.

Aunque era bien sabido que muchos criptosistemas ampliamente utilizados eran inseguros contra tal atacante, durante muchos años los diseñadores del sistema consideraron que el ataque no era práctico y tenía un interés mayormente teórico. Esto comenzó a cambiar a fines de la década de 1990, particularmente cuando Daniel Bleichenbacher demostró un ataque de texto cifrado adaptable y práctico contra servidores SSL utilizando una forma de encriptación RSA.

Cramer-Shoup no fue el primer esquema de encriptación para proporcionar seguridad contra el ataque de texto cifrado adaptado. Naor-Yung, Rackoff-Simon y Dolev-Dwork-Naor propusieron conversiones probables y seguras de los esquemas estándar (IND-CPA) en los esquemas IND-CCA1 e IND-CCA2. Estas técnicas son seguras bajo un conjunto estándar de suposiciones criptográficas (sin oráculos aleatorios), sin embargo se basan en técnicas complejas de prueba de conocimiento cero, y son ineficientes en términos de costo computacional y tamaño de texto cifrado. Una variedad de otros enfoques, incluyendo OAEP de Bellare/Rogaway y Fujisaki-Okamoto logran construcciones eficientes utilizando una abstracción matemática conocida como oráculo aleatorio. Desafortunadamente, implementar estos esquemas en la práctica requiere la sustitución de alguna función práctica (por ejemplo, una función hash criptográfica) en lugar del oráculo aleatorio. Un creciente cuerpo de evidencia sugiere la inseguridad de este enfoque, aunque no se han demostrado ataques prácticos contra los esquemas desplegados.

El criptosistema

Cramer-Shoup consta de tres algoritmos: el generador de claves, el algoritmo de cifrado y el algoritmo de descifrado.

Generación clave

• Alice genera una descripción eficiente de un grupo cíclico $G$ de orden $q$, con dos generadores aleatorios distintos $g_{1}$, $g_{2}$.
• Alice escoge 5 valores aleatorios $(x_{1},x_{2},y_{1},y_{2},z)$ de ${0,...,q-1}$.
• Alice calcula $c=g_{1}^{x_{1}}g_{2}^{x_{2}},d=g_{1}^{y_{1}}g_{2}^{y_{2}},h=g_{1}^{z}$
• Alice publica $(c,d,h)$, junto con la descripción de $G,q,g_{1},g_{2}$, como su clave pública. Alice conserva $(x_{1},x_{2},y_{1},y_{2},z)$ como llave secreta. El grupo se puede compartir entre los usuarios del sistema.

Encriptación

Para encriptar un mensaje $m$ para Alicia bajo la llave pública $(G,q,g_{1},g_{2},c,d,h)$,

• Bob convierte $m$ en un elemneto de $G$.
• Bob escoge un $k$ aleatorio entre ${0,...,q-1}$, entonces calcula:

• $u_{1}=g_{1}^{k},u_{2}=g_{2}^{k}$
• $e=h^{k}m$
• $a=H(u_{1},u_{2},e)$, donde H() es una función hash unidireccional universal (o una función hash criptográfica resistente a colisiones, que es un requisito más fuerte).
• $v=c^{k}d^{ka}$

• Bob envía el texto cifrado $(u_{1},u_{2},e,v)$ a Alicia.

Descifrado

Para descifrar un texto cifrado $(u_{1},u_{2},e,v)$ con la llave secreta de Alice $(x_{1},x_{2},y_{1},y_{2},z)$,

• Alice calcula $a=H(u_{1},u_{2},e)$ y verifica que $u_{1}^{x_{1}}u_{2}^{x_{2}}(u_{1}^{y_{1}}u_{2}^{y_{2}})^{a}=v$. Si esta prueba falla, se anula el descifrado adicional y se rechaza la salida.
• En otro caso, Alice calcula el texto como $m=e/(u_{1}^{z})$.

La etapa de descifrado descifra correctamente cualquier texto cifrado formado correctamente, ya que

$u_{1}^{z}=g_{1}^{kz}=h^{k}$, y $m=e/h^{k}$.

Si el espacio de posibles mensajes es mayor que el tamaño de $G$, entonces Cramer-Shoup se puede usar en un criptosistema híbrido para mejorar la eficiencia en mensajes largos.

Referencias

• Cramer–Shoup cryptosystem

• Datos: Q1138784