RC5

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 24 februarie 2015; verificările necesită 18 modificări .

RC5

Creator	Ron Rivest
Creată	1994
publicat	1994
Dimensiunea cheii	0-2040 biți (128 în mod implicit)
Dimensiunea blocului	32, 64 sau 128 de biți (64 este valoarea implicită pentru platformele pe 32 de biți)
Numărul de runde	1-255 (12 în mod implicit)
Tip de	Rețeaua Feistel

RC5 ( Ron's Code 5 sau Rivest's Cipher 5 ) este un cifru bloc dezvoltat de Ron Rivest de la RSA Security cu un număr variabil de runde , lungime bloc și lungime cheie . Acest lucru extinde domeniul de utilizare și simplifică tranziția la o versiune mai puternică a algoritmului.

Descriere

Există mai multe variante diferite ale algoritmului , în care transformările în „jumătățile” ale clasicului RC5 sunt oarecum modificate. Algoritmul clasic folosește trei operații primitive și inversiunile acestora:

adiție modulo $2^{w}$
SAU exclusiv pe biți ( XOR )
operații de deplasare ciclică cu un număr variabil de biți ( ). $x\lll y$

Principala inovație este utilizarea unei operații de deplasare cu un număr variabil de biți, care nu a fost folosită în algoritmii de criptare anteriori. Aceste operațiuni sunt la fel de rapide pe majoritatea procesoarelor , dar în același timp complică semnificativ criptoanaliza diferențială și liniară a algoritmului.

Criptarea folosind algoritmul RC5 constă în două etape. Procedura de extindere a cheii și criptarea în sine . Pentru decriptare, se efectuează mai întâi procedura de extindere a cheii, iar apoi operațiunile inversează procedura de criptare. Toate operațiile de adunare și scădere sunt efectuate modulo . $2^{w}$

Opțiuni

Deoarece algoritmul RC5 are parametri variabili, desemnarea algoritmului cu parametri specifici este RC5-W/R/b , unde

W este jumătate din lungimea blocului în biți , valorile posibile sunt 16, 32 și 64. Pentru o implementare eficientă, se recomandă ca valoarea lui W să fie luată egală cu cuvântul mașină . De exemplu, pentru platformele pe 32 de biți, alegerea optimă este W = 32, care corespunde unei dimensiuni de bloc de 64 de biți.
R este numărul de runde , valorile posibile sunt de la 0 la 255. Creșterea numărului de runde asigură o creștere a nivelului de securitate al cifrului. Deci, când R = 0, informațiile nu vor fi criptate. Algoritmul RC5 utilizează, de asemenea, un tabel de chei extinse cu lungimea cuvântului care este derivat dintr-o cheie specificată de utilizator. $2(R+1)$
b este lungimea cheii în octeți , valorile posibile sunt de la 0 la 255.

Extensie cheie

Înainte de criptarea sau decriptarea directă a datelor, se efectuează o procedură de extindere a cheii. Procedura de generare a cheii constă din patru pași:

Generație constantă
Împărțirea cheii în cuvinte
Construirea unui tabel de chei extinse
Amestecarea

Generație constantă

Pentru un parametru dat , două variabile pseudoaleatoare sunt generate folosind două constante matematice: ( exponent ) și ( Rata de aur ). $W$ $e$ $f$

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

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

unde este rotunjirea la cel mai apropiat număr întreg impar. ${\textrm {Impar}}()$

Pentru că obțineți următoarele constante: $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}$

Împărțirea cheii în cuvinte

În această etapă, cheia este copiată într-o matrice de cuvinte ... , unde , unde , adică numărul de octeți dintr-un cuvânt. $K_{0}\dots K_{{b-1}}$ $L_0$ $L_{{c-1}}$ $c=b/u$ $u=W/8$

Dacă nu este un multiplu de , atunci completați cu zero biți la cel mai apropiat multiplu mai mare de . $b$ $W/8$ $L$ $c$ $W/8$

Dacă , atunci setăm valoarea lui , și . $b=c=0$ $c=1$ $L_{0}=0$

Construirea unui tabel de chei extinse

În această etapă, este construit tabelul de chei extins , care se realizează după cum urmează: $S_{0}\dots S_{{2*(R+1)-1}}$

S_{0}=P_{w}

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

Amestecă

Următoarele acțiuni sunt efectuate ciclic de N ori:

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

unde sunt variabile temporare ale căror valori inițiale sunt egale cu 0. Numărul de iterații ale buclei este maximul dintre cele două valori și . $G,H,i,j$ $N$ $3*c$ $(3\cdot 2\cdot (R+1))$

Criptare

Înainte de prima rundă, se efectuează operațiunile de impunere a unei chei extinse asupra datelor criptate:

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

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

În fiecare rundă se efectuează următoarele acțiuni:

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

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

Decriptare

Pentru Decriptarea datelor, se folosesc operațiuni inverse, adică se efectuează următoarele runde: $i=R,R-1,...,1$

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

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

După ce toate rundele au fost finalizate, mesajul original este găsit din expresia:

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

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

Proprietăți

Algoritmul RC5 are următoarele proprietăți: [1]

Potrivit atât pentru implementarea hardware cât și pentru software (algoritmul folosește operațiuni care rulează la fel de rapid pe toate procesoarele ).
Fiecare rundă procesează întregul bloc (o rundă tipică a rețelei Feistel procesează doar un „subbloc”).
La fel de bun pentru mașinile cu lungimi diferite de cuvinte de mașină (adică funcționează bine și pe mașinile pe 64 de biți).
Are o structură repetată cu un număr variabil de runde, ceea ce permite utilizatorului să aleagă între o viteză de criptare mai mare și un cifru mai sigur.
Are o lungime variabilă a cheii, care permite utilizatorului să aleagă nivelul de securitate care se potrivește specificului aplicației sale.
Destul de simplu de implementat și analizat.
Nu necesită memorie, ceea ce îi permite să fie folosit chiar și pe dispozitive mobile și portabile.

Securitate

RSA a petrecut mult timp analizând modul în care funcționează cu un bloc pe 64 de biți. Așa că în perioada 1995-1998 au publicat o serie de rapoarte în care au analizat în detaliu puterea criptografică a algoritmului RC5. Scorul pentru criptoanaliza liniară arată că algoritmul este sigur după 6 runde. Criptanaliza diferențială necesită texte clare selectate pentru algoritmul cu 5 runde, pentru 10 runde, pentru 12 runde și pentru 15 runde. Și din moment ce sunt posibile doar texte clare diferite, criptoanaliza diferențială este imposibilă pentru un algoritm de 15 sau mai multe runde. Deci este recomandat să folosiți 18-20 de runde, sau cel puțin 15 runde în loc de cele 12 runde pe care însuși Rivest le-a recomandat. $2^{24}$ $2^{{45}}$ $2^{{53}}$ $2^{{68}}$ $2^{64}$

Provocare de securitate RSA

Pentru a stimula studiul și utilizarea cifrului RC5, RSA Security la 28 ianuarie 1997 s-a oferit să spargă o serie de mesaje criptate cu algoritmul RC5 cu parametri diferiți [2] , atribuind un premiu de 10.000 USD pentru spargerea fiecărui mesaj. cei mai slabi parametri este RC5-32/12/5 a fost spart în câteva ore. Cu toate acestea, ultimul cifr RC5-32/12/8 care a fost spart a necesitat 5 ani de calcul de către proiectul de calcul distribuit RC5-64 (aici 64= b 8, lungimea cheii în biți) condus de distributed.net . RC5-32 /12/ b pentru b de la 9 la 16 este încă impenetrabil .% taste. [3]

În mai 2007, RSA Security Inc. a anunțat încetarea sprijinului pentru concurs și plata recompenselor bănești. Pentru a menține proiectul RC-72 în funcțiune , distributed.net a decis să sponsorizeze un premiu de 4.000 USD pentru acesta din fonduri proprii. [patru]

Atacul de rulare

Pe platformele în care se efectuează o operație de rotație cu un număr variabil de biți pentru un număr diferit de cicluri de procesor , este posibil un atac de rulare asupra algoritmului RC5. Două variante ale unui astfel de atac au fost formulate de către criptoanalistii Howard Hayes și Helena Handschuh . Ei au descoperit că cheia ar putea fi calculată după efectuarea a aproximativ 220 de operațiuni de criptare cu timpi de execuție foarte precisi și apoi 228 până la 240 de operațiuni de criptare de probă. Cea mai simplă metodă de combatere a unor astfel de atacuri este de a forța ca schimburile să fie executate într-un număr constant de cicluri (de exemplu, în timpul executării celei mai lente schimburi).

Variante ale algoritmului

Deoarece una dintre proprietățile RC5 este ușurința de implementare și analiză, este logic ca mulți criptologi[ cine? ] a dorit să îmbunătățească algoritmul clasic. Structura generală a algoritmului a rămas neschimbată, s-au schimbat doar acțiunile efectuate pe fiecare bloc în procesul de criptare în sine . Deci, au existat mai multe versiuni diferite ale acestui algoritm:

RC5XOR

În acest algoritm, adăugarea cu cheia rotundă modulo este înlocuită cu operația XOR: $2^{w}$

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

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

Acest algoritm s-a dovedit a fi vulnerabil la criptoanaliza diferențială și liniară. Biryukov și Kushilevits au reușit să găsească un atac de criptoanaliza diferențială pentru algoritmul RC5XOR-32/12/16 folosind 228 de texte clare selectate.

RC5P

În acest algoritm, adăugarea a două „subblocuri” procesate prin operația XOR este înlocuită cu adăugarea modulo : $2^{w}$

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}

Acest algoritm s-a dovedit a fi vulnerabil la criptoanaliza diferențială.

RC5PFR

În acest algoritm, deplasarea ciclică este efectuată de un număr fix de biți pentru o rundă dată, și nu de unul variabil.

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}

unde este un număr fix. $R_i$

Acest algoritm nu este bine înțeles, dar se presupune că[ de cine? ] că este instabil la criptoanaliza diferențială.

RC5KFR

În acest algoritm, numărul de biți de mutat depinde de cheia algoritmului și de runda curentă:

{\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}

De asemenea, acest algoritm nu este bine înțeles.

RC5RA

În acest algoritm, numărul de biți de deplasare este determinat folosind o funcție dintr-un alt „subbloc”:

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}

Presupus,[ de cine? ] că algoritmul RC5RA este și mai rezistent la metodele de criptoanaliza cunoscute decât RC5.

Note

↑ Rivest, R. L. (1994). „Algoritmul de criptare RC5” (pdf) . Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e . pp. 86-96. Textul „ref-en” a fost omis ( ajutor ) Arhivat la 17 aprilie 2007 la Wayback Machine
↑ The RSA Laboratories Secret-Key Challenge Arhivat 23 mai 2004.
↑ RC5-72: Statistici generale ale proiectului . Consultat la 14 februarie 2010. Arhivat din original la 9 octombrie 2018. (nedefinit)
↑ distributed.net: bloguri de personal - 2008 - septembrie - 08

Link -uri

Schneier B. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Întrebări frecvente despre cifrurile simetrice (link nu este disponibil) . - pe baza materialelor conferinței fido7.ru.crypt. Consultat la 11 noiembrie 2009. Arhivat din original pe 22 august 2011. (Rusă)
Metode moderne pentru distrugerea algoritmilor de criptare (link inaccesibil) . — Descrierea unor metode de atac asupra algoritmilor de criptare. Preluat la 4 decembrie 2009. Arhivat din original la 21 mai 2009. (Rusă)

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher