RC4

RC4 (též ARC4 nebo ARCFOUR) je v informatice název kryptografického algoritmu. Je používán například pro šifrovaný přenos webových stránek (HTTPS) nebo pro zabezpečení přenosu v bezdrátových sítích (Wi-Fi). Šifra RC4 je jednoduchá, rychlá, ale má i slabé stránky, které omezují její použitelnost.

Historie
Šifru RC4 navrhl Ron Rivest z RSA Security v roce 1987. RC4 byla původně obchodním tajemství, ale v září 1994 byl popis šifry anonymně zaslán do Cypherpunks, odkud byl odeslán do usenetové skupiny sci.crypt a odtamtud se volně šířil po Internetu. Zveřejnění kódu zneplatnilo obchodní tajemství, ale problém nastal s názvem RC4, který byl chráněn ochranou známkou. Proto vznikly alternativní názvy, jako ARC4 nebo ARCFOUR, které ochrannou známku obešly. Šifra RC4 se stala součástí běžně používaných šifrovacích protokolů (SSL/TLS pro HTTPS nebo WEP a WPA pro bezdrátové sítě).

Hlavním faktorem úspěchu RC4 je široký rozsah použitelnosti v aplikacích, jeho rychlost a jednoduchost: efektivní a snadná implementace v softwaru i hardwaru.

Popis
Šifra RC4 generuje pseudonáhodný proud bajtů (keystream). Stejně jako proudové šifry, používá k šifrování spojení náhodných bajtů spolu s čistým textem (operací XOR) a dešifrování probíhá podobným způsobem, ale inverzně. Ke generování keystreamu používá šifra vnitřní stav, který tvoří:

pole bajtů o délce 256 (S)
dvě celočíselné proměnné (i a j)
Pole S se inicializuje za použití klíče o volitelné délce až 256 bajtů (2048 bitů), viz dále.

Algoritmus pro rozvrhnutí klíče
Algoritmus pro rozvrhnutí klíče (anglicky key-scheduling algorithm) je použit pro inicializaci permutace v poli S. Délka klíče je definována jako počet bajtů klíče a může být v rozmezí od 1 do 256, většinou mezi 5 a 16, což odpovídá klíč o délce 40–128 bitů. Nejdříve je pole S inicializováno na S[i] = i. Pole S je pak zpracována v cyklu s 256 opakováními podobným způsobem jako hlavní PRGA, ale navíc přidává bajty z klíče.

for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod keylength]) mod 256
prohoď S[i] a S[j]
endfor
Pseudonáhodné generování

Vyhledávací cyklus RC4.
V mnoha iteracích, které jsou nutné, generátor upravuje stav a výstupy bitů v keystream. V každé iteraci generátor k přírůstku i přidává hodnotu S, na kterou ukazuje i a j a vymění hodnoty S[i] a S [j] (každý prvek S je tak vyměněn s jiným prvkem alespoň jednou za 256 iterací). Výsledným bajtem iterace je prvek S s indexem S[i]+S[j] (modulo 256).

i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
prohoď S[i] a S[j]
K := S[(S[i] + S[j]) mod 256]
output K
endwhile
Implementace
Mnoho proudových šifer je založeno na lineárních posuvných registrech, které jsou snadno a rychle implementovatelné v hardwaru, méně však v softwaru. Návrh RC4 se vyhýbá použití lineárních posuvných registrů a je ideální pro implementaci v softwaru, protože vyžaduje pouze bajtovou manipulaci.

Testovací vektory
Testovací vektory nejsou oficiální, ale jsou používány pro testování implementace RC4. Klíče a Text jsou v ASCII, zašifrovaný řetězec je v šestnáctkové soustavě (HEX).

Klíč Keystream Text Zašifrováno
Key eb9f7781b734ca72a719... Plaintext BBF316E8D940AF0AD3
Wiki 6044db6d41b7... pedia 1021BF0420
Secret 04d46b053ca87b59... Attack at dawn 45A01F645FC35B383552544B9BF5
Použití RC4
WEP
WPA (výchozí algoritmus, přenastavením může být nahrazen algoritmem AES-CCMP)
BitTorrent protokol šifrování
Microsoft Point-to-Point šifrování
Secure Sockets Layer (volitelně)
Secure shell (volitelně)
Remote Desktop Protocol
Kerberos (volitelně)
PDF
Skype (v modifikaci)