RC4
 | Ovaj članak je započet ili proširen kroz projekat seminarskih radova. Potrebno je proveriti prevod, pravopis i viki-sintaksu. Kada završite sa proverom, dopišete da nakon |provereno=. |
| Opšte | |
|---|---|
| Projektant(i) | Ronald Rivest (RSA Security) |
| Datum objave | procurela 1994.(dizajnirana 1987) |
| Detalji šifre | |
| Veličina ključa | 40–2048 bitova |
RC4 je jedna od najpopularnijih protočnih šifara. Koristi se u popularnim protokolima kao što su: TLS (za zaštitu internet saobraćaja) i WEP (za zaštitu bežičnih mreža). Iako je ova šifra popularna zbog svoje jednostavnosti i brzine, ona poseduje i neke nedostatke zbog kojih je njena upotreba u novijim sistemima dovedena u pitanje.
Počev od 2013. godine, pojavile su se spekulacije, da je RC4 šifru moguće razbiti čak i kada se koristi u TLS protokolu, zbog čega je preporuka Microsoft-a da se RC4 onemogući kad god je to moguće.[1]
Istorija
[uredi | uredi izvor]RC4 je dizajnirao Ronald Rivest, 1987. godine. Šifra je držana u tajnosti sve do septembra 1994. godine, kada je njen izvorni kod anonimno postavljen na Cypherpunks mejling listu[2]. Ubrzo je izvorni kod postavljen i na sci.crypt diskusionu grupu, odakle je pronašao put do mnogih internet sajtova.
Vremenom, RC4 je pronašao svoju primenu u protokolima poput TLS-a i WEP protokola.
Opis algoritma
[uredi | uredi izvor]RC4 generiše niz pseudo-slučajnih bitova. Generisani niz bitova, naziva se niz ključa (engl. keystream) i u kombinaciji sa otvorenim tekstom (engl. plaintext) daje šifrovanu poruku (engl. ciphertext). Šifrovanje(engl. encryption) se vrši primenom operacije eksluzivne disjunkcije (XOR) na generisani niz bitova i otvoreni tekst. Dešifrovanje (engl. decryption) se takođe vrši primenom eksluzivne disjunkcije (korišćenjem generisanog niza bitova i šifrovanog teksta), jer operacija XOR na ovako zadatom skupu podataka predstavlja involuciju.
Generisanje niza bitova, sastoji se iz dva koraka. Najpre se bira broj n (obično se uzima da je n=8). Zatim se pravi niz od 2n brojeva, koji predstavlja identičku permutaciju. U drugom koraku, korišćenjem ključa vrši se premeštanje elemenata početnog niza, čime se dobija niz S0, S1,...,S2n-1, koji je permutacija skupa {0,1,...2n-1}. Koristeći algoritam za generisanje pseudo-slučajnih brojeva (engl. Pseudo-random generation algorithm), iz dobijene permutacije, dobija se pseudo-slučajni niz brojeva, koji predstavlja niz ključa.
Algoritam koji od početne(identičke) permutacije, promenom redosleda elemenata, pravi permutaciju iz koje se dobija pseudo-slučajni niz brojeva, naziva se key-scheduling algoritmom.
Da bi se formirao traženi niz (niz ključa), najpre se stavi Si=i, za i=0,1,...,2n-1. Zatim se od polaznog ključa, formira niz od 2n n-torki bitova, za koje takođe smatramo da se nalaze u intervalu od 0 do 2n-1. Ključ se po potrebi periodično ponavlja, sve dok ne popuni niz: K0, K1,...,K2n-1. Primenom RC4 algoritma na ovako izabran skup podataka, dobijamo niz ključa kojim šifrujemo otvoreni tekst.
Dužina ključa, koji se koristi za dobijanje permutacije, obično je između 40 i 256 bita.
Prikaz key-scheduling algoritma
[uredi | uredi izvor]Niz S se najpre inicijalizuje na identičku permutaciju, a zatim se članovi niza S premeštaju po principu koji nalikuje osnovnom algoritmu za generisanje pseudo-slučajnih brojeva. Algoritam za generisanje pseudo-slučajnih brojeva, će biti prikazan u svom izvornom obliku nešto kasnije, jer je i on deo RC4 алгоритма.
for i=0 to 2n-1 do //generisanje identičke permutacije
S[i] := i
endfor
j := 0 //inicijalizacija brojača
for i=0 to 2n-1 do
j:= j + S[i] + K[i] (mod 2n)
zameni S[i] i S[j]
endfor
Приказ алгоритма за генерисање псеудо-случајних бројева
[uredi | uredi izvor]i:=0; j:=0 //inicijalizacija brojača for r=0 to l-1 do //generisanje l slučajnih bitova i := i+1 (mod 2n) j := j+S[i] (mod 2n) zameni S[i] i S[j] t := S[i] + S[j](mod 2n) vrati S[t] //S[t] je deo pseudo-slučajnog niza bitova koji se koristi za šifrovanje endfor
Улога индекса i i j u prikazanim algoritmima
[uredi | uredi izvor]Uloga indeksa i je da obezbedi da se svaki član niza S promeni bar jednom, dok indeks j obezbeđuje da se elementi menjaju na slučajan način.
Primer
[uredi | uredi izvor]Za potrebe prikaza rada ovog algoritma, uzećemo da je n=3, l=12 i neka je naš ključ 011001100001101. Kako je n=3, niz kojim je zadat ključ delimo u grupe od po 3 cifre: 011 001 100 001 101. Kada se dati ključ prevede u dekadni sistem, njegove vrednosti (respektivno) su: 3, 1, 4, 1, 5. Kako naš niz ima 23=8 elemenata, potrebno je da ključ proširimo periodično do dužine 8 i na taj način dobijamo niz: 3, 1, 4, 1, 5, 3, 1, 4.
[K0, K1, K2, K3, K4, K5, K6, K7] = [3, 1, 4, 1, 5, 3, 1, 4]
| i | j | t | St | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||
| 0 | 3 | 3 | 1 | 2 | 0 | 4 | 5 | 6 | 7 | ||
| 1 | 5 | 3 | 5 | 2 | 0 | 4 | 1 | 6 | 7 | ||
| 2 | 3 | 3 | 5 | 0 | 2 | 4 | 1 | 6 | 7 | ||
| 3 | 6 | 3 | 5 | 0 | 6 | 4 | 1 | 2 | 7 | ||
| 4 | 7 | 3 | 5 | 0 | 6 | 7 | 1 | 2 | 4 | ||
| 5 | 3 | 3 | 5 | 0 | 1 | 7 | 6 | 2 | 4 | ||
| 6 | 6 | 3 | 5 | 0 | 1 | 7 | 6 | 2 | 4 | ||
| 7 | 6 | 3 | 5 | 0 | 1 | 7 | 6 | 4 | 2 | ||
| 0 | 0 | 3 | 5 | 0 | 1 | 7 | 6 | 4 | 2 | ||
| 1 | 5 | 3 | 1 | 3 | 6 | 0 | 1 | 7 | 5 | 4 | 2 |
| 2 | 5 | 5 | 0 | 3 | 6 | 5 | 1 | 7 | 0 | 4 | 2 |
| 3 | 6 | 5 | 0 | 3 | 6 | 5 | 4 | 7 | 0 | 1 | 2 |
| 4 | 5 | 7 | 2 | 3 | 6 | 5 | 4 | 0 | 7 | 1 | 2 |
| 5 | 4 | 7 | 2 | 3 | 6 | 5 | 4 | 7 | 0 | 1 | 2 |
| 6 | 5 | 1 | 6 | 3 | 6 | 5 | 4 | 7 | 1 | 0 | 2 |
| 7 | 7 | 4 | 7 | 3 | 6 | 5 | 4 | 7 | 1 | 0 | 2 |
| 0 | 2 | 0 | 5 | 5 | 6 | 3 | 4 | 7 | 1 | 0 | 2 |
| 1 | 0 | 3 | 4 | 6 | 5 | 3 | 4 | 7 | 1 | 0 | 2 |
| 2 | 3 | 7 | 2 | 6 | 5 | 4 | 3 | 7 | 1 | 0 | 2 |
| 3 | 6 | 3 | 0 | 6 | 5 | 4 | 0 | 7 | 1 | 3 | 2 |
| 4 | 5 | 0 | 6 | 6 | 5 | 4 | 0 | 1 | 7 | 3 | 2 |
Kao rezultat, dobija se niz St čije su vrednosti elemenata: 1, 0, 0, 2, 2, 6, 7, 5, 4, 2, 0, 6. Dobijeni niz brojeva, predstavimo u binarnom obliku (reprezentacija sa 3 bita): 001, 000, 000, 010, 010, 110, 111, 101, 100, 010, 000, 110. Niz ključa, dobija se spajanjem dobijenih binarnih brojeva (onim redom kojim su navedeni) i u ovom slučaju je: 001000000010010110111101100010000110. Uz pomoć dobijenog ključa i primenom operacije XOR, šifruje se binarna reprezentacija otvorenog teksta.
Primene RC4
[uredi | uredi izvor]- WEP
- TLS / SSL (opciono)
- enkripcija BitTorrent protokola
- Skype (u modifikovanom obliku)
- Kerberos (opciono)
Kod kriptosistema označenih sa „(opciono)“, RC4 je jedna od nekoliko šifara koja se može koristiti na tom sistemu.
Reference
[uredi | uredi izvor]- ^ „Security Advisory 2868725: Recommendation to disable RC4. Microsoft.”. 12. 11. 2013. Arhivirano iz originala 18. 11. 2013. g. Pristupljeno 7. 1. 2014.
- ^ „Thank you Bob Anderson”. 9. 9. 1994. Arhivirano iz originala 04. 04. 2008. g. Pristupljeno 8. 1. 2014.
Literatura
[uredi | uredi izvor]- M. Živković, Kriptografija, Matematički fakultet Beograd, Beograd, april 2012
- D. Lambić, Kurs kriptografije, Učiteljski fakultet Sombor, Sombor, 2012
