Criptosistema Cramer-Shoup

El sistema Cramer-Shoup es un algoritmo de cifrado de clave asimétrica y fue el primer sistema eficiente que demostró ser seguro contra ataques de texto cifrado adaptables elegidos utilizando suposiciones criptográficas estándar. Su seguridad se basa en la intransigencia computacional (ampliamente asumida, pero no probada) de la suposición de Diffie-Hellman decisional . Desarrollado por Ronald Cramer y Victor Shoup en 1998, es una extensión del criptosistema ElGamal . A diferencia de ElGamal, que es extremadamente maleable, Cramer-Shoup agrega otros elementos para garantizar 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 el doble de grande que en ElGamal.

La definición de seguridad lograda por Cramer-Shoup se denomina formalmente " indistinguibilidad bajo un ataque de texto cifrado elegido adaptativo " (IND-CCA2). Esta definición de seguridad es actualmente la definición más sólida conocida para un criptosistema de clave pública: supone que el atacante tiene acceso a un oráculo de descifrado que descifrará cualquier texto cifrado utilizando la clave de descifrado secreta del esquema. El componente "adaptativo" de la definición de seguridad significa que el atacante tiene acceso a este oráculo de descifrado tanto antes como después de observar un texto cifrado objetivo específico para atacar (aunque se le prohíbe utilizar el oráculo simplemente para descifrar este texto cifrado objetivo). La noción más débil de seguridad contra ataques de texto cifrado elegido no adaptativos (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 sistemas criptográficos de uso generalizado no eran seguros contra este tipo de atacantes, durante muchos años los diseñadores de sistemas consideraron que el ataque era poco práctico y de interés fundamentalmente teórico. Esto empezó a cambiar a finales de los años 90, en particular cuando Daniel Bleichenbacher demostró un ataque práctico de texto cifrado adaptable contra servidores SSL utilizando una forma de cifrado RSA . ^[1]

Cramer–Shoup no fue el primer esquema de cifrado que proporcionó seguridad contra ataques de texto cifrado elegido adaptativo. Naor–Yung, Rackoff–Simon y Dolev–Dwork–Naor propusieron conversiones demostrablemente seguras de esquemas estándar (IND-CPA) a 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 del texto cifrado. Una variedad de otros enfoques, incluidos OAEP de Bellare / Rogaway y Fujisaki–Okamoto, logran construcciones eficientes utilizando una abstracción matemática conocida como oráculo aleatorio . Desafortunadamente, para implementar estos esquemas en la práctica se 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, ^[2] aunque no se han demostrado ataques prácticos contra esquemas implementados.

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

• Alice genera una descripción eficiente de un grupo cíclico de orden con dos generadores aleatorios distintos .${\estilo de visualización G}$${\estilo de visualización q}$ $Estilo de visualización g_{1},g_{2}$
• Alicia elige cinco valores aleatorios de .${\displaystyle ({x}_{1},{x}_{2},{y}_{1},{y}_{2},z)}$${\displaystyle \{0,\ldots ,q-1\}}$
• Alice calcula .${\displaystyle c={g}_{1}^{x_{1}}g_{2}^{x_{2}},d={g}_{1}^{y_{1}}g_{2}^{y_{2}},h={g}_{1}^{z}}$
• Alice publica , junto con la descripción de , como su clave pública . Alice conserva como su clave secreta . El grupo puede ser compartido entre usuarios del sistema.${\estilo de visualización (c,d,h)}$${\displaystyle G,q,g_{1},g_{2}}$${\displaystyle (x_{1},x_{2},y_{1},y_{2},z)}$

Para cifrar un mensaje a Alice bajo su clave pública , ${\estilo de visualización m}$${\displaystyle (G,q,g_{1},g_{2},c,d,h)}$

• Bob se convierte en un elemento de .${\estilo de visualización m}$${\estilo de visualización G}$
• Bob elige un número al azar de y luego calcula: ${\estilo de visualización k}$${\displaystyle \{0,\ldots ,q-1\}}$
  • ${\displaystyle u_{1}={g}_{1}^{k},u_{2}={g}_{2}^{k}}$
  • ${\displaystyle e=h^{k}m}$
  • ${\displaystyle \alpha =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).
  • ${\displaystyle v=c^{k}d^{k\alpha}}$
• Bob envía el texto cifrado a Alice.${\displaystyle (u_{1},u_{2},e,v)}$

Para descifrar un texto cifrado con la clave secreta de Alicia , ${\displaystyle (u_{1},u_{2},e,v)}$${\displaystyle (x_{1},x_{2},y_{1},y_{2},z)}$

• Alice calcula y verifica que . Si esta prueba falla, se cancela el descifrado posterior y se rechaza la salida.${\displaystyle \alpha =H(u_{1},u_{2},e)\,}$${\displaystyle {u}_{1}^{x_{1}}u_{2}^{x_{2}}({u}_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v\,}$
• De lo contrario, Alice calcula el texto sin formato como .${\displaystyle m=e/({u}_{1}^{z})\,}$

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

${\displaystyle {u}_{1}^{z}={g}_{1}^{kz}=h^{k}\,}$, y${\displaystyle m=e/h^{k}.\,}$

Si el espacio de mensajes posibles es mayor que el tamaño de , entonces Cramer-Shoup puede usarse en un criptosistema híbrido para mejorar la eficiencia en mensajes largos. ${\estilo de visualización G}$

• Ronald Cramer y Victor Shoup . "Un sistema criptográfico de clave pública práctico y demostrablemente seguro contra ataques de texto cifrado adaptables". En actas de Crypto 1998, LNCS 1462, pág. 13 y siguientes (ps, pdf)
• Implementaciones de juguete de Cramer–Shoup en Emacs Lisp y Java
• Cobertura periodística de 1998 sobre la publicación de Cramer y Shoup en Wired News y en Crypto-Gram de Bruce Schneier
• Ronald Cramer y Victor Shoup : "Pruebas de hash universales y un paradigma para el cifrado seguro de clave pública de textos cifrados seleccionados". En actas de Eurocrypt 2002, LNCS 2332, págs. 45-64. Versión completa (pdf)