Пређи на садржај

RC4

С Википедије, слободне енциклопедије
RC4
Опште
Пројектант(и)Роналд Ривест (RSA Security)
Датум објавепроцурела 1994.(дизајнирана 1987)
Детаљи шифре
Величина кључа40–2048 битова

RC4 је једна од најпопуларнијих проточних шифара. Користи се у популарним протоколима као што су: TLS (за заштиту интернет саобраћаја) и WEP (за заштиту бежичних мрежа). Иако је ова шифра популарна због своје једноставности и брзине, она поседује и неке недостатке због којих је њена употреба у новијим системима доведена у питање.

Почев од 2013. године, појавиле су се спекулације, да је RC4 шифру могуће разбити чак и када се користи у TLS протоколу, због чега је препорука Microsoft-a да се RC4 онемогући кад год је то могуће.[1]

Историја

[уреди | уреди извор]

RC4 је дизајнирао Роналд Ривест, 1987. године. Шифра је држана у тајности све до септембра 1994. године, када је њен изворни код анонимно постављен на Cypherpunks мејлинг листу[2]. Убрзо је изворни код постављен и на sci.crypt дискусиону групу, одакле је пронашао пут до многих интернет сајтова.

Временом, RC4 је пронашао своју примену у протоколима попут TLS-а и WEP протокола.

Опис алгоритма

[уреди | уреди извор]

RC4 генерише низ псеудо-случајних битова. Генерисани низ битова, назива се низ кључа (engl. keystream) и у комбинацији са отвореним текстом (engl. plaintext) даје шифровану поруку (engl. ciphertext). Шифровање(engl. encryption) се врши применом операције екслузивне дисјункције (XOR) на генерисани низ битова и отворени текст. Дешифровање (engl. decryption) се такође врши применом екслузивне дисјункције (коришћењем генерисаног низа битова и шифрованог текста), јер операција XOR на овако задатом скупу података представља инволуцију.

Генерисање низа битова, састоји се из два корака. Најпре се бира број n (обично се узима да је n=8). Затим се прави низ од 2n бројева, који представља идентичку пермутацију. У другом кораку, коришћењем кључа врши се премештање елемената почетног низа, чиме се добија низ S0, S1,...,S2n-1, који је пермутација скупа {0,1,...2n-1}. Користећи алгоритам за генерисање псеудо-случајних бројева (engl. Pseudo-random generation algorithm), из добијене пермутације, добија се псеудо-случајни низ бројева, који представља низ кључа.

Алгоритам који од почетне(идентичке) пермутације, променом редоследа елемената, прави пермутацију из које се добија псеудо-случајни низ бројева, назива се key-scheduling алгоритмом.

Да би се формирао тражени низ (низ кључа), најпре се стави Si=i, за i=0,1,...,2n-1. Затим се од полазног кључа, формира низ од 2n n-торки битова, за које такође сматрамо да се налазе у интервалу од 0 до 2n-1. Кључ се по потреби периодично понавља, све док не попуни низ: K0, K1,...,K2n-1. Применом RC4 алгоритма на овако изабран скуп података, добијамо низ кључа којим шифрујемо отворени текст.

Дужина кључа, који се користи за добијање пермутације, обично је између 40 и 256 бита.

Приказ key-scheduling алгоритма

[уреди | уреди извор]

Низ S се најпре иницијализује на идентичку пермутацију, а затим се чланови низа S премештају по принципу који наликује основном алгоритму за генерисање псеудо-случајних бројева. Алгоритам за генерисање псеудо-случајних бројева, ће бити приказан у свом изворном облику нешто касније, јер је и он део 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

Приказ алгоритма за генерисање псеудо-случајних бројева

[уреди | уреди извор]
 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 и j у приказаним алгоритмима

[уреди | уреди извор]

Улога индекса i је да обезбеди да се сваки члан низа S промени бар једном, док индекс j обезбеђује да се елементи мењају на случајан начин.

За потребе приказа рада овог алгоритма, узећемо да је n=3, l=12 и нека је наш кључ 011001100001101. Како је n=3, низ којим је задат кључ делимо у групе од по 3 цифре: 011 001 100 001 101. Када се дати кључ преведе у декадни систем, његове вредности (респективно) су: 3, 1, 4, 1, 5. Како наш низ има 23=8 елемената, потребно је да кључ проширимо периодично до дужине 8 и на тај начин добијамо низ: 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

Као резултат, добија се низ St чије су вредности елемената: 1, 0, 0, 2, 2, 6, 7, 5, 4, 2, 0, 6. Добијени низ бројева, представимо у бинарном облику (репрезентација са 3 бита): 001, 000, 000, 010, 010, 110, 111, 101, 100, 010, 000, 110. Низ кључа, добија се спајањем добијених бинарних бројева (оним редом којим су наведени) и у овом случају је: 001000000010010110111101100010000110. Уз помоћ добијеног кључа и применом операције XOR, шифрује се бинарна репрезентација отвореног текста.

Примене RC4

[уреди | уреди извор]
  • WEP
  • TLS / SSL (опционо)
  • енкрипција BitTorrent протокола
  • PDF
  • Skype (у модификованом облику)
  • Kerberos (опционо)

Код криптосистема означених са „(опционо)“, RC4 је једна од неколико шифара која се може користити на том систему.

Референце

[уреди | уреди извор]
  1. ^ „Security Advisory 2868725: Recommendation to disable RC4. Microsoft.”. 12. 11. 2013. Архивирано из оригинала 18. 11. 2013. г. Приступљено 7. 1. 2014. 
  2. ^ „Thank you Bob Anderson”. 9. 9. 1994. Архивирано из оригинала 04. 04. 2008. г. Приступљено 8. 1. 2014. 

Литература

[уреди | уреди извор]
  • М. Живковић, Криптографија, Математички факултет Београд, Београд, април 2012
  • Д. Ламбић, Курс криптографије, Учитељски факултет Сомбор, Сомбор, 2012

Спољашње везе

[уреди | уреди извор]