Salsa 20

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2. huhtikuuta 2015 tarkistetusta versiosta . vahvistus vaatii 31 muokkausta .

Salsa20 on Daniel Bernsteinin kehittämä tietovirran salausjärjestelmä. Algoritmi esiteltiin eSTREAM- kilpailussa , jonka tarkoituksena oli luoda eurooppalaiset standardit postijärjestelmien välittämän tiedon salaukselle. Algoritmi voitti kilpailun ensimmäisessä profiilissa (suorat salakirjoitukset ohjelmistosovelluksille, joilla on suuri suorituskyky).

Salsa20-salaus käyttää seuraavia toimintoja:

32 -bittisten numeroiden lisääminen;
bittikohtainen lisäys modulo 2 (xor) ;
bitti siirtyy .

Algoritmi käyttää hash-funktiota 20 syklillä . Sen päämuunnokset muistuttavat AES -algoritmia .

Algoritmin kuvaus

Käsitteet

Seuraavassa joukon {0,1,…,2 32 −1} elementtiä kutsutaan sanaksi ja kirjoitetaan se heksadesimaalimuodossa etuliitteellä 0x.

Kahden sanan modulo 2 32 lisääminen merkitään merkillä " ". $+$

Yksinomainen tai (bittinen summaus) merkitään symbolilla " " $\oplus$

$c$ - sanan bittisyklinen siirto vasemmalle merkitään . Jos kuvittelet kuinka niin $u$ $u\ll c$ $u$ ${\displaystyle u=\sum _{i=0}2^{i}u_{i))$

$u\lll c=\sum_{i=0}2^{i+c \mod 32}u_i$

Algoritmissa käytetyt funktiot

quarterround(y)

Järjestelmän pääyksikkö on neljän sanan muunnos. Alla kuvatut yleisemmät muunnokset on rakennettu siitä. $neljänneskierros(y)$

Sen olemus on siinä, että jokaiseen sanaan lisäämme kaksi edellistä, siirrämme (syklisesti) summaa tietyllä määrällä bittejä ja bitti bitiltä summaamme tuloksen valitulla sanalla. Seuraavat toiminnot suoritetaan uusilla sanamerkityksillä.

Oletetaan, että se on 4 sanan sarja, niin funktio on missä $y$ $y=(y_{0},y_{1},y_{2},y_{3})$ $quarterround(y)=(z_{0},z_{1},z_{2},z_{3})$

z_{1}=y_{1}\oplus ((y_{0}+y_{3})\lll 7),

z_{2}=y_{2}\oplus ((z_{1}+y_{0})\lll 9),

z_{3}=y_{3}\oplus ((z_{2}+z_{1})\lll 13),

z_{0}=y_{0}\oplus ((z_{3}+z_{2})\lll 18).

Esimerkiksi:

neljänneskierros(0x00000001; 0x00000000; 0x00000000; 0x00000000)
= (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Voit ajatella tätä funktiota muunnoksena sanoista y 0 , y 1 , y 2 ja y 3 . Jokainen näistä muunnoksista on palautuva, kuten myös toiminto kokonaisuudessaan.

rowround(y)

$y={\begin{pmatrix}y_{{0}}&y_{{1}}&y_{{2}}&y_{{3}}\\y_{{4}}&y_{{5}}&y_{{6 }}&y_{{7}}\\y_{{8}}&y_{{9}}&y_{{10}}&y_{{11}}\\y_{{12}}&y_{{13}}&y_{ {14}}&y_{{15}}\end{pmatrix}}$

Tässä muunnoksessa otetaan 16 sanaa. Edustamme niitä 4x4-matriisin muodossa. Otetaan tämän matriisin jokainen rivi ja muunnetaan tämän matriisin sanat funktiolla . Sanat riviltä otetaan järjestyksessä alkaen i -:nnestä rivistä, jossa i = { 0,1,2,3 }. $neljänneskierros(y)$

Antaa olla 16 sanan sekvenssi, sitten myös 16 sanan sekvenssi missä $y=(y_{0},y_{1},y_{2},...,y_{15})$ $rowround(y)=(z_{0},z_{1},z_{2},...,z_{15})$

(z_{0},z_{1},z_{2},z_{3})=neljänneskierros(y_{0},y_{1},y_{2},y_{3}),

(z_{5},z_{6},z_{7},z_{4})=neljänneskierros(y_{5},y_{6},y_{7},y_{4}),

(z_{10},z_{11},z_{8},z_{9})=neljänneskierros(y_{10},y_{11},y_{8},y_{9}),

(z_{15},z_{12},z_{13},z_{14})=neljänneskierros(y_{15},y_{12},y_{13},y_{14}).

columnround(y)

Tässä otetaan saman matriisin sarakkeet. Muunnetaan ne funktiolla , analogisesti korvaamalla arvot siihen, alkaen j -sarakkeesta j - sarakkeeseen, missä j = {0,1,2,3}. $neljänneskierros(y)$

Funktio columnround(y)=(z) toimii myös 16 sanan sekvenssillä niin, että

(z_{0},z_{4},z_{8},z_{12})=neljänneskierros(y_{0},y_{4},y_{8},y_{12}),

(z_{5},z_{9},z_{13},z_{1})=neljänneskierros(y_{5},y_{9},y_{13},y_{1}),

(z_{10},z_{14},z_{2},z_{6})=neljänneskierros(y_{10},y_{14},y_{2},y_{6}),

(z_{15},z_{3},z_{7},z_{11})=neljänneskierros(y_{15},y_{3},y_{7},y_{11}).

doubleround(y)

Doubleround (y) -funktio on peräkkäinen sovellus sarakkeen ympäri ja sitten rivikierrosfunktioista : doubleround(y) = rowround(columnround(y))

Salsa20()

Tämä algoritmi käyttää sanasyöttöä , joka alkaa pienellä tavulla . Tätä varten tässä on muunnos $littleendian(b)$

Antaa olla 4-tavuinen sekvenssi, sitten sana sellainen $b=(b_{0},b_{1},b_{2},b_{3})$ $littleendian(b)$

{\displaystyle littleendian(b)=b_{0}+2^{8}b_{1}+2^{16}b_{2}+2^{24}b_{3))

Lopullinen muunnos on alkuperäisen sekvenssin ja 20 kierroksen vuorottelevien sarake- ja rivimuunnosten tulos.

$Salsa20(x)=x\oplus doubleround^{10}(x)$

Missä $x=(x[0],x[1],...,x[63]),$

x_{0}=pieni(x[0],x[1],x[2],x[3]),

x_{1}=pieni(x[4],x[5],x[6],x[7]),

…

x_{15}=pieni(x[60],x[61],x[62],x[63]).

x[i] ovat tavuja x ja x j ovat sanoja, joita käytetään yllä olevissa funktioissa.

Jos

$(z_{0},z_{1},...,z_{15})=doubleround^{10}(x_{0},x_{1},...,x_{15})$ ,

niin Salsa20(x) on tulossarja

$littleendian^{-1}(z_{0}+x_{0}),..., littleendian^{-1}(z_{15}+x_{15})$

Avaimen laajennus Salsa20:lle

Laajennus muuntaa 32- tai 16-tavuisen avaimen k ja 16-tavuisen luvun n 64-tavuiseksi sekvenssiksi . $Salsa20_{k}(n)$

K - laajennus käyttää vakioita
$\sigma _{0}=(101,120,112,97),~\sigma _{1}=(110,100,32,51),~\sigma _{2}=(50,45,98,121),~\sigma _{ 3}=(116 101 32 107)$

32-tavuiselle k ja

$\tau _{0}=(101;120;112;97),~\tau _{1}=(110;100;32;49),~\tau _{2}=(54;45;98; 121),~\tau _{3}=(116;101;32;107)$

16-tavuiselle k .

Nämä ovat "expand 32-byte k" ja "expand 16-byte k" ASCII - koodissa.

Olkoon k 0 ,k 1 ,n:llä 16-tavuisia sekvenssejä, niin .
$Salsa20_{{k_{0},k_{1}}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{ 1},\sigma _{3})$

Jos meillä on vain yksi 16-tavuinen sekvenssi k , niin
$Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})$

Salsa20-salaustoiminto

Tavusekvenssin salaus , koska tulee olemaan $l$ $m$ $l\in \{0,1,...2^{{70}}\}$ $Salsa20_{k}(v)\oplus m$

$v$ — yksilöllinen 8-tavuinen numero (ei kerran).

Salateksti on tavukokoinen , aivan kuten tavallinen teksti. $l$

Salsa20 k ( v ) on 270 tavun sekvenssi.

Salsa20_{k}(v,{\alleviivaus {0))),Salsa20_{k}(v,{\alleviivaus {1))),Salsa20_{k}(v,{\alleviivaus {2))) ,...,Salsa20_{k}(v,{\alleviivaus {2^{64}-1)))

Missä on ainutlaatuinen 8 tavun sekvenssi , joka vastaavasti $\alleviivaus {i}$ $(i_{0},i_{1},...,i_{7})$ $i=i_{0}+2^{8}i_{1}+...+2^{{56}}i_{7}$

Salsa20_{k}(v)\oplus (m[0],m[1],..,m[l-1])=(c[0],c[1],...,c[l- yksi])

Missä $c[i]=m[i]\oplus Salsa20_{k}(v,{\mathcal {b}}\alleviivaus {i/64}{\mathcal {c}})[i\mod 64]$

Suorituskyky

Koska kunkin sarakkeen ja jokaisen rivin muunnokset ovat toisistaan riippumattomia, salaukseen tarvittavat laskelmat voidaan helposti rinnastaa . Tämä antaa merkittävän nopeuden lisäyksen useimmille nykyaikaisille alustoille.

Algoritmilla ei käytännössä ole ylimääräistä laskentaa, joka tarvitaan salaussyklin suorittamiseen. Tämä koskee myös keskeisiä muutoksia. Monet salausjärjestelmät käyttävät esilaskutoimituksia, joiden tulokset on tallennettava prosessorin ensimmäisen tason (L1) välimuistiin . Koska ne riippuvat avaimesta, laskelmat on suoritettava uudelleen. Salsa20:ssä riittää, että avain ladataan muistiin.

Salsa20/8- ja Salsa20/12-versiot

Salsa20/8 ja Salsa20/12 ovat salausjärjestelmiä, jotka käyttävät samaa mekanismia kuin Salsa20, mutta niissä on 8 ja 12 salauskierrosta alkuperäisen 20:n sijaan. Salsa20 tehtiin suurella kestovoimalla. Sen sijaan Salsa20/8 osoittaa hyviä tuloksia nopeudessa, ohittaen useimmissa tapauksissa monet muut salausjärjestelmät, mukaan lukien AES ja RC4 [1] .

XSalsa20 variantti

Salsa20-algoritmista on myös Daniel Bernsteinin ehdottama muunnelma, joka kasvattaa nonce- pituuden 64 bitistä 192 bittiin. Tämän muunnelman nimi on XSalsa20. Noncen kasvanut koko mahdollistaa kryptografisesti vahvan näennäissatunnaislukugeneraattorin käytön sen luomiseen , kun taas turvallinen salaus 64-bittisellä noncen kanssa vaatii laskurin käyttöä törmäysten suuren todennäköisyyden vuoksi [2] .

Cryptanalysis

Vuonna 2005 Paul Crowley ilmoitti hyökkäyksestä Salsa20/5:tä vastaan, jonka arvioitu aikamonimutkaisuus on 2165 . Tämä ja sitä seuraavat hyökkäykset perustuvat typistettyyn differentiaaliseen kryptausanalyysiin . Tästä kryptoanalyysistä hän sai 1 000 dollarin palkinnon Salsa20:n kirjoittajalta.

Vuonna 2006 Fischer, Meier, Berbain , Biasse ja Robshaw raportoivat 2117 kompleksisuushyökkäyksestä Salsa/6:ta vastaan ja 2217 monimutkaisuudesta Salsa20 /7:ää vastaan linkitetyillä avaimilla .

Vuonna 2008 Aumasson, Fischer, Khazaei, Meier ja Rechberger raportoivat hyökkäyksestä Salsa20/7:ään vastaan vaikeudella 2153 ja ensimmäisestä hyökkäyksestä Salsa20/8:aan vaikeudella 2251 .

Toistaiseksi ei ole ollut julkisia raportteja Salsa20/12:een ja koko Salsa20/20:een kohdistuvista hyökkäyksistä.

ChaCha

Vuonna 2008 Daniel Bernstein julkaisi ChaCha-nimisen stream - salausperheen, jonka tarkoituksena oli parantaa tietojen sekoittamista yhdellä kierroksella ja oletettavasti parantaa kryptografista vahvuutta samalla tai jopa hieman suuremmalla nopeudella [3] .

ChaCha20 on kuvattu RFC 7539:ssä (toukokuu 2015).

Järjestelmän pääyksikkö toimii täällä eri tavalla. Nyt jokainen operaatio muuttaa yhden sanan. Muutokset tapahtuvat syklisesti "vastakkaiseen suuntaan", alkaen 0. sanasta. Summa- ja bittisummaoperaatiot vuorottelevat siirron mukana, sana lisätään edelliseen.

Funktio Quarterround(a, b, c, d), jossa a, b, c, d-sanat, ChaChassa näyttää tältä:

a+=b;~~d\oplus =a;~~d\lll =16;

c+=d;~~b\oplus =c;~~b\lll =12;

a+=b;~~d\oplus =a;~~d\lll =8;

c+=d;~~b\oplus =c;~~b\lll =7;

Tässä käytetään samoja aritmeettisia operaatioita, mutta jokaista sanaa muutetaan kahdesti konversiota kohden yhden kerran sijaan.

Lisäksi salauksen alkutilaa (avaimen laajennus) muutetaan Salsaan verrattuna: ensimmäiset 128 bittiä ovat vakioita, joita seuraa 256 bittiä avainta, 32 bittiä laskuria ja sitten 96 bittiä ainutlaatuista nonce-sekvenssiä.

Muistiinpanot

↑ Arkistoitu kopio . Haettu 11. marraskuuta 2010. Arkistoitu alkuperäisestä 15. joulukuuta 2017. (määrätön)
↑ Arkistoitu kopio . Haettu 13. syyskuuta 2016. Arkistoitu alkuperäisestä 18. syyskuuta 2018. (määrätön)
↑ Arkistoitu kopio . Haettu 11. marraskuuta 2010. Arkistoitu alkuperäisestä 2. toukokuuta 2018. (määrätön)

Linkit

Symmetriset salausjärjestelmät
Suoratoista salauksia	A3 A5 A8 Desim F-FCSR Vilja HC-256 KCipher-2 MIKKI MUGI HAUKI Phelix RC4 Kani TIIVISTE LUMI SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistelin verkko	GOST 28147-89 (Magma) blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra SOPIMUS DES DESX DFC E2 enRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 UusiDES NDS RC5 RC6 SIEMEN Simon Sinopoli jätkä SM4 Speck TEE XTEA XXTEA Raiden RTEA Kolminkertainen DES Kaksi kalaa
SP verkko	Heinäsirkka 3 tapaa ABC AARIA AES (Rijndael) Akelarre Anubis BaseKing Basso Omatic Vyö CRYPTON Timantti 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer esittää Sateenkaari TURVALLISTA HAI NELIÖ Käärme kolme kalaa
Muut	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher