SWIFFT

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. helmikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

SWIFFT
Kehittäjät	Vadim Lyubashevsky, Daniel Michiancio, Chris Peikert, Alon Rosen
Luotu	2008
julkaistu	2008
Tyyppi	hash-toiminto

SWIFFT on joukko kryptografisia hajautusfunktioita, joiden turvallisuus on todistettu [1] [2] [3] . Ne perustuvat FFT ( Fast Fourier Transform ) -muunnokseen ja käyttävät LLL-reduced bases -algoritmia . SWIFFT-funktioiden kryptografinen turvallisuus (asymptoottisessa mielessä) [4] on matemaattisesti todistettu käyttämällä suositeltuja parametreja [5] . Törmäysten löytäminen SWIFFT:ssä on pahimmassa tapauksessa vähintään yhtä aikaa vievää kuin lyhyiden vektoreiden löytäminen syklisistä/ ideaaleista hiloista . SWIFFT:n käytännön soveltaminen on arvokasta juuri niissä tapauksissa, joissa törmäyskestävyys on erityisen tärkeää. Esimerkiksi digitaaliset allekirjoitukset, joiden on säilyttävä luotettavina pitkään.

Tämä algoritmi tarjoaa noin 40 Mb/s suorituskyvyn Intel Pentium 4 -prosessorilla kellotaajuudella 3,2 GHz [6] [1] . SWIFFT:ssä käytetyn FFT:n nopeuttamiseksi on tehty tutkimusta [7] . Tämän seurauksena algoritmin nopeus kasvoi yli 13 kertaa [6] . Tämä SWIFFT-toteutus osoittautui nopeammaksi kuin yleisesti käytettyjen hash-funktioiden toteutukset [8] .

Vuoden 2012 National Institute of Standards and Technology [2] -kilpailussa SWIFFTX:ää (SWIFFT:n muunnos) ehdotettiin SHA-3 :ksi (korvaamaan vanhemman SHA-2:n ja erityisesti SHA-1:n [9] ), mutta se hylättiin ensimmäinen kierros [10] .

Työn kuvaus

SWIFFT-funktiot voidaan kuvata yksinkertaisena algebrallisena lausekkeena jonkin polynomirenkaan yli [1] [11] . Toimintojen perhe riippuu kolmesta pääparametrista : olkoon potenssi 2, - pieni kokonaisluku ja - ei välttämättä alkuluku , mutta se on parempi valita alkuluku. Määrittelemme sen muodon renkaaksi . Esimerkiksi polynomien rengas , jonka kertoimet ovat kokonaislukuja, on luku, jolla suoritamme modulo-jaon, ja . Alku voi olla alemman asteen polynomi kertoimilla alkaen . $R$ $n$ $m>0$ $p>0$ $R$ $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $\alpha$ $s$ $\alpha ^{n}+1$ $R$ $n$ $Z_{p}$

Määritelty funktio SWIFFT-perheessä määritellään kiinteiksi rengaselementeiksi , joita kutsutaan kertojiksi. Tämä funktio renkaan päälle voidaan kirjoittaa seuraavassa muodossa: $m$ $a_{1},\ldots ,a_{m}\in R$ $R$ $R$

$\sum _{i=1}^{m}(a_{i}\cdot x_{i})$ ,

missä ovat polynomit, joiden binäärikertoimet vastaavat pituuden binaarisyöteviestiä . $x_{1},\ldots ,x_{m}\in R$ $mn$

Toimintaalgoritmi on seuraava: [1] [12] [11]

Taken on redusoitumaton polynomi over $\alpha$ $\mathbb {Z} [\alpha ]$
Syöte on pituinen viesti $M$ $mn$
$M$ muunnetaan polynomijoukoksi tietyssä polynomirenkaassa binäärikertoimilla $m$ $p_{i}$ $R$
Fourier-kertoimet lasketaan jokaiselle $p_{i}$
Kiinteät Fourier-kertoimet asetetaan SWIFFT-perheen mukaan $a_{i}$
Fourier - kertoimet kerrotaan pareittain kullekin $p_{i}$ $a_{i}$ $i$
Käänteistä Fourier-muunnosta käytetään korkeintaan astepolynomien saamiseksi $m$ $f_{i}$ $2n$
Laskettu modulo ja . $f=\summa _{i=1}^{m}(f_{i})$ $s$ $\alpha ^{n}+1$
$f$ muunnetaan biteiksi ja lähetetään ulostuloon $n\log(p)$

Nopea Fourier-muunnos vaiheessa 4 on helppo kääntää. Se suoritetaan hämmennyksen aikaansaamiseksi - tuloon annettujen bittien sekoitus.
Lineaarinen yhdistelmä vaiheessa 6 on hämmentävä , koska se pakkaa syötteen.

Esimerkki

Parametrien n , m ja p ominaisarvot valitaan seuraavasti: n = 64, m = 16, p = 257 [13] . Näille parametreille mikä tahansa perheen kiinteä pakkausfunktio hyväksyy syötteeksi viestin, jonka pituus on mn = 1024 bittiä (128 tavua). Tulos on alueella , jolla on koko . Lähtötiedot voidaan esittää käyttämällä 528 bittiä (66 tavua). $\mathbb {Z} _{p}^{n}$ $p^{n}=257^{64}$ $\mathbb {Z} _{p}^{n}$

Polynomien kertolaskutuloksen laskenta

Vaikein osa yllä olevan lausekkeen laskemisessa on kertolaskutuloksen laskeminen [1] [14] . Nopea tapa laskea tietty tulo on käyttää konvoluutiolausetta , joka sanoo, että tietyissä olosuhteissa: $a_{i}\cdot x_{i}$

{\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}

Tässä tarkoittaa Fourier-muunnosta ja operaatio tarkoittaa kertoimien kertomista samalla indeksillä. Yleensä konvoluutiolauseella on konvoluutio , ei kertolasku. Voidaan kuitenkin osoittaa, että polynomien kertolasku on konvoluutio. ${\mathcal {F}}$ $\cdot$ $*$

Nopea Fourier-muunnos

Fourier-muunnoksen löytämiseksi käytämme nopeaa Fourier-muunnosta (FFT), joka kestää [1] . Kertolalgoritmi on seuraava [14] : laskemme kaikki Fourier-kertoimet kaikille polynomeille kerralla käyttämällä FFT:tä. Kerromme sitten pareittain näiden kahden polynomin vastaavat Fourier-kertoimet. Kun käytämme käänteistä FFT:tä, jonka jälkeen saamme polynomin, jonka aste ei ole suurempi kuin . $O(n\log(n))$ $2n$

Diskreetti Fourier-muunnos

Tavallisen Fourier-muunnoksen sijaan SWIFFT käyttää Discrete Fourier-muunnosta (DFT) [1] [14] . Se käyttää yhtenäisyyden juuria monimutkaisten yhtenäisyyden juurien sijaan . Tämä on totta, jos on äärellinen kenttä ja sen 2 n :nnet yksinkertaiset ykseyden juuret ovat olemassa annetussa kentässä. Nämä ehdot täyttyvät, jos otamme sellaisen alkuluvun , joka on jaollinen luvulla . $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$ $s$ $p-1$ $2n$

Vaihtoehtojen valinta

Parametrien m , p , n on täytettävä seuraavat vaatimukset [15] :

n :n on oltava kahden potenssi
p on oltava alkuluku
p -1:n on oltava jaollinen luvulla 2 n
$\log(p)<$ m

Voit ottaa esimerkiksi seuraavat parametrit: n =64, m =16, p =257. Otamme suorituskyvyn tasolle 40 Mb / s [6] , turvallisuus törmäysten etsinnästä - operaatiot. $2^{106}$

Tilastolliset ominaisuudet

Universaali hajautus. SWIFFT-funktioperhe on universaali [1] . Toisin sanoen mille tahansa perheestä erilaiselle kiinteälle ja satunnaisesti valitulle funktiolle todennäköisyys, että yhtälö pätee, on kääntäen verrannollinen valitun alueen arvoon. $x,x*$ $f$ $f(x)=f(x*)$
Säännöllisyys. SWIFFT-perheen kutistusfunktiot ovat säännöllisiä [1] .
entropiageneraattori. SWIFFT on entropiageneraattori [1] . Hajautustaulukoissa ja niihin liittyvissä sovelluksissa on toivottavaa, että funktioon syötettyjen arvojen avaimet jakautuvat tasaisesti (tai lähellä tasaista jakautumista), vaikka syöttöarvot olisivat jakautuneet epätasaisesti. Hash-funktioita, jotka käyttäytyvät tällä tavalla, kutsutaan entropiageneraattoreiksi, koska ne voivat tuottaa epätasaisesti jakautuneita parametreja (melkein) yhtenäiseksi ulostuloksi. Muodollisesti tällä ominaisuudella on yleensä funktioperhe, josta yksi funktio valittiin satunnaisesti.

Salausominaisuudet ja suojaus

SWIFFT ei ole näennäissatunnainen funktio lineaarisuuden vuoksi [1] . SWIFFT-perheen mielivaltaiselle funktiolle pätee seuraava: kahdelle tuloparametrille , joka voi olla myös syöteparametri, . Tämän suhteen toteutuminen ei sovellu satunnaiselle funktiolle, ja hyökkääjä voi helposti erottaa funktiomme satunnaisesta. $f$ $x_{1}$ $x_{2}$ $x_{1}+x_{2}$ $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$

SWIFFT-funktioperheelle on osoitettu kryptografinen vastustuskyky törmäyksille (asymptoottisessa mielessä) suhteellisen kohtuullisella oletuksella lyhyiden vektoreiden löytämisen ongelman monimutkaisuudesta pahimmassa tapauksessa syklisissä/ideaalisissa hilassa. Tämä tarkoittaa, että SWIFFT-funktioperhe kestää myös toista esikuvahyökkäystä [4] [16] .

Teoreettinen vakaus

SWIFFT - Todistettu turvallisuus salaustoiminnot [1] [3] . Kuten useimmissa tapauksissa, funktioiden turvallisuuden todistaminen perustuu siihen, että funktioissa käytettyä matemaattista ongelmaa ei voida ratkaista polynomiajassa. Tämä tarkoittaa, että SWIFFT:n vahvuus on vain siinä, että se perustuu monimutkaiseen matemaattiseen ongelmaan.

SWIFFT:n tapauksessa todistettu turvallisuus piilee ongelmassa löytää lyhyitä vektoreita syklisistä/ ideaalihiloista [17] . Voidaan todistaa, että seuraava väite on totta: oletetaan, että meillä on algoritmi, joka löytää funktiotörmäyksiä SWIFFT:n satunnaiselle versiolle, joka on saatu kohdasta , jossain mahdollisessa ajassa todennäköisyydellä . Tämä tarkoittaa, että algoritmi toimii vain pienellä mutta huomattavalla osalla perheen toimintoja. Sitten voimme löytää myös algoritmin , joka voi aina löytää lyhyen vektorin mistä tahansa ideaalisesta hilasta renkaan yli jossain mahdollisessa ajassa riippuen ja . Tämä tarkoittaa, että törmäysten löytäminen SWIFFT:ssä ei ole yhtä vaikeaa, ongelmana on löytää lyhyitä vektoreita hilassa yli , jolle on olemassa vain eksponentiaalisia algoritmeja. $f$ $f$ $T$ $s$ $f_{2}$ $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $T_{2}$ $T$ $s$ $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$

Käytännöllinen kestävyys

Tämän hash-funktion kirjoittajat tutkivat sen haavoittuvuuksia eri hyökkäyksille ja havaitsivat, että "syntymäpäivä"-hyökkäys vaatii vähiten hash-laskentatoimintoja (2 106 ) törmäysten löytämiseksi. [18] [1] . Permutaatiohyökkäykset vaativat 2 448 laskentaa vakioparametreille. Mahdollisten arvojen täydellinen luettelointi vaatisi 2 528 hash-laskentaa. Tämä riittää yleensä tekemään vihollisen hyökkäyksen mahdottomaksi.

Katso myös

Nopea Fourier-muunnos

Muistiinpanot

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Lyubashevsky ym., 2008 .
↑ 12 Arbitman et al., 2008 .
↑ 1 2 Györfi et al., 2012 , s. 2.
↑ 12 Arbitman et al., 2008 , s. yksi.
↑ Buchmann ja Lindner 2009 , s. 1-2.
↑ 1 2 3 Györfi et al., 2012 , s. viisitoista.
↑ Györfi et al., 2012 , s. 15-16.
↑ Györfi et al., 2012 , s. 16.
↑ PRE-SHA-3 KILPAILU . National Institute of Standards and Technology (15. huhtikuuta 2005). Arkistoitu alkuperäisestä 9. elokuuta 2017. (määrätön)
↑ Toisen kierroksen ehdokkaat . National Institute of Standards and Technology (19. tammikuuta 2010). Haettu 14. helmikuuta 2010. Arkistoitu alkuperäisestä 10. huhtikuuta 2012. (määrätön)
↑ 1 2 Györfi et al., 2012 , s. 3.
↑ Arbitman et ai., 2008 , s. 4-5.
↑ Györfi ym., 2012 .
↑ 1 2 3 Györfi et al., 2012 , s. neljä.
↑ Buchmann, Lindner, 2009 .
↑ Sarinay, 2010 , s. 9.
↑ Arbitman et ai., 2008 , s. 10-11.
↑ Buchmann ja Lindner 2009 , s. 2.

Kirjallisuus

Kirjat

Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .

Artikkelit

Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFT: Vaatimaton ehdotus FFT-tiivistykseen (englanniksi) // Fast Software Encryption - 2008. - Vol. 5086. - s. 54-72. doi:10.1007/ 978-3-540-71039-4_4
Arbitman Y. , Dogon G. , Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFTX: A Proposal for the SHA-3 Standard (englanniksi) - 2008.
Buchmann J. , Lindner R. Secure Parameters for SWIFFT (englanti) // Progress in Cryptology - INDOCRYPT 2009 : 10. kansainvälinen kryptologiakonferenssi Intiassa, New Delhi, Intia, 13.-16. joulukuuta 2009. Proceedings / B. Roy , N Sendrier - Springer Berlin Heidelberg , 2009. - P. 1-17. - ISBN 978-3-642-10627-9 - doi:10.1007/978-3-642-10628-6_1
Šarinay J. Interpreting Hash Function Security Proofs (englanniksi) // Provable Security : 4th International Conference, ProvSec 2010, Malacca, Malesia, 13.-15.10.2010. Proceedings / S. Heng , K. Kurosawa - Springer Berlin Heidelberg , 2010 -s. 119-132. — ISBN 978-3-642-16279-4 — doi:10.1007/978-3-642-16280-0_8
Győrfi T. , Cret O. , Hanrot G. , Brisebarre N. High-Throughput Hardware Architecture for the SWIFFT / SWIFFTX hash Functions // Cryptology ePrint Archive - International Association for Cryptologic Research , 2012.

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA