Encryption DES con MICROCHIP

La casa costruttrice Microchip ha proposto tempo fa una libreria software per supportare algoritmi di data encryption quali: il Triple DES (TDES) e l’Advanced Encryption Standard (AES).

Il Data Encryption Standard (DES) è un algoritmo di cifratura con chiave a 56 bit ed è diventato famoso per essere stato scelto, nel 1976, come standard dal FIPS (Federal Information Processing Standard) per il governo degli Stati Uniti d’America. Le esigue dimensioni della chiave di codifica ed il mantenuto segreto riguardo alcune scelte progettuali resero il DES centro di numerose polemiche. Ciononostante il DES divenne, di fatto, uno standard internazionale e fu pertanto oggetto di un’intensa analisi accademica che pose le basi per la ricerca inerente gli algoritmi di cifratura ed i processi di crittoanalisi. In realtà la chiave utilizzata per la codifica tramite DES è di 64 bit, dei quali 8 utilizzati per il controllo di parità. L’algoritmo esegue una permutazione del messaggio e lo divide in blocchi. L’algoritmo di codifica esegue diversi cicli, ognuno con una chiave di ciclo diversa ottenuta per scorrimento della matrice ricavata dalla chiave effettiva di 56 bit, nei quali mette in OR un blocco del messaggio con la chiave di ciclo, e successivamente gli altri blocchi. Il prodotto finale ottenuto dalla cascata dei diversi cicli costituisce il messaggio cifrato. La figura 1 rappresenta la schematizzazione del DES, mentre la figura 4 mostra la sua struttura.

Figura 1: schematizzazione del DES.

Figura 2: lunghezza della chiave.

Figura 3: lo swap dei bit.

Figura 4: struttura del DES.

Nel 1999, dopo alcuni tentativi di violazione portati a termine nel corso dei precedenti 12 mesi, il Governo americano decise di adottarne una versione irrobustita denominata Triple-DES, in cui la cifratura si otteneva eseguendo 3 volte il DES con 3 chiavi differenti (per un totale di 168 bit complessivi), si veda la figura 6.

Figura 5: algoritmo del DES.

Figura 6: triple DES.

Solo nel 2002 il NIST ha selezionato come standard un nuovo algoritmo, il Rijndael, divenuto poi l’Advanced Encryption Standard, abbreviato AES, per pensionare il vecchio DES. Il nome AES deriva da una combinazione di quello dei due inventori; infatti, fu sviluppato da due belgi, Daemen e Rijmen, entrambi dell’università cattolica di Leuven, e sottoposto al processo di selezione dell’AES con il nome di Rijndael.

Che cos’è il DES

L’algoritmo Data Encryption Standard (DES), adottato dal governo americano nel 1977, è un blocco di crittazione che trasforma blocchi di dati a 64 bit in blocchi sotto una chiave di 56 bit tramite sostituzioni e scambi. E’ ufficialmente descritto nel FIPS PUB 46. Infatti, la chiave del DES è un blocco di 64 bit suddiviso in 8 sottoblocchi (byte) di 8 bit ciascuno; l’ultimo bit di ogni sottoblocco è di controllo: i bit liberi sono quindi 56. L’algoritmo è lo stesso sia per decifrazione e sia per la cifratura ed è mostrato graficamente in figura 5.

Il blocco identificato come plaintext in ingresso è composto da 64 bit di testo in chiaro, viene dapprima trasformato mediante una trasposizione iniziale, sezione permutation. Dopo essere sottoposto a 16 passate di una funzione F è di nuovo trasposto per mezzo di una trasposizione finale che è l’inversa di quella iniziale: l’uscita della trasposizione finale (final permutation) è il risultato finale (ciphertext). Le trasposizioni iniziali e finali sono riportate nelle tabelle 1 e 2.

Tabella 1: trasposizione iniziale - IP

Tabella 2: trasposizione finale - IP^-1

Queste tabelle vanno lette da sinistra a destra e dall’alto verso il basso. In questo modo, la trasposizione iniziale traspone:
plaintext = b1b2b3…b64 in b58b50b42…b7.

Vediamo di seguito una descrizione dell’algoritmo diviso per diverse fasi di elaborazione:

■ 1-Elaborazione della chiave. In questa fase si prende una chiave (parola) di 64 bit. Questa chiave può essere inserita direttamente o può provenire da una fonte diversa, quale un sistema di generazione automatico. L’ottavo bit di ogni byte della chiave è considerato come bit di parità. In questo modo, per ottenere una chiave con una parità corretta, ogni byte deve contenere un numero dispari di bit, cioè un numero dispari di “1” nella chiave, figura 2.

■ 2-Calcolo del key schedule. In questo passo occorre eseguire delle permutazioni sulla parola di 64-bit. Il bit 1, cioè il più significativo, diventa il bit 57 del blocco permutato della parola originale; il bit 2 diventa il 49 del blocco permutato e così via fino a quando il bit 56 diventa il bit 4 della parola originale. In questo modo i bit di parità della parola vengono scartati, figura 3.

La tabella 3 è la tabella per la sua trasposizione.

Tabella 3: permutazione (PC-1)

■ 3-A questo punto è necessario dividere la chiave permutata in due metà. I primi 28 bit sono chiamati C[0] e gli ultimi 28 bit sono chiamati D[0].

■ 4-Occorre calcolare 16 sottoparole, con i=1. Si eseguono uno o due spostamenti a sinistra con C[i-1] e D[i-1] per poi arrivare a C[i] e D[i]. I numeri utilizzati dallo shift (scorrimento) necessari per ogni esecuzione sono riportati nella tabella 4.

Tabella 4: spostamenti a sinistra

■ 5-A questo punto occorre cambiare la concatenazione C[i]D[i] come indicato sotto. Questo crea K[i], un blocco di 48 bit e per questo scopo si utilizza la tabella 5. La procedura prosegue fino a quando non si arriva a coprire K[16] ripetendo i passi al punto 4.

Tabella 5: permutazione (PC-2)

■ 6-Si procede con il blocco da 64 bit. Occorre memorizzare un blocco di 64 bit, se il blocco risulta inferiore a 64 bit, allora deve essere sistemato correttamente per questa operazione. Si eseguono le permutazioni sul blocco utilizzando la permutazione iniziale IP, tabella 1.

■ 7-Si dividono i due blocchi in 2 metà. I primi 32 bit sono chiamati L[0], mentre gli ultimi 32 bit R[0].

■ 8-Si applicano le 16 sottoparole al blocco, iniziando con i = 1.

■ 8.1-Si espandono i 32 bit R[i-1] in 48 bit come si vede nella funzione di selezione bit raffigurata in tabella 6.

Tabella 6: espansione (E)

■ 8.2-Occorre eseguire un or esclusivo E(R[i-1]) con K[i].

■ 8.3-Si suddividono E(R[i-1]) xor K[i] in 8 blocchi da 6 bit l’uno. I bit 1-6 sono B[1],i bit 7-12 sono B[2], così fino a quando i bit 43-48 diventano B[8].

■ 8.4-Sostituire tutti i valori trovati nelle S-box per tutti B[j]. Iniziando con j = 1. Tutti i valori nei S-box devono essere considerati lunghi 4 bit.

■ 8.4.1-Prendere il primo e il sesto bit di B[j] assieme come un valore a 2 bit (chiamandolo m) indicando la riga in S[j] da guardare per la sostituzione.

■ 8.4.2-Prendere il secondo e il quinto bit di B[j] assieme come un valore a 4 bit (chiamandolo n) indicando la colonna in S[j] per trovare la sostituzione.

■ 8.4.3-Sostituire B[j] con S[j][m][n] con i valori S-box

■ 8.4.4-Si conclude questo ciclo iterativo quando tutti gli 8 blocchi sono stati sostituiti ripetendo i passi previsti dal punto 8.4.1.

■ 9-Cambia la concatenazione di B[1] fino a B[8] come indicato nella tabella 7.

Tabella 7: permutazione P

■ 10-Or esclusivo dei valori risultanti con L[i-1]. Questi, tutti assieme, il tuo R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])), dove B[j] e’ un blocco a 6 bits di E(R[i-1]) xor K[i]. (La funzione di R[i] puo essere scritta semplicemente come: R[i] = L[i-1] xor f(R[i-1], K[i]).)

■ 11-Si esegue L[i] = R[i-1].

■ 12-Ritorna a 8.4.1 fino a quando K[16] e’ stato preso in considerazione.

■ 13-Per ultimo si esegue la seguente permutazione sul blocco R[16]L[16]. (nota che questo blocco R precede il blocco L questa volta.) secondo la tabella delle permutazione finale, tabella 2.

Quello che abbiamo mostrato è una descrizione dell’algoritmo DES per crittografare un blocco di 64 bit. La decrittazione utilizza lo stesso procedimento utilizzando le parole K[i] in ordine inverso. Il TripleDes è una valida alternativa al DES. In questo caso si mette in cifra il messaggio tre volte, con tre password diverse, questo permette di ottenere una dimensione delle chiavi triplicata. In ogni caso, la libreria di Microchip è corredata da un ottimo Application Note (AN1044) che ha il merito di descrive in maniera dettagliata sia il Triple-DES, che è un derivato del DES, e sia ‘AES. Microchip propone sei primitive disponibili nella libreria che distribuisce. In questo modo, qualora si volesse utilizzare il TDES sarà necessario utilizzare le tre funzioni initTDES, TDES_encrypt e TDES_decrypt. Viceversa, se si volesse, invece, utilizzare l’AES allora sarà necessario fare ricorso a AESEncrypt, AESDecrypt, AESCalcDecKey. La libreria è disponibile direttamente dalla Microchip e non può essere scaricata dal sito. Le tabella 8 mostra le prestazioni di questa implementazione; infatti, la tabella 8 pone in evidenza le prestazioni di ordine temporale.