algoritmo de firma de Rabin

En criptografía , el algoritmo de firma de Rabin es un método de firma digital publicado originalmente por Michael O. Rabin en 1979. ^{[ 1 ] [ 2 ]}

El algoritmo de firma de Rabin fue uno de los primeros esquemas de firma digital propuestos. Al utilizar una función de puerta trasera con un hash del mensaje en lugar del mensaje mismo, a diferencia de las propuestas anteriores de firmas basadas en hash de un solo uso o firmas basadas en puerta trasera sin hash, ^{[ 3 ] [ 4 ]} el de Rabin fue el primer diseño publicado que cumplió con lo que ahora es el estándar moderno de seguridad para firmas digitales para más de un mensaje: la infalsificación existencial bajo un ataque de mensaje elegido . ^{[ 5 ]}

Las firmas de Rabin se asemejan a las firmas RSA con exponente${\displaystyle e=2}$, pero esto conduce a diferencias cualitativas que permiten una implementación más eficiente ^{[ 5 ]} y una garantía de seguridad relativa a la dificultad de la factorización de enteros , ^{[ 1 ] [ 2 ] [ 6 ]} que no se ha demostrado para RSA . Sin embargo, las firmas de Rabin han tenido relativamente poco uso o estandarización fuera de IEEE P1363 ^{[ 7 ]} en comparación con esquemas de firma RSA como RSASSA-PKCS1-v1_5 y RSASSA-PSS .

El esquema de firma de Rabin está parametrizado por una función hash aleatoria.${\displaystyle H(m,u)}$de un mensaje${\displaystyle m}$y${\displaystyle k}$-cadena de aleatorización de bits${\displaystyle u}$.

Clave pública

Una clave pública es un par de números enteros.${\displaystyle (n,b)}$con${\displaystyle 0\leq b<n}$y${\displaystyle n}$extraño.${\displaystyle b}$se elige arbitrariamente y puede ser una constante fija.

Firma

Una firma en un mensaje${\displaystyle m}$es un par${\displaystyle (u,x)}$de un${\displaystyle k}$cadena de bits${\displaystyle u}$y un número entero${\displaystyle x}$de tal manera que$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}.}$$

Clave privada

La clave privada para una clave pública${\displaystyle (n,b)}$es el secreto factorización prima impar${\displaystyle p\cdot q}$de${\displaystyle n}$, elegidos uniformemente al azar de algún espacio grande de números primos.

Firmar un mensaje

Para hacer una firma en un mensaje${\displaystyle m}$Utilizando la clave privada, el firmante comienza eligiendo una${\displaystyle k}$cadena de bits${\displaystyle u}$uniformemente al azar y calcula${\displaystyle c:=H(m,u)}$. Dejar${\displaystyle d=(b/2){\bmod {n}}}$. Si${\displaystyle c+d^{2}}$es un no residuo cuadrático módulo${\displaystyle n}$, el firmante comienza de nuevo con un número aleatorio independiente${\displaystyle u}$. ^{[ 1 ] : pág. 10} De lo contrario, el firmante calcula$${\displaystyle {\begin{aligned}x_{p}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {p}},\\x_{q}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {q}},\end{aligned}}}$$utilizando un algoritmo estándar para calcular raíces cuadradas módulo un número primo — eligiendo${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$lo hace más fácil. Las raíces cuadradas no son únicas, y las diferentes variantes del esquema de firma hacen diferentes elecciones de raíz cuadrada; ^{[ 5 ]} en cualquier caso, el firmante debe asegurarse de no revelar dos raíces diferentes para el mismo hash.${\displaystyle c}$. ${\displaystyle x_{p}}$y${\displaystyle x_{q}}$satisfacer las ecuaciones$${\displaystyle {\begin{aligned}x_{p}(x_{p}+b)&\equiv H(m,u){\pmod {p}},\\x_{q}(x_{q}+b)&\equiv H(m,u){\pmod {q}}.\end{aligned}}}$$ El firmante utiliza entonces el teorema chino del resto para resolver el sistema.$${\displaystyle {\begin{aligned}x&\equiv x_{p}{\pmod {p}},\\x&\equiv x_{q}{\pmod {q}},\end{aligned}}}$$para${\displaystyle x}$, de modo que${\displaystyle x}$Satisface$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}$$según sea necesario. El firmante revela${\displaystyle (u,x)}$como firma en${\displaystyle m}$.

El número de ensayos para${\displaystyle u}$antes${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}$se puede resolver${\displaystyle x}$se distribuye geométricamente con un promedio de alrededor de 4 ensayos, porque aproximadamente 1/4 de todos los enteros son residuos cuadráticos módulo${\displaystyle n}$.

Seguridad frente a cualquier adversario definida genéricamente en términos de una función hash.${\displaystyle H}$(es decir, la seguridad en el modelo de oráculo aleatorio ) se deriva de la dificultad de factorizar${\displaystyle n}$Cualquier adversario con alta probabilidad de éxito en la falsificación puede, con una probabilidad casi igual de alta, encontrar dos raíces cuadradas distintas.${\displaystyle x_{1}}$y${\displaystyle x_{2}}$de un número entero aleatorio${\displaystyle c}$módulo${\displaystyle n}$. Si${\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}$entonces${\displaystyle \gcd(x_{1}\pm x_{2},n)}$es un factor no trivial de${\displaystyle n}$, desde${\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}$entonces${\displaystyle n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2})}$pero${\displaystyle n\nmid x_{1}\pm x_{2}}$. ^{[ 2 ]} Formalizar la seguridad en términos modernos requiere completar algunos detalles adicionales, como el codominio de${\displaystyle H}$; si establecemos un tamaño estándar${\displaystyle K}$para los factores primos,${\displaystyle 2^{K-1}<p<q<2^{K}}$, entonces podríamos especificar${\displaystyle H\colon \{0,1\}^{*}\times \{0,1\}^{k}\to \{0,1\}^{K}}$. ^{[ 6 ]}

La aleatorización de la función hash se introdujo para permitir al firmante encontrar un residuo cuadrático, pero el hash aleatorio para firmas posteriormente se volvió relevante por derecho propio para teoremas de seguridad más estrictos ^{[ 2 ]} y resistencia a ataques de colisión en funciones hash fijas. ^{[ 8 ] [ 9 ] [ 10 ]}

• Firmas de Rabin-Williams en cr.yp.to