RC5

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 februari 2015; kontroller kräver 18 redigeringar .

RC5

Skapare	Ron Rivest
Skapad	1994
publiceras	1994
Nyckelstorlek	0-2040 bitar (128 som standard)
Block storlek	32, 64 eller 128 bitar (64 är standard för 32-bitars plattformar)
Antal omgångar	1-255 (12 som standard)
Sorts	Feistel nätverk

RC5 ( Ron's Code 5 eller Rivest's Cipher 5 ) är ett blockchiffer utvecklat av Ron Rivest från RSA Security med ett variabelt antal rundor , blocklängd och nyckellängd . Detta utökar användningsområdet och förenklar övergången till en starkare version av algoritmen.

Beskrivning

Det finns flera olika varianter av algoritmen , där transformationerna i "halvrundorna" av den klassiska RC5 är något modifierade. Den klassiska algoritmen använder tre primitiva operationer och deras inversioner:

modulo tillägg $2^{w}$
bitvis exklusiv ELLER ( XOR )
cykliska skiftoperationer med ett variabelt antal bitar ( ). $x\lll y$

Den huvudsakliga innovationen är användningen av en skiftoperation med ett variabelt antal bitar, vilket inte användes i tidigare krypteringsalgoritmer. Dessa operationer är lika snabba på de flesta processorer , men komplicerar samtidigt den differentiella och linjära kryptoanalysen av algoritmen avsevärt.

Kryptering med RC5-algoritmen består av två steg. Nyckelexpansionsprocedur och själva kryptering . För dekryptering utförs först nyckelexpansionsproceduren och sedan återgår operationerna till krypteringsproceduren. Alla additions- och subtraktionsoperationer utförs modulo . $2^{w}$

Alternativ

Eftersom RC5-algoritmen har variabla parametrar, är beteckningen för algoritmen med specifika parametrar RC5-W/R/b , där

W är hälften av blockets längd i bitar , möjliga värden är 16, 32 och 64. För effektiv implementering rekommenderas att värdet på W tas lika med maskinordet . Till exempel, för 32-bitars plattformar, är det optimala valet W = 32, vilket motsvarar en blockstorlek på 64 bitar.
R är antalet rundor , möjliga värden är från 0 till 255. Att öka antalet rundor ger en ökning av chifferets säkerhetsnivå. Så, när R = 0, kommer informationen inte att krypteras. RC5-algoritmen använder också en ordlängdsförlängd nyckeltabell som härleds från en användarspecificerad nyckel. $2(R+1)$
b är nyckelns längd i byte , möjliga värden är från 0 till 255.

Nyckelförlängning

Innan du direkt krypterar eller dekrypterar data utförs en nyckelexpansionsprocedur. Nyckelgenereringsproceduren består av fyra steg:

Konstant generation
Dela upp nyckeln i ord
Bygga ett bord med utökade nycklar
Blandning

Konstant generation

För en given parameter genereras två pseudo-slumpvariabler med hjälp av två matematiska konstanter: ( exponent ) och ( Golden Ratio ). $W$ $e$ $f$

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

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

där är avrundning till närmaste udda heltal. ${\textrm {Odd}}()$

För du får följande konstanter: $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}$

Dela upp nyckeln i ord

I detta skede kopieras nyckeln till en rad ord … , där , där , det vill säga antalet byte i ett ord. $K_{0}\dots K_{{b-1}}$ $L_0$ $L_{{c-1}}$ $c=b/u$ $u=W/8$

Om inte en multipel av , utfylld med nollbitar till närmaste större multipel av . $b$ $W/8$ $L$ $c$ $W/8$

Om , då ställer vi in värdet på , och . $b=c=0$ $c=1$ $L_{0}=0$

Bygga en tabell med utökade nycklar

I detta skede byggs det utökade nyckelbordet , vilket utförs enligt följande: $S_{0}\dots S_{{2*(R+1)-1}}$

S_{0}=P_{w}

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

Blanda

Följande åtgärder utförs cykliskt N gånger:

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

var är temporära variabler vars initiala värden är lika med 0. Antalet iterationer av slingan är det maximala av de två värdena och . $G,H,i,j$ $N$ $3*c$ $(3\cdot 2\cdot (R+1))$

Kryptering

Före den första omgången utförs operationerna med att lägga en utökad nyckel på den krypterade datan:

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

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

I varje omgång utförs följande åtgärder:

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

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

Dekryptering

För datadekryptering används omvända operationer, det vill säga följande omgångar utförs: $i=R,R-1,...,1$

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

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

Efter att alla omgångar har slutförts hittas det ursprungliga meddelandet från uttrycket:

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

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

Egenskaper

RC5-algoritmen har följande egenskaper: [1]

Lämplig för både hårdvaru- och mjukvaruimplementering (algoritmen använder operationer som går lika snabbt på alla processorer ).
Varje omgång bearbetar hela blocket (en typisk Feistel-nätverksrunda behandlar endast ett "underblock").
Lika bra för maskiner med olika maskinordslängder (det vill säga, det fungerar också bra på 64-bitars maskiner).
Den har en repeterande struktur med ett variabelt antal omgångar, vilket gör att användaren kan välja mellan en högre krypteringshastighet och ett säkrare chiffer.
Den har en variabel nyckellängd, vilket gör att användaren kan välja den säkerhetsnivå som passar specifikationerna för hans applikation.
Ganska enkel att implementera och analysera.
Det är inte krävande för minnet, vilket gör att det kan användas även i mobila och bärbara enheter.

Säkerhet

RSA har ägnat mycket tid åt att analysera hur det fungerar med ett 64-bitars block. Så under perioden 1995 till 1998 publicerade de ett antal rapporter där de analyserade i detalj den kryptografiska styrkan hos RC5-algoritmen. Poängen för linjär kryptoanalys visar att algoritmen är säker efter 6 omgångar. Differentiell kryptoanalys kräver utvalda klartexter för 5-runda algoritmen, för 10-runder, för 12-runder och för 15-runder. Och eftersom det bara finns möjliga olika klartexter är differentiell kryptoanalys omöjlig för en algoritm på 15 eller fler omgångar. Så det rekommenderas att använda 18-20 omgångar, eller åtminstone 15 omgångar istället för de 12 omgångarna som Rivest själv rekommenderade. $2^{24}$ $2^{{45}}$ $2^{{53}}$ $2^{{68}}$ $2^{64}$

RSA Security Challenge

För att stimulera studien och användningen av RC5-chifferet erbjöd RSA Security den 28 januari 1997 att bryta en serie meddelanden krypterade med RC5-algoritmen med olika parametrar, [2] och tilldela ett pris på $10 000 för att bryta varje meddelande. de svagaste parametrarna är RC5-32/12/5 hackades inom några timmar. Det sista RC5-32/12/8-chifferet som knäcktes krävde dock 5 års beräkning av det distribuerade beräkningsprojektet RC5-64 (här 64= b 8, nyckellängd i bitar) ledd av distributed.net . RC5-32 /12/ b för b från 9 till 16 är fortfarande ogenomtränglig . % nycklar. [3]

I maj 2007 hade RSA Security Inc. meddelade att stödet för tävlingen och betalningen av monetära belöningar upphörde. För att hålla RC-72- projektet igång beslutade distributed.net att sponsra ett pris på $4 000 för det med egna medel. [fyra]

Runtime attack

På plattformar där ett variabelt antal bitars rotationsoperation utförs för ett annat antal processorcykler , är en runtime- attack på RC5-algoritmen möjlig. Två varianter av en sådan attack formulerades av kryptoanalytikerna Howard Hayes och Helena Handschuh . De fann att nyckeln kunde beräknas efter att ha utfört cirka 220 krypteringsoperationer med mycket exakta körtider och sedan 228 till 240 testkrypteringsoperationer. Den enklaste metoden för att bekämpa sådana attacker är att tvinga skift att utföras i ett konstant antal cykler (till exempel under utförandet av det långsammaste skiftet).

Varianter av algoritmen

Eftersom en av egenskaperna hos RC5 är dess enkla implementering och analys, är det logiskt att många kryptologer[ vem? ] ville förbättra den klassiska algoritmen. Algoritmens allmänna struktur förblev oförändrad, endast de åtgärder som utfördes på varje block i själva krypteringsprocessen ändrades . Så det fanns flera olika versioner av denna algoritm:

RC5XOR

I denna algoritm ersätts addition med modulo round-tangenten med XOR-operationen: $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))

Denna algoritm visade sig vara sårbar för differentiell och linjär kryptoanalys. Biryukov och Kushilevits lyckades hitta en differentiell kryptoanalysattack för RC5XOR-32/12/16-algoritmen med hjälp av 228 utvalda klartexter.

RC5P

I denna algoritm ersätts tillägget av två bearbetade "subblock" av XOR-operationen med modulo-addition : $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}

Denna algoritm visade sig vara sårbar för differentiell kryptoanalys.

RC5PFR

I denna algoritm utförs det cykliska skiftet av ett fast antal bitar för en given omgång, och inte av en variabel.

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

var är ett fast nummer. $R_i$

Denna algoritm är inte väl förstådd, men det antas att[ av vem? ] att den är instabil för differentiell kryptoanalys.

RC5KFR

I den här algoritmen beror antalet bitar som ska skiftas på nyckeln till algoritmen och på den aktuella rundan:

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

Denna algoritm är inte heller väl förstådd.

RC5RA

I denna algoritm bestäms antalet skiftbitar med hjälp av någon funktion från ett annat "subblock":

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

Förment,[ av vem? ] att RC5RA-algoritmen är ännu mer motståndskraftig mot kända kryptoanalysmetoder än RC5.

Anteckningar

↑ Rivest, R. L. (1994). "RC5-krypteringsalgoritmen" (pdf) . Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e . pp. 86-96. "ref-en" text utelämnad ( hjälp ) Arkiverad 17 april 2007 på Wayback Machine
↑ RSA Laboratories Secret-Key Challenge arkiverad 23 maj 2004.
↑ RC5-72: Övergripande projektstatistik . Hämtad 14 februari 2010. Arkiverad från originalet 9 oktober 2018. (obestämd)
↑ distributed.net: personalbloggar - 2008 - september - 08

Länkar

Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .
Vanliga frågor om symmetriska chiffer (länk ej tillgänglig) . - baserat på materialet från fido7.ru.crypt-konferensen. Hämtad 11 november 2009. Arkiverad från originalet 22 augusti 2011. (ryska)
Moderna metoder för att bryta krypteringsalgoritmer (otillgänglig länk) . — Beskrivning av några attackmetoder på krypteringsalgoritmer. Hämtad 4 december 2009. Arkiverad från originalet 21 maj 2009. (ryska)

Symmetriska kryptosystem
Streama chiffer	A3 A5 A8 Decim F-FCSR Spannmål HC-256 KCipher-2 MICKEY MUGI GÄDDA Phelix RC4 Kanin TÄTA SNÖ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel nätverk	GOST 28147-89 (Magma) blåsfisk Kamelia CAST-128 CAST-256 CIFERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra HANDLA DES DESX DFC E2 ENRUPT FEAL HPC ANING KASUMI Khafre Khufu LOKI97 MacGuffin MARS MASKA DIMMIG1 Ny DES NDS RC5 RC6 UTSÄDE Simon Sinople skipjack SM4 Fläck TE XTEA XXTEA Raiden RTEA Trippel DES Tvåfisk
SP nätverk	gräshoppa 3 sätt ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bälte CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna djävulen närvarande Regnbåge SÄKRARE HAJ FYRKANT Orm tre fiskar
Övrig	GRODA NUSH REDOC SC2000 SHACAL CS-Chiffer