L'algoritmo più comune e conosciuto crittografia simmetricaÈ DES (Standard di crittografia dei dati). L’algoritmo è stato sviluppato nel 1977 ed è stato adottato come standard dal NIST (National Institute of Standards and Technology, USA) nel 1980.
DES lo è rete classica Feishtel con due rami. I dati vengono crittografati in blocchi a 64 bit utilizzando una chiave a 56 bit. L'algoritmo converte un input a 64 bit in un output a 64 bit in diversi cicli. La lunghezza della chiave è di 56 bit. Il processo di crittografia si compone di quattro fasi. La prima fase esegue una permutazione iniziale (IP) del testo sorgente a 64 bit (whitening), durante la quale i bit vengono riordinati secondo tabella standard. La fase successiva è composta da 16 round della stessa funzione, che utilizza le operazioni di spostamento e sostituzione. Nella terza fase, le metà sinistra e destra dell'output dell'ultima (16a) iterazione vengono scambiate. Infine, il quarto stadio esegue una permutazione IP-1 del risultato ottenuto nel terzo stadio. La permutazione IP-1 è l'inverso della permutazione iniziale.
Fig.4. Algoritmo DES
La figura mostra un metodo che utilizza una chiave a 56 bit. Inizialmente, la chiave viene fornita all'input della funzione di permutazione. Quindi, per ciascuno dei 16 round, la sottochiave K i è una combinazione di spostamento circolare sinistro e permutazione. La funzione di permutazione è la stessa per ogni round, ma le sottochiavi K i per ogni round sono diverse a causa del ripetuto spostamento dei bit della chiave.
La permutazione iniziale e la sua inversione sono determinate da una tabella standard. Se M è 64 bit arbitrari, allora X = IP(M) sono i 64 bit riorganizzati. Se applichiamo la funzione di permutazione inversa Y = IP-1 (X) = IP-1 (IP(M)), otteniamo la sequenza di bit originale.
Descrizione del giro des
Diamo un'occhiata alla sequenza delle trasformazioni utilizzate in ogni round.
Fig.5. Illustrazione di un giro dell'algoritmo DES
Un blocco di input a 64 bit passa attraverso 16 giri, con ogni iterazione che produce un valore intermedio a 64 bit. I lati sinistro e destro di ciascun valore intermedio vengono trattati come valori separati a 32 bit, indicati L e R. Ogni iterazione può essere descritta come segue:
R io = L io -1 F(R io -1 , K io)
Pertanto, l'output della metà sinistra L i è uguale all'input della metà destra R i-1. L'output della metà destra di R i è il risultato dell'applicazione di un'operazione XOR a L i-1 e di una funzione F dipendente da R i-1 e K i .
Diamo un'occhiata alla funzione F in modo più dettagliato. R i , che viene fornito all'ingresso della funzione F, ha una lunghezza di 32 bit. Innanzitutto, R i viene espanso a 48 bit utilizzando una tabella che specifica la permutazione più l'espansione a 16 bit. L'espansione avviene come segue. I 32 bit vengono divisi in gruppi di 4 bit e quindi espansi a 6 bit aggiungendo i bit più esterni di due gruppi adiacenti. Ad esempio, se parte del messaggio di input
Efgh ijkl mnop . . .
quindi il risultato dell'espansione è il messaggio
Defghi hijklm lmnopq. . .
Il valore risultante a 48 bit viene quindi sottoposto a XOR con la sottochiave a 48 bit K i . Il valore risultante a 48 bit viene quindi inserito nella funzione di sostituzione, che risulta in un valore a 32 bit.
La sostituzione consiste di otto S-box, ciascuna delle quali riceve 6 bit in ingresso e produce 4 bit in uscita. Queste trasformazioni sono definite da tabelle speciali. Il primo e l'ultimo bit del valore di input della S-box determinano il numero di riga nella tabella, i 4 bit centrali determinano il numero di colonna. L'intersezione di una riga e di una colonna determina l'output a 4 bit. Ad esempio, se l'input è 011011, il numero di riga è 01 (riga 1) e il numero di colonna è 1101 (colonna 13). Il valore nella riga 1 e nella colonna 13 è 5, ovvero l'uscita è 0101.
Il valore risultante a 32 bit viene quindi elaborato utilizzando la permutazione P, il cui scopo è riordinare i bit il più possibile in modo che nel successivo ciclo di crittografia ogni bit venga probabilmente elaborato da una S-box diversa.
La chiave per un singolo round K i è composta da 48 bit. Le chiavi K i sono ottenute utilizzando il seguente algoritmo. Per la chiave a 56 bit utilizzata come input per l'algoritmo, viene prima eseguita una permutazione secondo la tabella Permuted Choice 1 (PC-1). La chiave risultante a 56 bit è divisa in due parti a 28 bit, indicate rispettivamente come C0 e D0. Ad ogni round, C i e D i vengono spostati ciclicamente a sinistra indipendentemente di 1 o 2 bit, a seconda del numero di round. I valori risultanti sono l'input per il turno successivo. Sono anche l'input di Permuted Choice 2 (PC-2), che produce un valore di output a 48 bit che è l'input della funzione F(R i-1, K i).
Il processo di decrittografia è simile al processo di crittografia. L'input dell'algoritmo è un testo cifrato, ma le chiavi K i vengono utilizzate in ordine inverso. Nel primo giro si usa dir 16, nell'ultimo giro si usa dir 1. Sia l'output dell'i-esimo ciclo di crittografia L i ||R i . Quindi l'input corrispondente del (16-i)-esimo round di decrittazione sarà R i ||L i .
Dopo l'ultimo giro del processo di decrittazione, le due metà dell'output vengono scambiate in modo che l'input della permutazione finale IP-1 sia R 16 ||L 16 . L'output di questa fase è testo in chiaro.
- Esercitazione
Ciao %nomeutente%!
Molte persone sanno che lo standard predefinito nel campo della crittografia simmetrica per molto tempo era considerato Algoritmo DES. Il primo attacco riuscito a questo algoritmo immortale è stato pubblicato nel 1993, 16 anni dopo la sua adozione come standard. Il metodo, che l'autore ha chiamato crittoanalisi lineare, in presenza di 2 47 coppie testo chiaro/cifrato, consente di aprire la chiave segreta del cifrario DES in 2 43 operazioni.
Di seguito al taglio cercherò di delineare brevemente i punti principali di questo attacco.
Crittoanalisi lineare
La crittoanalisi lineare è un tipo speciale di attacco cifre simmetriche, volto a recuperare una chiave di crittografia sconosciuta da un file noto aprire i messaggi e i relativi testi cifrati.IN caso generale Un attacco basato sulla crittoanalisi lineare si riduce alle seguenti condizioni. L'attaccante ha grande quantità coppie testo in chiaro/testo cifrato ottenute utilizzando la stessa chiave di crittografia K. L'obiettivo dell'attaccante è recuperare parte o tutta la chiave K.
Prima di tutto, l'aggressore esamina il codice e trova il cosiddetto analogo statistico, cioè un'equazione della forma seguente, che vale con probabilità P ≠ 1/2 per una coppia arbitraria di testo pubblico/privato e una chiave fissa:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
dove P n, C n, K n sono gli n-esimi bit del testo, testo cifrato e chiave.
Una volta trovata tale equazione, l'aggressore può recuperare 1 bit di informazioni chiave utilizzando il seguente algoritmo
Algoritmo 1
Sia T il numero di testi per i quali il membro sinistro dell'equazione (1) è uguale a 0, quindi
Se T>N/2, dove N è il numero di testi in chiaro conosciuti.
Supponiamo che K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (quando P>1/2) o 1 (quando P<1/2).
Altrimenti
Supponiamo che K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (quando P>1/2) o 0 (quando P<1/2).
È ovvio che il successo dell'algoritmo dipende direttamente dal valore di |P-1/2| e dal numero di coppie di testi aperti/chiusi disponibili N. Quanto più la probabilità P di uguaglianza (1) differisce da 1/2, tanto minore è il numero di testi aperti N necessari per l'attacco.
I problemi da risolvere affinché l’attacco abbia successo sono due:
- Come trovare un'equazione efficace della forma (1).
- Come utilizzare questa equazione per ottenere più di un bit di informazioni sulla chiave.
Descrizione del DES
Ma prima descriviamo brevemente come funziona l'algoritmo. Del DES è già stato detto abbastanza. Una descrizione completa del cifrario può essere trovata su Wikipedia. Tuttavia, per spiegare ulteriormente l’attacco avremo bisogno di una serie di definizioni che è meglio introdurre in anticipo.Quindi, DES è un codice a blocchi basato sulla rete Feistel. Il codice ha una dimensione del blocco di 64 bit e una dimensione della chiave di 56 bit. Consideriamo lo schema di crittografia dell'algoritmo DES. 
Come si può vedere dalla figura, durante la crittografia del testo vengono eseguite le seguenti operazioni:
- Permutazione iniziale dei bit. In questa fase, i bit del blocco di input vengono mescolati in un certo ordine.
- Successivamente i bit misti vengono divisi in due metà, che vengono inviate all'ingresso della funzione Feistel. Per il DES standard, la rete Feistel include 16 round, ma esistono altre varianti dell'algoritmo.
- I due blocchi ottenuti nell'ultimo giro di trasformazione vengono combinati e sul blocco risultante viene eseguita un'altra permutazione.
In ogni giro della rete Feistel, i 32 bit meno significativi del messaggio vengono fatti passare attraverso la funzione f: 
Vediamo le operazioni eseguite in questa fase:
- Il blocco di input viene passato attraverso la funzione di estensione E, che converte un blocco da 32 bit in un blocco da 48 bit.
- Il blocco risultante viene aggiunto alla chiave rotonda K i .
- Il risultato del passo precedente è diviso in 8 blocchi da 6 bit ciascuno.
- Ciascuno dei blocchi B i ricevuti viene fatto passare attraverso la funzione di sostituzione S-Box i , che sostituisce la sequenza di 6 bit con un blocco di 4 bit.
- Il blocco risultante a 32 bit viene passato attraverso la permutazione P e restituito come risultato della funzione f.
Di grande interesse per noi dal punto di vista della crittoanalisi cifrata sono i blocchi S, progettati per nascondere la connessione tra i dati di input e di output della funzione f. Per attaccare con successo il DES, costruiremo prima analoghi statistici per ciascuna delle S-box, e poi li estenderemo all'intero cifrario.
Analisi del blocco S
Ciascuna S-box accetta una sequenza di 6 bit come input e per ciascuna di queste sequenze viene restituito un valore fisso di 4 bit. Quelli. ci sono un totale di 64 opzioni di input e output. Il nostro compito è mostrare la relazione tra i dati di ingresso e di uscita dei blocchi S. Ad esempio, per la terza S-box del cifrario DES, il 3° bit della sequenza di input è uguale al 3° bit della sequenza di output in 38 casi su 64. Pertanto, abbiamo trovato il seguente analogo statistico per la terza S -scatola:S 3 (x) = x, che si realizza con probabilità P=38/64.
Entrambi i lati dell'equazione rappresentano 1 bit di informazione. Pertanto, se i lati sinistro e destro fossero indipendenti l'uno dall'altro, l'equazione dovrebbe essere soddisfatta con una probabilità pari a 1/2. Pertanto, abbiamo appena dimostrato la relazione tra l'input e l'output della terza S-box dell'algoritmo DES.
Consideriamo come possiamo trovare un analogo statistico della S-box nel caso generale.
Per una S-box S a , 1 ≤ α ≤ 63 e 1 ≤ β ≤ 15, il valore NS a (α, β) descrive quante volte su 64 possibili bit di ingresso XOR S a sovrapposti ai bit α sono uguali a i bit di uscita XOR sovrapposti ai bit α β, ovvero:
dove il simbolo è AND logico.
I valori di α e β per i quali NS a (α, β) è maggiormente diverso da 32 descrivono l'analogo statistico più efficiente della S-box S a .
L'analogo più efficace è stato trovato nel 5° S-box del cifrario DES per α = 16 e β = 15 NS 5 (16, 15) = 12. Ciò significa che vale la seguente equazione: Z=Y ⊕ Y ⊕ Y ⊕ Y, dove Z è la sequenza di input della S-box e Y è la sequenza di output.
Oppure tenendo conto del fatto che nell'algoritmo DES, prima di entrare nella S-box, i dati vengono sommati modulo 2 con una chiave rotonda, cioè Z = X ⊕ K otteniamo
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, dove X e Y sono i dati di input e output della funzione f senza tenere conto delle permutazioni.
L'equazione risultante viene eseguita su tutti i cicli dell'algoritmo DES con la stessa probabilità P=12/64.
La tabella seguente mostra un elenco di quelli efficaci, vale a dire avendo la deviazione maggiore da P=1/2, analoghi statistici per ciascun blocco s dell'algoritmo DES. 
Costruzione di analoghi statistici per più cicli di DES
Mostriamo ora come possiamo combinare gli analoghi statistici di diversi cicli di DES e infine ottenere un analogo statistico per l'intero cifrario.Per fare ciò, considera una versione a tre round dell’algoritmo:
Usiamo un efficiente analogo statistico della quinta s-box per calcolare alcuni bit del valore X(2).
Sappiamo che con probabilità 12/64 l'uguaglianza vale nella funzione f X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, dove X è il secondo bit di ingresso della 5a S-box, è essenzialmente il 26° bit della sequenza ottenuta dopo aver espanso i bit di ingresso. Analizzando la funzione di espansione possiamo stabilire che il 26° bit è sostituito dal 17° bit della sequenza X(1).
Allo stesso modo, Y,..., Y sono essenzialmente il 17°, 18°, 19° e 20° bit della sequenza ottenuta prima della permutazione P. Esaminando la permutazione P, troviamo che i bit Y,..., Y sono in realtà i bit Y (1), Y(1), Y(1), Y(1).
Il bit chiave K coinvolto nelle equazioni è il 26° bit della prima sottochiave K1 e quindi l'analogo statistico assume la seguente forma:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Quindi, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) con probabilità P=12/64.
Conoscendo 3, 8, 14, 25 bit della sequenza Y(1), puoi trovare 3, 8, 14, 25 bit della sequenza X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) o tenendo conto dell'equazione (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) con una probabilità di 12/64.
Troviamo un'espressione simile usando l'ultimo round. Questa volta abbiamo l'equazione
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Perché
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
lo capiamo
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4)
con una probabilità di 12/64.
Uguagliando i membri destri delle equazioni (3) e (4) otteniamo
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 con probabilità (12/64) 2 +(1-12/64) 2.
Tenendo conto del fatto che X(1) = PR e X(3) = CR otteniamo un analogo statistico
áL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5)
,
che viene eseguito con probabilità (12/64) 2 + (1-12/64) 2 =0,7.
L'analogo statistico sopra descritto può essere rappresentato graficamente come segue (i bit nella figura sono numerati da destra a sinistra e partendo da zero): 
Tutti i bit sul lato sinistro dell'equazione sono noti all'attaccante, quindi può applicare l'algoritmo 1 e scoprire il valore di K1 ⊕ K3. Mostriamo come, utilizzando questo analogo statistico, è possibile aprire non 1, ma 12 bit della chiave di crittografia K.
Attacco al DES con testo in chiaro noto
Presentiamo un metodo con il quale è possibile espandere l'attacco e ottenere immediatamente 6 bit della prima connessione.Nel comporre l'equazione (5), abbiamo tenuto conto del fatto che non conosciamo il valore di F1(PR, K1). Pertanto, abbiamo utilizzato il suo analogo statistico K1 ⊕ PR.
Restituiamo il valore F1(PR, K1) al posto dell'espressione K1 ⊕ PR e otteniamo la seguente equazione:
áL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , che verrà eseguito con probabilità 12/64. La probabilità è cambiata poiché abbiamo lasciato solo l’analogo statistico del terzo round, tutti gli altri valori sono fissi.
Abbiamo già determinato sopra che il valore di F1(PR, K1) è influenzato dai bit di ingresso della 5a S-box, vale a dire dai bit chiave K1 e dai bit del blocco PR. Mostriamo come, avendo solo un insieme di testi aperti/chiusi, è possibile ripristinare il valore di K1. Per fare ciò, utilizzeremo l’algoritmo 2.
Algoritmo 2
Sia N il numero di coppie di testo aperto/chiuso conosciute prima dell'attacco. Quindi per aprire la chiave è necessario eseguire i seguenti passaggi.
Per (i=0; i<64; i++) do
{
Per(j=0; j
se(áL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) allora
T io = T io +1
}
}
Come probabile sequenza K1, viene preso un valore di i tale che l'espressione |T i -N/2| ha il valore massimo.
Dato un numero sufficiente di testi in chiaro conosciuti, l'algoritmo avrà un'alta probabilità di restituire il valore corretto dei sei bit della prima sottochiave K1. Ciò è spiegato dal fatto che se la variabile i non è uguale a K1, allora il valore della funzione F1(PR j, K) sarà casuale e il numero di equazioni per tale valore di i per cui il lato sinistro è uguale a zero tenderà a N/2. Se la sottochiave viene indovinata correttamente, il lato sinistro sarà uguale al bit fisso K3 con probabilità 12/64. Quelli. ci sarà una deviazione significativa da N/2.
Avendo ricevuto 6 bit della sottochiave K1, puoi allo stesso modo aprire 6 bit della sottochiave K3. Tutto quello che devi fare è sostituire C con P e K1 con K3 nell'equazione (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
L'algoritmo 2 restituirà il valore K3 corretto perché il processo di decrittografia dell'algoritmo DES è identico al processo di crittografia, solo la sequenza della chiave è invertita. Quindi nel primo ciclo di decrittazione viene utilizzata la chiave K3 e nell'ultimo ciclo viene utilizzata la chiave K1.
Avendo ricevuto 6 bit delle sottochiavi K1 e K3, l'attaccante recupera 12 bit della chiave comune della cifra K, perché le chiavi rotonde sono la consueta permutazione della chiave K. Il numero di testi in chiaro necessari per un attacco riuscito dipende dalla probabilità dell'analogo statistico. Per craccare una chiave DES a 12 bit e 3 round, sono sufficienti 100 coppie di testo pubblico/privato. Per aprire 12 bit di una chiave DES a 16 round, saranno necessarie circa 244 coppie di testi. I restanti 44 bit della chiave vengono aperti utilizzando la normale forza bruta.
Algoritmo DES
I principali vantaggi dell'algoritmo DES:
· viene utilizzata una sola chiave di lunghezza pari a 56 bit;
· dopo aver crittografato un messaggio utilizzando un pacchetto, è possibile utilizzarne un altro per decrittografarlo;
· la relativa semplicità dell'algoritmo garantisce un'elevata velocità di elaborazione delle informazioni;
· stabilità sufficientemente elevata dell'algoritmo.
DES crittografa blocchi di dati a 64 bit utilizzando una chiave a 56 bit. La decrittazione in DES è l'operazione inversa della crittografia e viene eseguita ripetendo le operazioni di crittografia in ordine inverso (nonostante l'apparente ovvietà, questo non sempre viene fatto. Successivamente esamineremo i cifrari in cui crittografia e decrittografia vengono eseguite utilizzando algoritmi diversi) .
Il processo di crittografia consiste in una permutazione iniziale dei bit di un blocco di 64 bit, sedici cicli di crittografia e, infine, una permutazione inversa dei bit (Fig. 1).
Va subito notato che TUTTE le tabelle fornite in questo articolo sono STANDARD e pertanto dovrebbero essere incluse nell'implementazione dell'algoritmo senza modifiche. Tutte le permutazioni e i codici nelle tabelle sono selezionati dagli sviluppatori in modo tale da rendere il processo di decrittazione il più difficile possibile selezionando una chiave. La struttura dell'algoritmo DES è mostrata in Fig. 2.
Fig.2. Struttura dell'algoritmo di crittografia DES
Si legga il successivo blocco T da 8 byte dal file, che viene trasformato utilizzando la matrice di permutazione iniziale IP (Tabella 1) come segue: il bit 58 del blocco T diventa il bit 1, il bit 50 diventa il bit 2, ecc., che sarà risultato in: T(0) = IP(T).
La sequenza di bit risultante T(0) è divisa in due sequenze di 32 bit ciascuna: L(0) - bit sinistri o di ordine superiore, R(0) - bit destri o di ordine inferiore.
Tabella 1: Matrice di permutazione iniziale IP
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Quindi viene eseguita la crittografia, composta da 16 iterazioni. Il risultato dell'i-esima iterazione è descritto dalle seguenti formule:
R(i) = L(i-1) xor f(R(i-1), K(i)) ,
dove xor è l'operazione OR ESCLUSIVO.
La funzione f è chiamata funzione di crittografia. I suoi argomenti sono la sequenza di 32 bit R(i-1), ottenuta alla (i-1)esima iterazione, e la chiave di 48 bit K(i), che è il risultato della conversione della chiave di 64 bit K. Nel dettaglio, la funzione di crittografia e l'algoritmo per ottenere le chiavi K(i) sono descritti di seguito.
Alla 16a iterazione si ottengono le sequenze R(16) e L(16) (senza permutazione), che vengono concatenate in una sequenza R(16)L(16) a 64 bit.
Quindi le posizioni dei bit di questa sequenza vengono riorganizzate secondo la matrice IP -1 (Tabella 2).
Tabella 2: Matrice di permutazione inversa IP -1
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
Le matrici IP -1 e IP sono correlate come segue: il valore del 1° elemento della matrice IP -1 è 40, e il valore del 40° elemento della matrice IP è 1, il valore del 2° l'elemento della matrice IP -1 è 8 e il valore dell'ottavo elemento della matrice IP è uguale a 2, ecc.
Il processo di decrittografia dei dati è inverso al processo di crittografia. Tutti i passaggi devono essere eseguiti in ordine inverso. Ciò significa che i dati decrittografati vengono prima riorganizzati secondo la matrice IP-1, quindi sulla sequenza di bit R(16)L(16) vengono eseguite le stesse azioni del processo di crittografia, ma in ordine inverso.
Il processo di decrittazione iterativo può essere descritto dalle seguenti formule:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, ..., 16 .
Alla 16a iterazione si ottengono le sequenze L(0) e R(0), che vengono concatenate in una sequenza L(0)R(0) a 64 bit.
Le posizioni dei bit di questa sequenza vengono quindi riorganizzate in base alla matrice IP. Il risultato di tale permutazione è la sequenza originale a 64 bit.
Consideriamo ora la funzione di crittografia f(R(i-1),K(i)). È mostrato schematicamente in Fig. 3.
Fig.3. Calcolo della funzione f(R(i-1), K(i))
Per calcolare il valore della funzione f, vengono utilizzate le seguenti funzioni di matrice:
E - estensione di una sequenza da 32 bit a 48 bit,
S1, S2, ..., S8 - conversione di un blocco da 6 bit in uno da 4 bit,
P - permutazione di bit in una sequenza di 32 bit.
La funzione di espansione E è definita nella Tabella 3. Secondo questa tabella, i primi 3 bit di E(R(i-1)) sono i bit 32, 1 e 2 e gli ultimi sono 31, 32 e 1.
Tabella 3: Funzione di estensione E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
Il risultato della funzione E(R(i-1)) è una sequenza di 48 bit che viene sommata modulo 2 (operazione xor) con la chiave di 48 bit K(i). La sequenza risultante di 48 bit è divisa in otto blocchi da 6 bit B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). Questo è:
E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .
Le funzioni S1, S2, ..., S8 sono definite nella Tabella 4.
Tabella 4
Alla tabella 4. sono necessari ulteriori chiarimenti. Sia l'input della funzione di matrice Sj un blocco a 6 bit B(j) = b1b2b3b4b5b6, quindi il numero a due bit b1b6 indica il numero di riga della matrice e b2b3b4b5 il numero di colonna. Il risultato di Sj(B(j)) sarà un elemento a 4 bit situato all'intersezione della riga e della colonna specificate.
Ad esempio, B(1)=011011. Quindi S1(B(1)) si trova all'intersezione tra la riga 1 e la colonna 13. Nella colonna 13 della riga 1 il valore è 5. Ciò significa S1(011011)=0101.
Applicando l'operazione di selezione a ciascuno dei blocchi da 6 bit B(1), B(2), ..., B(8), otteniamo la sequenza di 32 bit S1(B(1))S2(B(2 ))S3( B(3))...S8(B(8)).
Infine, per ottenere il risultato della funzione di crittografia, è necessario riorganizzare i bit di questa sequenza. A questo scopo viene utilizzata la funzione di permutazione P (Tabella 5). Nella sequenza di input, i bit vengono riorganizzati in modo che il bit 16 diventi il bit 1, il bit 7 diventi il bit 2 e così via.
Tabella 5: Funzione di permutazione P
Così,
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Per completare la descrizione dell'algoritmo di crittografia dei dati, resta da presentare l'algoritmo per ottenere chiavi a 48 bit K(i), i=1...16. Ad ogni iterazione viene utilizzato un nuovo valore di chiave K(i), calcolato dalla chiave iniziale K. K è un blocco di 64 bit con otto bit di parità situati nelle posizioni 8,16,24,32,40,48, 56.64.
Per rimuovere i bit di controllo e riorganizzare quelli rimanenti, viene utilizzata la funzione G della preparazione iniziale della chiave (Tabella 6).
Tabella 6
Matrice G di preparazione della chiave iniziale
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
Il risultato della trasformazione G(K) sarà diviso in due blocchi da 28 bit C(0) e D(0), e C(0) sarà composto dai bit 57, 49, ..., 44, 36 della chiave K e D(0 ) saranno costituiti dai bit 63, 55, ..., 12, 4 della chiave K. Dopo aver definito C(0) e D(0), C(i) e D(i), i= 1...16, sono determinati ricorsivamente. Per fare ciò, applicare uno spostamento ciclico a sinistra di uno o due bit, a seconda del numero di iterazioni, come mostrato nella Tabella 7.
Tabella 7
Tabella dei turni per il calcolo delle chiavi
| Numero di iterazione | Shift (bit) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
Il valore risultante viene nuovamente “miscelato” secondo la matrice H (Tabella 8).
Tabella 8: Matrice di completamento chiave H
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
La chiave K(i) sarà composta dai bit 14, 17, ..., 29, 32 della sequenza C(i)D(i). Così:
K(i) = H(C(i)D(i))
Lo schema a blocchi dell'algoritmo di calcolo della chiave è mostrato in Fig. 4.
Fig.4. Schema a blocchi dell'algoritmo per il calcolo della chiave K(i)
Il ripristino del testo originale viene eseguito utilizzando questo algoritmo, ma prima si utilizza la chiave
K(15), poi K(14) e così via. Ora dovresti capire perché l'autore consiglia insistentemente di utilizzare le matrici fornite. Se diventi un ladro, potresti ritrovarti con un codice molto segreto, ma non sarai in grado di decifrarlo da solo!
Modalità operative dell'algoritmo DES
Per soddisfare al meglio tutti i requisiti dei sistemi di crittografia commerciali, sono implementate diverse modalità di funzionamento dell'algoritmo DES. Le modalità più utilizzate sono:
· codebook elettronico (Electronic Codebook) – BCE;
· catena di blocchi digitali (Cipher Block Chaining) - CBC;
· feedback digitale (Cipher Feedback) - CFB;
· feedback esterno (Output Feedback) - OFB.
In questa modalità, il file sorgente M è diviso in blocchi da 64 bit (8 byte ciascuno): M = M(1)M(2)...M(n). Ciascuno di questi blocchi viene crittografato in modo indipendente utilizzando la stessa chiave di crittografia (Fig. 5). Il vantaggio principale di questo algoritmo è la sua facilità di implementazione. Lo svantaggio è che è relativamente debole contro i crittoanalisti esperti.
DES(Data Encryption Standard) - Un algoritmo di crittografia simmetrico in cui una chiave viene utilizzata sia per la crittografia che per la decrittografia dei dati. Il DES è stato sviluppato da IBM e approvato dal governo statunitense nel 1977 come standard ufficiale (FTPS 46-3). DES ha blocchi a 64 bit e una struttura di rete Feistel a 16 cicli; utilizza una chiave a 56 bit per la crittografia. L'algoritmo utilizza una combinazione di trasformazioni non lineari (S-box) e lineari (permutazioni E, IP, IP-1). Per DES sono consigliate diverse modalità:Cifratura a blocchi
I dati di input per un codice a blocchi sono un blocco di n bit e una chiave di k bit. L'output, dopo aver applicato la trasformazione della crittografia, è un blocco crittografato a n bit e piccole differenze nei dati di input solitamente portano a un cambiamento significativo nel risultato. I codici a blocchi vengono implementati applicando ripetutamente alcune trasformazioni di base a blocchi di testo sorgente.Trasformazioni di base:
Trasformazioni di Feistel Network
Questa è una trasformazione su vettori (blocchi) che rappresentano le metà sinistra e destra del registro a scorrimento. L'algoritmo DES utilizza una trasformazione della rete Feistel in avanti nella crittografia (vedere Fig. 1) e una trasformazione della rete Feistel inversa nella decrittografia (vedere Fig. 2).
Schema di crittografia dell'algoritmo DES
Il testo di origine è un blocco a 64 bit. Il testo cifrato è un blocco a 64 bit.
Il processo di crittografia consiste in una permutazione iniziale, 16 cicli di crittografia e una permutazione finale.
Diamo un'occhiata al diagramma dettagliato dell'algoritmo DES:
L i R i =1,2\ldots.metà sinistra e destra del blocco a 64 bit L i R i
k i - Chiavi a 48 bit
f - funzione di crittografia
IP - permutazione iniziale
IP -1 - permutazione finale. 
Secondo la tabella, i primi 3 bit del blocco IP(T) risultante dopo la permutazione iniziale di IP sono i bit 58, 50, 42 del blocco di ingresso T, e i suoi ultimi 3 bit sono i bit 23, 15, 7 del blocco di ingresso. Successivamente, il blocco IP(T) a 64 bit partecipa a 16 cicli della trasformata di Feistel.
16 cicli di trasformazione di Feistel:
Dividere IP(T) in due parti L 0 ,R 0 , dove L 0 ,R 0 sono rispettivamente i 32 bit più significativi e i 32 bit meno significativi del blocco T0 IP(T)= L 0 R 0 .
Sia T i -1 = L i -1 R i -1 il risultato dell'iterazione (i-1), quindi viene determinato il risultato dell'iterazione i-esima T i = L i R i:
L io = R io - 1 La metà sinistra di L i è uguale alla metà destra del vettore precedente L i - 1 R i - 1 . E la metà destra di R i è la somma di bit di L i - 1 e f(R i - 1, k i) modulo 2.
Nella trasformata di Feistel a 16 cicli, la funzione f svolge il ruolo di crittografia. Consideriamo in dettaglio la funzione f.
Gli argomenti della funzione f sono il vettore a 32 bit R i - 1 , la chiave a 48 bit k i , che sono il risultato della conversione della chiave cifrata originale a 56 bit k.
Per calcolare la funzione f si utilizzano la funzione di espansione E, la trasformazione S, composta da 8 trasformazioni S-box, e la permutazione P.
La funzione E espande il vettore a 32 bit R i - 1 nel vettore a 48 bit E(R i - 1) duplicando alcuni bit da R i - 1, mentre l'ordine dei bit del vettore E(R i - 1 ) è indicato nella tabella 2. 
I primi tre bit del vettore E(R i - 1) sono i bit 32, 1, 2 del vettore R i -1. La tabella 2 mostra che i bit 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 sono duplicati. Gli ultimi 3 bit del vettore E(Ri - 1) sono i bit 31, 32, 1 del vettore Ri - 1. Il blocco E(R i -1) ottenuto dopo il riarrangiamento viene sommato modulo 2 con le chiavi k i e poi presentato sotto forma di otto blocchi consecutivi B 1 , B 2 ,...B 8 .
E(R i - 1) = B 1 B 2 ...B 8
Ogni Bj è un blocco di 6 bit. Successivamente, ciascuno dei blocchi B j viene trasformato in un blocco a 4 bit B" j utilizzando le trasformazioni S j. Le trasformazioni S j sono determinate dalla Tabella 3. Supponiamo che B 3 = 101111 e vogliamo trovare B" 3. Il primo e l'ultimo bit di B 3 sono la rappresentazione binaria del numero a, 0. Il valore della funzione f(R i - 1,k i) (32 bit) si ottiene permutazione P applicata al blocco B di 32 bit " 1 B" 2 ...B" 8. La permutazione P è data dalla Tabella 4. 
f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
Secondo la tabella 4, i primi quattro bit del vettore risultante dopo l'azione della funzione f sono i bit 16, 7, 20, 21 del vettore B" 1 B" 2 ...B" 8
Generazione delle chiavi k i .
Le chiavi k i si ottengono dalla chiave iniziale k (56 bit = 7 byte o 7 caratteri ASCII) in questo modo. Otto bit, situati nelle posizioni 8, 16, 24, 32, 40, 48, 56, 64, vengono aggiunti alla chiave k in modo che ogni byte contenga un numero dispari di uno. Viene utilizzato per rilevare errori nello scambio e nell'archiviazione delle chiavi. Quindi viene eseguita una permutazione per la chiave estesa (ad eccezione dei bit aggiunti 8, 16, 24, 32, 40, 48, 56, 64). Questa permutazione è definita come nella Tabella 5. 
Questa permutazione è definita da due blocchi C 0 e D 0 di 28 bit ciascuno. I primi 3 bit di C0 sono i bit 57, 49, 41 della chiave estesa. E i primi tre bit di D 0 sono i bit 63, 55, 47 della chiave estesa. C i ,D i i=1,2,3…sono ottenuti da C i - 1 ,D i - 1 mediante uno o due spostamenti ciclici a sinistra secondo la Tabella 6. 
La chiave k i , i=1,…16 è composta da 48 bit selezionati tra i bit del vettore C i D i (56 bit) secondo la Tabella 7. Il primo e il secondo bit k i sono i bit 14, 17 del vettore C i D i 
La permutazione finale IP - 1 agisce su T 16 e serve per ripristinare la posizione. È l'inverso della permutazione IP. La permutazione finale è determinata dalla Tabella 8. 
Modalità di utilizzo del DES DES può essere utilizzato in quattro modalità.
Lo standard DES è progettato per proteggere dall'accesso non autorizzato a informazioni sensibili ma non classificate nel governo e nelle organizzazioni commerciali degli Stati Uniti. L'algoritmo alla base dello standard si diffuse abbastanza rapidamente e già nel 1980 fu approvato dal National Institute of Standards and Technology degli Stati Uniti. Da questo momento in poi il DES diventa uno standard non solo di nome, ma anche di fatto. Appaiono software e microcomputer specializzati progettati per crittografare e decrittografare le informazioni nelle reti di dati.
Ad oggi, DES è l’algoritmo più comune utilizzato nei sistemi di sicurezza delle informazioni commerciali. Inoltre, l'implementazione dell'algoritmo DES in tali sistemi diventa un segno di buona forma.
I principali vantaggi dell'algoritmo DES:
· viene utilizzata una sola chiave di lunghezza pari a 56 bit;
· dopo aver crittografato un messaggio utilizzando un pacchetto, è possibile utilizzarne un altro per decrittografarlo;
· la relativa semplicità dell'algoritmo garantisce un'elevata velocità di elaborazione delle informazioni;
· stabilità sufficientemente elevata dell'algoritmo.
DES crittografa blocchi di dati a 64 bit utilizzando una chiave a 56 bit. La decrittazione in DES è l'operazione inversa della crittografia e viene eseguita ripetendo le operazioni di crittografia in ordine inverso (nonostante l'apparente ovvietà, questo non sempre viene fatto. Successivamente esamineremo i cifrari in cui crittografia e decrittografia vengono eseguite utilizzando algoritmi diversi) .
Il processo di crittografia consiste in una permutazione iniziale di bit di un blocco da 64 bit, sedici cicli di crittografia e infine una permutazione di bit inversa (Figura 1).
Va subito notato che TUTTE le tabelle fornite in questo articolo sono STANDARD e pertanto dovrebbero essere incluse nell'implementazione dell'algoritmo senza modifiche. Tutte le permutazioni e i codici nelle tabelle sono selezionati dagli sviluppatori in modo tale da rendere il processo di decrittazione il più difficile possibile selezionando una chiave. La struttura dell'algoritmo DES è mostrata in Fig. 2.
Riso. 2.
Si legga il successivo blocco T da 8 byte dal file, che viene trasformato utilizzando la matrice di permutazione iniziale IP (Tabella 1) come segue: il bit 58 del blocco T diventa il bit 1, il bit 50 diventa il bit 2, ecc., che sarà risultato in: T(0) = IP(T).
La sequenza di bit risultante T(0) è divisa in due sequenze di 32 bit ciascuna: L(0) - bit sinistri o di ordine superiore, R(0) - bit destri o di ordine inferiore.
Tabella 1: Matrice di permutazione iniziale IP
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Quindi viene eseguita la crittografia, composta da 16 iterazioni. Il risultato dell'i-esima iterazione è descritto dalle seguenti formule:
R(i) = L (i-1) xor f (R(i-1), K(i)),
dove xor è l'operazione OR ESCLUSIVO.
La funzione f è chiamata funzione di crittografia. I suoi argomenti sono la sequenza di 32 bit R(i-1), ottenuta alla (i-1)esima iterazione, e la chiave di 48 bit K(i), che è il risultato della conversione della chiave di 64 bit K. Nel dettaglio, la funzione di crittografia e l'algoritmo per ottenere le chiavi K(i) sono descritti di seguito.
Alla 16a iterazione si ottengono le sequenze R(16) e L(16) (senza permutazione), che vengono concatenate in una sequenza R(16) L(16) di 64 bit.
Quindi le posizioni dei bit di questa sequenza vengono riorganizzate secondo la matrice IP -1 (Tabella 2).
Tabella 2: Matrice di permutazione inversa IP -1
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
Le matrici IP -1 e IP sono correlate come segue: il valore del 1° elemento della matrice IP -1 è 40, e il valore del 40° elemento della matrice IP è 1, il valore del 2° l'elemento della matrice IP -1 è 8 e il valore dell'ottavo elemento della matrice IP è uguale a 2, ecc.
Il processo di decrittografia dei dati è inverso al processo di crittografia. Tutti i passaggi devono essere eseguiti in ordine inverso. Ciò significa che i dati da decifrare vengono prima riorganizzati secondo la matrice IP-1, e poi sulla sequenza di bit R(16) L(16) vengono eseguite le stesse azioni come nel processo di cifratura, ma in ordine inverso.
Il processo di decrittazione iterativo può essere descritto dalle seguenti formule:
R(i-1) = L(i), i = 1, 2,…, 16;
L (i-1) = R(i) xor f (L(i), K(i)), i = 1, 2,…, 16.
Alla 16a iterazione si ottengono le sequenze L(0) e R(0), che vengono concatenate in una sequenza L(0) R(0) a 64 bit.
Le posizioni dei bit di questa sequenza vengono quindi riorganizzate in base alla matrice IP. Il risultato di tale permutazione è la sequenza originale a 64 bit.
Consideriamo ora la funzione di crittografia f (R(i-1), K(i)). È mostrato schematicamente in Fig. 3.
Riso. 3.
Per calcolare il valore della funzione f, vengono utilizzate le seguenti funzioni di matrice:
E - estensione di una sequenza da 32 bit a 48 bit,
S1, S2,…, S8 - conversione di un blocco da 6 bit in uno da 4 bit,
P - permutazione di bit in una sequenza di 32 bit.
La funzione di espansione E è determinata dalla tabella. 3. Secondo questa tabella, i primi 3 bit di E (R(i-1)) sono i bit 32, 1 e 2 e gli ultimi sono 31, 32 e 1.
Tabella 3: Funzione di estensione E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
Il risultato della funzione E (R(i-1)) è una sequenza di 48 bit che viene aggiunta modulo 2 (operazione xor) con la chiave di 48 bit K(i). La sequenza risultante di 48 bit è divisa in otto blocchi da 6 bit B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). Questo è:
E (R(i-1)) xor K(i) = B(1) B(2)… B(8).
Le funzioni S1, S2,…, S8 sono definite nella tabella. 4.
Tabella 4
A tavola 4. Sono necessari ulteriori chiarimenti. Sia l'input della funzione di matrice Sj un blocco a 6 bit B(j) = b1b2b3b4b5b6, quindi il numero a due bit b1b6 indica il numero di riga della matrice e b2b3b4b5 il numero di colonna. Il risultato di Sj (B(j)) sarà un elemento a 4 bit situato all'intersezione della riga e della colonna specificate.
Ad esempio, B(1)=011011. Quindi S1 (B(1)) si trova all'intersezione tra la riga 1 e la colonna 13. Nella colonna 13 della riga 1 il valore è 5. Ciò significa S1 (011011)=0101.
Applicando l'operazione di selezione a ciascuno dei blocchi da 6 bit B(1), B(2),…, B(8), otteniamo una sequenza di 32 bit S1 (B(1)) S2 (B(2)) S3 (B(3))... S8 (B(8)).
Infine, per ottenere il risultato della funzione di crittografia, è necessario riorganizzare i bit di questa sequenza. A questo scopo viene utilizzata la funzione di permutazione P (Tabella 5). Nella sequenza di input, i bit vengono riorganizzati in modo che il bit 16 diventi il bit 1, il bit 7 diventi il bit 2 e così via.
Tabella 5: Funzione di permutazione P
Così,
f (R(i-1), K(i)) = P (S1 (B(1)),… S8 (B(8)))
Per completare la descrizione dell'algoritmo di crittografia dei dati, resta da presentare l'algoritmo per ottenere chiavi a 48 bit K(i), i=1...16. Ad ogni iterazione viene utilizzato un nuovo valore di chiave K(i), calcolato dalla chiave iniziale K. K è un blocco di 64 bit con otto bit di parità situati nelle posizioni 8,16,24,32,40,48, 56.64.
Per rimuovere i bit di controllo e riorganizzare il resto, viene utilizzata la funzione G della preparazione iniziale della chiave (Tabella 6).
Tabella 6
Matrice G di preparazione della chiave iniziale
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
Il risultato della trasformazione G(K) sarà diviso in due blocchi da 28 bit C(0) e D(0), e C(0) sarà composto dai bit 57, 49, ..., 44, 36 della chiave K e D(0) saranno costituiti dai bit 63, 55,…, 12, 4 tasti K. Dopo aver determinato C(0) e D(0), C(i) e D(i), i=1… 16, sono determinati ricorsivamente. Per fare ciò applicare uno spostamento ciclico a sinistra di uno o due bit, a seconda del numero di iterazioni, come mostrato in tabella. 7.
Tabella 7. Tabella dei turni per il calcolo delle chiavi
|
Numero di iterazione |
Shift (bit) |
Il valore risultante viene nuovamente “miscelato” secondo la matrice H (Tabella 8).
Tabella 8: Matrice di completamento chiave H
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
La chiave K(i) sarà composta dai bit 14, 17,…, 29, 32 della sequenza C(i) D(i). Così:
K(i) = H (C(i) D(i))
Lo schema a blocchi dell'algoritmo di calcolo della chiave è mostrato in Fig. 4.
Riso. 4.
Il ripristino del testo originale viene effettuato utilizzando questo algoritmo, ma prima si utilizza la chiave K(15), poi K(14) e così via. Ora dovresti capire perché l'autore consiglia insistentemente di utilizzare le matrici fornite. Se diventi un ladro, potresti ritrovarti con un codice molto segreto, ma non sarai in grado di decifrarlo da solo!
