RC5

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. februar 2015; checks kræver 18 redigeringer .

RC5

Skaber	Ron Rivest
Oprettet	1994
offentliggjort	1994
Nøglestørrelse	0-2040 bit (128 som standard)
Blokstørrelse	32, 64 eller 128 bit (64 er standard for 32-bit platforme)
Antal runder	1-255 (12 som standard)
Type	Feistel netværk

RC5 ( Ron's Code 5 eller Rivest's Cipher 5 ) er en blokchiffer udviklet af Ron Rivest fra RSA Security med et variabelt antal runder , bloklængde og nøglelængde . Dette udvider anvendelsesområdet og forenkler overgangen til en stærkere version af algoritmen.

Beskrivelse

Der findes flere forskellige varianter af algoritmen , hvor transformationerne i "halvrunderne" af den klassiske RC5 er noget modificeret. Den klassiske algoritme bruger tre primitive operationer og deres inversioner:

modulo tilføjelse $2^{w}$
bitvist eksklusiv ELLER ( XOR )
cykliske skiftoperationer med et variabelt antal bit ( ). $x\lll y$

Den vigtigste nyskabelse er brugen af en skiftoperation med et variabelt antal bit, som ikke blev brugt i tidligere krypteringsalgoritmer. Disse operationer er lige hurtige på de fleste processorer , men komplicerer samtidig den differentielle og lineære kryptoanalyse af algoritmen betydeligt.

Kryptering ved hjælp af RC5-algoritmen består af to trin. Nøgleudvidelsesprocedure og selve kryptering . Til dekryptering udføres nøgleudvidelsesproceduren først, og derefter vender handlingerne tilbage til krypteringsproceduren. Alle additions- og subtraktionsoperationer udføres modulo . $2^{w}$

Indstillinger

Da RC5-algoritmen har variable parametre, er betegnelsen for algoritmen med specifikke parametre RC5-W/R/b , hvor

W er halvdelen af blokkens længde i bit , mulige værdier er 16, 32 og 64. For effektiv implementering anbefales det, at værdien af W tages lig med maskinordet . For eksempel, for 32-bit platforme, er det optimale valg W = 32, hvilket svarer til en blokstørrelse på 64 bit.
R er antallet af runder , mulige værdier er fra 0 til 255. Forøgelse af antallet af runder giver en stigning i sikkerhedsniveauet for chifferen. Så når R = 0, bliver informationen ikke krypteret. RC5-algoritmen bruger også en ordlængde udvidet nøgletabel, der er afledt af en brugerspecificeret nøgle. $2(R+1)$
b er længden af nøglen i bytes , mulige værdier er fra 0 til 255.

Nøgleudvidelse

Før direkte kryptering eller dekryptering af data udføres en nøgleudvidelsesprocedure. Nøglegenereringsproceduren består af fire trin:

Konstant generation
Spaltning af nøglen i ord
Opbygning af et bord med udvidede nøgler
Blanding

Konstant generation

For en given parameter genereres to pseudo-random variable ved hjælp af to matematiske konstanter: ( eksponent ) og ( Gyldent forhold ). $W$ $e$ $f$

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

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

hvor er afrunding til nærmeste ulige heltal. ${\textrm {Ulige}}()$

For du får følgende 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}$

Opdele nøglen i ord

På dette trin kopieres nøglen til en række ord ... , hvor , hvor , dvs. antallet af bytes i et ord. $K_{0}\dots K_{{b-1}}$ $L_0$ $L_{{c-1}}$ $c=b/u$ $u=W/8$

Hvis ikke et multiplum af , så polstret med nul bit til det nærmeste større multiplum af . $b$ $W/8$ $L$ $c$ $W/8$

Hvis , så sætter vi værdien af , og . $b=c=0$ $c=1$ $L_{0}=0$

Opbygning af en tabel med udvidede nøgler

På dette stadium er det udvidede nøglebord bygget , som udføres som følger: $S_{0}\dots S_{{2*(R+1)-1}}$

S_{0}=P_{w}

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

Bland

Følgende handlinger udføres cyklisk N gange:

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

hvor er midlertidige variabler, hvis startværdier er lig med 0. Antallet af iterationer af løkken er det maksimale af de to værdier og . $G,H,i,j$ $N$ $3*c$ $(3\cdot 2\cdot (R+1))$

Kryptering

Inden første runde udføres operationerne med at pålægge en udvidet nøgle på de krypterede data:

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

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

I hver runde udføres følgende handlinger:

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

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

Dekryptering

Til datadekryptering bruges omvendte operationer, det vil sige , at følgende runder udføres: $i=R,R-1,...,1$

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

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

Efter at alle runder er gennemført, findes den oprindelige besked fra udtrykket:

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

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

Egenskaber

RC5-algoritmen har følgende egenskaber: [1]

Velegnet til både hardware- og softwareimplementering (algoritmen bruger operationer, der kører lige hurtigt på alle processorer ).
Hver runde behandler hele blokken (en typisk Feistel-netværksrunde behandler kun en "underblok").
Lige så god til maskiner med forskellige maskinordlængder (det vil sige, det fungerer også godt på 64-bit maskiner).
Den har en gentagende struktur med et variabelt antal runder, som giver brugeren mulighed for at vælge mellem en højere krypteringshastighed og en mere sikker chiffer.
Den har en variabel nøglelængde, som giver brugeren mulighed for at vælge det sikkerhedsniveau, der passer til de specifikke applikationer.
Ret nem at implementere og analysere.
Det er ikke krævende for hukommelsen, hvilket gør det muligt at bruge det selv i mobile og bærbare enheder.

Sikkerhed

RSA har brugt meget tid på at analysere, hvordan det fungerer med en 64-bit blok. Så i perioden fra 1995 til 1998 udgav de en række rapporter, hvor de analyserede i detaljer den kryptografiske styrke af RC5-algoritmen. Scoren for lineær kryptoanalyse viser, at algoritmen er sikker efter 6 runder. Differentiel kryptoanalyse kræver udvalgte klartekster til 5-runders algoritme, for 10-runder, for 12-runder og for 15-runder. Og da der kun er mulige forskellige klartekster, er differentiel kryptoanalyse umulig for en algoritme på 15 eller flere runder. Så det anbefales at bruge 18-20 runder, eller mindst 15 runder i stedet for de 12 runder, som Rivest selv anbefalede. $2^{24}$ $2^{{45}}$ $2^{{53}}$ $2^{{68}}$ $2^{64}$

RSA Security Challenge

For at stimulere undersøgelsen og brugen af RC5-chifferet tilbød RSA Security den 28. januar 1997 at bryde en række meddelelser krypteret med RC5-algoritmen med forskellige parametre, [2] ved at tildele en præmie på $10.000 for at bryde hver meddelelse. de svageste parametre er RC5-32/12/5 blev hacket inden for et par timer. Den sidste RC5-32/12/8-chiffer, der blev knækket, krævede dog 5 års beregning af det distribuerede computerprojekt RC5-64 (her 64= b 8, nøglelængde i bit) ledet af distributed.net . RC5-32 /12/ b for b fra 9 til 16 er stadig uigennemtrængeligt . % nøgler. [3]

I maj 2007 var RSA Security Inc. annoncerede opsigelse af støtten til konkurrencen og udbetaling af pengebelønninger. For at holde RC-72- projektet i gang , besluttede distributed.net at sponsorere en præmie på $4.000 til det af egne midler. [fire]

Runtime angreb

På platforme, hvor et variabelt antal bits rotationsoperation udføres for et andet antal processorcyklusser , er et runtime- angreb på RC5-algoritmen muligt. To varianter af et sådant angreb blev formuleret af kryptoanalytikerne Howard Hayes og Helena Handschuh . De fandt ud af, at nøglen kunne beregnes efter at have udført omkring 220 krypteringsoperationer med meget nøjagtige udførelsestider og derefter 228 til 240 prøvekrypteringsoperationer. Den enkleste metode til at bekæmpe sådanne angreb er at tvinge skift til at blive udført i et konstant antal cyklusser (for eksempel under udførelsen af det langsomste skift).

Varianter af algoritmen

Da en af egenskaberne ved RC5 er dens lette implementering og analyse, er det logisk, at mange kryptologer[ hvem? ] ønskede at forbedre den klassiske algoritme. Algoritmens generelle struktur forblev uændret, kun de handlinger, der blev udført på hver blok i selve krypteringsprocessen, ændrede sig . Så der var flere forskellige versioner af denne algoritme:

RC5XOR

I denne algoritme erstattes addition med modulo-rundtasten af 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))

Denne algoritme viste sig at være sårbar over for differentiel og lineær kryptoanalyse. Biryukov og Kushilevits formåede at finde et differentielt kryptoanalyseangreb for RC5XOR-32/12/16-algoritmen ved hjælp af 228 udvalgte klartekster.

RC5P

I denne algoritme erstattes tilføjelsen af to behandlede "underblokke" af 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}

Denne algoritme viste sig at være sårbar over for differentiel kryptoanalyse.

RC5PFR

I denne algoritme udføres det cykliske skift af et fast antal bits for en given runde og ikke af 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}

hvor er et fast nummer. $R_i$

Denne algoritme er ikke godt forstået, men det antages at[ af hvem? ] at den er ustabil overfor differentiel kryptoanalyse.

RC5KFR

I denne algoritme afhænger antallet af bit, der skal skiftes, af nøglen til algoritmen og af den aktuelle runde:

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

Denne algoritme er heller ikke godt forstået.

RC5RA

I denne algoritme bestemmes antallet af skiftbit ved hjælp af en funktion fra en anden "underblok":

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

Formodes,[ af hvem? ] at RC5RA-algoritmen er endnu mere modstandsdygtig over for kendte kryptoanalysemetoder end RC5.

Noter

↑ Rivest, R. L. (1994). "RC5-krypteringsalgoritmen" (pdf) . Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e . pp. 86-96. "ref-en" tekst udeladt ( hjælp ) Arkiveret 17. april 2007 på Wayback Machine
↑ RSA Laboratories Secret-Key Challenge arkiveret 23. maj 2004.
↑ RC5-72: Overordnet projektstatistik . Hentet 14. februar 2010. Arkiveret fra originalen 9. oktober 2018. (ubestemt)
↑ distributed.net: personaleblogs - 2008 - september - 08

Links

Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Ofte stillede spørgsmål om symmetriske chiffer (link ikke tilgængeligt) . - baseret på materialerne fra fido7.ru.crypt-konferencen. Hentet 11. november 2009. Arkiveret fra originalen 22. august 2011. (Russisk)
Moderne metoder til at bryde krypteringsalgoritmer (utilgængeligt link) . — Beskrivelse af nogle angrebsmetoder på krypteringsalgoritmer. Hentet 4. december 2009. Arkiveret fra originalen 21. maj 2009. (Russisk)

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher