Criptosistema Cramer-Shoup

El sistema Cramer-Shoup és un algoritme d'encriptación de clau asimètrica, i va anar el primer esquema eficient que es va comprovar que era segur contra l'atac de text sifrat elegit per mig de l'us de suposicions criptogràfiques estàndar. La seua seguritat es basa en la intratabilidad computacional (àmpliament assumida, pero no provada) de la suposició decisional de Diffie-Hellman. Desenrollat per Ronald Cramer i Victor Shoup en 1998, és una extensió del criptosistema ElGamal. En contrast en ElGamal, que és extremadament maleable, Cramer-Shoup agrega atres elements per a assegurar la no maleabilidad inclús contra un atacant ingeniós. Esta no maleabilidad es conseguix per mig de l'us d'una funció hash unidireccional universal i càlculs adicionals, lo que dona com resultat un text sifrat que és dos voltes més gran que en ElGamal.

Atac de text sifrat adaptable

La definició de seguritat conseguida per Cramer-Shoup formalment es denomina "indistinguibilidad baix atac de text sifrat adaptable" (IND-CCA2). Esta definició de seguritat és actualment la definició més sòlida coneguda per a un sistema criptográfico de clau pública: assumix que l'atacant té accés a un oràcul de dessifrat que dessifrarà qualsevol text sifrat utilisant la clau secreta de dessifrat de l'esquema. El component "adaptatiu" de la definició de seguritat significa que l'atacant té accés a este oràcul de dessifrat abans i despuix d'observar un text sifrat objectiu específic per a atacar (encara que té prohibit usar l'oràcul para simplement dessifrar este text sifrat objectiu). La noció més dèbil de seguritat contra els atacs de text sifrat no adaptatius elegits (IND-CCA1) solament permet a l'atacant accedir al oràcul de dessifrat abans d'observar el text sifrat objectiu.

Encara que era ben sabut que molts criptosistemas àmpliament utilisats eren insegurs contra tal atacant, durant molts anys els dissenyadors del sistema varen considerar que l'atac no era pràctic i tenia un interés majorment teòric. Açò va escomençar a canviar a fins de la década de 1990, particularment quan Daniel Bleichenbacher va demostrar un atac de text sifrat adaptable i pràctic contra servidors SSL utilisant una forma d'encriptación RSA.

Cramer-Shoup no va ser el primer esquema d'encriptación per a proporcionar seguritat contra l'atac de text sifrat adaptat. Naor-Yung, Rackoff-Simon i Dolev-Dwork-Naor varen propondre conversió provables i segures dels esquemes estàndar (IND-CPA) en els esquemes IND-CCA1 i IND-CCA2. Estes tècniques són segures baix un conjunt estàndar de suposicions criptogràfiques (sense oràculs aleatoris), no obstant es basen en tècniques complexes de prova de coneiximent zero, i són ineficientes en térmens de cost computacional i tamany de text sifrat. Una varietat d'atres enfocaments, incloent OAEP de Bellare/Rogaway i Fujisaki-Okamoto conseguixen construccions eficients utilisant una abstracció matemàtica coneguda com oràcul aleatori. Desafortunadament, implementar estos esquemes en la pràctica requerix la substitució d'alguna funció pràctica (per eixemple, una funció hash criptográfica) en lloc de l'oràcul aleatori. Un creixent cos d'evidència sugerix l'inseguritat d'este enfocament, encara que no s'han demostrat atacs pràctics contra els esquemes desplegats.

El criptosistema

Cramer-Shoup consta de tres algoritmes: el generador de claus, l'algoritme de sifrat i l'algoritme de dessifrat.

Generació clau

• Alice genera una descripció eficient d'un grup cíclico $G$ d'orde $q$, en dos generadors aleatoris distints $g_1$, $g_2$.
• Alice tria 5 valors aleatoris $(x_1,x_2,y_1,y_2,z)$ de $0,\mathrm{...},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)$, junt en la descripció de $G,q,g_1,g_2$, com la seua clau pública. Alice conserva $(x_1,x_2,y_1,y_2,z)$ com a clau secreta. El grup es pot compartir entre els usuaris del sistema.

Encriptación

Per a encriptar un mensage $m$ per a Alicia baix la clau pública $(G,q,g_1,g_2,c,d,h)$,

• Bob convertix $m$ en un elemneto de $G$.
• Bob tria un $k$ aleatori entre $0,\mathrm{...},q-1$, llavors calcula:

• $u_1=g_1^k,u_2=g_2^k$
• $e=h^{k}m$
• $a=H(u_1,u_2,e)$, a on H() és una funció hash unidireccional universal (o una funció hash criptogràfica resistent a colisions, que és un requisit més fort).
• $v=c^k{d}^{ka}$

• Bob envia el text sifrat $(u_1,u_2,e,v)$ a Alicia.

Dessifrat

Per a dessifrar un text sifrat $(u_1,u_2,e,v)$ en la clau secreta d'Alice $(x_1,x_2,y_1,y_2,z)$,

• Alice calcula $a=H(u_1,u_2,e)$ i verifica que $u_1^{x_1}{u}_2^{x_2}(u_1^{y_1}{u}_2^{y_2}{)}^a=v$. Si esta prova falla, s'anula el dessifrat adicional i es rebuja l'eixida.
• En un atre cas, Alice calcula el text com $m=e/(u_1^z)$.

L'etapa de dessifrat dessifra correctament qualsevol text sifrat format correctament, ya que

$u_1^z=g_1^{kz}=h^k$, i $m=e/h^k$.

Si l'espai de possibles mensages és major que el tamany de $G$, llavors Cramer-Shoup es pot usar en un criptosistema híbrit per a millorar l'eficiència en mensages llarcs.

Referències

• Cramer–Shoup cryptosystem