Hash de dominio completo

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 24 de enero de 2019; las comprobaciones requieren 30 ediciones .

En criptografía , Full Domaine Hash ( FDH o Full Domain Hash ) es un esquema de firma basado en RSA que sigue el paradigma hash y firma . Es demostrablemente seguro (es decir, no se ve afectado por ataques adaptativos de mensajes elegidos) en el modelo aleatorio de Oracle . FDH implica codificar el mensaje usando una función cuyo tamaño de imagen es el tamaño del módulo RSA , y luego elevar el resultado a la potencia secreta del exponente RSA .

Introducción

Desde el descubrimiento de la criptografía de clave pública por parte de Whitfield Diffie y Martin Hellman [ 1 ] , uno de los temas de investigación más importantes ha sido el desarrollo de criptosistemas prácticos y demostrablemente (en la práctica) seguros. La prueba de la seguridad práctica suele ser la complejidad computacional desde la resolución de un problema bien conocido hasta la ruptura de un criptosistema. Los problemas bien conocidos incluyen la factorización de números enteros grandes , el cálculo del logaritmo discreto módulo un número primo p, o la extracción de una raíz módulo un número entero compuesto, en el que se basa el criptosistema RSA [2] .

Una práctica muy común para firmar con RSA es primero codificar el mensaje, agregar un salt al mensaje y luego elevarlo a la potencia de la clave pública. Este paradigma de "hash and decrypt" es la base de numerosos estándares como PKCS # 1 v2.0 [3] . El esquema es tomar una función hash cuyo tamaño de salida es exactamente el tamaño del módulo: este es el esquema hash de dominio completo (FDH) presentado por Bellard y Rogaway en el artículo "Los oráculos aleatorios son prácticos: un paradigma para el diseño de protocolos eficientes" [4] . Se puede demostrar que el esquema FDH es seguro en el modelo de Oracle aleatorio, suponiendo que es difícil invertir RSA , es decir, tomar un módulo raíz como un entero compuesto. La metodología del oráculo aleatorio fue presentada por Bellard y Rogaway en "Los oráculos aleatorios son prácticos: un paradigma para el diseño de protocolos eficientes" [4] , donde muestran cómo desarrollar esquemas de firma altamente seguros a partir de cualquier función con una entrada secreta . En el modelo de oráculo aleatorio , una función hash se trata como un oráculo que produce un valor aleatorio para cada nueva solicitud. En el artículo original, un oráculo aleatorio convierte una secuencia de 0 y 1 de longitud fija en una secuencia de longitud infinita y selecciona aleatoriamente una subsecuencia de la longitud requerida de la secuencia . El trabajo seminal de Bellard y Rogaway enfatiza que para la aplicación práctica de la seguridad comprobable, es importante considerar reducciones de seguridad "duras". Una degradación de seguridad es "difícil" cuando cualquier acción del criptoanalista para romper el esquema de firma da como resultado que un problema bien establecido se resuelva con suficiente probabilidad, idealmente con una probabilidad de 1. En este caso, el esquema de firma es casi tan seguro como el problema bien establecido. Por el contrario, si la contracción es "débil", es decir, la probabilidad antes mencionada es demasiado pequeña, la garantía para el esquema de firma puede ser bastante débil. ${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty}$

Definición

El esquema de firma hash de dominio completo (Gen, Sign, Verify) se define de la siguiente manera. El algoritmo de generación de claves ejecuta RSA para obtener el archivo . Da salida donde y . El algoritmo de firma y verificación tiene acceso a un oráculo con función hash ${\ estilo de visualización (N, e, d)}$ ${\ estilo de visualización (pk, sk)}$ $pk=(N,e)$ $sk=(N,d)$ $H_{FDH}:{\{0,1\}}\to {\mathbb {Z} _{N}}$

La firma y verificación se realiza de la siguiente manera:

{\textstyle {\begin{aligned}SignFDH_{N,d}(M)\\y\leftarrow H_{FDH}(M)\\return:y^{d}modN\\\\VerifyFDH_{N,e} (M,x)\\y\leftarrow x^{e}modN;\\y'\leftarrow H_{FDH}(M)\\if(y=y')then\\return:1\\else\\ retorno:0\end{alineado}}}

Análisis de seguridad del esquema FDH

El enfoque de Bellard y Rogway

Teorema 1 Suponga que RSA es -seguro (con probabilidad ɛ′ tarda t′ tiempo en romperse) Entonces el esquema de firma FDH es -seguro, donde ${\ estilo de visualización (t', \ varepsilon ')}$ $(t,\varepsilon)$

{\begin{alineado}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\varepsilon &=(q_{\text{hash}} +q_{\text{sig}))*\varepsilon '\end{alineado}}

La desventaja de este resultado es que puede ser mucho más pequeño que . Por ejemplo, si asumimos que un criptoanalista puede consultar el número de firmas y calcular hashes en mensajes incluso si la probabilidad de inversión de RSA es solo , todo lo que obtenemos es que la probabilidad es casi , lo que no es satisfactorio. Para obtener un nivel de seguridad aceptable, debemos utilizar un tamaño de módulo mayor, lo que afectará positivamente la eficiencia del circuito. ${\ estilo de visualización \ varepsilon '}$ $\varepsilon$ $q_{\text{sig}}=2^{30}$ $q_{\text{hash}}=2^{60}$ ${\ estilo de visualización 2^{-61}}$ $1/2$

Para obtener el margen de seguridad más adecuado, Bellar y Rogaway desarrollaron un nuevo esquema, el esquema de firma probabilística , que proporciona una estricta reducción de seguridad: la probabilidad de falsificación de firma es casi tan pequeña como con inversión . En cambio, existe un enfoque alternativo que se puede aplicar al esquema FDH para obtener un mejor límite. [5] ${\ estilo de visualización (PSS)}$ ${\ Displaystyle RSA (\ varepsilon = \ varepsilon ')}$

Enfoque alternativo

Otra reducción que da una mejor estimación de seguridad para FDH se basa en la demostración del teorema

Teorema 2 Sea RSA seguro. Entonces el esquema de firma FDH es seguro, donde ${\ estilo de visualización (t', \ épsilon ')}$ ${\ estilo de visualización (t, \ épsilon)}$

{\begin{alineado}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\epsilon &={\frac {1}{\left (1-{\frac {1}{q_{\text{sig}}}}\right)^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{alineado}}

Para grandes , . $q_{\text{sig}}$ $\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$

Definición 1

Llamaremos inversor a un algoritmo que rompe RSA, cuya probabilidad de éxito después de que no haya transcurrido más de t tiempo de procesamiento es de al menos ɛ. $yo$ ${\ estilo de visualización (t, \ épsilon)}$

Definición 2

Un falsificador es un algoritmo que viola el esquema de firma (Gen, Sign, Verify) si, después de no más de solicitudes al oráculo hash, solicitudes firmadas y tiempo de procesamiento, genera una falsificación de firma con una probabilidad de al menos ɛ . $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon)$ $q_{\text{hash}}$ $q_{\text{sig}}$ $t$

Prueba Sea un falsificador el que rompe la FDH. Asumimos que nunca repite la misma solicitud de oráculo de hash o solicitud de firma. Construyendo un inversor que crackea RSA. El inversor recibe como entrada , donde está la clave pública, y se elige aleatoriamente en (un subconjunto de todos los mensajes con hash). El inversor intenta encontrar de dónde está definida la función RSA . El inversor se inicia para esta clave pública. El falsificador realiza solicitudes de oráculo hash y solicitudes de firma. al recibir una respuesta del oráculo hash, los firma de forma independiente. $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon)$ $F$ $yo$ ${\ estilo de visualización (t', \ épsilon ')}$ $yo$ ${\ estilo de visualización (N, e, y)}$ ${\ estilo de visualización (N, e)}$ $y$ ${\ estilo de visualización \ mathbb {Z} _ {N}}$ $yo$ ${\ estilo de visualización x = f ^ {-1} (y)}$ $F$ ${\ estilo de visualización N, e}$ $yo$ $F$ $F$ $yo$

Para simplificar, asumimos que cuando realiza una solicitud para firmar un mensaje , ya ha realizado la solicitud correspondiente al hash oráculo para . Si no, continuamos e independientemente creamos una solicitud hash-oracle para el mensaje El inversor utiliza un contador que inicialmente se establece en cero. Al consultar el oráculo hash para un mensaje , el inversor incrementa , hace coincidir el mensaje hash con el mensaje original y elige un número aleatorio en . luego regresa con probabilidad y con probabilidad . Aquí hay una probabilidad fija, que se determinará más adelante. Al realizar una solicitud de firma para , ya ha solicitado un hash , por lo que para algunos .If , regresa como una firma. De lo contrario, el proceso se detiene y el inversor falla. $F$ $METRO$ $METRO$ $METRO$ $yo$ $i$ $F$ $METRO$ $yo$ $i$ $M_{i}=M$ $Rhode Island}$ ${\ estilo de visualización \ mathbb {Z} _ {N}}$ $yo$ $h_{i}=r_{i}^{e}modN$ $pags$ $h_{i}=y*r_{i}^{e}modN$ $1 p$ $pags$ $F$ $METRO$ $METRO$ ${\ Displaystyle M = M_ {i}}$ $i$ $h_{i}={r_{i}}^{e}modN$ $yo$ ${\ Displaystyle r_ {i}}$

Al final, termina el trabajo y muestra una falsificación . Suponemos que el hash se solicitó antes. Si no, hace una solicitud al propio oráculo hash, por lo que en cualquier caso para algunos . Entonces, si , obtenemos y sale como el recíproco de . De lo contrario, el proceso se detiene y el inversor falla. $F$ ${\ estilo de visualización (M, x)}$ $F$ $METRO$ $yo$ ${\ Displaystyle M = M_ {i}}$ $i$ $h_{i}=y*{r_{i}}^{e}modN$ $x={h_{i}}^{d}=y^{d}*r_{i}modN$ $yo$ $y^{d}={\frac {x}{r_{i))}modN$ $y$

La probabilidad de que respondamos a todas las solicitudes de firma es al menos . Luego imprime el inverso para con probabilidad . Por lo tanto, con probabilidad al menos , infiere lo contrario para . La función es máxima para y ${\displaystyle p^{q_{\text{sig})))$ $yo$ $y$ $F$ $1 p$ $\alpha (p)=p^{q_{\text{sig))}*(1-p)$ $yo$ $y$ $F$ ${\ estilo de visualización \ alfa (p)}$ $p_{\text{máx}}=1-1/(q_{\text{sig}}+1)$

{\displaystyle \alpha (p_{\text{max)))={\frac {1}{q_{\text{sig))))(1-{\frac {1}{1+q_{\text{ firma))))^{1+q_{\text{firma))))

Por lo tanto obtenemos:

{\begin{alineado}\epsilon (k)&={\frac {1}{\left(1-{\frac {1}{q_{\text{sig}}+1}}\right) ^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{alineado}}

para los grandes $q_{\text{sig}}$

$\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$ .

El tiempo de ejecución es el tiempo de ejecución sumado al tiempo necesario para calcular los valores . Es esencialmente un único cálculo RSA, que es tiempo cúbico (o mejor). Esto da la fórmula para . $yo$ $F$ $hola}$ $t$

Abreviatura final

La calidad de la nueva reducción no depende de la cantidad de llamadas hash realizadas por el falsificador, y depende únicamente de la cantidad de solicitudes de firma. Esto tiene una importancia práctica, ya que en aplicaciones reales el número de llamadas a la función hash está limitado únicamente por la capacidad de procesamiento del falsificador, mientras que el número de solicitudes de firma puede estar limitado: el firmante puede negarse a firmar más de o mensajes. Sin embargo, la reducción aún no es rígida y sigue existiendo una brecha significativa entre la seguridad precisa de FDH y la seguridad precisa de PSS . $2^{20}$ $2^{30}$

En muchas pruebas de seguridad en el modelo aleatorio de Oracle, el inversor tiene que "adivinar" qué consulta hash usará el adversario para falsificar, lo que resulta en un factor en la probabilidad de éxito. Se ha demostrado que el mejor método es incluir una consulta en respuesta a muchas consultas hash para que la falsificación sea más útil para el inversor. Esta observación también se aplica al esquema de firma de Rabin [6] , al esquema de firma de Peye [7] , así como al esquema de firma de Gennaro-Halevi-Rabin [8] , para el cual el coeficiente en la prueba de seguridad aleatoria del oráculo también se puede reducir a . $q_{\text{hash}}$ $y$ $q_{\text{hash}}$ ${\ Displaystyle q_ {sig}}$

Notas

↑ Nuevas direcciones en criptografía . Consultado el 25 de diciembre de 2018. Archivado desde el original el 12 de octubre de 2019. (indefinido)
↑ Un método para obtener firmas digitales y criptosistemas de clave pública . Consultado el 25 de diciembre de 2018. Archivado desde el original el 26 de diciembre de 2018. (indefinido)
↑ Especificaciones de criptografía RSA . Consultado el 25 de diciembre de 2018. Archivado desde el original el 12 de diciembre de 2018. (indefinido)
↑ 1 2 Los oráculos aleatorios son prácticos: un paradigma para diseñar protocolos eficientes . Consultado el 25 de diciembre de 2018. Archivado desde el original el 24 de diciembre de 2018. (indefinido)
↑ La seguridad exacta de las firmas digitales - Cómo firmar con RSA y Rabin . Consultado el 25 de diciembre de 2018. Archivado desde el original el 23 de diciembre de 2018. (indefinido)
↑ Firmas digitalizadas y funciones de clave pública tan intratables como la factorización . Consultado el 25 de diciembre de 2018. Archivado desde el original el 3 de noviembre de 2018. (indefinido)
↑ Sistemas criptográficos de clave pública basados en clases de residuos de grado compuesto. Actas de Eurocrypt'99 . Consultado el 25 de diciembre de 2018. Archivado desde el original el 6 de mayo de 2021. (indefinido)
↑ Firmas seguras de hash y firma sin el oráculo aleatorio, actas de Eurocrypt'99 . Consultado el 25 de diciembre de 2018. Archivado desde el original el 14 de julio de 2012. (indefinido)