Firmas Digitales

Son similares a los MACs, dado que su objetivo es la integridad, pero tienen ciertas ventajas:

• Son públicamente verificables
• Son transferibles: Puede enviarse simultáneamente a varios destinatarios o reenviarse y sigue siendo verificable
• Proveen no repudio: Quien firme algo no puede negar haberlo hecho, lo cual es muy importante cuando está reglamentado jurídicamente.

La firma digital es una terna de algoritmos

• Gen: $(n)\to k=(sk,pk)$
• Sign: $s\leftarrow {\text{Sign}}_{sk}(m)$
• Vrfy: $b={\text{Vrfy}}_{pk}(m,s)$

Donde para todo $m$ y $k$ válidos: ${\text{Vrfy}}_{pk}(m,{\text{Sign}}_{sk}(m))=1$

RSA-Signature

Es idéntico a RSA-Encryption, pero invirtiendo los papeles de las claves:

• 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{Sign}}_{sk}(m)\equiv m^d\text{mod}n$
• ${\text{Vrfy}}_{pk}(m,s)=(m==s^e\text{mod}n)$

Este esquema, aunque es común en los libros, es inseguro. Si consideramos el adversario $A$:

• $s\leftarrow S$ (selecciona una firma al azar)
• Calcula $m=s^e\mathrm{mod}n$
• Emite $(m,s)$

Consigue pasar Sig-Forge, y otro posible ataque:

• $s_1=f(m_1)$, $s_2=f(m_2)$
• Emite $(m_1\ast m_2,s_1\ast s_2)$

Hashed RSA

Busca solucionar los problemas de RSA-Signature, introduciendo una función de hash libre de colisiones:

• ${\mathrm{Sign}}_{sk}(m)\equiv H(m{)}^d\mathrm{mod}n$
• ${\mathrm{Vrfy}}_{pk}(m,s)=(H(m)==s^e\mathrm{mod}n)$

WARNING

No posee una prueba de seguridad a menos que se asuma un modelo ideal de $H$

Digital Signature Standard

Similar a AES, es un standard establecido por los Estados Unidos

• Gen
  • Seleccionar $H(x):$ SHA1 o SHA2
  • Tamaño de claves: $(L,N)$: $(1024,160)$, $(2048,224)$, $(2048,256)$ o $(3072,256)$
  • $q\leftarrow$ primo de tamaño $N$ (bits)
  • $p\leftarrow$ primo de tamaño $P$ tal que $(p-1)\equiv 0\mathrm{mod}q$
  • $g\leftarrow$ generador de orden $q\mathrm{mod}q$, tal que $g^{(p-1)/q}\ne 1$
  • Seleccionar $p,q,g$, ($G=Z_p^{\ast }$)
  • $x\leftarrow Z_q$, $y=g^x\mathrm{mod}p$
  • $pk=(p,q,g,y)$, $sk=(p,q,g,x)$
• Sign
  • $k\leftarrow Z_q$, $r=(g^k\mathrm{mod}p)\mathrm{mod}q$
  • $s=\left(H(m)+x\ast r\right)\ast k^{-1}\mathrm{mod}q$
  • ${\mathrm{Sign}}_{sk}(m)=(r,s)$
• Vrfy
  • $v_1=\left(H(m)\ast s^{-1}\right)\mathrm{mod}q$
  • $v_2=r\ast s-1\mathrm{mod}q$
  • ${\mathrm{Vrfy}}_{pk}(m,(r,s))=(r==g^{u_1}\ast y^{u_2})\mathrm{mod}p\mathrm{mod}q$