RC5 — simetrična blokovna šifra Rivesta: opis, parametri in lastnosti

RC5 — podroben vodnik o simetrični blokovni šifri Rivesta: opis, parametri (velikost bloka, ključ, število krogov) in ključne lastnosti ter varnostne značilnosti.

V kriptografiji je RC5 preprosta, a prilagodljiva blokovna šifra s simetričnim ključem. RC5 je leta 1994 zasnoval Ronald Rivest kot parametriziran algoritem z namenom raziskovanja vpliva različnih gradnikov (velikost besed, število krogov, dolžina ključa) na varnost in učinkovitost. "RC" pomeni "Rivestova šifra" ali "Ronova šifra".

Opis in osnovni elementi

RC5 deluje na dveh besedah velikosti w bitov; velikost bloka je torej 2w bitov. Tipične vrednosti za w so 16, 32 ali 64, kar daje blokovne velikosti 32, 64 ali 128 bitov. Algoritem uporablja tri osnovne operacije:

• seštevanje modulo 2^w (ADD),
• izključujoči OR (XOR),
• rotacije (circular left/right shifts) z zneskom rotacije, ki je odvisen od podatkov (data-dependent rotations).

Struktura je Feistelovi podobna, a s pomembnimi razlikami zaradi podatkovno odvisnih rotacij. Enostavnost šifriranja/dešifriranja je v nasprotju z bolj kompleksno razširitvijo ključa (key schedule), kjer se skrivni ključ razširi v tabelo podključev S z uporabo posebnih konstanta in iterativnega mešanja.

Parametri

• w — velikost besede v bitih (16, 32, 64). Blok je 2w bitov.
• r — število krogov (0–255). Več krogov običajno pomeni večjo varnost, a nižjo hitrost.
• b — dolžina skrivnega ključa v bajtih (0–255 bajtov, torej do 2040 bitov).

Pogosta oznaka je RC5-w/r/b (npr. RC5-32/12/16: w=32, r=12, b=16). Prvotno predlagani parametri so bili w=32 (blok 64 bitov), r=12 in ključ dolžine 128 bitov (b=16).

Osnovna aritmetika in konstante

Tabela podključev S ima dolžino t = 2r + 2. Za inicializacijo se uporabljata dve konstanti P_w in Q_w, izpeljani iz iracionalnih števil (e in zlatega reza). V praksi sta to neparni celi števili, primer za w = 32 sta na primer 0xB7E15163 (P) in 0x9E3779B9 (Q).

Razširitev ključa (key schedule)

Postopek razširitve ključa je naslednji (opis v besedilu, ohranite natančnost pri implementaciji):

• Vhodni ključ K (b bajtov) razdelimo v c = ceil(b / (w/8)) število w-bitnih besed L[0..c-1], z upoštevanjem malo-endian razporeditve bajtov.
• Inicializiramo tabelo S[0..t-1]: S[0] = P_w; za i = 1..t-1 nastavimo S[i] = S[i-1] + Q_w (mod 2^w).
• Mešanje S in L: vzpostavimo spremenljivki A = B = 0, i = j = 0, ter izvedemo 3 * max(t, c) korakov:
  • A = S[i] = (S[i] + A + B) <<< 3;
  • B = L[j] = (L[j] + A + B) <<< (A + B);
  • i = (i + 1) mod t; j = (j + 1) mod c.

(<<< označuje rotacijo v levo za količino, vzeto modulo w; operacije so v aritmetiki modulo 2^w.) Ta del je namenjen razpršitvi informacij iz skrivnega ključa v tabelo S in je običajno najdražji del priprave ključa v smislu računske zahtevnosti.

Šifriranje in dešifriranje (psevdokoda)

Naj bo vhodni blok razdeljen na dve w-bitni besedi A in B. Šifriranje:

• A = A + S[0];
• B = B + S[1];
• za i = 1..r:
  • A = ((A ^ B) <<< (B & (w-1))) + S[2*i];
  • B = ((B ^ A) <<< (A & (w-1))) + S[2*i + 1];

Dešifriranje je inverzno zaporedje (uporabimo odštevanja modulo 2^w in rotacije v desno z istimi količinami rotacije), začnemo z odštevanjem S[1] in S[0] po končnem krogu in izvajamo zanke od r nazaj do 1.

Lastnosti in prednosti

• Visoka prilagodljivost: parametri w, r in b omogočajo prilagajanje varnosti in hitrosti.
• Preprostost implementacije: jedro šifriranja/dešifriranja je kratek in učinkovit niz operacij, primeren za programske in strojne implementacije.
• Data-dependent rotations (rotacije, odvisne od podatkov) prinesejo dodatno nekonvencionalno nelinearnost v primerjavi s klasičnimi Feistelovimi shemami.

Varnost in kriptoanalize

RC5 je bil predmet obsežnih raziskav kriptoanalitikov. Pomembne ugotovitve so:

• Za zmanjšano število krogov obstajajo učinkovitejše kriptoanalize (diferencialne in povezane-ključeve metode) kot naključni napadi; to pomeni, da je varnost močno odvisna od izbrane vrednosti r.
• Polna različica z dovolj velikim številom krogov in dolgo ključno dolžino ni bila sistematično zlomljena; klasični napadi so za polne parametre običajno prakticno neučinkoviti (osiromašitev do brute-force kompleksnosti 2^keysize).
• Pri izbiri parametrov je treba upoštevati sodobne kriptoanalitične rezultate in priporočila; pogosto r >= 12 za w = 32 velja za minimalno priporočilo v prvih predlogih, vendar so za nove zahteve po varnosti predlagane večje vrednosti.

Na splošno se RC5 zaradi številnih raziskav in alternativ (npr. AES) uporablja manj pogosto kot standardizirane šifre, a ostaja pomemben iz zgodovinskega vidika in kot predmet študij zaradi svoje preprostosti in novih gradnikov (data-dependent rotations).

Izvedba in učinkovitost

• V strojnih okolijih (CPU z ukazi za rotacije) je RC5 zelo hiter, saj uporablja osnovne, učinkovite strojne operacije (ADD, XOR, ROTATE).
• Key schedule je bolj obremenilen kot posamezno šifriranje, zato se pri potrebi po večih sporočilih z istim ključem predhodno izvede razširitev ključa in S shrani.
• Zaradi prilagodljivih parametrov je RC5 uporaben v sistemih, kjer želimo nadzorovati kompromis med hitrostjo in varnostjo (npr. vgrajeni sistemi z omejenimi viri ali v aplikacijah z visokimi varnostnimi zahtevami).

Izpeljanke in zgodovina

RC5 je prispeval k razvoju poznejših konstrukcij; neposredni naslednik RC5 je RC6, ki je bil med kandidati za standard AES. RC5 je zaradi svoje zasnove postal tudi pogosto izhodišče za raziskave v akademskem svetu.

Zaključek

RC5 je elegantna, parametrizirana blokovna šifra, ki je pomembna zaradi svoje preprostosti in uporabe data-dependent rotacij. Pravilna izbira parametrov (w, r, b) je ključna za zagotovitev zadostne varnosti; medtem ko so bile odkrite kriptoanalize proti zmanjšanim različicam, polni parametri z ustreznim številom krogov in dovolj dolgo ključno dolžino ostajajo odporni na znane praktične napade. Zaradi razširjenih študij in obilo literature je RC5 še vedno koristen za razumevanje in primerjavo blokovnih šifer.

Vprašanja in odgovori

V: Kaj je RC5?

V: Kaj pomeni "RC"?

V: Kateri so parametri šifre RC5?

V: Kakšna je splošna struktura algoritma?

V: Kako zapleten je razpored ključev?

V: Zakaj je RC5 privlačen za kriptoanalitike?

Išči po črki