# Lucifer (cifrario)

In crittografia Lucifer è una famiglia di algoritmi crittografici sviluppati per uso civile all'inizio degli anni settanta da Horst Feistel e colleghi all'IBM. Lucifer fu pubblicato nel 1971 ma una versione anteriore, denominata DTD-1, fu messa in commercio nel 1970 come sistema per rendere sicure le transazioni bancarie.
Lucifer è stato uno dei primi cifrari a blocchi ed è il precursore del DES.

## L'algoritmo originario

La prima versione del Lucifer utilizzava una chiave lunga 48 bit ed operava su blocchi di 48 bit. La struttura centrale era una rete di Feistel (un algoritmo crittografico sviluppato precedentemente sempre da Feistel e qui utilizzato come funzione centrale del cifrario), una rete a sostituzione e permutazione che operava su 2 S-box a 4 bit; la chiave crittografica indicava quale S-Box utilizzare. Lucifer operava su 24 bit per volta ma poteva anche operare su 8 bit per volta utilizzando una particolare modalità sequenziale.

### Varianti

Una variante del Lucifer utilizzava una chiave a 64 bit e blocchi dati a 32 bit, con una addizione modulo 4 ed una singola S-Box a 4 bit. L'algoritmo era strutturato per operare su 4 bit per ciclo di clock. Questa variante potrebbe essere una delle più piccole implementazioni di cifrari a blocchi nota.
Una variante più robusta fu presentata dallo stesso Feistel nel 1973: essa operava su chiavi e blocchi entrambi di 128 bit di lunghezza. Il cifrario utilizzava sempre 2 S-Box per le permutazioni.
Una variante tarda del Lucifer fu presentata nel 1984 da Arthur Sorkin. Questa versione del Lucifer utilizzava sempre chiavi e blocchi lungh 128 bit ma raddoppiava il numero di passaggi, da 8 a 16.

### La variante di Arthur Sorkin

La variante descritta da Sorkin lavora con 16 permutazioni ma non ha permutazioni iniziali o finali. La chiave ed i blocchi sono entrambi a 128 bit. La rete di Feistel opera prendendo in input metà blocco (64 bit) dati, 64 bit di una sotto-chiave generata dal gestore della chiave ed 8 bit denominati "interchange control bits" (ICB), che controllano un'operazione di scambio. I 64 bit dei dati vengono gestiti a gruppi di 8 bit (1 byte) e se l'ICB corrispondente ad un particolare byte è uguale a zero, allora vengono invertiti i 4 bit di sinistra con i 4 bit di destra. Se invece l'ICB è uguale a 1, il byte non viene modificato. Ogni byte è poi processato da 2 S-Box, indicate con S0 ed S1: S0 opera sui 4 bit di sinistra mentre S1 opera sui bit di destra. L'output risultante dalle 2 S-Box viene riassemblato e poi combinato con la sotto-chiave mediante un'operazione di XOR. Questa operazione, denominata interruzione della chiave, viene seguita da una permutazione in 2 passaggi: nel primo il byte viene permutato tramite un'operazione fissa; nel secondo passaggio i bit vengono mescolati fra i byte.
Il gestore della chiave è relativamente semplice. All'inizio del processo i 128 bit della chiave vengono caricati un registro a rotazione. Ad ogni passaggio i 64 bit più a sinistra del registro formano la sottochiave da utilizzarsi in quel particolare passaggio, mentre gli 8 bit più a destra formano l'ICB. Dopo ogni passaggio, il registro è ruotato di 56 bit a sinistra.
Questa variante del Lucifer si dimostrò sensibile alla crittanalisi differenziale: per circa metà delle chiavi il cifrario poteva essere violato con 2$^{36}$ testi in chiaro ed un tempo di 2$^{36}$.

## Dal Lucifer al DES

Nel 1973 il National Bureau of Standards americano (adesso NIST) pubblicò un bando per la ricerca di un algoritmo crittografico pubblico per la protezione dei dati non sensibili. Tra il 1973 ed il 1974 IBM propose un algoritmo denominato DEA, acronimo di Data Encryption Algorithm e direttamente derivato dal Lucifer. Nel 1975 l'NSA, l'agenzia americana per la sicurezza, lo pubblicò nel Federal Register per iniziare a studiarlo. Dopo un lungo lavoro, il DEA fu accettato come nuovo standard crittografico nel novembre del 1976 e pubblicato ufficialmente il 15 gennaio 1977 con il nome di DES. Rispetto alle specifiche proposte da IBM, la lunghezza della chiave fu ridotta a 56 bit mentre i blocchi a 64 bit; in compenso, le S-Box furono profondamente modificate in modo da resistere anche alla crittanalisi differenziale.

## Curiosità

Il nome "Lucifer" deriverebbe, tramite un gioco di parole, da "Demon", che sarebbe la versione troncata di "Demonstration", il nome del nuovo algoritmo come lo intendeva Feistel quando stava lavorandoci sopra. Ma per le limitazioni del sistema operativo del suo computer, che non poteva gestire nomi così lunghi, egli doveva salvare il file con il nome "Demon".