RC4
Опште | |
---|---|
Пројектант(и) | Роналд Ривест (RSA Security) |
Датум објаве | процурела 1994.(дизајнирана 1987) |
Детаљи шифре | |
Величина кључа | 40–7003204800000000000♠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 протокола
- Skype (у модификованом облику)
- Kerberos (опционо)
Код криптосистема означених са „(опционо)“, RC4 је једна од неколико шифара која се може користити на том систему.
Референце
Литература
- М. Живковић, Криптографија, Математички факултет Београд, Београд, април 2012
- Д. Ламбић, Курс криптографије, Учитељски факултет Сомбор, Сомбор, 2012
Спољашње везе
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- Original posting of RC4 algorithm to Cypherpunks mailing list, Archived version
- IETF Draft - A Stream Cipher Encryption Algorithm "Arcfour"
- RC4 Implementation in Delphi