RC5
Da Wikipedia, l'enciclopedia libera.
RC5 è un algoritmo progettato da Rivest nel 1995. Questo cifrario è completamente parametrizzato.
In Blowfish, l’unico parametro è la dimensione della chiave, mentre gli altri due parametri sono fissi. In RC5 tutti e tre i parametri sono variabili. Infatti:
- la dimensione dei blocchi è variabile; può essere di 32, 64 o 128 bit;
- il numero di round è variabile: va da 0 a 255;
- la dimensione della chiave è variabile: va da 0 a 255 byte.
Ovviamente, come vedremo, non tutti i parametri producono un algoritmo buono, perché se la taglia della chiave è 0 byte, non stiamo facendo niente. Altrettanto dicasi per i round, se è 0.
Indice |
[modifica] RC5 orientato alla parola
La caratteristica di RC5 è innanzi tutto quella di essere orientato alla parola macchina; quindi, tutte le operazioni sono eseguite su stringhe che hanno esattamente la lunghezza della parola macchina, ossia dipendente dall’architettura della macchina su cui sta girando il cifrario.
Un’altra caratteristica è che usa operazioni comuni dei processori, proprio perché sono orientati alla parola macchina ed anche rotazioni data-dependant. È un algoritmo che usa poca memoria, quindi adatto per dispositivi quali le smart card, ed è semplice da analizzare ed implementare. Infatti l’RC5 è stato utilizzato in diversi prodotti, ad es. BSAFE, JSAFE, S/MAIL.
Innanzi tutto, dobbiamo ricordare che RC5 si basa su una macchina con un’architettura little-endian. In realtà può funzionare anche su una macchina con architettura big-endian, ma il procedimento d’espansione della chiave ha bisogno di alcune modifiche. Quindi, l’architettura che noi considereremo è la little-endian.
Possiamo affermare che RC5 è una famiglia di cifrari che dipendono dai parametri
w/r/b
laddove w denota la lunghezza della parola macchina (32, 64, 128 bit), ovvero il taglio del blocco. In realtà è il cifrario che cifra 2 word di lunghezza w, ottenendo come cifrato 2 word di lunghezza w; w può essere la lunghezza di una word 16, 32, 64 bit, quindi, per l’architettura a 16 bit, funziona su parola a 16 bit, cifrando un blocco di 2w (2*16) alla volta.
Per architetture a 32 bit, la taglia del blocco è di 64 bit (2*32), per l’architettura a 64 bit la taglia del blocco è 128 (2*64).
Ecco perché prima abbiamo sostenuto che la taglia del blocco è 32, 64, 128 bit, ma in realtà sono trattate come 2 word dove la lunghezza del word è un parametro del cifrario.
r è il numero di round che varia da 0 a 255, quindi ci sarà una prima fase che sarà differente da tutte le altre, dopodiché gli r round sono tutti uguali. Ogni round utilizzerà 2 sottochiavi; in totale, dalla chiave iniziale, saranno generate 2 sottochiavi per ogni round, quindi 2r, e 2 per la fase iniziale. Pertanto, in totale saranno generate 2r+2 sottochiavi.
Quando vedremo la fase di schedulazione della chiave, noteremo che, dalla chiave composta di b bytes, che varia da 0 a 255, saranno prodotte 2r+2 sottochiavi, ed ogni sottochiave è una parola di w bit.
[modifica] RC5 w/r/b
In generale, quando si dice
RC5 w/r/b
significa che si sta indicando il cifrario RC5 che lavora su 2 parole di w bit con un numero di round pari ad r e con una chiave lunga b bytes.
Le operazioni su RC5 sono tutte orientate alla parola macchina, sono quindi tutte operazioni di w bit, e sono le seguenti:
- la somma a+b modulo 2w;
- la sottrazione a-b modulo 2w;
- a X-Or b bit a bit
- a << b (operazione data-dependant), ossia shift circolare a sinistra di b bit applicata alla word a
- a >> b (operazione data-dependant), ossia shift circolare a destra di b bit applicata alla word a
La prima operazione da vedere è la schedulazione della chiave. Partiamo da una chiave di b bytes, dove b è un parametro di RC5. Immaginiamo che questi b bytes siano memorizzati nell’array K; quindi abbiamo
K[0,….,b-1]
A partire da questa chiave devo produrre un altro array che è l’array S (array delle sottochiavi), perché in totale mi servono 2r+2 sottochiavi; quindi abbiamo
S[0,….,2r+1]
In effetti, per produrre questo array S che verrà poi usato nella fase di cifratura, devo effettuare una conversione dai bytes per ottenere delle word, dopodiché su queste word svolgerò delle operazioni per andare ad aggiornare il contenuto di questo array S (Mixing Function).
Questo array intermedio è l’array L, array di word, che si ottiene dall’array K di bytes. Su una macchina ad architettura little-endian stiamo semplicemente copiando il contenuto dell’array K nell’array L; in totale, L avrà c locazioni, dove c= .
Nel caso 8b non dovesse essere un multiplo di w, aggiungiamo degli zeri per fare il padding.
[modifica] Algoritmo di schedulazione
Vediamo l’algoritmo di schedulazione della chiave, il quale è diviso in 2 fasi:
- la prima fase va a mettere nell’array S (quello finale) dei valori d’inizializzazione che dipendono da certe costanti. In seguito, usando l’array L che contiene la chiave, tale array è modificato. Pertanto, vi è una fase d’inizializzazione costituita dalle prime 3 linee di codice, dipendenti da 2 costanti Pw e Qw, costanti di w bit. In particolare, nella prima locazione dell’array S metto Pw, e poi, dalla locazione 1 fino a 2r+1 aggiorno la locazione S[i], andando a sommare la costante Qw alla locazione immediatamente precedente. Quindi, al termine della prima fase, l’array S è pieno e dipende da queste 2 costanti. Vediamo che queste costanti dipendono dalla parola macchina e con il pedice w stiamo indicando i bit della costante. Pw è l’espansione binaria a w bit del numero di Nepero (e=2.71828182459045… in decimale); in particolare Pw =Odd[(e-2)2w] dove Odd(x) indica l’intero dispari più vicino ad x. Qw è l’espansione binaria a w bit del rapporto aureo (in decimale); in particolare, Qw =Odd[(φ-1)2w]. Questi valori sono già stati calcolati, e sono sotto forma di tabella ed il loro valore dipende dai w bit: A questo punto, l’array S contiene dei valori iniziali, e la chiave non è stata ancora usata.
- la seconda fase, chiamata Mixing Function, sfrutta l’array L, nel quale abbiamo copiato in precedenza la chiave. In particolare, quello che accade è che vi è un ciclo che è eseguito 3*max tra le cardinalità dei 2 array (tra c e 2r+2), ed in ogni operazione si va ad aggiornare l’array S e l’array L. S è aggiornato in base al valore attuale di S[i] e a 2 word a w bit, X e Y, inizialmente inizializzate a 0, e poi con uno shift a sinistra di 3 locazioni. L viene aggiornato in base al valore attuale di L[j] e a 2 word a w bit X e Y, e poi una rotazione che dipende dai dati, cioè la rotazione dipende dal valore di X+Y. Dopodiché, ogni volta, gli indici i e j vengono incrementati.
In pratica, l’array S che era stato inizializzato con le costanti Pw e Qw, subisce degli aggiornamenti che dipendono dall’array L, array di c word ottenuto dalla chiave iniziale. Il risultato finale equivale ad un array S aggiornato, array di 2r+2 locazioni, ognuna di w bit. Quindi, la fase di schedulazione della chiave prende in input una chiave di b bytes e produce 2r+2 sottochiavi, ognuna di w bit.
[modifica] Fase di cifratura
Ora descriviamo la fase di cifratura: partendo da un blocco di 2 parole di w bit, produce un altro blocco di 2 parole di w bit, tramite r round. Ogni round userà 2 chiavi schedulate e poi vi è un round iniziale che usa altre 2 sottochiavi, per un totale di 2r+2.
Nell’algoritmo, in pratica, sono svolte operazioni di somma su word di w bit, operazioni di X-Or e shift circolari data-dependant. Il testo in chiaro è memorizzato nelle 2 word A e B, ognuna di w bit e l’output sarà ancora memorizzato nelle 2 word A e B, utilizzando l’array S con 2r+2 sottochiavi schedulate.
Si aggiorna A con la prima sottochiave e B con la seconda sottochiave (abbiamo usato già 2 sottochiavi), dopodiché ci sono r round, in cui vengono usate 2 diverse sottochiavi schedulate S[2i] e S[2i+1] (abbiamo usato altre 2r sottochiavi); nel round si esegue prima l’X-Or bit a bit tra A e B, poi si esegue uno shift di B, e poi si esegue una somma con la chiave schedulata S[2i] ed andando ad aggiornare A.
Inoltre, nel round si esegue anche un X-Or bit a bit tra B ed A, poi si esegue uno shift a sinistra che dipende dal valore di A, ed infine una somma con la sottochiave S[2i+1], aggiornando il valore di B.
A differenza di DES e dei cifrari di Feistel, nell’RC5 entrambe le metà sono aggiornate nel round sia la parte A sia la parte B, mentre nei cifrari di Feistel un pezzo era ricopiato e si aggiornava mezza parte del blocco. La decifratura è perfettamente l’inversione della cifratura: infatti, sono svolti prima gli r round a partire dall’ultimo al 1° e gli ultimi 2 aggiornamenti. Le operazioni nella decifratura sono sottrazioni di word di w bit, X-Or bit a bit e shift a destra che dipendono dai valori A o B.
[modifica] Le caratteristiche di RC5
Le caratteristiche salienti di RC5 sono:
- le rotazioni sono dipendenti dai dati e non sono fisse; questo fatto complica gli attacchi di crittoanalisi differenziale e lineare, proprio perché l’ammontare dello shift dipende dal dato;
- in ogni round le operazioni coinvolgono tutto il blocco, a differenza di quello che accadeva per il DES;
- RC5 è una famiglia che dipende dai parametri r/w/b, quindi se si vuole specificare un particolare cifrario dobbiamo specificare i valori r/w/b; ad es. RC5-32/16/16 è quello che prevede la parola macchina a 32 bit, quindi che cifra blocchi di 64 bit (2 parole di 32 bit), con 16 round e 16 bytes di lunghezza per la chiave. Questa configurazione risulta essere un buon compromesso tra sicurezza ed efficienza.
[modifica] Voci correlate
[modifica] Collegamenti esterni
Portale Informatica: accedi alle voci di Wikipedia che parlano di Informatica
