Esquema probabilístico de la firma de Rabin

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de febrero de 2019; las comprobaciones requieren 8 ediciones .

El esquema de firma probabilística de Rabin es un método de firma digital propuesto originalmente por Michael O. Rabin en 1979 [1] . El esquema de firma de Rabin fue uno de los primeros esquemas de firma digital propuestos y es el único que relaciona directamente la complejidad de la falsificación de firma con el problema de factorización de enteros . El algoritmo característico de Rabin no es adecuado en un modelo de cálculo aleatorio de Oracle que supone que el problema de factorización de enteros es indecidible. El esquema de la firma Rabin también está estrechamente relacionado con el criptosistema Rabin .

El algoritmo original

Generación de claves
- Se seleccionan números primos , cada uno aproximadamente del tamaño de un bit, y se calcula el producto . $pags$ $q$ $k/2$ ${\ estilo de visualización n = p \ cdot q}$
- A continuación, se selecciona uno al azar de . $b$ $\{1,\ldots,n\}$
- La clave pública es un par . ${\ estilo de visualización (n, b)}$
- clave privada, respectivamente . $(p, q)$
Firma
- Para firmar un mensaje , se selecciona y calcula un número aleatorio . $metro$ $tu$ $m\cdot U\mod n$
- Entonces la ecuación está resuelta . $x(x+b)\mod n=m\cdot U\mod n$
- Si no hay solución a la ecuación, se elige un nuevo valor y la ecuación se resuelve de nuevo. $tu$
- La firma del mensaje será un par $metro$ ${\ estilo de visualización (U, x)}$
Examen
- Dado el mensaje y la firma, el verificador realiza cálculos y luego verifica que sean iguales. $metro$ ${\ estilo de visualización (U, x)}$ $V$ $x(x+b)mod$ $m\cdot U\mod n$

El algoritmo original no utiliza funciones hash y se considera poco fiable. [2]

Algoritmo seguro y simplificado

El algoritmo seguro y protegido [3] se basa en una función hash resistente a colisiones . ${\displaystyle H:\{0,1\}^{*}\rightarrow \{0,1\}^{k))$

En la mayoría de las vistas, el algoritmo se simplifica eligiendo . Se supone que la función hash con el número de bits de salida es un oráculo aleatorio y el algoritmo funciona de la siguiente manera: ${\ estilo de visualización b = 0}$ $H$ $k$

Generación de claves

Se eligen números primos , cada uno aproximadamente del tamaño de un bit, y mod 4 es igual a 3. A continuación, se calcula el producto . $pags$ $q$ $k/2$ $pags$ $q$ ${\ estilo de visualización n = p \ cdot q}$
Открытым ключом в этом случае является . $norte$
La clave privada será el par . $(p, q)$

Firma

Para firmar un mensaje , se selecciona y calcula un número aleatorio . $metro$ $tu$ ${\ estilo de visualización H (m, U)}$
Si no es un módulo cuadrado , se elige un nuevo valor . ${\ estilo de visualización H (m, U)}$ $norte$ $tu$
Después de eso, se encuentra un valor de x, que es la solución a la ecuación . $x^{2}=H(m,U)\mod n$
La firma del mensaje será una pareja . $metro$ ${\ estilo de visualización (U, x)}$

Examen

Dado el mensaje y la firma, el verificador realiza cálculos y luego verifica que sean iguales. $metro$ ${\ estilo de visualización (U, x)}$ $V$ $x^{2}modificación$ ${\ estilo de visualización H (m, U)}$

Notas

En algunas implementaciones del algoritmo, el valor no se usa. En cambio, es posible terminar multiplicando el valor hash por dos números a o b con propiedades y , donde denota el símbolo de Legendre . Entonces, para cualquier módulo, solo uno de los cuatro números será un módulo cuadrado , y es este número el que se elige para firmar digitalmente el mensaje. $tu$ $\left({\tfrac {a}{p}}\right)=-\left({\tfrac {a}{q}}\right)=-1$ $\left({\tfrac {b}{q}}\right)=-\left({\tfrac {b}{p}}\right)=-1$ ${\ estilo de visualización (\ cdot)}$ $H$ $norte$ ${\ estilo de visualización H, aH, bH, abH}$ $norte$

Para simplificar aún más el algoritmo, debe cambiar el mensaje hasta que la firma pase la verificación. $metro$

\\ Función de cambio de mensaje para verificación de firma def root ( m : str , p , q ): while True : x = h ( m ) sig = pow ( p , q - 2 , q ) * p * pow ( x , ( q + 1 ) / 4 , q ) sig = ( pow ( q , p - 2 , p ) * q * pow ( x , ( p + 1 ) / 4 , p ) + sig ) % ( nrabin ) si ( sig * sig ) % nrabin == x : print ( "Escribir mensaje extendido en el archivo m.txt" ) f = open ( 'm.txt' , 'w' ) f . escribir ( m ) f . cerrar () romper m = m + ' ' volver sig

Seguridad

Si la función hash es un oráculo aleatorio, es decir, su salida es realmente aleatoria en , entonces falsificar una firma para cualquier mensaje es tan difícil como calcular la raíz cuadrada de un elemento aleatorio a partir de . $H$ $\mathbb {Z} /n\mathbb {Z}$ $metro$ $\mathbb {Z} /n\mathbb {Z}$

Para probar [4] que obtener una raíz cuadrada aleatoria es tan difícil como la factorización, debe notarse que en la mayoría de los casos hay cuatro raíces cuadradas diferentes, ya que tiene dos módulos de raíces cuadradas y dos módulos de raíces cuadradas , y cada par da un módulo de raíz cuadrada por el teorema chino del resto . Algunas de las raíces pueden tener el mismo valor, pero la probabilidad de que esto ocurra es extremadamente pequeña. $norte$ $pags$ $q$ $norte$

Si es posible encontrar dos raíces cuadradas diferentes tales que pero , esto conduce inmediatamente a una factorización de , ya que los factores primos son divisibles por , pero no divisibles. Entonces el cálculo dará como resultado una factorización no trivial . $X$ $y$ $x^{2}=y^{2}\mod n$ ${\ estilo de visualización x \ neq \ pm y \ mod n}$ $norte$ $norte$ ${\ estilo de visualización x^{2}-y^{2}=(xy)(x+y)}$ ${\ estilo de visualización \ nombre del operador {gcd} (x \ pm y, n)}$ $norte$

Ahora se supone que existe un algoritmo eficiente para encontrar al menos una raíz cuadrada. Luego se elige un módulo aleatorio y se eleva al cuadrado , después de utilizar el algoritmo se saca la raíz cuadrada del módulo y se obtiene una nueva raíz , que tiene una probabilidad del 50% . $r$ $norte$ $r^{2}=R\mod n$ $R$ $norte$ $r^\principal$ $r\neq \pm r^{\prime }\mod n$

Véase también

Notas

↑ Firmas digitalizadas y funciones de clave pública tan intratables como la factorización (enlace no disponible)
↑ | Michele Elia, Davide Schipani, Sobre la firma de Rabin c.1-3 . Consultado el 13 de diciembre de 2019. Archivado desde el original el 22 de septiembre de 2019. (indefinido)
↑ | Michele Elia, Davide Schipani, Sobre la firma de Rabin c.5-9 . Consultado el 13 de diciembre de 2019. Archivado desde el original el 22 de septiembre de 2019. (indefinido)
↑ Firmas digitalizadas y funciones de clave pública tan intratables como la factorización c.15-19 (enlace no disponible)

Literatura

Michele Elia, Davide Schipani, Sobre la firma de Rabin , 2011 PDF
Buchmann, Johannes. Einführung in die Kryptographie . segunda edicion. Berlín: Springer, 2001. ISBN 3-540-41283-2
Menezes, Alfred; van Oorschot, Paul C.; y Vanstone, Scott A. Manual de criptografía aplicada .
Rabin, Miguel. Firmas digitalizadas y funciones de clave pública tan intratables como la factorización (en PDF). Laboratorio de Ciencias de la Computación del MIT, enero de 1979.
Scott Lindhurst, Un análisis del algoritmo de Shank para calcular raíces cuadradas en campos finitos. en R Gupta y KS Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, agosto de 1999.
R Kumanduri y C Romero, Number Theory w/ Computer Applications, Alg 9.2.9, Prentice Hall, 1997. Una probabilística para la raíz cuadrada de un residuo cuadrático módulo a primo.

Enlaces

Fuente

Smart N. Criptografía. - M.: Technosfera, 2005. S. 525.