RC5 - 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.