RC5 - RC5

RC5
RC5 InfoBox Diagram.svg
Jedna runda (dwie połówki) szyfru blokowego RC5
Ogólny
Projektanci Ron Rivest
Opublikowane po raz pierwszy 1994
Następcy RC6 , Akelarre
Szczegóły szyfru
Kluczowe rozmiary 0 do 2040 bitów (sugerowane 128)
Rozmiary bloków 32, 64 lub 128 bitów (sugerowane 64)
Struktura Sieć podobna do Feistela
Rundy 1-255 (12 sugerowanych pierwotnie)
Najlepsza publiczna kryptoanaliza
12-rundowy RC5 (z blokami 64-bitowymi) jest podatny na atak różnicowy przy użyciu 2 44 wybranych tekstów jawnych.

W kryptografii , RC5 jest symetryczny klucz szyfr blokowy wyróżnia się prostotą. Zaprojektowany przez Ronalda Rivesta w 1994 roku, RC oznacza „Rivest Cipher” lub alternatywnie „Ron's Code” (porównaj RC2 i RC4 ). Advanced Encryption Standard (AES) kandydat RC6 oparto na RC5.

Opis

W przeciwieństwie do wielu schematów, RC5 ma zmienny rozmiar bloku (32, 64 lub 128 bitów ), rozmiar klucza (0 do 2040 bitów) i liczbę rund (0 do 255). Pierwotny sugerowany wybór parametrów to 64-bitowy rozmiar bloku, 128-bitowy klucz i 12 rund.

Kluczową cechą RC5 jest wykorzystanie rotacji zależnych od danych; jednym z celów RC5 było zachęcenie do badania i oceny takich operacji, jak prymityw kryptograficzny . RC5 składa się również z szeregu modułowych dodatków i eXclusive OR (XOR) . Ogólna struktura algorytmu to sieć podobna do Feistela . Procedury szyfrowania i deszyfrowania można określić w kilku wierszach kodu. Jednak harmonogram kluczy jest bardziej złożony, rozszerzając klucz za pomocą zasadniczo jednokierunkowej funkcji z rozwinięciami binarnymi zarówno e, jak i złotego podziału jako źródeł „ nic w rękawie ”. Kusząca prostota algorytmu wraz z nowatorstwem rotacji zależnych od danych uczyniła RC5 atrakcyjnym obiektem badań dla kryptoanalityków. RC5 jest zasadniczo oznaczany jako RC5-w/r/b, gdzie w=rozmiar słowa w bitach, r=liczba rund, b=liczba 8-bitowych bajtów w kluczu.

Algorytm

Szyfrowanie i deszyfrowanie RC5 rozszerzają losowy klucz na 2 (r+1) słowa, które będą używane sekwencyjnie (i tylko raz każde) podczas procesów szyfrowania i deszyfrowania. Wszystkie poniższe informacje pochodzą z poprawionego artykułu Rivesta na temat RC5.

Rozszerzenie klucza

Algorytm rozwijania klucza jest zilustrowany poniżej, najpierw w pseudokodzie, a następnie w przykładowym kodzie C skopiowanym bezpośrednio z dodatku do artykułu referencyjnego.

Zgodnie ze schematem nazewnictwa artykułu stosuje się następujące nazwy zmiennych:

  • w - Długość słowa w bitach, zwykle 16, 32 lub 64. Szyfrowanie odbywa się w blokach po 2 słowa.
  • u = w/8 - Długość słowa w bajtach.
  • b - Długość klucza w bajtach.
  • K[] — klucz, traktowany jako tablica bajtów (przy użyciu indeksowania od 0).
  • c - Długość klucza w słowach (lub 1, jeśli b = 0).
  • L[] - Tymczasowa tablica robocza używana podczas planowania kluczy. zainicjowane do klucza słowami.
  • r — liczba rund do użycia podczas szyfrowania danych.
  • t = 2(r+1) - liczba wymaganych okrągłych podkluczy.
  • S[] - Okrągłe słowa podklucza.
  • P w — pierwsza magiczna stała, zdefiniowana jako , gdzie Odd jest najbliższą nieparzystą liczbą całkowitą dla danego wejścia, e jest podstawą logarytmu naturalnego , a w jest zdefiniowane powyżej. Dla wspólnych wartości w , powiązane wartości P w są podane tutaj w postaci szesnastkowej:
    • Dla w = 16: 0xB7E1
    • Dla w = 32: 0xB7E15163
    • Dla w = 64: 0xB7E151628AED2A6B
  • Q w - Druga magiczna stała, zdefiniowana jako , gdzie Odd jest najbliższą nieparzystą liczbą całkowitą dla danego wejścia, gdzie jest złotym podziałem , a w jest zdefiniowane powyżej. W przypadku wspólnych wartości w , powiązane wartości Q w są podane tutaj w postaci szesnastkowej:
    • Dla w = 16: 0x9E37
    • Dla w = 32: 0x9E3779B9
    • Dla w = 64: 0x9E3779B97F4A7C15
# Break K into words
# u = w / 8
c = ceiling(max(b, 1) / u)
# L is initially a c-length list of 0-valued w-length words
for i = b-1 down to 0 do:
    L[i / u] = (L[i / u] <<< 8) + K[i]
     
# Initialize key-independent pseudorandom S array
# S is initially a t=2(r+1) length list of undefined w-length words
S[0] = P_w
for i = 1 to t-1 do:
    S[i] = S[i - 1] + Q_w
    
# The main key scheduling loop
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

Przykładowy kod źródłowy znajduje się w dodatku do artykułu Rivesta na temat RC5. Implementacja jest zaprojektowana do pracy z w=32, r=12 i 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 obejmowało kilka rund prostej funkcji. Wydaje się, że zalecane jest 12 lub 20 rund, w zależności od potrzeb bezpieczeństwa i względów czasowych. Poza zmiennymi użytymi powyżej w algorytmie wykorzystywane są następujące zmienne:

  • A, B — dwa słowa tworzące blok tekstu jawnego do zaszyfrowania.
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]

# The ciphertext block consists of the two-word wide block composed of A and B, in that order.
return A, B

Oto przykładowy kod C podany przez Rivest.

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;
}

Deszyfrowanie

Deszyfrowanie jest dość prostym odwróceniem procesu szyfrowania. Poniższy pseudokod przedstawia proces.

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

Oto przykładowy kod C podany przez Rivest.

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];
}

Kryptoanaliza

12-rundowy RC5 (z blokami 64-bitowymi) jest podatny na atak różnicowy przy użyciu 2 44 wybranych tekstów jawnych. Sugeruje się 18-20 rund jako wystarczającą ochronę.

Wiele z tych problemów zostało rozwiązanych za pomocą przetwarzania rozproszonego , zorganizowanego przez Distributed.net . Distributed.net ma wiadomości RC5 w trybie brute-forced zaszyfrowane kluczami 56-bitowymi i 64-bitowymi i pracuje nad złamaniem klucza 72-bitowego od 3 listopada 2002 r. Na dzień 6 sierpnia 2021 r. 7900% przestrzeni kluczy zostało przeszukanych i na podstawie stawki zarejestrowanej tego dnia, wypełnienie 100% przestrzeni kluczy zajęłoby 127 lat. Zadanie to zainspirowało wiele nowych i nowatorskich rozwiązań w dziedzinie przetwarzania klastrowego.

Firma RSA Security , która posiadała patent na algorytm, zaoferowała serię nagród w wysokości 10 000 USD za złamanie szyfrogramów zaszyfrowanych za pomocą RC5, ale konkursy te zostały przerwane w maju 2007 r. W rezultacie firma distribution.net zdecydowała się ufundować nagrodę pieniężną. Osoba, która odkryje zwycięski klucz, otrzyma 1000 USD, jej zespół (jeśli dotyczy) otrzyma 1000 USD, a Free Software Foundation 2000 USD.

Zobacz też

Bibliografia

Linki zewnętrzne