RC5: parametrizovaná bloková šifra Ronalda Rivesta v kryptografii

RC5 — parametrizovaná bloková šifra Ronalda Rivesta: flexibilní velikosti bloku/klíče, datově závislé rotace a analýza bezpečnosti pro moderní kryptografii.

V kryptografii je RC5 jednoduchá bloková šifra se symetrickým klíčem. Šifru RC5 navrhl Ronald Rivest v roce 1994 a jedná se o parametrizovaný algoritmus s proměnnou velikostí bloku, proměnnou velikostí klíče a proměnným počtem kol. Zkratka "RC" znamená "Rivestova šifra", případně "Ronova šifra".

Parametry a zápis

Aby bylo možné zajistit různé úrovně bezpečnosti a efektivity, má RC5 proměnnou velikost bloku (32, 64 nebo 128 bitů), proměnnou velikost klíče (0 až 2040 bitů) a proměnný počet kol (0 až 255). Původní navrhovaná volba parametrů byla 64bitová velikost bloku, 128bitový klíč a 12 kol.

V praxi se často používá zápis RC5-w/r/b, kde

• w je velikost slova v bitech (např. 32),
• r je počet kol (např. 12),
• b je délka tajného klíče v bajtech (např. 16).

Princip operace

Klíčovým rysem RC5 je použití datově závislých rotací, tedy rotací o počet bitů určený hodnotou zpracovávaných dat. Jedním z cílů RC5 bylo studovat a vyhodnocovat operace blokových šifer jako kryptografického primitiva. Struktura algoritmu kombinuje opakované kroky jednoduchých operací:

• modulární sčítání (word addition),
• bitové XOR (eXclusive OR),
• cyklické rotace (data-dependent rotates).

Obecná struktura algoritmu připomíná Feistelovu síť, ale není klasickou Feistelovou strukturou; pracuje se dvěma slovy A a B a v každém kole se obě slova vzájemně mísí pomocí sčítání, XOR a rotací závislých na druhém slovu. Šifrovací a dešifrovací rutiny jsou relativně krátké a snadno implementovatelné v několika řádcích kódu.

Rozvrh klíče (key schedule)

Rozvrh klíče vytváří pole pomocných slov S[0..2r+1], které se používá při šifrování a dešifrování. Princip rozšíření klíče je navržen tak, aby byl jednoduchý, ale zajistil dostatečné „rozmíchání“ klíče do interních konstant. Rozšíření zahrnuje inicializaci S pomocí dvou konstant odvozených z matematických konstant (jako zdroje "nic v rukávu") — používané konstanty jsou odvozeny z přirozené exponenciály e a zlatého řezu — a následné iterované míchání polí S a L (pole získané z původního tajného klíče) pomocí sčítání a rotací.

Výstupem rozvrhu je pole S dostatečně dlouhé (2r+2 slov, každé o velikosti w bitů), které se pak používá v samotných kolech šifrování.

Příklad základního průběhu šifrování

Simplifikovaný popis jedné iterace (pro ilustraci, bez přesného zápisu):

• Inicializace: A = A + S[0]; B = B + S[1]
• Pro i = 1 až r:
  • A = ((A xor B) <<< B) + S[2i]
  • B = ((B xor A) <<< A) + S[2i+1]

Dešifrování provádí inverzní operace v opačném pořadí: používá se opačné sčítání/subtrakce, pravé rotace a XOR.

Bezpečnost a kryptoanalýza

Jednoduchost algoritmu spolu s novostí rotace závislé na datech učinily z RC5 atraktivní předmět studia pro kryptoanalytiky. Byla zkoumána řada útoků proti zjednodušeným (redukovanému počtu kol) verzím RC5 pomocí technik jako diferencová a lineární kryptoanalýza či útoky vázané na související klíče. Obecně platí:

• pro malé počty kol lze nalézt praktické útoky;
• pro doporučenou konfiguraci (např. RC5-32/12/16) nebyly publikovány praktické útoky lámající celý klíč v rozumném čase, nicméně bezpečnostní marže se zvyšovaly dalšími studiemi;
• pro vyšší bezpečnost je možné zvýšit počet kol (např. na 16 nebo 20) – RC5 je navržen tak, aby tuto parametrizaci podporoval.

V kryptografické komunitě se pro RC5 objevily přesné analýzy omezující bezpečnostní margin u různých parametrů, a proto se doporučuje volit parametry podle očekávaných hrozeb a životnosti šifrovaných dat.

Výkonnost a implementace

RC5 je navržena tak, aby byla rychlá v softwaru na běžných CPU: používá operace, které jsou nativní pro většinu procesorů (sčítání, XOR, rotace). Díky jednoduchosti operací je RC5 vhodná i pro omezené prostředky (embedded systémy). Implementace je krátká a přehledná, což usnadňuje audit a učení se kryptografii.

Varianty a následníci

Vliv RC5 byl významný: myšlenka datově závislých rotací a parametrizovatelné konstrukce vedly ke vzniku dalších návrhů. Nejznámějším následníkem je RC6, který navrhli autoři RC5 (včetně R. Rivesta) jako jednu z finalistických nominací v soutěži AES; RC6 rozšiřuje myšlenky RC5 o další operace (např. multiplikace), aby dosáhl lepší bezpečnostní marže.

Využití a historie

RC5 se používá zejména jako pedagogický příklad blokové šifry a byl také implementován v různých knihovnách a aplikacích. Díky své parametrizovatelnosti a jednoduchosti slouží i jako testovací objekt pro nové analytické metody v kryptografii.

Doporučení pro použití

• Používejte dostatečně dlouhý klíč a doporučený či vyšší počet kol – výběr parametrů závisí na požadované bezpečnosti a výkonu.
• Vyrábějte implementace pečlivě (správné rotace, práce s přetečením slov, bezpečné zpracování klíče v paměti).
• V aplikacích s dlouhou životností citlivých dat zvažte moderní standardy (např. AES) nebo pečlivě odhadněte požadavky a rizika při použití RC5.

RC5 je tedy zajímavý příklad flexibilní, snadno implementovatelné blokové šifry, která významně ovlivnila další vývoj symetrických algoritmů a kryptografickou analýzu.

Otázky a odpovědi

Otázka: Co je RC5?

Otázka: Co znamená zkratka "RC"?

Otázka: Jaké jsou parametry RC5?

Otázka: Jaká je obecná struktura algoritmu?

Otázka: Jak složitý je plán klíče?

Otázka: Proč je RC5 pro kryptoanalytiky atraktivní?

Hledání podle dopisu