SFLASH

Az SFLASH egy aszimmetrikus digitális aláírási algoritmus , amelyet a NESSIE európai projekt ajánlott 2003-ban. A SFLASH a Matsumoto-Imai( MI ) sémán alapul, amelyet C* -nak is neveznek . Az algoritmus többdimenziós nyilvános kulcssémák családjába tartozik, azaz minden aláírást és üzenetkivonatot a végső K mező elemei képviselnek. Az SFLASH-t nagyon specifikus alkalmazásokhoz tervezték, ahol a klasszikus algoritmusok költségei ( RSA , Elliptic Curves , DSA és mások) rendkívül magasak lesznek. : nagyon lassúak és nagy aláírásmérettel rendelkeznek. A SFLASH tehát az olcsó intelligens kártyák igényeinek kielégítésére jött létre.

Az SFLASH sokkal gyorsabb és egyszerűbb, mint az RSA, mind az aláírás létrehozásában, mind pedig ellenőrzésében (ellenőrzésében).

Bevezetés

A cikkben a következő jelöléseket használjuk:

$\|$ — meghatározza az összefűzési operátort .
${\displaystyle [\lambda ]_{r\rightarrow s))$ a következőképpen definiált operátor: , ahol , valamint az r és s egész számoknak teljesíteniük kell: . $[\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$

Algoritmus paraméterei

Az SFLASH algoritmus két meghatározott mezőt használ:

$K=F_{128}$ ként határozzuk meg . Határozza meg bijekcióként és K között : $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)$ . Határozza meg bijekcióként és között : $\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 bites rejtett karakterlánc.

Az SFLASH algoritmus két affin bijekciót is használ: s és t tól -ig . Mindegyik rejtett lineáris (67*67 mátrix) és konstans (67*1 oszlop). $K^{67}$ $K^{67}$ $S_{L},T_{L}$ $S_{C},T_{C}$

Nyissa meg az Options

A nyilvános kulcs a G from to függvényben található, a következőképpen definiálva: $K^{67}$ $K^{56}$ ${\displaystyle G(X)=[t(\varphi ^{-1}(F(\varphi (s(X)))))]_{0\jobbra 391))$

F egy függvény től ig definiálva $\Phi$ $\Phi$ $\forall A\in \Phi ,F(A)=A^{128^{33}+1}$

Kulcsgenerálás

Legyen next_7bit_random_string egy 7 bites karakterlánc, amely a CSPRBG (Cryptographically Secure PseudoRandom Bit Generator) hétszeri meghívásával jön létre. Először megkapjuk a húr első bitjét, majd a másodikat, és így tovább a hetedikig.

1) generálunk

S_L

Két módszer használható egy fordított 67x67-es mátrix létrehozására :

S_L

A mátrixot elemenként töltjük ki, amíg ki nem töltjük a teljes mátrixot:

i=0-tól 66-ig j=0 és 66 között S_L[i,j]=pi(következő_7 bites_random_karakterlánc)

Az LU dekompozíciót használjuk , ahol az alsó háromszögmátrix 67x67, a felső háromszögmátrix pedig 67x67. Miután megtaláltuk a és mátrixokat , meghatározzuk : ${\displaystyle L_{S))$ $U_{S}$ ${\displaystyle L_{S))$ $U_{S}$ $S_{L}=L_{S}\times U_{S}.$

i=0 és 66 között j=0 és 66 között { ha (i<j) akkor {U_S[i,j]=pi(next_7bit_random_string); L_S[i,j]=0;}; ha (i>j) akkor {L_S[i,j]=pi(next_7bit_random_string); U_S[i,j]=0;}; ha (i=j) akkor {ismétlés (z=next_7bit_random_string) amíg z!=(0,0,0,0,0,0,0); U_S[i,j]=pi(z); L_S[i,j]=1;}; }; 2) generálunk

S_{C}

A CSPRBG segítségével keresse meg a K új 67 elemét (a mátrixoszlop tetejétől az aljáig). A K minden eleme megtalálható a következő függvény segítségével:

$\pi$ (next_7bit_random_string)

3) generálunk

T_{L}

Ugyanaz, mint a mátrix .

S_L

4) Generálunk

T_{C}

Ugyanaz, mint az oszlop .

S_{C}

5) Generálunk

\Delta

A CSPRBG (Cryptographically Secure PseudoRandom Bit Generator) segítségével 80 véletlenszerű bitet generálunk.

Aláírás létrehozása

Legyen M az üzenetünk, amelyhez S aláírást szeretnénk találni. Az S aláírás létrehozása a következő algoritmussal rendelkezik:

1) Legyen - ezek az SHA-1 kriptográfiai kivonatoló algoritmussal meghatározott karakterláncok : ${\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) Keresse meg a V - 392 bites karakterláncot a következőképpen:

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

3) Keresse meg a W - 77 bites karakterláncot a következőképpen:

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

4) Keresse meg Y - 56 K elemből álló sztringet a következőképpen:

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

5) Keresse meg az R-t – egy 11 K elemből álló sztringet a következőképpen:

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

6) Keresse meg a B elemet : $\Phi$

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

7) Keresse meg az A - elemet : $\Phi$

A=F^{-1}(B)

, ahol F egy -től -ig terjedő függvény, amely a következőképpen definiálható:

\Phi

\Phi

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

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

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

9) Aláírás S – 469 bites karakterlánc a következőképpen lett beszerezve:

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

Az aláírás ellenőrzése (ellenőrzése)

Adott egy M üzenet (bit karakterlánc) és egy S aláírás (256 bites karakterlánc). A következő algoritmust használjuk az M üzenet S aláírásának érvényességének meghatározására:

1) Legyen - ezek az SHA-1 kriptográfiai kivonatoló algoritmussal meghatározott karakterláncok : ${\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) Keresse meg a V - 392 bites karakterláncot a következőképpen:

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

3) Keresse meg Y - 56 K elemből álló sztringet a következőképpen:

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

4) Keresse meg az Y'-t – egy 56 K elemből álló sztringet:

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

5) Hasonlítsa össze a kapott Y és Y' karakterláncokat. Ha megegyeznek, akkor az aláírást elfogadják, ellenkező esetben elutasítják.

Irodalom

Nicolas T. Courtois, Louis Goubin és Jacques Patarin. SFLASHv3, egy gyors aszimmetrikus aláírási séma, 2003" Archiválva : 2007. július 13. a Wayback Machine -nél , Algoritmusspecifikáció a fejlesztőktől
"Vivien Dubois, Pierre-Alain Fouque, Adi Shamir és Jacques Stern, az SFLASH gyakorlati kriptanalízise" Archiválva 2011. június 7-én a Wayback Machine -nél, az SFLASH elleni jelenlegi támadások leírása

Linkek

Többdimenziós kriptográfia (Multivariate cryptography)