RC5

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. února 2015; kontroly vyžadují 18 úprav .

RC5

Tvůrce	Ron Rivest
Vytvořeno	1994
zveřejněno	1994
Velikost klíče	0–2040 bitů (128 ve výchozím nastavení)
Velikost bloku	32, 64 nebo 128 bitů (64 je výchozí pro 32bitové platformy)
Počet kol	1-255 (výchozí 12)
Typ	Síť Feistel

RC5 ( Ron's Code 5 nebo Rivest's Cipher 5 ) je bloková šifra vyvinutá Ronem Rivestem z RSA Security s proměnným počtem kol , délkou bloku a délkou klíče . To rozšiřuje rozsah použití a zjednodušuje přechod na silnější verzi algoritmu.

Popis

Existuje několik různých variant algoritmu , ve kterých jsou transformace v "půlkolách" klasického RC5 poněkud upraveny. Klasický algoritmus používá tři primitivní operace a jejich inverze:

modulo přidání $2^{w}$
bitový exkluzivní OR ( XOR )
operace cyklického posunu o proměnný počet bitů ( ). $x\lll y$

Hlavní inovací je použití operace posunu o proměnný počet bitů, což se v dřívějších šifrovacích algoritmech nepoužívalo. Tyto operace jsou stejně rychlé na většině procesorů , ale zároveň výrazně komplikují diferenciální a lineární kryptoanalýzu algoritmu.

Šifrování pomocí algoritmu RC5 se skládá ze dvou fází. Postup rozšíření klíče a samotné šifrování . Při dešifrování se nejprve provede postup rozšíření klíče a poté se operace obrátí k postupu šifrování. Všechny operace sčítání a odčítání se provádějí modulo . $2^{w}$

Možnosti

Protože má algoritmus RC5 proměnné parametry, označení algoritmu se specifickými parametry je RC5-W/R/b , kde

W je polovina délky bloku v bitech , možné hodnoty jsou 16, 32 a 64. Pro efektivní implementaci se doporučuje , aby se hodnota W rovnala strojovému slovu . Například pro 32bitové platformy je optimální volba W = 32, což odpovídá velikosti bloku 64 bitů.
R je počet kol , možné hodnoty jsou od 0 do 255. Zvýšení počtu kol poskytuje zvýšení úrovně zabezpečení šifry. Takže když R = 0, informace nebudou zašifrovány. Algoritmus RC5 také používá tabulku rozšířených klíčů délky slova , která je odvozena z uživatelem zadaného klíče. $2(R+1)$
b je délka klíče v bajtech , možné hodnoty jsou od 0 do 255.

Rozšíření klíče

Před přímým šifrováním nebo dešifrováním dat se provede postup rozšíření klíče. Postup generování klíče se skládá ze čtyř kroků:

Konstantní generace
Rozdělení klíče na slova
Vytvoření tabulky rozšířených klíčů
Míchání

Konstantní generování

Pro daný parametr jsou generovány dvě pseudonáhodné proměnné pomocí dvou matematických konstant: ( exponent ) a ( Zlatý poměr ). $W$ $E$ $F$

Q_{w}\leftarrow {\textrm {Odd}}((f-1)\cdot 2^{w})

P_{w}\leftarrow {\textrm {Odd}}((e-2)\cdot 2^{w})

kde je zaokrouhlení na nejbližší liché celé číslo. ${\textrm {Odd}}()$

Získáte tak následující konstanty: $w=16.32.64$

$P_{16}={\texttt {1011011111100001}}_{2}={\texttt {B7E1}}_{16}$
$Q_{16}={\texttt {1001111000110111}}_{2}={\texttt {9E37}}_{16}$
$P_{32}={\texttt {10110111111000010101000101100011}}_{2}={\texttt {B7E15163}}_{16}$
$Q_{32}={\texttt {10011110001101110111100110111001}}_{2}={\texttt {9E3779B9}}_{16}$
$P_{64}={\texttt {B7E151628AED2A6B}}_{16}$
$Q_{64}={\texttt {9E3779B97F4A7C15}}_{16}$

Rozdělení klíče na slova

V této fázi je klíč zkopírován do pole slov … , kde , kde , tedy počet bajtů ve slově. $K_{0}\tečky K_{{b-1}}$ $L_0$ $L_{{c-1}}$ $c=b/u$ $u=W/8$

Pokud ne násobkem , pak doplněno nulovými bity na nejbližší větší násobek . $b$ $W/8$ $L$ $C$ $W/8$

Pokud , pak nastavíme hodnotu , a . $b=c=0$ $c=1$ $L_{0}=0$

Vytvoření tabulky rozšířených klíčů

V této fázi je vytvořena rozšířená tabulka klíčů , která se provádí následovně: $S_{0}\tečky S_{{2*(R+1)-1}}$

S_{0}=P_{w}

S_{{i+1}}=S_{{i}}+Q_{w}

Zamíchat

Následující akce se provádějí cyklicky Nkrát:

G=S_{i}=(S_{i}+G+H)\lll 3

H=L_{j}=(L_{j}+G+H)\lll (G+H)

i=(i+1)\mod (2(R+1))

j=(j+1)\mod c

kde jsou dočasné proměnné, jejichž počáteční hodnoty se rovnají 0. Počet iterací smyčky je maximum ze dvou hodnot a . $G,H,i,j$ $N$ $3*c$ $(3\cdot 2\cdot (R+1))$

Šifrování

Před prvním kolem se provedou operace vložení rozšířeného klíče na zašifrovaná data:

A=(A+S_{0})\;{\bmod {\;}}2^{w}

B=(B+S_{1})\;{\bmod {\;}}2^{w}

V každém kole se provádějí následující akce:

{\displaystyle A=((A\oplus B)\lll B)+S_{2i))

B=((B\oplus A)\lll A)+S_{2i+1}

Dešifrování

Pro dešifrování dat se používají reverzní operace, to znamená , že se provádějí následující kola: $i=R,R-1,...,1$

B=((B-S_{2i+1})\ggg A)\oplus A

A=((A-S_{2i})\ggg B)\oplus B

Po dokončení všech kol je původní zpráva nalezena z výrazu:

B=(B-S_{1})\;{\bmod {\;}}2^{w}

A=(A-S_{0})\;{\bmod {\;}}2^{w}

Vlastnosti

Algoritmus RC5 má následující vlastnosti: [1]

Vhodné pro hardwarovou i softwarovou implementaci (algoritmus používá operace, které běží stejně rychle na všech procesorech ).
Každé kolo zpracuje celý blok (typické kolo sítě Feistel zpracovává pouze „dílčí blok“).
Stejně dobré pro stroje s různými délkami strojového slova (to znamená, že funguje dobře i na 64bitových strojích).
Má opakující se strukturu s proměnným počtem kol, což uživateli umožňuje volit mezi vyšší rychlostí šifrování a bezpečnější šifrou.
Má variabilní délku klíče, která uživateli umožňuje vybrat si úroveň zabezpečení, která vyhovuje specifikům jeho aplikace.
Poměrně jednoduchá implementace a analýza.
Je nenáročný na paměť, což umožňuje jeho použití i v mobilních a přenosných zařízeních.

Zabezpečení

RSA strávila spoustu času analýzou toho, jak funguje s 64bitovým blokem. V období od roku 1995 do roku 1998 tedy publikovali řadu zpráv, ve kterých podrobně analyzovali kryptografickou sílu algoritmu RC5. Skóre pro lineární kryptoanalýzu ukazuje, že algoritmus je bezpečný po 6 kolech. Diferenciální kryptoanalýza vyžaduje vybrané otevřené texty pro 5-kolový algoritmus, pro 10-kolový, pro 12-kolový a pro 15-kolový. A protože existují pouze možné různé holé texty, diferenciální kryptoanalýza je nemožná pro algoritmus 15 nebo více kol. Doporučuje se tedy použít 18-20 nábojů, nebo alespoň 15 nábojů místo 12 nábojů, které doporučoval sám Rivest. $2^{24}$ $2^{{45}}$ $2^{{53}}$ $2^{{68}}$ $2^{64}$

RSA Security Challenge

Pro stimulaci studia a používání šifry RC5 nabídla RSA Security 28. ledna 1997 prolomení série zpráv zašifrovaných algoritmem RC5 s různými parametry [2] a přidělila odměnu 10 000 $ za prolomení každé zprávy. nejslabší parametry je RC5-32/12/5 byl hacknut během několika hodin. Poslední šifra RC5-32/12/8, která měla být prolomena, však vyžadovala 5 let výpočtů v rámci projektu distribuovaných výpočtů RC5-64 (zde 64= b 8, délka klíče v bitech) vedeného distribuovaným.net . RC5-32 /12/ b pro b od 9 do 16 je stále neprostupné . [3]

V květnu 2007 RSA Security Inc. oznámila ukončení podpory soutěže a vyplacení peněžních odměn. Aby projekt RC-72 pokračoval v chodu , rozhodl se distribuovaný.net sponzorovat za něj cenu 4 000 $ z vlastních prostředků. [čtyři]

Runtime útok

Na platformách, kde se operace rotace s proměnným počtem bitů provádí pro různý počet cyklů procesoru , je možný runtime útok na algoritmus RC5. Dvě varianty takového útoku formulovali kryptanalytici Howard Hayes a Helena Handschuh . Zjistili, že klíč lze vypočítat po provedení asi 220 šifrovacích operací s vysoce přesnými časy provedení a poté 228 až 240 zkušebních šifrovacích operací. Nejjednodušší metodou boje proti takovým útokům je vynutit provádění směn v konstantním počtu cyklů (například při provádění nejpomalejší směny).

Varianty algoritmu

Protože jednou z vlastností RC5 je snadná implementace a analýza, je logické, že mnoho kryptologů[ kdo? ] chtěl vylepšit klasický algoritmus. Obecná struktura algoritmu zůstala nezměněna, změnily se pouze akce prováděné na každém bloku v procesu samotného šifrování . Takže existovalo několik různých verzí tohoto algoritmu:

RC5XOR

V tomto algoritmu je sčítání pomocí kulatého klíče modulo nahrazeno operací XOR: $2^{w}$

{\displaystyle A_{i+1}=((A_{i}\oplus B_{i})\lll B_{i})\oplus S_{2i))

{\displaystyle B_{i+1}=((B_{i}\oplus A_{i})\lll A_{i})\oplus S_{2i+1))

Tento algoritmus se ukázal být citlivý na diferenciální a lineární kryptoanalýzu. Biryukovovi a Kushilevitsovi se podařilo najít diferenciální kryptoanalytický útok pro algoritmus RC5XOR-32/12/16 pomocí 228 vybraných otevřených textů.

RC5P

V tomto algoritmu je přidání dvou zpracovaných „podbloků“ operací XOR nahrazeno přidáním modulo : $2^{w}$

{\displaystyle A_{i+1}=((A_{i}+B_{i})\lll B_{i})+S_{2i))

B_{i+1}=((B_{i}+A_{i})\lll A_{i})+S_{2i+1}

Ukázalo se, že tento algoritmus je citlivý na diferenciální kryptoanalýzu.

RC5PFR

V tomto algoritmu se cyklický posun provádí pevným počtem bitů pro dané kolo, nikoli proměnným.

{\displaystyle A_{i+1}=((A_{i}\oplus B_{i})\lll R_{i})+S_{2i))

B_{i+1}=((B_{i}\oplus A_{i})\lll R_{i})+S_{2i+1}

kde je pevné číslo. $R_i$

Tento algoritmus není dobře pochopen, ale předpokládá se, že ano[ kým? ] že je nestabilní vůči diferenciální kryptoanalýze.

RC5KFR

V tomto algoritmu závisí počet bitů, které se mají posunout, na klíči algoritmu a na aktuálním kole:

{\displaystyle A_{i+1}=((A_{i}\oplus B_{i})\lll R_{i}(L_{i}))+S_{2i))

B_{i+1}=((B_{i}\oplus A_{i})\lll R_{i}(L_{i}))+S_{2i+1}

Tento algoritmus také není dobře pochopen.

RC5RA

V tomto algoritmu je počet bitů posunu určen pomocí nějaké funkce z jiného „podbloku“:

{\displaystyle A_{i+1}=((A_{i}\oplus B_{i})\lll f(L_{i}))+S_{2i))

B_{i+1}=((B_{i}\oplus A_{i})\lll f(L_{i}))+S_{2i+1}

Předpokládá se,[ kým? ] , že algoritmus RC5RA je ještě odolnější vůči známým metodám kryptoanalýzy než RC5.

Poznámky

↑ Rivest, R. L. (1994). „Šifrovací algoritmus RC5“ (pdf) . Sborník z druhého mezinárodního workshopu o rychlém softwarovém šifrování (FSE) 1994e . str. 86-96. "ref-en" text vynechán ( help ) Archivováno 17. dubna 2007 na Wayback Machine
↑ The RSA Laboratories Secret-Key Challenge Archivováno 23. května 2004.
↑ RC5-72: Celková statistika projektu . Získáno 14. února 2010. Archivováno z originálu 9. října 2018. (neurčitý)
↑ Distributed.net: blogy zaměstnanců - 2008 - září - 08

Odkazy

Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Nejčastější dotazy týkající se symetrických šifer (odkaz není k dispozici) . - na základě materiálů konference fido7.ru.crypt. Získáno 11. listopadu 2009. Archivováno z originálu 22. srpna 2011. (Ruština)
Moderní metody pro prolomení šifrovacích algoritmů (nepřístupný odkaz) . — Popis některých metod útoku na šifrovací algoritmy. Získáno 4. prosince 2009. Archivováno z originálu dne 21. května 2009. (Ruština)

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) blowfish Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher