RC5
Ten artykuł dotyczy kryptografii. Zobacz też: RC5 (RTV). |
Runda algorytmu RC5 | |
Rodzaj algorytmu | symetryczny szyfr blokowy |
---|---|
Data stworzenia | 1994 |
Autorzy | Ron Rivest |
Wielkość bloku wejściowego | 32, 64, 128 [bit] |
Długość klucza | 0 do 2040 [bit] |
Liczba rund | 1 do 255 |
RC5 – szybki szyfr blokowy opracowany przez Ronalda Rivesta w 1994 roku, dla RSA Security. RC5 nie jest kolejną wersją algorytmu RC4, który jest szyfrem strumieniowym szyfrującym pojedyncze bajty, a nie całe bloki. Natomiast RC6 jest ulepszoną wersją RC5. Tak więc RC5 i RC4 niewiele mają wspólnego poza nazwą i ich autorem. RC jest skrótem od Rivest Cipher lub stosowanym zamiennie Ron’s Code.
RC5 stosuje zmienną długość bloków (32, 64 lub 128 bitów), kluczy (od 0 do 2040 bitów) oraz liczbę rund (od 1 do 255).
Algorytm
Zarówno przy szyfrowaniu, jak i odszyfrowywaniu następuje rozszerzenie losowego klucza na 2(r+1) wyrazów, które będą kolejno użyte w procesie szyfrowania i odszyfrowywania (każdy z nich zostanie użyty tylko raz).
Rozszerzenie klucza
Poniżej przedstawiono algorytm rozszerzenia klucza (zarówno w pseudokodzie, jak i w języku C).
Używane są następujące zmienne[1]:
- w – Długość słowa wyrażona w bitach, wynosi przeważnie 16, 32 lub 64. Szyfrowanie odbywa się za pomocą dwuwyrazowych bloków.
- u = w/8 – Długość słowa, wyrażona w bajtach.
- b – Długość klucza, wyrażona w bajtach.
- K[] – Klucz, rozważany jako tablica bajtów (przy indeksowaniu rozpoczynającym się od 0.)
- c – Długość klucza, wyrażona w ilości słów (wynosi 1, jeżeli b = 0).
- L[] – Tymczasowa tablica robocza używana do tzw. mechanizmu „Key schedule”. Zawiera tyle elementów, z ilu słów składa się klucz.
- r – Liczba rund, które odbędą się podczas szyfrowania danych
- t = 2(r+1) – liczba podkluczy rund.
- S[] – Wyrazy podklucza rundy.
- Pw – Pierwsza stała magiczna, definiowana jako gdzie Np oznacza najbliższą nieparszystą liczbę względem danych wejściowych, e jest liczbą Eulera, w jest zdefiniowane powyżej.
Dla wspólnych wartości w, powiązane wartości Pw przedstawiono w zapisie szesnastkowym:
- Dla w = 16: 0xB7E1
- Dla w = 32: 0xB7E15163
- Dla w = 64: 0xB7E151628AED2A6B
- Qw – Druga stała magiczna, definiowana jako gdzie Np oznacza najbliższą nieparszystą liczbę względem danych wejściowych,
oznacza Złoty podział, w zdefiniowano powyżej. Dla wspólnych wartości w, powiązane wartości Qw przedstawiono w zapisie szesnastkowym:
- Dla w = 16: 0x9E37
- Dla w = 32: 0x9E3779B9
- Dla w = 64: 0x9E3779B97F4A7C15
# "Rozbijanie" klucza K na słowa # u = w / 8 c = ceiling( max(b, 1) / u ) # L jest początkowo listą o długości c, składającą się z wyrazów o długości w for i = b-1 down to 0 do: L[i/u] = (L[i/u] << 8) + K[i] # Inicjacja niezależnej od klucza, pseudolosowej tablicy S # S jest początkowo listą o długości t=2(r+1) zawierającą niezdefiniowane słowa o długości w S[0] = P_w for i = 1 to t-1 do: S[i] = S[i-1] + Q_w # Główna pętla mechanizmu "key scheduling" i = j = 0 A = B = 0 do 3 * max(t, c) times: A = S[i] = (S[i] + A + B) <<< 3 B = L[j] = (L[j] + A + B) <<< (A + B) i = (i + 1) % t j = (j + 1) % c # return S
W poniższym kodzie używane są następujące wartości zmiennych: w = 32, r = 12, oraz b = 16.
void RC5_SETUP(unsigned char *K) { // w = 32, r = 12, b = 16 // c = max(1, ceil(8 * b/w)) // t = 2 * (r+1) WORD i, j, k, u = w/8, A, B, L[c]; for(i = b-1, L[c-1] = 0; i != -1; i--) L[i/u] = (L[i/u] << 8) + K[i]; for(S[0] = P, i = 1; i < t; i++) S[i] = S[i-1] + Q; for(A = B = i = j = k = 0; k < 3 * t; k++, i = (i+1) % t, j = (j+1) % c) { A = S[i] = ROTL(S[i] + (A + B), 3); B = L[j] = ROTL(L[j] + (A + B), (A + B)); } }
Szyfrowanie
Szyfrowanie składa się z kilku rund prostej funkcji. Zaleca się sotsowanie 12 lub 20 rund, w zależności od oczekiwanego poziomu bezpieczeństwa i czasu. Poza parametrami zdeifiniowanymi powyżej, w przedstawionym algorytmie wykorzystuje się również następujące zmienne:
- A, B – Dwa słowa, tworzące blok tekstu jawnego, poddawanego szyfrowaniu
A = A + S[0] B = B + S[1] for i = 1 to r do: A = ((A ^ B) <<< B) + S[2 * i] B = ((B ^ A) <<< A) + S[2 * i + 1] # Szyfrogram zawiera dwuwyrazowy blok, składający się kolejno ze słów: A oraz B. return A, B
Przykład w języku C:
void RC5_ENCRYPT(WORD *pt, WORD *ct) { WORD i, A = pt[0] + S[0], B = pt[1] + S[1]; for(i = 1; i <= r; i++) { A = ROTL(A ^ B, B) + S[2*i]; B = ROTL(B ^ A, A) + S[2*i + 1]; } ct[0] = A; ct[1] = B; }
Odszyfrowywanie
Odszyfrowywanie jest stosunkowo prostym odwróceniem procesu szyfrowania, co przedstawiono w poniższym pseudokodzie:
for i = r down to 1 do: B = ((B - S[2 * i + 1]) >>> A) ^ A A = ((A - S[2 * i]) >>> B) ^ B B = B - S[1] A = A - S[0] return A, B
Przykład w języku C:
void RC5_DECRYPT(WORD *ct, WORD *pt) { WORD i, B=ct[1], A=ct[0]; for(i = r; i > 0; i--) { B = ROTR(B - S[2*i + 1], A) ^ A; A = ROTR(A - S[2*i], B) ^ B; } pt[1] = B - S[1]; pt[0] = A - S[0]; }
Zobacz też
- RC2
- RC4
- RC6
- Distributed.net
Przypisy
- ↑ http://people.csail.mit.edu/rivest/Rivest-rc5rev.pdf
Linki zewnętrzne
- RSA Laboratories FAQ: What are RC5 and RC6?. rsasecurity.com. [zarchiwizowane z tego adresu (2006-12-29)].
- The RC Encryption Algorithm – Ronald L. Rivest, 20 March 1997