SFLASH

SFLASH este un algoritm de semnătură digitală asimetrică recomandat de proiectul european NESSIE în 2003. SFLASH se bazează pe schema Matsumoto-Imai( MI ), numită și C* . Algoritmul aparține unei familii de scheme de chei publice multidimensionale, adică fiecare semnătură și fiecare hash de mesaj este reprezentată de elemente ale câmpului final K. SFLASH a fost conceput pentru aplicații foarte specifice în care costurile algoritmilor clasici ( RSA , Curbe Eliptice , DSA și altele) devin extrem de înalte.: sunt foarte lente și au o dimensiune mare a semnăturii. Așadar, SFLASH a fost creat pentru a răspunde nevoilor de carduri inteligente ieftine.

SFLASH este mult mai rapid și mai ușor decât RSA, atât la crearea, cât și la verificarea (verificarea) unei semnături.

Introducere

Următoarea notație va fi folosită pe parcursul acestui articol:

$\|$ — definește operatorul de concatenare .
$[\lambda]_{r\rightarrow s)$ este un operator definit astfel: , unde , și numerele întregi r și s trebuie să satisfacă: . $[\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$

Parametrii algoritmului

Algoritmul SFLASH utilizează două câmpuri definite:

$K=F_{128}$ definit ca . Definiți ca o bijecție între și K ca: $K=F_{2}[X]/(X^{7}+X+1)$ $\pi$ $\{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)$ . Definiți ca o bijecție între și ca: $\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$ — șir ascuns de 80 de biți.

Algoritmul SFLASH utilizează, de asemenea, două bijecții afine s și t de la la . Fiecare dintre acestea este ascunsă liniară (matricea 67*67) și, respectiv, constantă (coloana 67*1). $K^{67}$ $K^{67}$ $S_{L},T_{L}$ $S_{C},T_{C}$

Deschide Opțiuni

Cheia publică se află în funcția G de la până la definită ca: $K^{67}$ $K^{56}$ $G(X)=[t(\varphi ^{-1}(F(\varphi (s(X)))))]_{0\rightarrow 391)$

F este o funcție de la până la definită ca $\Phi$ $\Phi$ $\forall A\in \Phi ,F(A)=A^{128^{33}+1}$

Generare cheie

Fie next_7bit_random_string un șir de 7 biți, care este generat prin apelarea CSPRBG (Cryptographically Secure PseudoRandom Bit Generator) de 7 ori. Mai întâi obținem primul bit de sfoară, apoi al doilea și așa mai departe până la al șaptelea.

1) Noi generăm

S_L

Două metode pot fi utilizate pentru a genera o matrice inversată 67x67 :

S_L

Vom umple matricea câte un element până când umplem întreaga matrice:

pentru i=0 până la 66 pentru j=0 până la 66 S_L[i,j]=pi(next_7bit_random_string)

Folosim descompunerea LU , unde este matricea triunghiulară inferioară 67x67 și matricea triunghiulară superioară 67x67. După găsirea matricelor și , determinăm : $L_{S)$ $U_{S}$ $L_{S)$ $U_{S}$ $S_{L}=L_{S}\times U_{S}.$

pentru i=0 până la 66 pentru j=0 până la 66 { dacă (i<j) atunci {U_S[i,j]=pi(next_7bit_random_string); L_S[i,j]=0;}; dacă (i>j) atunci {L_S[i,j]=pi(next_7bit_random_string); U_S[i,j]=0;}; dacă (i=j) atunci {repeat (z=next_7bit_random_string) până la z!=(0,0,0,0,0,0,0); U_S[i,j]=pi(z); L_S[i,j]=1;}; }; 2) Noi generăm

S_{C}

Utilizați CSPRBG pentru a găsi noile 67 de elemente ale lui K (din partea de sus până în jos a coloanei matricei). Fiecare element al lui K se găsește folosind funcția:

$\pi$ (next_7bit_random_string)

3) Noi generăm

T_{L}

La fel ca și matricea .

S_L

4) Noi generăm

T_{C}

La fel ca și coloana .

S_{C}

5) Noi generăm

\Delta

Folosind CSPRBG (Cryptographically Secure PseudoRandom Bit Generator) generăm 80 de biți aleatori.

Crearea unei semnături

Fie M mesajul nostru pentru care dorim să găsim o semnătură S. Crearea unei semnături S are următorul algoritm:

1) Fie - acestea sunt șiruri determinate folosind algoritmul de hashing criptografic 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) Găsiți șir V - 392 de biți ca:

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

3) Găsiți W - șir de 77 de biți ca:

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

4) Găsiți Y - un șir de 56 K elemente ca:

Y=(\pi ([V]_{0\rightarrow 6}),\pi ([V]_{7\rightarrow 13}),...,\pi ([V]_{385\ săgeată la dreapta 391}))

5) Găsiți R - un șir de 11 K elemente ca:

R=(\pi ([W]_{0\rightarrow 6}),\pi ([W]_{7\rightarrow 13}),...,\pi ([W]_{70\ săgeată dreapta 76))

6) Găsiți B - element ca: $\Phi$

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

7) Găsiți A - element ca: $\Phi$

A=F^{-1}(B)

, unde F este o funcție de la până la definită ca:

\Phi

\Phi

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

8) Găsiți - linia 67 elemente K: $X=(X_{0},...,X_{66})$

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

9) Semnătura S - șir de 469 de biți obținut ca:

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

Verificarea (verificarea) semnăturii

Dat un mesaj M (șir de biți) și o semnătură S (șir de 256 de biți). Următorul algoritm este utilizat pentru a determina validitatea semnăturii S a mesajului M:

1) Fie - acestea sunt șiruri determinate folosind algoritmul de hashing criptografic 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) Găsiți șir V - 392 de biți ca:

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

3) Găsiți Y - un șir de 56 K elemente ca:

Y=(\pi ([V]_{0\rightarrow 6}),\pi ([V]_{7\rightarrow 13}),...,\pi ([V]_{385\ săgeată la dreapta 391}))

4) Găsiți Y' - un șir de 56 K elemente ca:

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

5) Comparați șirurile rezultate Y și Y'. Dacă sunt egale, atunci semnătura este acceptată, în caz contrar este respinsă.

Literatură

Nicolas T. Courtois, Louis Goubin și Jacques Patarin. SFLASHv3, o schemă rapidă de semnătură asimetrică, 2003" Arhivat 13 iulie 2007 la Wayback Machine , specificația algoritmului de la dezvoltatori
„Vivien Dubois, Pierre-Alain Fouque, Adi Shamir and Jacques Stern, Practical Cryptanalysis of SFLASH” Arhivat 7 iunie 2011 la Wayback Machine , o descriere a atacurilor actuale asupra SFLASH

Link -uri

Criptografia multidimensională (criptografie multivariată)