FLASH

SFLASH es un algoritmo de firma digital asimétrica recomendado por el proyecto europeo NESSIE en 2003. SFLASH se basa en el esquema Matsumoto-Imai( MI ), también llamado C* . El algoritmo pertenece a una familia de esquemas de clave pública multidimensional, es decir, cada firma y cada hash de mensaje está representado por elementos del campo final K. SFLASH fue diseñado para aplicaciones muy específicas donde los costos de los algoritmos clásicos ( RSA , Elliptic Curves , DSA y otros) se vuelven extremadamente altos. : son muy lentos y tienen un tamaño de firma grande. Entonces SFLASH fue creado para satisfacer las necesidades de las tarjetas inteligentes económicas.

SFLASH es mucho más rápido y sencillo que RSA, tanto a la hora de crear como de verificar (verificar) una firma.

Introducción

La siguiente notación se utilizará a lo largo de este artículo:

$\|$ — define el operador de concatenación .
${\ estilo de visualización [\ lambda] _ {r \ flecha derecha s))$ es un operador definido como sigue: , donde , y los enteros r y s deben satisfacer: . $[\lambda ]_{r\rightarrow s}=(\lambda_{r},\lambda_{r+1},...,\lambda_{s-1},\lambda_{s })$ ${\ estilo de visualización \ lambda = (\ lambda _ {1},..., \ lambda _ {m})}$ ${\ estilo de visualización 0 \ leq r \ leq s \ leq m}$

Parámetros del algoritmo

El algoritmo SFLASH utiliza dos campos definidos:

$K=F_{128}$ definido como . Definir como una biyección entre y K como: $K=F_{2}[X]/(X^{7}+X+1)$ $\Pi$ ${\ estilo de visualización \ {0,1 \} ^ {7}}$ $\forall b=(b_{0},...,b_{6})\in \{0,1\}^{7},\pi (b)=(b_{6}X^{ 6}+...+b_{1}X+b_{0})\mod X^{7}+X+1$
$\Phi =K[X]/(x^{67}+X^{5}+X^{2}+X+1)$ . Definir como una biyección entre y como: $\varphi$ $K^{67}$ $\Fi$ $\forall \omega =(\omega _{0},...,\omega _{66})\in K^{67},\varphi (\omega)=(\omega _{66}X ^{66}+...+\omega _{1}X+\omega _{0})\mod X^{67}+X^{5}+X^{2}+X+1$
$\Delta$ — Cadena oculta de 80 bits.

El algoritmo SFLASH también usa dos biyecciones afines s y t de a . Cada uno de los cuales es lineal oculto (matriz 67*67) y constante (columna 67*1), respectivamente. $K^{67}$ $K^{67}$ ${\ estilo de visualización S_ {L}, T_ {L}}$ $S_{C},T_{C}$

Opciones abiertas

La clave pública reside en la función G from to definida como: $K^{67}$ $K^{56}$ ${\displaystyle G(X)=[t(\varphi ^{-1}(F(\varphi (s(X)))))]_{0\rightarrow 391))$

F es una función de a definida como $\Fi$ $\Fi$ $\forall A\en \Phi,F(A)=A^{128^{33}+1}$

Generación de claves

Deje que next_7bit_random_string sea una cadena de 7 bits, que se genera llamando a CSPRBG (Generador de bits pseudoaleatorios criptográficamente seguros) 7 veces. Primero obtenemos el primer bit de la cadena, luego el segundo, y así hasta el séptimo.

1) Generamos

S_L

Se pueden utilizar dos métodos para generar una matriz invertida de 67x67 :

S_L

Llenaremos la matriz un elemento a la vez hasta llenar toda la matriz:

para i=0 a 66 para j=0 a 66 S_L[i,j]=pi(next_7bit_random_string)

Usamos la descomposición LU , donde la matriz triangular inferior es 67x67 y la matriz triangular superior 67x67. Después de encontrar las matrices y , determinamos : ${\ estilo de visualización L_ {S}}$ $U_{S}$ ${\ estilo de visualización L_ {S}}$ $U_{S}$ $S_{L}=L_{S}\veces U_{S}.$

para i=0 a 66 para j=0 a 66 { si (i<j) entonces {U_S[i,j]=pi(next_7bit_random_string); L_S[i,j]=0;}; si (i > j) entonces {L_S[i,j]=pi(next_7bit_random_string); U_S[i,j]=0;}; si (i=j) entonces {repetir (z=next_7bit_random_string) hasta z!=(0,0,0,0,0,0,0); U_S[i,j]=pi(z); L_S[i,j]=1;}; }; 2) Generamos

{\ estilo de visualización S_ {C}}

Use CSPRBG para encontrar los nuevos 67 elementos de K (desde la parte superior hasta la parte inferior de la columna de la matriz). Cada elemento de K se encuentra usando la función:

$\Pi$ (next_7bit_random_string)

3) Generamos

{\ estilo de visualización T_ {L}}

Igual que la matriz .

S_L

4) Generamos

T_{C}

Igual que la columna .

{\ estilo de visualización S_ {C}}

5) Generamos

\Delta

Usando CSPRBG (Generador de bits pseudoaleatorios criptográficamente seguros) generamos 80 bits aleatorios.

Creación de una firma

Sea M nuestro mensaje para el que queremos encontrar una firma S. La creación de una firma S tiene el siguiente algoritmo:

1) Let - estas son cadenas determinadas usando el algoritmo hash criptográfico SHA-1 : ${\displaystyle M_{0},M_{1},M_{2},M_{3))$

M_{0}=SHA-1(M)

M_{1}=SHA-1(M_{0}\|0x00)

M_{2}=SHA-1(M_{0}\|0x01)

M_{3}=SHA-1(M_{0}\|0x02)

2) Encuentre V - Cadena de 392 bits como:

{\displaystyle V=[M_{1}]_{0\rightarrow 159}\|[M_{2}]_{0\rightarrow 159}\|[M_{3}]_{0\rightarrow 71))

3) Encuentra W - Cadena de 77 bits como:

{\displaystyle W=[SHA-1(V\|\Delta )]_{0\rightarrow 76))

4) Encuentra Y - una cadena de 56 K elementos como:

Y=(\pi ([V]_{0\rightarrow 6}),\pi ([V]_{7\rightarrow 13}),...,\pi ([V]_{385\ flecha derecha 391}))

5) Encuentra R - una cadena de 11 K elementos como:

R=(\pi ([W]_{0\rightarrow 6}),\pi ([W]_{7\rightarrow 13}),...,\pi ([W]_{70\ flecha derecha 76))

6) Encuentra B - elemento como: $\Fi$

B=\varphi (t^{-1}(Y\|R))

7) Encuentra un elemento A como: $\Fi$

{\ estilo de visualización A = F ^ {-1} (B)}

, donde F es una función de a definida como:

\Fi

\Fi

\forall A\en \Phi,F(A)=A^{128^{33}+1}

8) Buscar - línea 67 elementos K: ${\ estilo de visualización X = (X_{0},...,X_{66})}$

X=(X_{0},...,X_{66})=s^{-1}(\varphi^{-1}(A))

9) Firma S - Cadena de 469 bits obtenida como:

S=\pi ^{-1}(X_{0})\|...\|\pi ^{-1}(X_{66})

Verificación (verificación) de la firma

Dado un mensaje M (cadena de bits) y una firma S (cadena de 256 bits). El siguiente algoritmo se utiliza para determinar la validez de la firma S del mensaje M:

1) Let - estas son cadenas determinadas usando el algoritmo hash criptográfico SHA-1 : ${\displaystyle M_{0},M_{1},M_{2},M_{3))$

M_{0}=SHA-1(M)

M_{1}=SHA-1(M_{0}\|0x00)

M_{2}=SHA-1(M_{0}\|0x01)

M_{3}=SHA-1(M_{0}\|0x02)

2) Encuentre V - Cadena de 392 bits como:

{\displaystyle V=[M_{1}]_{0\rightarrow 159}\|[M_{2}]_{0\rightarrow 159}\|[M_{3}]_{0\rightarrow 71))

3) Encuentra Y - una cadena de 56 K elementos como:

Y=(\pi ([V]_{0\rightarrow 6}),\pi ([V]_{7\rightarrow 13}),...,\pi ([V]_{385\ flecha derecha 391}))

4) Encuentra Y' - una cadena de 56 K elementos como:

Y'=G(\pi ([S]_{0\rightarrow 6}),\pi ([S]_{7\rightarrow 13}),...,\pi ([S]_{ 385\flecha derecha 391}))

5) Compare las cadenas resultantes Y e Y'. Si son iguales, se acepta la firma, en caso contrario se rechaza.

Literatura

Nicolás T. Courtois, Louis Goubin y Jacques Patarin. SFLASHv3, un esquema de firma asimétrico rápido, 2003 " . Archivado el 13 de julio de 2007 en Wayback Machine , especificación de algoritmo de los desarrolladores
"Vivien Dubois, Pierre-Alain Fouque, Adi Shamir y Jacques Stern, Practical Cryptanalysis of SFLASH" Archivado el 7 de junio de 2011 en Wayback Machine , una descripción de los ataques actuales a SFLASH

Enlaces

Criptografía multidimensional (criptografía multivariante)