Questo sito contribuisce alla audience di

Trasformazioni mischianti e cifratori di Feistel

Nel suo Communication Theory of Secrecy Sistems, Shannon introdusse inoltre l’idea di trasformazioni mischianti (mixing transformations).Se viene applicata una trasformazione mischiante, i messaggi ad alta probabilità verrebbero dispersi su tutto lo spazio, e la descrizione adesso sarebbe assai complicata. L'articolo è tratto dalla tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

Appendice 2: Trasformazioni mischianti e cifratori di
Feistel

Nel suo Communication Theory of Secrecy Sistems, Shannon
introdusse inoltre l’idea di trasformazioni mischianti (mixing
transformations
), ovvero delle trasformazioni F tali che una regione
iniziale R, ragionevolmente coesa, viene mischiata, cioè sparpagliata,
con densità uniforme su tutto lo spazio se F è applicato un gran numero di
volte, periodicamente (FnR). In crittografia possiamo pensare
tutti i possibili messaggi di lunghezza N come lo spazio, ed i messaggi ad alta
probabilità come la regione R. Quest’ultimo gruppo ha una struttura
probabilistica abbastanza semplice. Se viene applicata una trasformazione
mischiante, i messaggi ad alta probabilità verrebbero dispersi su tutto lo
spazio, e la descrizione adesso sarebbe assai complicata.

Il prodotto di due trasformazioni (i.e.
due trasformazioni consecutive) che operano esattamente in questo modo è la
coppia Sostituzione e Permutazione (cascata di blocchi S-P). Le porte S
provvedono alla confusione dei bit di ingresso, le porte P provvedono invece
alla diffusione. Ricordiamo che per confusione si intende rendere la relazione
tra chiave e testo cifrato più complessa possibile, mentre la diffusione si
riferisce al riordino o espansione  su tutto il testo cifrato.
I cifratori a blocco moderni usano una cascata di questi blocchi S-P, per
ottenere sia confusione che diffusione. Questi due furono formalizzati
ulteriormente da Webster e Tavares come Valanga e Completezza (Avalanche
e Completeness), nel campo delle reti logiche.

Per effetto Valanga si intende una
trasformazione tale che cambiando un solo bit di ingresso, vengono alterati metà
dei bit di uscita (cioè metà dei bit di uscita dipendono dallo stesso bit di
ingresso). Più formalmente, una funzione F ha un buon effetto valanga se:

per ogni bit i, src="http://freeweb.supereva.com/guidaingegneria/tesi/gennari/tesi_file/image215.gif"
width=63 v:shapes="_x0000_i1119"> , si produce la coppia (x,
xi) con ogni coppia differente solo per il bit i
(ottenendo 2m-1 coppie, con x che sono tutti i
possibili messaggi/vettori di m cifre binarie), e si osservano le
2m-1 somme XOR, definite vettori valanga,
vi=F(x) XOR F(xi), allora circa metà
di queste somme dovrebbe essere uguale ad 1.

Per effetto
Completezza si intende una funzione complessa di tutti i bit di ingresso. Più
formalmente una funzione F ha un buon effetto valanga se:

per ogni bit
i, src="http://freeweb.supereva.com/guidaingegneria/tesi/gennari/tesi_file/image216.gif"
width=63 v:shapes="_x0000_i1120">, nel testo cifrato/vettore di uscita,
c’è almeno una coppia di messaggi/vettori x e xi
differenti solo per il bit i e per cui F(x) e
F(xi) differiscono per il bit j.

 

I cifratori Feistel, padri di tutti i cifratori a blocco, sono
descrivibili funzionalmente in questo modo. Diviso il messaggio in due metà
R0, L0, si fa entrare in una cascata di blocchi
S-P, in una sequenza di stadi successivi:

L(i) =
R(i-1)                                                                                                 

R(i) = L(i-1) XOR F( K(i), R(i-1)
)

Tabella XOR

border=1>
















x^y


z



0

1


1

1


0

0


1

0

style="BORDER-RIGHT: medium none; BORDER-TOP: medium none; BORDER-LEFT: medium none; BORDER-BOTTOM: medium none; BORDER-COLLAPSE: collapse"
cellSpacing=0 cellPadding=0 align=left border=1>


style="BORDER-RIGHT: windowtext 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: windowtext 0.5pt solid; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid"
vAlign=top>
 


style="BORDER-RIGHT: windowtext 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: windowtext 0.5pt solid; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; PADDING-TOP: 0cm; BORDER-BOTTOM: windowtext 0.5pt solid"
vAlign=top>
 



style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: 0.5pt solid; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>
 


style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>



style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: 0.5pt solid; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>
 


style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>



style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: 0.5pt solid; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>
 


style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>



style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: 0.5pt solid; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>
 


style="BORDER-RIGHT: 0.5pt solid; PADDING-RIGHT: 3.5pt; BORDER-TOP: medium none; PADDING-LEFT: 3.5pt; PADDING-BOTTOM: 0cm; BORDER-LEFT: medium none; PADDING-TOP: 0cm; BORDER-BOTTOM: 0.5pt solid"
vAlign=top>
0


 

src="http://freeweb.supereva.com/guidaingegneria/tesi/gennari/tesi_file/image218.gif"
width=442 v:shapes="_x0000_i1121">

 

Uno stadio di Feistel. A sx un stadio di cifraz. A dx uno stadio di
decifraz.(qui la funzione F  è stata chiamata g)

La funzione F incorpora lo stadio S-P, controllato da una parte della
chiave K(i) chiamata sottochiave (subkey). L’insieme delle sottochiavi è
detto prospetto delle chiavi (key schedule).

Una cascata, di 16 stadi in genere, di queste porte formano un cifratore
completo, facilmente reversibile come si vede nel diagramma.