VSH

En criptografía , un hash muy suave (VSH) es una función hash criptográfica eficiente de n bits desarrollada en 2005 por Scott Kotini, Lestra Arjen y Ron Steinfeld. Es resistente a las colisiones bajo el supuesto de una alta complejidad computacional para encontrar una raíz cuadrada no trivial de un módulo de número muy suave . [1] El concepto de una función muy suave significa que el límite de suavidad es una función polinomial fija de n. Este algoritmo hash supone una sola multiplicación por bit de mensaje y utiliza aritmética de tipo RSA , lo que elimina la necesidad de almacenar el código de función hash por separado. Por lo tanto, este algoritmo es útil en entornos integrados donde el espacio de código es limitado. También se puede usar una función hash muy fluida para crear una función de entrada secreta unidireccional que se puede aplicar en esquemas de firma para acelerar la verificación y mejorar la privacidad. $\ omega (n)$

VSSR y VSN

Para VSH, el principal problema matemático es la resistencia a la colisión, que consiste esencialmente en sacar raíces módulo n de números muy suaves, llamados raíces muy suaves (VSSR). A su vez, el problema de calcular un módulo de raíz muy suave está estrechamente relacionado con la factorización de números enteros utilizando el método de tamiz de campo numérico general . [2] [3]

Para constantes fijas c y n , un entero m se llama un número muy suave si todos los factores primos de m son como máximo (log n ) c . Un entero b es un módulo n cuadrático muy suave si el factor primo más grande b es como máximo (log n ) c y existe un entero x tal que . El entero x se llama raíz muy cuadrada módulo b . $b\equiv x^{2}\mod n$

Solo nos interesan las raíces donde x 2 ≥ n . Ya que, si x 2 < n , entonces la raíz se puede calcular fácilmente usando un campo de característica 0. Calcular una raíz muy suave es el siguiente problema: sea n el producto de dos números primos de aproximadamente el mismo tamaño y sea , y Sea una secuencia de números primos. Dado n , es necesario encontrar , tal que al menos uno de e 0 ,…, e k sea impar. ${\displaystyle k\leq (\log n)^{c))$ $p_{1}=2,p_{2}=3,p_{3}=5,\puntos$ $x\in \mathbb {Z} _{n}^{*}$ $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i))$

Ejemplo de VSN y VSSR

Que se fijen los siguientes parámetros: y . $c=5$ ${\ estilo de visualización n = 31}$

Luego , un número muy suave de los parámetros dados, porque es mayor que todos los factores primos . Por otro lado, no es un número muy suave en y . $m_{1}=35=5\cdot 7$ ${\ estilo de visualización (\ registro 31) ^ {5} ~ {\ punto {=}} ~ 7,37}$ $m_1$ $m_{2}=55=5\cdot 11$ $c=5$ ${\ estilo de visualización n = 31}$

Un entero es un módulo cuadrático muy suave porque es muy suave (de ) y existe tal que (mod ). Esta es una raíz cuadrada trivial porque , por lo tanto, el módulo no se tiene en cuenta al elevar al cuadrado. ${\ estilo de visualización b_ {1} = 9}$ $norte$ ${\ estilo de visualización c, n}$ ${\ estilo de visualización x_ {1} = 3}$ ${\ estilo de visualización x_{1}^{2}=b_{1}}$ $norte$ ${\ estilo de visualización 3 ^ {2} \ no \ geq n}$

Un número entero también es un resto de módulo cuadrático . Todos los factores primos son menores que 7.37, y todos los módulos de raíces cuadradas son iguales , ya que (mod ). La tarea de VSSR es encontrar por datos y . Y computacionalmente tan difícil como la factorización . ${\ estilo de visualización b_ {2} = 15}$ $norte$ ${\ estilo de visualización x_ {2} = 20}$ ${\ estilo de visualización 20 ^ {2} = 400 \ equivalente a 15}$ $norte$ $x_{2}$ $b_{2}$ $norte$ $norte$

VSH, algoritmo básico

Sea una secuencia de números primos. Sea la longitud del bloque, el entero más grande, tal que . Deje que haya un mensaje de bits que consista en , que debe tener un hash, con .Para calcular el hash [4] : $p_{1}=2,p_{2}=3,\ldots$ $k$ $\textstyle \prod _{i=1}^{k}p_{i}<n$ $metro$ $\ana$ $(m_{1},\ldots,m_{\ell })$ ${\ estilo de visualización \ ell <2^{k))$ $metro$

x0 = 1
Sea el entero más pequeño mayor o igual que el número de bloques. dejar por $L$ ${\ estilo de visualización l/k}$ $m_{i}=0$ $l<i\leq Lk$
Sea c una representación binaria de un mensaje de longitud y defina para . $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ $\ell _{i}\in \{0,1\}$ $\ana$ ${\displaystyle m_{Lk+i}=\ell _{i))$ ${\ estilo de visualización 1 \ leq i \ leq k}$
para cada j = 0, 1,…, L calculamos $x_{j+1}=x_{j}^{2}\prod_{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$
retorno x L + 1 .

La función del paso 4 se denomina función de compresión.

Propiedades VSH

No necesita saber la longitud del mensaje de antemano.
La complejidad de la detección de colisiones es igual a la complejidad de encontrar una raíz muy suave, por lo que VSH es resistente a colisiones. La resistencia a colisiones es la única propiedad comprobada de VSH. [5] [6]
La función de compresión no es resistente a colisiones. Sin embargo, la función hash es resistente a colisiones según la suposición VSSR. La próxima versión de VSH* usa compresión resistente a colisiones y es 5 veces más rápida en mensajes cortos. [7]
VSH es multiplicativo:

Sean x, y y z cadenas de tres bits de igual longitud, donde z consiste solo en cero bits y satisface x Y y = z. Entonces H(z)H(x O y) ≡ H(x)H(y) (mod n). VSH es inferior al clásico ataque de almacenamiento temporal que se aplica a hashes multiplicativos y aditivos. [ocho]

Variaciones VSH

Se han propuesto varias mejoras, aceleraciones y variantes más eficientes de VSH [9] . Ninguno de ellos cambia el concepto básico de la función:

VSH cúbico (en lugar de cuadrático).
VSH con un aumento en el número de números primos.
VSH con producto calculado de números primos.
VSH rápido.
VSH rápido con mayor número de bloques.
VSH-DL

VSH-DL - Logaritmo discreto VSH que no tiene una función de entrada secreta unidireccional , su seguridad depende de la dificultad de encontrar el logaritmo discreto módulo a número primo p .

El logaritmo discreto de número muy suave (VSDL) es el logaritmo discreto de algún VSN módulo algún número n .

De manera similar a la notación presentada anteriormente, tomamos como el -ésimo número primo. Sean una constante fija y , sean números primos tales que y . Problema VSDL: dado para encontrar números enteros tales que , donde para todos , además, al menos uno de ellos es distinto de cero. $Pi}$ $i$ $C$ $pags$ $q$ ${\ estilo de visualización p = 2q + 1}$ ${\displaystyle k\leq (\log p)^{c))$ $pags$ ${\displaystyle e_{1},...,e_{k))$ $2^{e_{1}}\equiv \prod_{i=2}^{k}p_{i}^{e_{i}}\mod p$ $|e_{i}|<q$ ${\ estilo de visualización i = 1,..., k}$ ${\displaystyle e_{1},...,e_{k))$

La suposición de VSDL es que no existe un algoritmo probabilístico de tiempo polinomial que resuelva VSDL. Existe una estrecha relación entre la complejidad de calcular un VSDL y la complejidad de calcular un logaritmo módulo discreto . $pags$

Véase también

Notas

↑ S.Contini, A.Lestra, R.Steinfield. VSH, una función hash resistente a colisiones eficiente y demostrable. // Eurocripta. - 2006. - S. 1-2 . Archivado desde el original el 4 de diciembre de 2018.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, una función hash resistente a colisiones eficiente y demostrable. // Eurocripta. - 2006. - S. 3 . Archivado desde el original el 4 de diciembre de 2018.
↑ Bart Preneel. [ https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf Los primeros 30 años de funciones hash criptográficas y la competencia NIST SHA-3] // Pista de criptógrafos en la Conferencia RSA. - 2010. - S. 5 . Archivado desde el original el 11 de agosto de 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, una función hash resistente a colisiones eficiente y demostrable. // Eurocripta. - 2006. - S. 6 . Archivado desde el original el 4 de diciembre de 2018.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, una función hash resistente a colisiones eficiente y demostrable. // Eurocripta. - 2006. - S. 8 . Archivado desde el original el 4 de diciembre de 2018.
↑ M.-JOSaarinen. Seguridad de VSH en el mundo real // INDOCRYPT. - 2006. - S. 2 . Archivado desde el original el 8 de agosto de 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, una función hash resistente a colisiones eficiente y demostrable. // Eurocripta. - 2006. - S. 14 . Archivado desde el original el 4 de diciembre de 2018.
↑ M.-JOSaarinen. Seguridad de VSH en el mundo real // INDOCRYPT. - 2006. - S. 3-4 . Archivado desde el original el 8 de agosto de 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, una función hash resistente a colisiones eficiente y demostrable. // Eurocripta. - 2006. - S. 10-13 . Archivado desde el original el 4 de diciembre de 2018.

Literatura

S.Contini, A.Lestra, R.Steinfield. VSH, una función hash resistente a colisiones eficiente y demostrable. // Eurocripta. - 2006. - S. 1-13 .
M.-JOSaarinen. Seguridad de VSH en el mundo real // INDOCRYPT. — 2006.
Bart Preneel. [ https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf Los primeros 30 años del hash criptográfico

Funciones y la competencia NIST SHA-3] // Pista de criptógrafos en la Conferencia RSA. - 2010. - S. 5 . Archivado desde el original el 11 de agosto de 2017.