RC5 — szyfr blokowy Rivesta (algorytm 1994, parametry i rotacje)

RC5 – przegląd szyfru blokowego Rivesta (1994): parametry, zmienne rozmiary bloku i klucza, liczba rund oraz innowacyjne rotacje zależne od danych. Zrozum działanie i bezpieczeństwo.

W kryptografii RC5 jest prostym, ale elastycznym szyfrem z symetrycznym kluczem blokowym. Zaprojektował go Ronald Rivest w 1994 roku. RC5 to sparametryzowany algorytm: użytkownik może dobierać wielkość bloku, długość klucza oraz liczbę rund, co pozwala dopasować kompromis między bezpieczeństwem a wydajnością. Skrót „RC” pochodzi od „Rivest Cipher” (lub potocznie „Ron's Code”).

Parametry i notacja

RC5 jest zwykle notowany jako RC5-w/r/b, gdzie:

• w — rozmiar słowa w bitach (zwykle 16, 32 lub 64),
• r — liczba rund (0–255),
• b — długość klucza w bajtach (0–255; czyli do 2040 bitów).

Dzięki temu algorytm można dostosować np. jako RC5-32/12/16 (słowo 32-bitowe, 12 rund, klucz 16 bajtów = 128 bitów) — konfiguracja pierwotnie sugerowana przez autora dla typowych zastosowań.

Podstawowe operacje

RC5 opiera się na trzech prostych operacjach wykonywanych na słowach o długości w bitów:

• dodawanie modulo 2^w,
• operator XOR (eXclusive OR),
• cykliczne rotacje o zmiennym przesunięciu, przy czym ilość rotacji zależy od zawartości słowa — stąd nazwa „rotacje zależne od danych”.

Ogólna struktura algorytmu to sieć typu Feistel, a prostota tych operacji powoduje, że implementacja szyfrowania i deszyfrowania zajmuje tylko kilka linii kodu w większości języków programowania.

Szyfrowanie i deszyfrowanie — skrótowy opis

Blok danych dzielony jest na dwie zmienne A i B, każda długości w bitów. Tablica rundowa S ma 2(r+1) słów. Schemat szyfrowania (skrótowo):

• A = A + S[0]; B = B + S[1];
• dla i = 1 do r:
  • A = ((A XOR B) <<< (B mod w)) + S[2*i];
  • B = ((B XOR A) <<< (A mod w)) + S[2*i+1];

Deszyfrowanie wykonuje odwrotne operacje w odwrotnej kolejności (odejmowanie zamiast dodawania, rotacje w prawo zamiast w lewo oraz XOR jak poprzednio).

Schemat rozszerzania klucza (key schedule)

Rozszerzanie klucza w RC5 tworzy tablicę słów S, która jest używana podczas rund. Procedura w skrócie:

• Podziel bajty sekretnego klucza na słowa L[0..c-1] o długości w bitów (c = ceil(8*b/w)).
• Zainicjuj tablicę S długości t = 2*(r+1): S[0] = P_w; dla i=1..t-1: S[i] = S[i-1] + Q_w (wszystko modulo 2^w).
• Wymieszaj S i L wykonując 3 * max(t, c) iteracji, w każdej iteracji aktualizując S[i] i L[j] poprzez dodanie i rotację — to zapewnia rozproszenie (diffusion) klucza do tablicy rundowej.

Stałe P_w i Q_w są dziwnymi (nieparzystymi) wartościami pochodzącymi z ułamkowych części e i złotej proporcji; przykładowe wartości:

• dla w = 16: P_w = 0xB7E1, Q_w = 0x9E37,
• dla w = 32: P_w = 0xB7E15163, Q_w = 0x9E3779B9,
• dla w = 64: P_w = 0xB7E151628AED2A6B, Q_w = 0x9E3779B97F4A7C15.

Właściwości i zalety

• Elastyczność parametrów (w, r, b) umożliwia dopasowanie algorytmu do różnych środowisk sprzętowych i wymagań bezpieczeństwa.
• Prosta implementacja — tylko podstawowe operacje arytmetyczne i bitowe, dzięki czemu RC5 jest szybki na CPU i łatwy do implementacji w sprzęcie.
• Innowacyjne użycie rotacji zależnych od danych, co zwiększa złożoność analityczną i dało inspirację do dalszych badań w kryptografii (np. RC6).

Bezpieczeństwo i znane ataki

RC5 był intensywnie badany przez kryptografów. Kilka ważnych uwag:

• Pełna siła systemu zależy od dobranych parametrów — krótsze klucze i mała liczba rund ułatwiają ataki (w tym brute-force i analizy różnicowe).
• Na zredukowane liczby rund znaleziono skuteczne ataki kryptanalizy różnicowej i inne techniki; z tego powodu liczba rund r powinna być dobrana ostrożnie. Dla powszechnie używanych parametrów (np. RC5-32/12/16) nie ma publicznego, praktycznego złamania całego algorytmu, ale analiza teoretyczna pokazuje słabości dla mniejszych r.
• Rotacje zależne od danych wprowadziły nowe techniki ataków (np. analizy wykorzystujące częściowe właściwości rotacji), co z kolei spowodowało dalsze badania i powstanie wariantów algorytmów blokowych.

W praktyce bezpieczeństwo RC5 należy oceniać w kontekście wybranych parametrów i wymagań systemu; dla krytycznych zastosowań zaleca się stosowanie sprawdzonych, aktualnych standardów kryptograficznych oraz dłuższych kluczy i większej liczby rund.

Zastosowania, patent i rozwinięcia

RC5 był używany w różnych bibliotekach kryptograficznych oraz protokołach. Algorytm był opatentowany przez firmę RSA Security, co przez pewien czas ograniczało jego swobodne wykorzystywanie w niektórych projektach; przed użyciem w nowych rozwiązaniach warto sprawdzić aktualny status licencji i patentów.

Na bazie RC5 powstał m.in. RC6 — rozszerzenie i modyfikacja zgłoszona w kontekście konkursu na standard AES, które dodało m.in. mnożenie słów i dodatkowe rejestry, jednocześnie zachowując ideę rotacji zależnych od danych.

Podsumowanie

RC5 to prosty i elastyczny szyfr blokowy zaprojektowany do eksperymentów i badań nad konstrukcją szyfrów. Jego największą cechą rozpoznawczą są rotacje zależne od danych oraz konfigurowalność parametrów (w, r, b). Dzięki temu RC5 dostarczył cennych obserwacji dla społeczności kryptograficznej i wpłynął na projekt kolejnych algorytmów, chociaż intensywna analiza wykazała, że bezpieczeństwo zależy wyraźnie od doboru parametrów.

Pytania i odpowiedzi

P: Co to jest RC5?

P: Co oznacza skrót "RC"?

P: Jakie są parametry RC5?

P: Jaka jest ogólna struktura algorytmu?

P: Jak bardzo złożony jest harmonogram klucza?

P: Dlaczego RC5 jest atrakcyjny dla kryptoanalityków?

Szukaj według litery