SLASH

SFLASH er en asymmetrisk digital signaturalgoritme anbefalet af det europæiske NESSIE-projekt i 2003. SFLASH er baseret på Matsumoto-Imai( MI )-skemaet, også kaldet C* . Algoritmen tilhører en familie af multidimensionelle offentlige nøgleskemaer, dvs. hver signatur og hver meddelelseshash er repræsenteret af elementer i det endelige felt K. SFLASH blev designet til meget specifikke applikationer, hvor omkostningerne ved klassiske algoritmer ( RSA , Elliptic Curves , DSA og andre) bliver ekstremt høje. : de er meget langsomme og har en stor signaturstørrelse. Så SFLASH blev skabt for at imødekomme behovene for billige smartkort.

SFLASH er meget hurtigere og nemmere end RSA, både til at skabe og til at verificere (verificere) en signatur.

Introduktion

Følgende notation vil blive brugt i hele denne artikel:

$\|$ — definerer sammenkædningsoperatoren .
${\displaystyle [\lambda ]_{r\rightarrow s))$ er en operator defineret som følger: , hvor , og heltal r og s skal opfylde: . $[\lambda ]_{r\rightarrow s}=(\lambda _{r},\lambda _{r+1},...,\lambda _{s-1},\lambda _{s })$ $\lambda =(\lambda _{1},...,\lambda _{m})$ $0\leq r\leq s\leq m$

Algoritmeparametre

SFLASH-algoritmen bruger to specifikke felter:

$K=F_{128}$ defineret som . Definer som en bijektion mellem og K som: $K=F_{2}[X]/(X^{7}+X+1)$ $\pi$ ${\displaystyle \{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)$ . Definer som en bijektion mellem og som: $\varphi$ $K^{67}$ $\Phi$ $\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$ — 80 bit skjult streng.

SFLASH-algoritmen bruger også to affine bijektioner s og t fra til . Hver af dem er skjult lineær (matrix 67*67) og konstant (kolonne 67*1). $K^{67}$ $K^{67}$ $S_{L},T_{L}$ $S_{C},T_{C}$

Åbn indstillinger

Den offentlige nøgle ligger i funktionen G fra til defineret som: $K^{67}$ $K^{56}$ ${\displaystyle G(X)=[t(\varphi ^{-1}(F(\varphi (s(X)))))]_{0\rightarrow 391))$

F er en funktion fra til defineret som $\Phi$ $\Phi$ $\forall A\in \Phi ,F(A)=A^{128^{33}+1}$

Nøglegenerering

Lad next_7bit_random_string være en 7-bit streng, som genereres ved at kalde CSPRBG(Cryptographically Secure PseudoRandom Bit Generator) 7 gange. Først får vi den første bit af strengen, derefter den anden og så videre indtil den syvende.

1) Vi genererer

S_L

To metoder kan bruges til at generere en inverteret 67x67 matrix :

S_L

Vi udfylder matricen ét element ad gangen, indtil vi udfylder hele matrixen:

for i=0 til 66 for j=0 til 66 S_L[i,j]=pi(next_7bit_random_string)

Vi bruger LU-dekomponeringen , hvor den nederste trekantede matrix er 67x67, og den øverste trekantede matrix er 67x67. Efter at have fundet matricerne og bestemmer vi : ${\displaystyle L_{S))$ $U_{S}$ ${\displaystyle L_{S))$ $U_{S}$ $S_{L}=L_{S}\ gange U_{S}.$

for i=0 til 66 for j=0 til 66 { hvis (i<j) da {U_S[i,j]=pi(next_7bit_random_string); L_S[i,j]=0;}; hvis (i>j) da {L_S[i,j]=pi(next_7bit_random_string); U_S[i,j]=0;}; hvis (i=j) så {gentag (z=next_7bit_random_string) indtil z!=(0,0,0,0,0,0,0); U_S[i,j]=pi(z); L_S[i,j]=1;}; }; 2) Vi genererer

S_{C}

Brug CSPRBG til at finde de nye 67 elementer i K (fra toppen til bunden af matrixkolonnen). Hvert element i K findes ved hjælp af funktionen:

$\pi$ (næste_7bit_tilfældig_streng)

3) Vi genererer

T_{L}

Samme som matrixen .

S_L

4) Vi genererer

T_{C}

Samme som kolonnen .

S_{C}

5) Vi genererer

\Delta

Ved at bruge CSPRBG (Cryptographically Secure PseudoRandom Bit Generator) genererer vi 80 tilfældige bits.

Oprettelse af en signatur

Lad M være vores budskab, som vi ønsker at finde en signatur S for. Oprettelse af en signatur S har følgende algoritme:

1) Lad - disse er strenge bestemt ved hjælp af den kryptografiske hashing-algoritme 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) Find V - 392 bit streng som:

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

3) Find W - 77 bit streng som:

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

4) Find Y - en streng med 56 K elementer som:

Y=(\pi ([V]_{0\højrepil 6}),\pi ([V]_{7\højrepil 13}),...,\pi ([V]_{385\ højrepil 391}))

5) Find R - en streng med 11 K elementer som:

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

6) Find B - element som: $\Phi$

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

7) Find A - element som: $\Phi$

A=F^{-1}(B)

, hvor F er en funktion fra til defineret som:

\Phi

\Phi

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

8) Find - linje 67 elementer K: $X=(X_{0},...,X_{66})$

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

9) Signatur S - 469 bit streng opnået som:

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

Verifikation (verifikation) af signaturen

Givet en besked M (streng af bit) og en signatur S (256-bit streng). Følgende algoritme bruges til at bestemme gyldigheden af signaturen S af beskeden M:

1) Lad - disse er strenge bestemt ved hjælp af den kryptografiske hashing-algoritme 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) Find V - 392 bit streng som:

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

3) Find Y - en streng med 56 K elementer som:

Y=(\pi ([V]_{0\højrepil 6}),\pi ([V]_{7\højrepil 13}),...,\pi ([V]_{385\ højrepil 391}))

4) Find Y' - en streng med 56 K elementer som:

Y'=G(\pi ([S]_{0\højrepil 6}),\pi ([S]_{7\højrepil 13}),...,\pi ([S]_{ 385\højrepil 391}))

5) Sammenlign de resulterende strenge Y og Y'. Hvis de er lige, så accepteres underskriften, ellers afvises den.

Litteratur

Nicolas T. Courtois, Louis Goubin og Jacques Patarin. SFLASHv3, et hurtigt asymmetrisk signaturskema, 2003" Arkiveret 13. juli 2007 på Wayback Machine , Algoritmespecifikation fra udviklere
"Vivien Dubois, Pierre-Alain Fouque, Adi Shamir og Jacques Stern, Practical Cryptanalysis of SFLASH" Arkiveret 7. juni 2011 på Wayback Machine , en beskrivelse af aktuelle angreb på SFLASH