La funzione DES "mangler" è invertibile?

6

Il codice simmetrico DES si basa su una rete Feistel operante ripetuta su metà a 32 bit del blocco a 64 bit. L'uso di Feistel significa che la funzione "mangler" utilizzata non ha bisogno di essere invertibile.

La funzione "mangler" opera espandendo una parola da 32 bit a 48 bit tramite un semplice algoritmo. Questo 48 bit è combinato con una chiave e poi riconvertito a 32 bit tramite S-box. Gli S-box ovviamente non sono invertibili, perché prendono un ingresso a 6 bit e producono un output a 4 bit.

Ma l'intera costruzione è invertibile. Supponendo che la chiave sia fissa, ogni ingresso a 32 bit della funzione "mangler" viene mappato su una distinta uscita a 32 bit? Oppure alcune uscite a 32 bit non vengono mai prodotte dalla funzione mangler e quindi non sono invertibili?

    
posta Nakedible 07.07.2011 - 21:49
fonte

1 risposta

5

No, non è invertibile. È possibile trovare due ingressi a 32 bit che, quando alimentati alla funzione "mangler" del DES, producono entrambi la stessa uscita a 32 bit. Questo è uno dei vantaggi della struttura di Feistel: la funzione "mangler" non ha bisogno di essere invertibile e si finisce con un codice a blocchi invertibile.

In effetti, il famoso attacco alla criptoanalisi differenziale di Biham e Shamir sul DES fa un uso importante di questo fatto. Approfittano del fatto che, quando una coppia di input a 32 bit soddisfano una determinata relazione, spesso producono lo stesso output dopo aver applicato la funzione "mangler". Ciò consente loro di trovare una caratteristica differenziale con probabilità relativamente alta, che consente loro di attaccare DES. L'attacco criptanalitico differenziale al DES non è molto pratico, ma è stato un enorme progresso nella scienza della crittanalisi e della progettazione a blocchi di codice.

P.S. A proposito, non ho mai sentito un crittografo chiamare questa funzione una funzione "mangler". In genere ho sentito dire che si chiama Feistel F. Quindi, se vai da un crittografo e chiedi loro della funzione "mangler" del DES, potrebbero darti un aspetto divertente; ora sai come parlare la loro lingua.

    
risposta data 07.07.2011 - 22:56
fonte

Leggi altre domande sui tag