Annotazione: Uno dei più famosi sistemi crittografici Con chiave privata DES - Standard di crittografia dei dati. Questo sistema è stato il primo a ricevere lo stato norma statale nel campo della crittografia dei dati. E sebbene il vecchio standard americano DES abbia perso il suo status ufficiale, questo algoritmo merita ancora attenzione quando si studia la crittografia. Inoltre, questa lezione spiega cos'è il doppio DES, un attacco meet-in-the-middle e come risolverlo. La stessa lezione discute brevemente nuovo standard US per un cifrario a blocchi: l'algoritmo di Rijndael.
Lo scopo della lezione: per far conoscere allo studente le informazioni di base sull'algoritmo Crittografia DES.
Informazioni di base
Uno dei sistemi crittografici a chiave privata più conosciuti è DES - Standard di crittografia dei dati... Questo sistema è stato il primo a ricevere lo stato di uno standard statale nel campo della crittografia dei dati. È stato sviluppato da specialisti dell'azienda IBM ed è entrato in vigore negli Stati Uniti nel 1977. Algoritmo DES ampiamente utilizzato per l'archiviazione e il trasferimento di dati tra vari sistemi informatici; v sistemi di posta, v sistemi elettronici disegni e scambio elettronico informazioni commerciali... Standard DES implementato sia software che hardware. Imprese paesi diversiè stata avviata la produzione di massa dispositivi digitali usando DES per crittografare i dati. Tutti i dispositivi sono passati certificazione obbligatoria per il rispetto della norma.
Nonostante il fatto che per qualche tempo questo sistema non abbia avuto lo status di standard statale, è ancora ampiamente utilizzato e merita attenzione quando si studiano i cifrari a blocchi di chiavi private.
Lunghezza chiave nell'algoritmo DESè di 56 bit. È con questo fatto che la principale controversia riguardante la capacità DES resistere a vari attacchi. Come sai, qualsiasi cifrario a blocchi con una chiave privata può essere violato provando tutte le possibili combinazioni di tasti. Con una lunghezza della chiave di 56 bit, sono possibili 2 56 chiavi diverse... Se un computer enumera 1.000.000 di chiavi in un secondo (che è approssimativamente uguale a 2 20), allora ci vorranno 2 36 secondi per scorrere tutte le 2 56 chiavi, o poco più di duemila anni, il che, ovviamente, è inaccettabile per gli intrusi.
Tuttavia, sono possibili quelli più costosi e più veloci. sistemi informatici, come Personal computer ... Ad esempio, se è possibile combinare un milione di processori per il calcolo parallelo, allora tempo massimo la selezione della chiave si riduce a circa 18 ore. Questo tempo non è troppo lungo e un crittoanalista dotato di una tecnica così costosa potrebbe eseguire un attacco crittografato con DES in un ragionevole lasso di tempo.
Allo stesso tempo, si può notare che il sistema DES può essere utilizzato in applicazioni di piccole e medie dimensioni per crittografare dati di scarso valore. Per la crittografia di dati di importanza nazionale o sistema di valore commerciale significativo DES attualmente, ovviamente, non dovrebbe essere utilizzato. Nel 2001, dopo un concorso appositamente annunciato negli Stati Uniti, è stato adottato un nuovo standard per un cifrario a blocchi, chiamato AES (Standard di crittografia avanzata), che si basava sulla cifra Rijndael sviluppato da specialisti belgi. Questo cifrario è discusso alla fine della lezione.
Impostazioni principali DES: dimensione blocco 64 bit, lunghezza chiave 56 bit, numero di round - 16. DESè un rete classica Feistel con due rami. L'algoritmo converte un blocco di dati di input a 64 bit in un blocco di output a 64 bit in diversi round. Standard DES costruita su uso combinato permutazioni, sostituzioni e giochi d'azzardo. I dati crittografati devono essere in formato binario.
Crittografia
Struttura generale DESè mostrato in Fig. 4.1. Il processo di crittografia per ogni blocco di dati originali a 64 bit può essere suddiviso in tre fasi:
- preparazione iniziale del blocco dati;
- 16 giri del "ciclo principale";
- elaborazione finale del blocco dati.
Nella prima fase, permutazione iniziale 64 bit blocco sorgente testo, durante il quale i bit vengono riordinati in un certo modo.
Nella fase successiva (principale), il blocco è diviso in due parti (rami), 32 bit ciascuna. Il ramo di destra viene trasformato usando una funzione F e la corrispondente chiave parziale ottenuto dalla chiave di crittografia principale utilizzando uno speciale algoritmo di conversione della chiave. Quindi i dati vengono scambiati tra i rami sinistro e destro del blocco. Questo viene ripetuto 16 volte in un ciclo.
Infine, nella terza fase, viene riorganizzato il risultato ottenuto dopo sedici passaggi del ciclo principale. Questa permutazione è l'opposto della permutazione iniziale.
Riso. 4.1.
Consideriamo più in dettaglio tutte le fasi della trasformazione crittografica secondo lo standard DES.
Nella prima fase, il blocco di dati originali a 64 bit viene sottoposto a una permutazione iniziale. In letteratura, questa operazione è talvolta chiamata "sbiancamento". Durante la permutazione iniziale, i bit del blocco dati vengono riordinati in un certo modo. Questa operazione conferisce una certa "casualità" al messaggio originale, riducendo la possibilità di utilizzare la crittoanalisi con metodi statistici.
Contemporaneamente alla permutazione iniziale del blocco dati, viene eseguita una permutazione iniziale di 56 bit della chiave. Dalla fig. 4.1. si vede che in ciascuno dei turni viene utilizzata la corrispondente chiave parziale K i a 48 bit. Le chiavi K i si ottengono secondo un certo algoritmo, utilizzando più volte ciascuno dei bit della chiave iniziale. In ogni round, la chiave a 56 bit viene divisa in due metà a 28 bit. Quindi le metà vengono spostate a sinistra di uno o due bit, a seconda del numero tondo. Dopo lo spostamento, 48 bit su 56 vengono selezionati in un certo modo. Poiché questo non solo seleziona un sottoinsieme dei bit, ma ne modifica anche l'ordine, questa operazione è chiamata "permutazione con compressione". Il suo risultato è un insieme di 48 bit. In media, ogni bit della chiave originale a 56 bit viene utilizzato in 14 sottochiavi su 16, sebbene non tutti i bit vengano utilizzati lo stesso numero di volte.
Successivamente, viene eseguito il ciclo di trasformazione principale, organizzato secondo la rete Feistel e composto da 16 cicli identici. In questo caso in ogni round (Fig. 4.2) si ottiene un valore intermedio a 64 bit, che viene poi elaborato nel round successivo.
Riso. 4.2.
I rami sinistro e destro di ciascun valore intermedio vengono trattati come valori separati a 32 bit, indicati con L e R.
Innanzitutto, il lato destro del blocco R i viene espanso a 48 bit utilizzando una tabella che definisce la permutazione più l'estensione a 16 bit. Questa operazione ridimensiona la metà destra in modo che corrisponda alla dimensione della chiave per l'operazione XOR. Inoltre, a causa di questa operazione, la dipendenza di tutti i bit del risultato dai bit dei dati originali e della chiave aumenta più velocemente (questo è chiamato "effetto valanga"). Più l'effetto valanga si manifesta quando si utilizza l'uno o l'altro algoritmo di crittografia, meglio è.
Dopo aver eseguito la permutazione dell'espansione, il valore a 48 bit risultante viene sottoposto a XOR con la sottochiave a 48 bit K i. Quindi il valore a 48 bit risultante viene inviato all'ingresso del blocco di sostituzione S (dall'inglese. Sostituzione - sostituzione), il risultato che è un valore a 32 bit. La sostituzione viene eseguita in otto box di sostituzione o otto S-box. Quando fare questo DES su carta sembra piuttosto complicato, per non parlare della sua implementazione software! Sviluppare un programma che funzioni correttamente e in modo ottimale completamente in conformità con DES, probabilmente, solo programmatori esperti... Alcune difficoltà sorgono quando implementazione del software, per esempio, una permutazione iniziale o una permutazione con espansione. Queste difficoltà sono dovute al fatto che originariamente era prevista l'attuazione DES solo hardware. Tutte le operazioni utilizzate nello standard sono facilmente eseguite dalle unità hardware e non ci sono difficoltà con l'implementazione. Tuttavia, qualche tempo dopo la pubblicazione dello standard, gli sviluppatori di software hanno deciso di non farsi da parte e iniziare anche a creare sistemi di crittografia. Ulteriore DES implementato sia in hardware che software.
Standard DES progettato per proteggere dall'accesso non autorizzato a importanti, ma non informazione riservata nel governo degli Stati Uniti e nelle organizzazioni commerciali. L'algoritmo alla base dello standard si diffuse piuttosto rapidamente e già nel 1980 fu approvato dal National Institute of Standards and Technology degli Stati Uniti. Da allora, DES è diventato uno standard non solo di nome ma di fatto. Apparire Software e microcomputer specializzati progettati per la crittografia e la decifratura delle informazioni nelle reti di trasmissione dati.
DES è di gran lunga l'algoritmo più diffuso utilizzato nei sistemi di sicurezza. 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 lunga 56 bit;
· Avendo crittografato un messaggio con un pacchetto, puoi utilizzarne un altro per decifrarlo;
La relativa semplicità dell'algoritmo fornisce ad alta velocità elaborazione delle informazioni;
· Robustezza sufficientemente elevata dell'algoritmo.
DES crittografa blocchi di dati a 64 bit utilizzando una chiave a 56 bit. La decrittazione DES è l'operazione inversa della crittografia e viene eseguita ripetendo le operazioni di crittografia in ordine inverso (nonostante l'apparente ovvietà, ciò non viene sempre eseguito. Successivamente considereremo le cifre in cui crittografia e decrittografia vengono eseguite utilizzando algoritmi diversi).
Il processo di crittografia consiste in uno scambio iniziale di bit di un blocco a 64 bit, sedici cicli di crittografia e infine uno scambio di bit inverso (Fig. 1).
Va notato subito che TUTTE le tabelle fornite in questo articolo sono STANDARD e quindi dovrebbero essere incluse nell'implementazione dell'algoritmo invariate. Tutte le permutazioni e i codici nelle tabelle sono stati selezionati dagli sviluppatori in modo tale da rendere il processo di decrittazione il più difficile possibile indovinando la chiave. La struttura dell'algoritmo DES è mostrata in Fig. 2.
Riso. 2.
Si legga dal file il successivo blocco T di 8 byte, che viene trasformato utilizzando la matrice di permutazione iniziale IP (Tabella 1) come segue: il bit 58 del blocco T diventa bit 1, bit 50 - bit 2, ecc., che risulterà in: T (0) = IP (T).
La sequenza di bit T (0) risultante è divisa in due sequenze di 32 bit ciascuna: L (0) - bit di sinistra o più significativi, R (0) - bit di destra o meno significativi.
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. Risultato dell'i-th l'iterazione è descritta 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 a 32 bit R (i-1), ottenuta alla (i-1) esima iterazione, e la chiave a 48 bit K (i), che è il risultato della trasformazione della chiave a 64 bit K. Di seguito sono descritti in dettaglio la funzione di cifratura e l'algoritmo per ottenere le chiavi K(i).
Alla 16a iterazione si ottengono le sequenze R (16) e L (16) (senza permutazione) che vengono concatenate in una sequenza di 64 bit R (16) L (16).
Quindi le posizioni dei bit di questa sequenza vengono permutate 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 e così via.
Il processo di decrittografia dei dati è inverso al processo di crittografia. Tutte le azioni devono essere eseguite in ordine inverso... Ciò significa che i dati decifrati vengono prima riorganizzati secondo la matrice IP-1, quindi vengono eseguite le stesse azioni sulla sequenza di bit R (16) L (16) come nel 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) x o 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 di 64 bit L (0) R (0).
Le posizioni dei bit di questa sequenza vengono quindi riorganizzate secondo la 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 - espansione di una sequenza da 32 bit a 48 bit,
S1, S2, ..., S8 - convertire un blocco a 6 bit in uno a 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 espansione 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 una chiave K (i) di 48 bit. Il risultato è una sequenza di 48 bit, suddivisa in otto blocchi di 6 bit B (1) B (2) B (3) B (4) B (5) B (6) B (7) B (8) . Questo è:
E (R (i-1)) xo K (i) = B (1) B (2)… B (8).
Le funzioni S1, S2, ..., S8 sono determinate dalla tabella. 4.
Tabella 4
A tavola. 4. Richiede ulteriori chiarimenti. Lascia che il blocco a 6 bit B (j) = b1b2b3b4b5b6 entri nell'ingresso della funzione di matrice Sj, 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)) è 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 della riga 1 e della colonna 13. La colonna 13 della riga 1 è impostata su 5. Quindi S1 (011011) = 0101.
Applicando l'operazione di selezione a ciascuno dei blocchi di 6 bit B (1), B (2), ..., B (8), si ottiene 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, i bit di questa sequenza devono essere scambiati. Per questo, viene utilizzata la funzione di permutazione P (Tabella 5). Nella sequenza di input, i bit vengono scambiati in modo che il bit 16 diventi il bit 1, il bit 7 diventi il bit 2 e così via.
Tabella 5: Funzione di trasferimento P
In questo modo,
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 fornire un algoritmo per ottenere chiavi a 48 bit K (i), i = 1 ... 16. Ad ogni iterazione, viene utilizzato un nuovo valore di chiave K (i), che viene 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 permutare il resto, viene utilizzata la funzione G della preparazione della chiave iniziale (Tabella 6).
Tabella 6
Matrice di preparazione della chiave iniziale G
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) è diviso in due blocchi di 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 in modo ricorsivo. Per fare ciò, applicare uno spostamento ciclico a sinistra di uno o due bit, a seconda del numero di iterazione, come mostrato nella tabella. 7.
Tabella 7. Tabella dei turni per il calcolo della chiave
|
Numero di iterazione |
Maiusc (bit) |
Il valore risultante viene nuovamente "miscelato" secondo la matrice H (Tabella 8).
Tabella 8: Matrice chiave di post-elaborazione 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à costituita dai bit 14, 17, ..., 29, 32 della sequenza C (i) D (i). In questo modo:
K (i) = H (C (i) D (i))
Lo schema a blocchi dell'algoritmo di calcolo chiave è mostrato in Fig. 4.
Riso. 4.
Recupero testo di partenza viene eseguito secondo questo algoritmo, ma prima si usa il tasto K (15), poi - K (14) e così via. Ora dovrebbe esserti chiaro perché l'autore consiglia vivamente di utilizzare le matrici fornite. Se inizi a essere ipocrita, devi aver ricevuto un codice molto segreto, ma tu stesso non puoi rivelarlo!
Che ANSI chiama DEA (Data Encryption Algorithm) e ISO - DEA-1, è diventato uno standard mondiale in 20 anni. Nel corso degli anni della sua esistenza, ha resistito all'assalto di vari attacchi e, con alcune restrizioni, è ancora considerato crittograficamente sicuro.
DES è un cifrario a blocchi che crittografa i dati in blocchi a 64 bit. A un'estremità dell'algoritmo viene immesso un blocco di testo in chiaro a 64 bit e all'altra estremità viene emesso un blocco di testo cifrato a 64 bit. DES è algoritmo simmetrico: Lo stesso algoritmo e la stessa chiave vengono utilizzati per la crittografia e la decrittografia (ad eccezione di lievi differenze nell'utilizzo della chiave). La lunghezza della chiave è di 56 bit. (La chiave è solitamente rappresentata come un numero a 64 bit, ma ogni ottavo bit viene utilizzato per la parità e ignorato. I bit di parità sono i più piccoli bit significativi byte chiave.) La chiave, che può essere un qualsiasi numero a 56 bit, può essere modificata in qualsiasi momento.
La resistenza alla crittografia è completamente determinata dalla chiave. L'elemento costitutivo fondamentale di DES è la combinazione di permutazioni e permutazioni. DES è composto da 16 cicli.
Vista generale del ciclo di conversione:
Se L i e R i sono le metà sinistra e destra ottenute come risultato dell'i-esima iterazione, K i è una chiave a 48 bit per il ciclo i e f è una funzione che esegue tutte le sostituzioni, permutazioni e XOR con un chiave, allora un ciclo di conversione può essere pensato come:
Tenendo conto della sostituzione F i (*) e della permutazione T (*), il ciclo di trasformazione può essere rappresentato come in Fig.
Si può vedere che ogni ciclo DES è un cifrario compositivo con due successive trasformazioni - la sostituzione F i (*) e la permutazione T (*) (tranne l'ultimo, sedicesimo ciclo, dove la permutazione è omessa).
Sostituzione:
(L io, R io) = (R io −1, L io −1) ⊕ f (R io −1, K)
è un'involuzione poiché
F io (F io (L io −1, R io −1)) = F io (R io −1, L io −1) ⊕ (f (R io −1, K io))) = (R io - 1, L i −1 ⊕ (f (R i −1, K i)) ⊕ (f (R i −1, K i))) = (L i −1, R i −1)
E la sostituzione
T (L io ′, R io ′) = (R io ′, L io ′),
è anche un'involuzione, poiché
T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′
Se denotiamo le permutazioni iniziale e finale come (IP) e (IP) - 1, la trasformazione DES diretta (crittografia) implementa la funzione:
DES = (IP) F 1 TF 2 T… F 15 TF 16 (IP) - 1,
e la trasformazione DES inversa (decrittografia) implementa la funzione:
DES - 1 = (IP) −1 F 16 TF 15 T… F 2 TF 1 (IP).
Pertanto, DES è un cifrario di Feistel ed è progettato per eseguire proprietà utile: Lo stesso algoritmo viene utilizzato per la crittografia e la decrittografia. L'unica differenza è che le chiavi devono essere utilizzate in ordine inverso.
Cioè, se le chiavi K 1, K 2, K 3, ..., K 16 sono state utilizzate per la crittografia, le chiavi di decrittazione saranno K 16, K 15, K 14, ..., K 1. L'algoritmo utilizza solo numeri aritmetici standard a 64 bit e operazioni logiche, quindi è facile da implementare nell'hardware.
DES opera su un blocco di testo in chiaro a 64 bit. Dopo la permutazione iniziale, il blocco viene suddiviso in metà destra e sinistra di 32 bit ciascuna. Quindi vengono eseguite 16 trasformazioni (funzione f), in cui i dati vengono combinati con la chiave. Dopo il sedicesimo ciclo, le metà destra e sinistra vengono combinate e l'algoritmo termina con la permutazione finale (inversa all'originale). Ad ogni ciclo (vedi Fig.), i bit chiave vengono spostati, quindi vengono selezionati 48 bit dai 56 bit chiave. La metà destra dei dati viene espansa a 48 bit dalla permutazione di diffusione, XORed con 48 bit della chiave spostata e permutata, attraversata attraverso 8 S-box per formare 32 nuovi bit e riorganizzata di nuovo. Queste quattro operazioni sono eseguite dalla funzione f.
Quindi il risultato della funzione f viene concatenato con la metà sinistra utilizzando un altro XOR. Come risultato di queste azioni, appare una nuova metà destra e la vecchia metà destra diventa una nuova metà sinistra. Questi passaggi vengono ripetuti 16 volte, formando 16 round DES.
Standard russo - GOST 28147-89
GOST 28147-89 è un cifrario a blocchi con una chiave a 256 bit e 32 cicli di conversione, che opera in blocchi a 64 bit. Il criptoalgoritmo utilizza anche chiave aggiuntiva che è discusso di seguito. Per la crittografia testo in chiaro prima è diviso nelle metà sinistra e destra di L e R. Nell'i-esimo ciclo, viene utilizzata la sottochiave K i:
L io = R io −1,
R i = L i −1 ⊕ (f (R i −1, K i)).
La funzione f è implementata come segue. Innanzitutto, la metà destra e la i-esima sottochiave vengono aggiunte modulo 2 32. Il risultato è suddiviso in otto sottosequenze a 4 bit, ognuna delle quali va all'ingresso della propria S-box. GOST utilizza otto diverse S-box, i primi 4 bit vanno nella prima S-box, i secondi 4 bit vanno nella seconda S-box e così via. Ogni S-box è una permutazione di numeri da 0 a 15. Ad esempio, una S-box può essere simile a: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. In questo caso, se l'input della S-box è 0, l'output è 7. Se l'input è 1, l'output è 10, ecc. Tutte e otto le S-box sono diverse, in realtà sono materiale chiave aggiuntivo. Le uscite di tutte e otto le S-box sono concatenate in una parola a 32 bit, quindi l'intera parola viene spostata ciclicamente a sinistra di 11 bit. Infine, il risultato viene sottoposto a XOR con la metà sinistra per creare una nuova metà destra e la metà destra diventa la nuova metà sinistra. Per generare le sottochiavi, la chiave originale a 256 bit viene suddivisa in otto blocchi a 32 bit: k 1, k 2, ..., k 8. Ogni ciclo utilizza la propria sottochiave. La decrittografia viene eseguita allo stesso modo della crittografia, ma l'ordine delle sottochiavi k i è invertito. Lo standard non definisce come vengono generate le S-box.
Differenze chiave tra DES e GOST
Le principali differenze tra DES e GOST sono le seguenti:
- DES utilizza una procedura complessa per generare sottochiavi dalle chiavi. In GOST, questa procedura è molto semplice;
- in DES è una chiave a 56 bit e in GOST è una chiave a 256 bit. Se aggiungiamo le permutazioni segrete delle S-box, la quantità totale di informazioni segrete GOST sarà di circa 610 bit;
- Gli S-box DES hanno ingressi a 6 bit e uscite a 4 bit e gli S-box GOST hanno ingressi e uscite a 4 bit. In entrambi gli algoritmi vengono utilizzate otto S-box, ma la S-box GOST è uguale a un quarto della S-box DES;
- DES utilizza una permutazione irregolare chiamata P-box e GOST utilizza uno spostamento a sinistra circolare di 11 bit;
- DES ha 16 cicli e GOST - 32.
Un attacco di potere a GOST è assolutamente senza speranza. GOST utilizza una chiave a 256 bit e, se vengono prese in considerazione le S-box segrete, la lunghezza della chiave sarà ancora maggiore. GOST sembra essere più robusto per la crittoanalisi differenziale e lineare rispetto a DES. Sebbene le S-box casuali GOST, con qualche scelta, non garantiscano un'elevata forza crittografica rispetto alle S-box DES fisse, la loro segretezza aumenta la resistenza di GOST alla crittoanalisi differenziale e lineare. Inoltre, l'efficacia di questi metodi crittoanalitici dipende dal numero di cicli di trasformazione: più cicli ci sono, più difficile è la crittanalisi. GOST utilizza il doppio dei cicli rispetto a DES, il che, probabilmente, porta all'incoerenza della crittoanalisi differenziale e lineare.
GOST non usa la permutazione dell'estensione che esiste in DES. La rimozione di questa permutazione dal DES lo indebolisce a causa della riduzione degli effetti delle valanghe; è ragionevole presumere che l'assenza di tale operazione in GOST influisca negativamente sulla sua forza crittografica. Dal punto di vista della forza crittografica, l'operazione di addizione aritmetica utilizzata in GOST non è peggiore dell'operazione XOR in DES.
La differenza principale sembra essere l'uso dello spostamento ciclico invece della permutazione in GOST. La permutazione DES aumenta l'effetto valanga. In GOST, una modifica in un bit di ingresso influisce su un blocco S di un ciclo di conversione, che quindi influenza due blocchi S del ciclo successivo, quindi tre blocchi del ciclo successivo, ecc. Occorrono otto cicli prima che la modifica di un bit di input influisca su ogni bit del risultato; in DES ci vogliono solo cinque cicli. Tuttavia, GOST è composto da 32 cicli e DES solo da 16.
Gli sviluppatori di GOST hanno cercato di raggiungere un equilibrio tra forza crittografica ed efficienza. Prendendo come base la costruzione di Feistel, hanno sviluppato un algoritmo crittografico migliore del DES per l'implementazione del software. Per aumentare la forza crittografica, è stata introdotta una chiave extra lunga e il numero di cicli è stato raddoppiato. Tuttavia, rimane aperta la questione se gli sforzi degli sviluppatori siano stati coronati dalla creazione di un algoritmo più crittografico rispetto a DES.
Vorobieva E., Lukyanova A.
L'algoritmo di crittografia simmetrica più comune e più noto è DES (Standard di crittografia dei dati). L'algoritmo è stato sviluppato nel 1977, nel 1980 è stato adottato dal NIST (National Institute of Standards and Technology, USA) come standard.
DES è una classica rete Feistel a due rami. I dati vengono crittografati in blocchi a 64 bit utilizzando una chiave a 56 bit. L'algoritmo converte l'input a 64 bit in output a 64 bit in diversi round. La lunghezza della chiave è di 56 bit. Il processo di crittografia ha quattro fasi. Il primo passo consiste nell'eseguire una permutazione iniziale (IP) del testo sorgente a 64 bit (sbiancamento), durante la quale i bit vengono riordinati secondo tavolo standard... La fase successiva consiste in 16 round della stessa funzione che utilizza operazioni di spostamento e sostituzione. Nella terza fase, le metà sinistra e destra dell'output dell'ultima (16a) iterazione vengono invertite. Infine, nella quarta fase, viene riorganizzato il risultato IP-1 ottenuto nella terza fase. La permutazione IP-1 è inversa alla permutazione iniziale.
figura 4. Algoritmo DES
La figura mostra il modo in cui viene utilizzata una chiave a 56 bit. Inizialmente, la chiave viene fornita all'ingresso della funzione di permutazione. Quindi, per ciascuno dei 16 cicli, la sottochiave K i è una combinazione di permutazione e spostamento ciclico sinistro. La funzione di permutazione è la stessa per ogni round, ma le sottochiavi K i sono diverse per ogni round a causa dello spostamento ripetuto dei bit della chiave.
La permutazione iniziale e la sua inversa sono determinate dalla tabella standard. Se M è casuale a 64 bit, allora X = IP (M) è permutato a 64 bit. Se applichiamo la funzione di permutazione inversa Y = IP-1 (X) = IP-1 (IP (M)), otteniamo la sequenza di bit originale.
Descrizione del round des
Considera la sequenza di trasformazioni usate in ogni round.
figura 5. Illustrazione di un ciclo di algoritmo DES
Il blocco di input a 64 bit passa attraverso 16 giri, e ad ogni iterazione si ottiene un valore intermedio a 64 bit. I lati sinistro e destro di ciascun valore intermedio vengono trattati come valori separati a 32 bit, etichettati L e R. Ogni iterazione può essere descritta come segue:
R io = L io -1 F (R io -1, K io)
Pertanto, l'uscita della metà sinistra di L i è uguale all'ingresso della metà destra di R i-1. L'uscita della metà destra di R i è il risultato di XORing L i-1 e una funzione F che dipende da R i-1 e K i.
Consideriamo più in dettaglio la funzione F. R i, che viene inviato all'ingresso della funzione F, è lungo 32 bit. Inizialmente, R i viene espanso a 48 bit utilizzando una tabella che definisce una permutazione più un'estensione a 16 bit. L'espansione avviene nel modo seguente. I 32 bit vengono suddivisi 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 l'estensione risulta nel messaggio
Defghi hijklm lmnopq. ... ...
Successivamente, per il valore a 48 bit risultante, viene eseguita un'operazione XOR con una sottochiave K i a 48 bit. Quindi il valore a 48 bit risultante viene inviato all'ingresso della funzione di sostituzione, il cui risultato è un valore a 32 bit.
La sostituzione consiste in otto S-box, ognuna delle quali riceve 6 bit in ingresso e produce 4 bit in uscita. Queste trasformazioni sono determinate da tabelle speciali. Il primo e l'ultimo bit dell'input S-box determinano il numero di riga nella tabella, i 4 bit centrali determinano il numero di colonna. L'intersezione di riga e colonna definisce 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, ad es. l'uscita è 0101.
Quindi il valore a 32 bit risultante viene elaborato utilizzando la permutazione P, il cui scopo è riordinare i bit il più possibile in modo che nel prossimo ciclo di crittografia, con un'alta probabilità, ogni bit venga elaborato da un altro S- scatola.
La chiave per un singolo round K i è composta da 48 bit. Le chiavi K i si ottengono con il seguente algoritmo. Per la chiave a 56 bit utilizzata come input per l'algoritmo, viene prima eseguita una permutazione in conformità con la tabella Scelta permuta 1 (PC-1). La chiave a 56 bit risultante è suddivisa in due parti a 28 bit, designate rispettivamente C0 e D0. Ad ogni round, Ci e D i vengono spostati ciclicamente a sinistra di 1 o 2 bit in modo indipendente, a seconda del numero di round. I valori risultanti sono l'input per il turno successivo. Sono anche un input per Permuted Choice 2 (PC-2), che produce un output a 48 bit che è l'input per F (R i-1, K i).
Il processo di decrittografia è simile al processo di crittografia. Il testo cifrato viene utilizzato all'input dell'algoritmo, ma le chiavi K i vengono utilizzate in ordine inverso. 16 m dir viene utilizzato nel primo giro, 1 m dir viene utilizzato nell'ultimo giro. Lascia che l'output dell'i-esimo ciclo di crittografia sia L i || R i. Quindi l'input corrispondente del (16-i) -esimo round di decrittazione sarà R i || L i.
Dopo l'ultimo round 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 è un testo normale.
Algoritmo DES
I principali vantaggi dell'algoritmo DES:
· Viene utilizzata una sola chiave lunga 56 bit;
· Avendo crittografato un messaggio con un pacchetto, puoi utilizzarne un altro per decifrarlo;
· La relativa semplicità dell'algoritmo garantisce un'elevata velocità di elaborazione delle informazioni;
· Robustezza sufficientemente elevata dell'algoritmo.
DES crittografa blocchi di dati a 64 bit utilizzando una chiave a 56 bit. La decrittazione DES è l'operazione inversa della crittografia e viene eseguita ripetendo le operazioni di crittografia in ordine inverso (nonostante l'apparente ovvietà, ciò non viene sempre eseguito. Successivamente considereremo le cifre in cui crittografia e decrittografia vengono eseguite utilizzando algoritmi diversi).
Il processo di crittografia consiste in una permutazione iniziale dei bit di un blocco a 64 bit, sedici cicli di crittografia e, infine, una permutazione inversa dei bit (Fig. 1).
Va notato subito che TUTTE le tabelle fornite in questo articolo sono STANDARD e quindi dovrebbero essere incluse nell'implementazione dell'algoritmo invariate. Tutte le permutazioni e i codici nelle tabelle sono stati selezionati dagli sviluppatori in modo tale da rendere il processo di decrittazione il più difficile possibile indovinando la chiave. La struttura dell'algoritmo DES è mostrata in Fig. 2.
figura 2. Struttura dell'algoritmo di crittografia DES
Si legga dal file il successivo blocco T di 8 byte, che viene trasformato utilizzando la matrice di permutazione iniziale IP (Tabella 1) come segue: il bit 58 del blocco T diventa bit 1, il bit 50 diventa bit 2, ecc., che risulterà in: T (0) = IP (T).
La sequenza di bit T (0) risultante è divisa in due sequenze di 32 bit ciascuna: L (0) - bit di sinistra o più significativi, R (0) - bit di destra o meno significativi.
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. Risultato 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 a 32 bit R (i-1), ottenuta alla (i-1) esima iterazione, e la chiave a 48 bit K (i), che è il risultato della trasformazione della chiave a 64 bit K. Di seguito sono descritti in dettaglio la funzione di cifratura e l'algoritmo per ottenere le chiavi K(i).
Alla 16a iterazione si ottengono le sequenze R (16) e L (16) (senza permutazione) che vengono concatenate in una sequenza di 64 bit R (16) L (16).
Quindi le posizioni dei bit di questa sequenza vengono permutate 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 e così via.
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 decifrati vengono prima riorganizzati secondo la matrice IP-1, quindi vengono eseguite le stesse azioni sulla sequenza di bit R (16) L (16) come nel 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) x o 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 di 64 bit L (0) R (0).
Le posizioni dei bit di questa sequenza vengono quindi riorganizzate secondo la 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.
figura 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 - espansione di una sequenza da 32 bit a 48 bit,
S1, S2, ..., S8: converte un blocco da 6 bit in un blocco a 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 espansione 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 una chiave K (i) di 48 bit. La sequenza di 48 bit risultante è suddivisa in otto blocchi di 6 bit B (1) B (2) B (3) B (4) B (5) B (6) B (7) B (8). Questo è:
E (R (i-1)) x o K (i) = B (1) B (2) ... B (8).
Le funzioni S1, S2, ..., S8 sono definite nella Tabella 4.
Tabella 4
Tabella 4. sono necessari ulteriori chiarimenti. Lascia che il blocco a 6 bit B (j) = b1b2b3b4b5b6 entri nell'ingresso della funzione di matrice Sj, 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)) è 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 della riga 1 e della colonna 13. La colonna 13 della riga 1 è impostata su 5. Quindi S1 (011011) = 0101.
Applicando l'operazione di selezione a ciascuno dei blocchi di 6 bit B (1), B (2), ..., B (8), si ottiene 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, i bit di questa sequenza devono essere scambiati. Per questo, viene utilizzata la funzione di permutazione P (Tabella 5). Nella sequenza di input, i bit vengono scambiati in modo che il bit 16 diventi il bit 1, il bit 7 diventi il bit 2 e così via.
Tabella 5: Funzione di trasferimento P
In questo modo,
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 fornire un algoritmo per ottenere chiavi a 48 bit K (i), i = 1 ... 16. Ad ogni iterazione, viene utilizzato un nuovo valore di chiave K (i), che viene 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 permutare il resto, viene utilizzata la funzione G della preparazione della chiave iniziale (Tabella 6).
Tabella 6
Matrice di preparazione della chiave iniziale G
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) è suddiviso in due blocchi di 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 definiti ricorsivamente. Per fare ciò, applicare uno spostamento ciclico a sinistra di uno o due bit, a seconda del numero di iterazione, come mostrato nella Tabella 7.
Tabella 7
Shift table per il calcolo della chiave
| Numero di iterazione | Maiusc (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 chiave di post-elaborazione 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à costituita dai bit 14, 17, ..., 29, 32 della sequenza C (i) D (i). In questo modo:
K (i) = H (C (i) D (i))
Lo schema a blocchi dell'algoritmo di calcolo chiave è mostrato in Fig. 4.
figura 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 dovrebbe esserti chiaro perché l'autore consiglia vivamente di utilizzare le matrici fornite. Se inizi a essere ipocrita, devi aver ricevuto un codice molto segreto, ma tu stesso non puoi rivelarlo!
Modalità operative DES
Per la piena soddisfazione di tutte le esigenze di sistemi commerciali crittografia, sono implementate diverse modalità di funzionamento dell'algoritmo DES. Le modalità più diffuse sono:
· Codebook elettronico (Electronic Codebook) - BCE;
Concatenamento di blocchi di cifratura - CBC;
· Feedback digitale (Cipher Feedback) - CFB;
· Feedback esterno (Output Feedback) - OFB.
In questa modalità file originale M è suddiviso in blocchi a 64 bit (8 byte ciascuno): M = M (1) M (2) ... M (n). Ciascuno di questi blocchi è crittografato in modo indipendente utilizzando la stessa chiave di crittografia (Figura 5). Il vantaggio principale di questo algoritmo è la sua facilità di implementazione. Lo svantaggio è la resistenza relativamente debole contro crittoanalisti esperti.
