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. Приступљено 8. 1. 2014. 

Литература[уреди | уреди извор]

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

Спољашње везе[уреди | уреди извор]