Salsa20

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2015. április 2-án áttekintett verziótól ; az ellenőrzéshez 31 szerkesztés szükséges .

A Salsa20 egy Daniel Bernstein által kifejlesztett adatfolyam-titkosítási rendszer. Az algoritmust az eSTREAM versenyen mutatták be , melynek célja a levelezőrendszerek által továbbított adatok titkosítására vonatkozó európai szabványok megalkotása volt. Az algoritmus a verseny győztese lett az első profilban (stream cipherek nagy áteresztőképességű szoftveralkalmazásokhoz).

A Salsa20 titkosító a következő műveleteket használja:

32 bites számok összeadása ;
bitenkénti összeadás modulo 2 (xor) ;
bit eltolódik .

Az algoritmus 20 ciklusú hash függvényt használ . Fő transzformációi az AES algoritmushoz hasonlítanak .

Az algoritmus leírása

Fogalmak

A következőkben a {0,1,…,2 32 −1} halmaz egy elemét szónak nevezzük, és hexadecimális formában írjuk fel 0x előtaggal.

A modulo 2 32 két szó hozzáadásának műveletét a " " jel jelöli . $+$

A kizárólagos vagy (bitenkénti összegzés) a " " szimbólummal lesz jelölve $\oplus$

$c$ - a szó bites ciklikus balra eltolása a -val lesz jelölve . Ha elképzeled, hogyan , akkor $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$

Az algoritmusban használt függvények

negyedkör(y)

A rendszer fő egysége a négy szón keresztüli átalakítás. Az alábbiakban ismertetett általánosabb transzformációk ebből épülnek fel. $negyedkör(y)$

Lényege abban rejlik, hogy minden szóhoz összeadjuk a két előzőt, eltolja (ciklikusan) az összeget meghatározott számú bittel és bitenként összegzi az eredményt a kiválasztott szóval. A későbbi műveletek új szójelentésekkel kerülnek végrehajtásra.

Tegyük fel, hogy ez egy 4 szóból álló sorozat, akkor a függvény a hol $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).

Például:

negyedkör(0x00000001; 0x00000000; 0x00000000; 0x00000000)
= (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Ezt a függvényt az y 0 , y 1 , y 2 és y 3 szavak transzformációjaként is felfoghatjuk . Ezen átalakítások mindegyike visszafordítható, akárcsak a funkció egésze.

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}}$

Ebben az átalakításban 16 szót veszünk fel. 4x4-es mátrix formájában ábrázoljuk őket. Ennek a mátrixnak minden sorát vesszük, és ennek a mátrixnak a szavait átalakítjuk a függvénnyel . A sorból származó szavakat a rendszer sorban veszi az i -ediktől kezdve az i -edik sorhoz, ahol i = {0,1,2,3}. $negyedkör(y)$

Legyen 16 szóból álló sorozat, akkor legyen 16 szóból álló sorozat is ahol $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})=negyedkör(y_{0},y_{1},y_{2},y_{3}),

(z_{5},z_{6},z_{7},z_{4})=negyedkör(y_{5},y_{6},y_{7},y_{4}),

(z_{10},z_{11},z_{8},z_{9})=negyedkör(y_{10},y_{11},y_{8},y_{9}),

(z_{15},z_{12},z_{13},z_{14})=negyedkör(y_{15},y_{12},y_{13},y_{14}).

oszlopkör(y)

Itt ugyanannak a mátrixnak az oszlopait vesszük. Alakítsuk át őket a függvénnyel , analógia útján behelyettesítve az értékeket, kezdve a j -edik oszlopból a j -edik oszlopba, ahol j = {0,1,2,3}. $negyedkör(y)$

A columnround(y)=(z) függvény szintén 16 szóból álló sorozaton működik úgy, hogy

(z_{0},z_{4},z_{8},z_{12})=negyedkör(y_{0},y_{4},y_{8},y_{12}),

(z_{5},z_{9},z_{13},z_{1})=negyedkör(y_{5},y_{9},y_{13},y_{1}),

(z_{10},z_{14},z_{2},z_{6})=negyedkör(y_{10},y_{14},y_{2},y_{6}),

(z_{15},z_{3},z_{7},z_{11})=negyedkör(y_{15},y_{3},y_{7},y_{11}).

doubleround(y)

A doubleround(y) függvény a columnround , majd a rowround függvények szekvenciális alkalmazása : doubleround (y) = rowround(columnround(y))

Salsa20()

Ez az algoritmus az alacsony bájttal kezdődő szóbevitelt használ . Ehhez itt van egy átalakítás $littleendian(b)$

Legyen egy 4 bájtos sorozat, akkor legyen olyan szó, hogy $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))

A végső transzformáció az eredeti sorozat bitenkénti összegzése, valamint 20 fordulós váltakozó oszlop- és sortranszformáció eredménye.

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

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

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

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

…

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

x[i] az x bájt, az x j pedig a fenti függvényekben használt szavak.

Ha egy

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

akkor a Salsa20(x) az eredmények sorozata

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

Kulcskiterjesztés Salsa20-hoz

A kiterjesztés egy 32 bájtos vagy 16 bájtos kulcsot k és egy 16 bájtos n számot alakít át 64 bájtos sorozatmá . $Salsa20_{k}(n)$

A k kiterjesztés a konstansokat használja
$\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 bájtos k és

$\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 bájtos k esetén .

Ezek az "expand 32-byte k" és a "expand 16-byte k" ASCII kódban.

Legyen k 0 ,k 1 ,n 16 bájtos sorozata, akkor .
$Salsa20_{{k_{0},k_{1}}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{ 1},\sigma _{3})$

Ha csak egy 16 bájtos k sorozatunk van, akkor
$Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})$

Salsa20 titkosítási funkció

Byte-szekvencia titkosítás , mert lesz $l$ $m$ $l\in \{0,1,...2^{{70}}\}$ $Salsa20_{k}(v)\oplus m$

$v$ — egyedi 8 bájtos szám (nem egyszer).

A titkosított szöveg bájt méretű lesz , akárcsak a sima szöveg. $l$

A Salsa20 k ( v ) egy 270 bájtos sorozat.

Salsa20_{k}(v,{\aláhúzás {0))),Salsa20_{k}(v,{\aláhúzás {1))),Salsa20_{k}(v,{\aláhúzás {2))) ,...,Salsa20_{k}(v,{\aláhúzás {2^{64}-1)))

Hol van egy 8 bájtból álló egyedi sorozat , amelyre ill $\aláhúzás {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- egy])

Ahol $c[i]=m[i]\oplus Salsa20_{k}(v,{\mathcal {b}}\aláhúzás {i/64}{\mathcal {c}})[i\mod 64]$

Teljesítmény

Tekintettel arra, hogy az egyes oszlopok és sorok transzformációi függetlenek egymástól, a titkosításhoz szükséges számítások könnyen párhuzamosíthatók . Ez jelentős sebességnövekedést biztosít a legtöbb modern platform számára.

Az algoritmus gyakorlatilag nem igényel többletköltséget a titkosítási ciklus futtatásához. Ez vonatkozik a legfontosabb változtatásokra is. Sok rejtjelező rendszer előszámításokra támaszkodik, amelyek eredményeit a processzor első szintű (L1) gyorsítótárában kell tárolni . Mivel ezek a kulcstól függenek, a számításokat újra el kell végezni. A Salsa20-ban elég egyszerűen betölteni a kulcsot a memóriába.

Salsa20/8 és Salsa20/12 változatok

A Salsa20/8 és a Salsa20/12 titkosítási rendszerek, amelyek ugyanazt a mechanizmust használják, mint a Salsa20, de az eredeti 20 helyett 8, illetve 12 titkosítási körrel. A Salsa20 nagy kitartással készült. Míg a Salsa20/8 jó eredményeket mutat sebességben, a legtöbb esetben megelőzve sok más titkosítási rendszert, beleértve az AES -t és az RC4 -et [1] .

XSalsa20 variáns

A Salsa20 algoritmusnak van egy változata, amelyet szintén Daniel Bernstein javasolt, és amely 64 bitről 192 bitre növeli a nonce hosszát. Ezt a változatot XSalsa20-nak hívják. A nonce megnövelt mérete lehetővé teszi egy kriptográfiailag erős pszeudo-véletlenszám-generátor használatát annak előállításához , míg a biztonságos titkosítás 64 bites nonce-val az ütközések nagy valószínűsége miatt számláló használatát igényli [2] .

Kriptanalízis

2005-ben Paul Crowley bejelentette a Salsa20/5 elleni támadást 2165 -re becsült időbonyolítással . Ez és az azt követő támadások csonka differenciális kriptográfiai elemzésen alapulnak . Ezért a kriptoanalízisért 1000 dollár jutalmat kapott a Salsa20 szerzőjétől.

2006-ban Fischer, Meier, Berbain , Biasse és Robshaw 2117-es összetettségi támadásról számolt be a Salsa/6 ellen, és egy 2217-es összetettségi támadásról a Salsa20 /7 ellen linkelt kulcsokkal .

2008-ban Aumasson, Fischer, Khazaei, Meier és Rechberger a Salsa20/7 elleni támadásról 2153 -as nehézséggel, a Salsa20/8 elleni első támadásról pedig 2251 -es nehézséggel számoltak be .

Eddig nem érkeztek nyilvános jelentések a Salsa20/12 és a teljes Salsa20/20 elleni támadásokról.

ChaCha

2008-ban Daniel Bernstein kiadott egy kapcsolódó adatfolyam -rejtjel-családot ChaCha néven, amelynek célja az volt, hogy javítsa az adatkeverést egy körben, és állítólag javítsa a kriptográfiai erősséget ugyanolyan vagy akár valamivel gyorsabb sebesség mellett [3] .

A ChaCha20 leírását az RFC 7539 (2015. május) írja le.

A rendszer fő egysége itt másként működik. Most minden művelet megváltoztatja az egyik szót. A változások ciklikusan „ellentétes irányban” mennek végbe, a 0. szótól kezdve. Az összeadás és a bitenkénti összeg műveletei váltakoznak az eltolás mellett, a szó hozzáadódik az előzőhöz.

A negyedkör(a, b, c, d) függvény, ahol a, b, c, d-szavak, a ChaCha-ban így néz ki:

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;

Ugyanazokat az aritmetikai műveleteket használjuk itt is, de minden szót átalakításonként kétszer módosítunk, nem egyszer.

Ezenkívül a titkosítás kezdeti állapota (kulcskiterjesztés) megváltozik a Salsához képest: az első 128 bit konstans, ezt követi a kulcs 256 bitje, a számláló 32 bitje, majd egy egyedi nonce sorozat 96 bitje.

Jegyzetek

↑ Archivált másolat . Letöltve: 2010. november 11. Az eredetiből archiválva : 2017. december 15. (határozatlan)
↑ Archivált másolat . Letöltve: 2016. szeptember 13. Az eredetiből archiválva : 2018. szeptember 18.. (határozatlan)
↑ Archivált másolat . Letöltve: 2010. november 11. Az eredetiből archiválva : 2018. május 2. (határozatlan)

Linkek

Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam	A3 A5 A8 Decim F-FCSR Gabona HC-256 KCipher-2 MICKEY MUGI CSUKA Phelix RC4 Nyúl FÓKA HÓ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel hálózat	GOST 28147-89 (Magma) blowfish Kamélia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra ÜZLET DES DESX DFC E2 EnRUPT FEAL HPC ÖTLET KASUMI Khafre Khufu LOKI97 MacGuffin MARS HÁLÓ MISTY1 NewDES NDS RC5 RC6 MAG Simon Sinopoli skipjack SM4 Folt TEA XTEA XXTEA Raiden RTEA Tripla DES Kéthal
SP hálózat	Szöcske 3 út ABC ÁRIA AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Öv CRYPTON Gyémánt2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer jelenlegi Szivárvány BIZTONSÁGOSBAN CÁPA NÉGYZET Kígyó háromhal
Egyéb	BÉKA NUSH REDOC SC2000 SHACAL CS-Cipher