Crittografia

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 (FⁿR). 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,  , si produce la coppia (x, x_i) con ogni coppia differente solo per il bit i (ottenendo 2^m-1 coppie, con x che sono tutti i possibili messaggi/vettori di m cifre binarie), e si osservano le 2^m-1 somme XOR, definite vettori valanga, v_i=F(x) XOR F(x_i), 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, , nel testo cifrato/vettore di uscita, c’è almeno una coppia di messaggi/vettori x e x_i differenti solo per il bit i e per cui F(x) e F(x_i) 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à R₀, L₀, 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

I link correlati all'argomento

• L'indice della tesi
• La tesi in formato pdf
• Metodi proposti da Shannon per la soluzione di cifrari classici
• Fondamenti della teoria dell'informazione