Salsa20

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 april 2015; verifiering kräver 31 redigeringar .

Salsa20 är ett strömkrypteringssystem utvecklat av Daniel Bernstein. Algoritmen presenterades vid eSTREAM- tävlingen , vars syfte var att skapa europeiska standarder för kryptering av data som överförs av postsystem. Algoritmen blev vinnaren av tävlingen i den första profilen (strömningschiffer för mjukvaruapplikationer med hög genomströmning).

Salsa20-chifferet använder följande operationer:

tillägg av 32-bitars nummer;
bitvis addition modulo 2 (xor) ;
bitskiftningar .

Algoritmen använder en hashfunktion med 20 cykler . Dess huvudsakliga transformationer liknar AES- algoritmen .

Beskrivning av algoritmen

Begrepp

I det följande kallar vi ett element i mängden {0,1,…,2 32 −1} för ett ord och skriver det i hexadecimal form med prefixet 0x.

Operationen att lägga till två ord modulo 2 32 kommer att betecknas med tecknet " ". $+$

Exklusiv eller (bitvis summering) kommer att betecknas med symbolen " " $\ plus$

$c$ - bit cyklisk vänsterförskjutning av ett ord kommer att betecknas med . Om du föreställer dig hur , då $u$ $du vill c$ $u$ ${\displaystyle u=\sum _{i=0}2^{i}u_{i))$

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

Funktioner som används i algoritmen

quarterround(y)

Systemets huvudenhet är transformationen över fyra ord. De mer allmänna transformationerna som beskrivs nedan är konstruerade utifrån det. $quarterround(y)$

Dess väsen ligger i det faktum att vi för varje ord lägger till de två föregående, skiftar (cykliskt) summan med ett visst antal bitar och bit för bit summerar resultatet med det valda ordet. Efterföljande operationer utförs med nya ordbetydelser.

Låt oss säga att det är en sekvens av 4 ord, då är funktionen var $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).

Till exempel:

quarterround(0x00000001; 0x00000000; 0x00000000; 0x00000000)
= (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Du kan tänka på denna funktion som en transformation av orden y 0 , y 1 , y 2 och y 3 . Var och en av dessa transformationer är reversibel, liksom funktionen som helhet.

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

I denna förvandling tar vi 16 ord. Vi representerar dem i form av en 4x4-matris. Vi tar varje rad i denna matris och transformerar orden i denna matris med funktionen . Ord från raden tas i ordning, med början från i -th för i -th rad, där i = {0,1,2,3}. $quarterround(y)$

Låta vara en sekvens av 16 ord, då också vara en sekvens av 16 ord där $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})=quarterround(y_{0},y_{1},y_{2},y_{3}),

(z_{5},z_{6},z_{7},z_{4})=quarterround(y_{5},y_{6},y_{7},y_{4}),

(z_{10},z_{11},z_{8},z_{9})=quarterround(y_{10},y_{11},y_{8},y_{9}),

(z_{15},z_{12},z_{13},z_{14})=quarterround(y_{15},y_{12},y_{13},y_{14}).

columnround(y)

Här tar vi kolumnerna i samma matris. Låt oss omvandla dem med funktionen , genom att analogt ersätta värdena i den, med början från den j -:e kolumnen för den j -:e kolumnen, där j = {0,1,2,3}. $quarterround(y)$

Funktionen columnround(y)=(z) fungerar också på en sekvens av 16 ord så att

(z_{0},z_{4},z_{8},z_{12})=quarterround(y_{0},y_{4},y_{8},y_{12}),

(z_{5},z_{9},z_{13},z_{1})=quarterround(y_{5},y_{9},y_{13},y_{1}),

(z_{10},z_{14},z_{2},z_{6})=quarterround(y_{10},y_{14},y_{2},y_{6}),

(z_{15},z_{3},z_{7},z_{11})=quarterround(y_{15},y_{3},y_{7},y_{11}).

doubleround(y)

Doubleround (y) -funktionen är en sekventiell tillämpning av kolumnrunda och sedan rowround-funktioner : doubleround(y) = rowround(kolumnrunda(y))

Salsa20()

Denna algoritm använder en ordpost som börjar med den låga byten . För att göra detta, här är en förvandling $littleendian(b)$

Låt vara en 4-byte sekvens, sedan vara ett ord som $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))

Den slutliga transformationen är den bitvisa summeringen av den ursprungliga sekvensen och resultatet av 20 omgångar av alternerande kolumn- och radtransformationer.

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

Var $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] är byte x och x j är ord som används i ovanstående funktioner.

Om en

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

då är Salsa20(x) resultatsekvensen

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

Nyckeltillägg för Salsa20

Tillägget konverterar en 32-byte eller 16-byte nyckel k och ett 16-byte nummer n till en 64-byte sekvens . $Salsa20_{k}(n)$

Förlängningen k använder konstanterna
$\sigma _{0}=(101,120,112,97),~\sigma _{1}=(110,100,32,51),~\sigma _{2}=(50,45,98,121),~\sigma _{ 3}=(116,101,32,107)$

för 32-byte k och

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

för 16-byte k .

Dessa är "expandera 32-byte k" och "expandera 16-byte k" i ASCII -kod.

Låt k 0 , k 1 ,n ha 16-byte-sekvenser, då .
$Salsa20_{{k_{0},k_{1}}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{ 1},\sigma _{3})$

Om vi bara har en 16-byte sekvens k då
$Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})$

Salsa20 krypteringsfunktion

Byte-sekvens chiffer , för kommer att vara $l$ $m$ $l\in \{0,1,...2^{{70}}\}$ $Salsa20_{k}(v)\oplus m$

$v$ — unikt 8-byte nummer (icke).

Chiffertexten kommer att vara bytestor , precis som klartexten. $l$

Salsa20 k ( v ) är en sekvens på 270 byte.

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

Var är en unik sekvens på 8 byte så att resp $\underline {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- ett])

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

Prestanda

På grund av det faktum att transformationerna av varje kolumn och varje rad är oberoende av varandra, kan de beräkningar som krävs för kryptering enkelt parallelliseras . Detta ger en betydande hastighetsökning för de flesta moderna plattformar.

Algoritmen har praktiskt taget ingen overheadberäkning som krävs för att köra krypteringscykeln. Detta gäller även viktiga förändringar. Många chiffersystem förlitar sig på förberäkningar, vars resultat måste lagras i processorns första nivå (L1) cache . Eftersom de beror på nyckeln måste beräkningarna utföras igen. I Salsa20 räcker det att helt enkelt ladda nyckeln i minnet.

Salsa20/8 och Salsa20/12 varianter

Salsa20/8 och Salsa20/12 är chiffersystem som använder samma mekanism som Salsa20, men med 8 respektive 12 krypteringsrundor istället för de ursprungliga 20. Salsa20 gjordes med mycket uthållighet. Medan Salsa20/8 visar goda resultat i hastighet, kör om i de flesta fall många andra chiffersystem, inklusive AES och RC4 [1] .

XSalsa20-variant

Det finns en variant av Salsa20-algoritmen, också föreslagen av Daniel Bernstein, som ökar nonce- längden från 64 bitar till 192 bitar. Denna variant kallas XSalsa20. Den ökade storleken på nonce tillåter användning av en kryptografiskt stark pseudoslumptalsgenerator för att generera den, medan säker kryptering med en 64-bitars nonce kräver användning av en räknare på grund av den höga sannolikheten för kollisioner [2] .

Kryptanalys

2005 meddelade Paul Crowley en attack mot Salsa20/5 med en beräknad tidskomplexitet på 2165 . Denna och efterföljande attacker är baserade på trunkerad differentiell kryptoanalys . För denna kryptoanalys fick han en belöning på 1 000 $ från författaren till Salsa20.

2006 rapporterade Fischer, Meier, Berbain , Biasse och Robshaw en 2117 komplexitetsattack mot Salsa/6 och en 2217 komplexitet mot Salsa20 /7 med länkade nycklar .

2008 rapporterade Aumasson, Fischer, Khazaei, Meier och Rechberger en attack på Salsa20/7 med en svårighetsgrad på 2153 och den första attacken på Salsa20/8 med en svårighetsgrad på 2251 .

Hittills har det inte förekommit några offentliga rapporter om attacker mot Salsa20/12 och hela Salsa20/20.

ChaCha

2008 publicerade Daniel Bernstein en relaterad familj av strömchiffer som heter ChaCha, som syftade till att förbättra datablandningen i en omgång och förmodligen förbättra kryptografisk styrka med samma eller till och med något snabbare hastighet [3] .

ChaCha20 beskrivs i RFC 7539 (maj 2015).

Systemets huvudenhet fungerar annorlunda här. Nu ändrar varje operation ett av orden. Förändringar sker cykliskt "i motsatt riktning", med början från det 0:e ordet. Operationerna addition och bitvis summa alternerar tillsammans med skiftet, ordet läggs till det föregående.

Funktionen quarterround(a, b, c, d), där a, b, c, d-ord, i ChaCha ser ut så här:

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;

Samma aritmetiska operationer används här, men varje ord ändras två gånger per omvandling istället för en gång.

Dessutom ändras det initiala tillståndet för chifferet (nyckelförlängningen) jämfört med Salsa: de första 128 bitarna är konstanter, följt av 256 bitar av nyckeln, 32 bitar av räknaren och sedan 96 bitar av en unik nonce-sekvens.

Anteckningar

↑ Arkiverad kopia . Hämtad 11 november 2010. Arkiverad från originalet 15 december 2017. (obestämd)
↑ Arkiverad kopia . Hämtad 13 september 2016. Arkiverad från originalet 18 september 2018. (obestämd)
↑ Arkiverad kopia . Hämtad 11 november 2010. Arkiverad från originalet 2 maj 2018. (obestämd)

Länkar

Symmetriska kryptosystem
Streama chiffer	A3 A5 A8 Decim F-FCSR Spannmål HC-256 KCipher-2 MICKEY MUGI GÄDDA Phelix RC4 Kanin TÄTA SNÖ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel nätverk	GOST 28147-89 (Magma) blåsfisk Kamelia CAST-128 CAST-256 CIFERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra HANDLA DES DESX DFC E2 ENRUPT FEAL HPC ANING KASUMI Khafre Khufu LOKI97 MacGuffin MARS MASKA DIMMIG1 Ny DES NDS RC5 RC6 UTSÄDE Simon Sinople skipjack SM4 Fläck TE XTEA XXTEA Raiden RTEA Trippel DES Tvåfisk
SP nätverk	gräshoppa 3 sätt ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bälte CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna djävulen närvarande Regnbåge SÄKRARE HAJ FYRKANT Orm tre fiskar
Övrig	GRODA NUSH REDOC SC2000 SHACAL CS-Chiffer