img062 (8)

296 ROZDZIAŁ 7. / GENERATORY LICZB PSEUDOLOSOWYCH I SZYFRY STRUMIENI*.

(pseudo)losowe permutacje. Jak wykazuje M. Robshaw w publikacji [RO okres generowanego ciągu z dużym prawdopodobieństwem przekracza tość lO¹⁰⁰. Na każdy przetwarzany bajt przypada od ośmiu do szesnastu pe cji, a szyfr daje się efektywnie implementować w sposób programowy.

RC4 stanowi podstawę protokołu SSL/TLS (Secure Sockets Layer/Tr Layer Security), który jest obecnie standardowym protokołem komunikacji glądarek z serwerami WWW. Wykorzystywany jest także przez protokoły (Wired Equivalent Privacy) i nowszy protokół WPA (WiFi Protected Access) są elementami standardu bezprzewodowych lokalnych IEEE 802.11.

Od momentu wynalezienia RC4 jego algorytm utrzymywany był w taje jako sekret handlowy firmy RSA Security. We wrześniu 1994 roku algon opublikowany został na liście dyskusyjnej Cypherpunks przez anonim nadawcę i tajemnica tajemnicą być przestała.

Algorytm RC4 jest nadzwyczaj prosty i łatwy do wyjaśnienia. Klucz o zr długości — od 1 do 256 bajtów — wykorzystywany jest do zainicjowania w* stanu S[0], ..., S[255], S[i] ma rozmiar 8-bitowego bajtu. W każdej chwili tor S zawiera permutację ciągu (0, 1, ..., 255). W czasie szyfrowania i des wektor S wykorzystywany jest do generowania pseudolosowej wartości k rysunek 7.5) przez wybór jednej z pozycji S[i] zgodnie z pewnym systematy schematem. Po dokonaniu tego wyboru wektor Sjest permutowany.

Inicjacja wektora S

Działanie algorytmu rozpoczyna się od zainicjowania wektora S rosn wartościami od 0 do 255 (S[i] = i, i = 0, 1, ..., 255. Tworzony jest także sowy 256-bajtowy wektor T. Jeśli klucz K jest 256-bajtowy, transferowany wprost do wektora T; krótszy klucz powtarzany jest cyklicznie aż do wypeł całego wektora S. Scenariusz ten można zapisać następująco (keylen oz^-długość klucza):

/* Inicjacja */

for i := 0 to 255 do

{

S [i] = i;

T[i] = K[ i mod keylen ];

1

Kolejnym krokiem jest wykonanie wstępnej permutacji wektora S. Kol pozycje, począwszy od S[0], zamieniane są z innymi pozycjami zgodnie ze matem wyznaczonym przez wektor T:

/* Wstępna permutacja */

i - o

for 1 = 0 to 255 do

1

j = (j + S[l] + T[i]) mod 256;

Zamień S[1] z S[j] ;

}

Ponieważ jedyną operacją wykonywaną na wektorze S jest zamiana element w dalszym ciągu zawiera on permutację ciągu (0, 1, ..., 255).