SFLASH

SFLASH on epäsymmetrinen digitaalinen allekirjoitusalgoritmi , jota NESSIE-eurooppalainen projekti suositteli vuonna 2003. SFLASH perustuu Matsumoto-Imai( MI ) -malliin, jota kutsutaan myös C* :ksi . Algoritmi kuuluu moniulotteisten julkisten avainten skeemojen perheeseen, eli jokaista allekirjoitusta ja jokaista viestin hajautusarvoa edustavat viimeisen kentän K elementit. SFLASH on suunniteltu hyvin erityisiin sovelluksiin, joissa klassisten algoritmien ( RSA , Elliptic Curves , DSA ja muut) muuttuvat erittäin korkeiksi. : ne ovat erittäin hitaita ja niillä on suuri allekirjoituskoko. Joten SFLASH luotiin täyttämään halpojen älykorttien tarpeet.

SFLASH on paljon nopeampi ja helpompi kuin RSA sekä allekirjoituksen luomisessa että varmentamisessa.

Johdanto

Tässä artikkelissa käytetään seuraavaa merkintää:

$\|$ — määrittää ketjutusoperaattorin .
${\displaystyle [\lambda ]_{r\rightarrow s))$ on operaattori, joka määritellään seuraavasti: , jossa , ja kokonaislukujen r ja s on täytettävä: . $[\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$

Algoritmin parametrit

SFLASH-algoritmi käyttää kahta määriteltyä kenttää:

$K=F_{128}$ määritelty nimellä . Määrittele bijektioksi ja K: n välillä seuraavasti: $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)$ . Määritä bijektioksi ja välillä : _ $\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-bittinen piilotettu merkkijono.

SFLASH-algoritmi käyttää myös kahta affinista bijektiota s ja t välillä - . Jokainen niistä on piilotettu lineaarinen (matriisi 67*67) ja vakio (sarake 67*1), vastaavasti. $K^{67}$ $K^{67}$ $S_{L},T_{L}$ $S_{C},T_{C}$

Avaa Asetukset

Julkinen avain on funktiossa G from to määritellään seuraavasti: $K^{67}$ $K^{56}$ ${\displaystyle G(X)=[t(\varphi ^{-1}(F(\varphi (s(X)))))]_{0\rightarrow 391))$

F on funktio välillä - määritelty $\Phi$ $\Phi$ $\forall A\in \Phi ,F(A)=A^{128^{33}+1}$

Avaimen luominen

Olkoon next_7bit_random_string 7-bittinen merkkijono, joka generoidaan kutsumalla CSPRBG (Cryptographically Secure PseudoRandom Bit Generator) 7 kertaa. Ensin saamme merkkijonon ensimmäisen bitin, sitten toisen ja niin edelleen seitsemänteen.

1) Luomme

S_L

Käänteisen 67x67 matriisin luomiseen voidaan käyttää kahta menetelmää:

S_L

Täytämme matriisin elementti kerrallaan, kunnes täytämme koko matriisin:

i = 0 - 66 j = 0 - 66 S_L[i,j]=pi(seuraava_7 bittiä_satunnainen_merkkijono)

Käytämme LU -hajottelua , jossa on alempi kolmiomatriisi 67x67 ja ylempi kolmiomatriisi 67x67. Kun olemme löytäneet matriisit ja , määritämme : ${\displaystyle L_{S))$ $U_{S}$ ${\displaystyle L_{S))$ $U_{S}$ $S_{L}=L_{S}\times U_{S}.$

i = 0 - 66 j = 0 - 66 { jos (i<j) niin {U_S[i,j]=pi(seuraava_7 bittiä_satunnainen_merkkijono); L_S[i,j]=0;}; jos (i>j) sitten {L_S[i,j]=pi(seuraava_7 bittiä_satunnainen_merkkijono); U_S[i,j]=0;}; jos (i=j) niin {toista (z=next_7bit_random_string) kunnes z!=(0,0,0,0,0,0,0); U_S[i,j]=pi(z); L_S[i,j]=1;}; }; 2) Luomme

S_{C}

Käytä CSPRBG:tä löytääksesi K:n uudet 67 elementtiä (matriisisarakkeen ylhäältä alas). Jokainen K:n elementti löytyy funktiolla:

$\pi$ (seuraava_7bit_satunnainen_merkkijono)

3) Luomme

{\näyttötyyli T_{L}}

Sama kuin matriisi .

S_L

4) Luomme

T_{C}

Sama kuin sarakkeessa .

S_{C}

5) Luomme

\Delta

Käyttämällä CSPRBG:tä (Cryptographically Secure PseudoRandom Bit Generator) luomme 80 satunnaista bittiä.

Allekirjoituksen luominen

Olkoon M viestimme, jolle haluamme löytää allekirjoituksen S. Allekirjoituksen luomisessa S on seuraava algoritmi:

1) Olkoon - nämä ovat SHA-1 kryptografisen hajautusalgoritmin avulla määritettyjä merkkijonoja : ${\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) Etsi V - 392-bittinen merkkijono seuraavasti:

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

3) Etsi W - 77-bittinen merkkijono seuraavasti:

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

4) Etsi Y - 56 K elementin merkkijono seuraavasti:

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

5) Etsi R - 11 K elementin merkkijono seuraavasti:

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

6) Etsi B - elementti seuraavasti: $\Phi$

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

7) Etsi A - elementti muodossa: $\Phi$

A=F^{-1}(B)

, jossa F on funktio alkaen - määritellään seuraavasti:

\Phi

\Phi

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

8) Etsi - rivin 67 elementit K: $X=(X_{0},...,X_{66})$

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

9) Allekirjoitus S - 469-bittinen merkkijono saatu seuraavasti:

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

Allekirjoituksen todentaminen (varmennus)

Annettu viesti M (bittijono) ja allekirjoitus S (256-bittinen merkkijono). Seuraavaa algoritmia käytetään määrittämään sanoman M allekirjoituksen S kelpoisuus:

1) Olkoon - nämä ovat SHA-1 kryptografisen hajautusalgoritmin avulla määritettyjä merkkijonoja : ${\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) Etsi V - 392-bittinen merkkijono seuraavasti:

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

3) Etsi Y - 56 K elementin merkkijono seuraavasti:

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

4) Etsi Y' - 56 K elementin merkkijono seuraavasti:

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

5) Vertaa tuloksena olevia merkkijonoja Y ja Y'. Jos ne ovat yhtä suuret, allekirjoitus hyväksytään, muuten se hylätään.

Kirjallisuus

Nicolas T. Courtois, Louis Goubin ja Jacques Patarin. SFLASHv3, nopea epäsymmetrinen allekirjoitusmalli, 2003" Arkistoitu 13. heinäkuuta 2007 Wayback Machinessa , Algoritmimääritykset kehittäjiltä
"Vivien Dubois, Pierre-Alain Fouque, Adi Shamir ja Jacques Stern, SFLASHin käytännön kryptaanalyysi" Arkistoitu 7. kesäkuuta 2011 Wayback Machinessa , kuvaus nykyisistä SFLASHia vastaan tehdyistä hyökkäyksistä

Linkit

Moniulotteinen salaus (Multivariate cryptography)