RC4

proudová šifra

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

editovat

Šifru RC4 navrhl Ron Rivest z RSA Security v roce 1987. RC4 byla původně obchodním tajemstvím, 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.

Š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ří:

  1. pole bajtů o délce 256 (S)
  2. 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

editovat

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í

editovat
 
Vyhledávací cyklus RC4.

Generátor mění svůj stav a produkuje bajty keystreamu. V každé iteraci generátor inkrementuje i; hodnotu S s indexem i přičte do 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 cyklu je prvek S s indexem S[i]+S[j] (všechny inkrementace a součty 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

editovat

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

editovat

Testovací vektory nejsou oficiální, ale lze je použít pro otestová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
\0 de188941a3375d3a8a061e67576e926d... \0\0\0\0\0\0\0\0 DE188941A3375D3A
Key eb9f7781b734ca72a7194a2867b64295... Plaintext BBF316E8D940AF0AD3
Wiki 6044db6d41b7e8e7a4d6f9fbd4428354... pedia 1021BF0420
Secret 04d46b053ca87b594172302aec9bb992... Attack at dawn 45A01F645FC35B383552544B9BF5

Použití RC4

editovat

U příkladů označených „(volitelně)“, je RC4 šifrování jednou z možných šifer, které lze použít.

Reference

editovat
  1. Skype's encryption procedure partly exposed [online]. www.h-online.com [cit. 2010-07-08]. Dostupné online. 

V tomto článku byl použit překlad textu z článku RC4 na anglické Wikipedii.