Criptosistemas Asimétricos

Es una terna de algoritmos

• Gen: $()\to \text{pk, sk}$ (public key, secret key)
• Enc: ${\text{Enc}}_{pk}(m)$
• Dec: ${\text{Dec}}_{sk}(c)$

Que cumple que para todo $m$ y $k$ válidos, ${\text{Dec}}_{sk}({\text{Enc}}_{pk}(m))=m$

“Textbook” RSA

• Gen:
  • Elegir $p,q\leftarrow \text{Nuˊmeros primos}$. $n=p\ast q$
  • $e\leftarrow (0,\varphi (n))|\text{MCD}(e,\varphi (n))=1$
  • Calcular $d$ tal que $e\ast d\equiv 1\text{mod}\varphi (n)$
  • $pk=(n,e)$, $sk=(n,d)$
• ${\text{Enc}}_{pk}(p)\equiv p^e\text{mod}n$
• ${\text{Dec}}_{sk}(c)\equiv c^d\text{mod}n$

Problemas

• Tal cual está formulado, el cifrado es determinístico, por lo cual no pasaría la prueba de Eavesdropping para sistemas asimétricos.
• Si $e$ y $m$ son pequeños, $m^e<n$ y entonces se puede calcular el logaritmo (durante mucho tiempo se utilizo $e=3$ para ahorrar tiempo, ouch)
• Módulos repetidos: Si dos pares de claves comparten el mismo $n$, es posible recuperar $n$ (y luego la clave privada)

PKCS 1 v1.5

RSA Labs Public Key Cryptography Standard, defina una versión con padding aleatorio de RSA: Sea $k$ la longitud de $n$ en bytes, solo se permiten cifrar mensajes de hasta $n-11$ bytes. Luego, sea $D$ la longitud de $m$ en bytes, el nuevo mensaje $m^{\prime }=00000000||00000010||r||00000000||m$, donde $r=k-D-3$ bytes aleatorios, distintos de cero para evitar ambigúedades. Se cree que es CPA-Secure, pero se encontraron ataques que muestran que no es CCA-Secure

El Gamal

Basado en el Intercambio Diffie-Hellman

• Gen
  • Seleccionar $G$, $q$, $g$ (Campo $G$ de tamaño $q$, $g$ un generador)
  • $x\leftarrow Z_q,h=g^x$
  • $pk=(G,q,g,h)$, $sk=(G,q,g,x)$
• Enc:
  • Sea $y\leftarrow Z_q$
  • ${\text{Enc}}_{pk}(m)=(c_1,c_2)=(g^y,h^y\ast m)$
• Dec: ${\text{Dec}}_{sk}(c)=c_2/c_1^x$

Se sabe que si la prueba de decisión de DH es difícil en G, entonces el gamal es CPA-Secure A diferencia de RSA, el gamal es probabilistico, permite reutilizar los parámetros $G$, $q$ y $g$, y no esta limitado a campos numéricos: Es decir, permite utilizar anillos de polinomios, que tienen $2^n$ elementos, por lo que es fácil mapear mensajes, o curvas elípticas, donde el problema de decisión de DH es más complejo.

En números

El nivel de seguridad es relativo a los tamaños de los conjuntos involucrados, es decir: En RSA, $n=p\ast q$, mientras que en el gamal, $n=q$. Cuando se utilizan campos numéricos $n\ge 1024$ bits, aunque en la actualidad se recomiendan 1536 o 2048 bits, pero para campos de otro tipo, los números pueden variar, por ejemplo sobre curvas elípticas, se recomienda $n\ge 320$ bits.