La crittanalisi lineare è uno dei frutti delle innovazioni crittanalitiche del XX secolo. Si basa sulla possibilità di disporre di una coppia messaggio chiaro-messaggio cifrato, cosa non impossibile nel campo delle telecomunicazioni.
Partendo da un testo chiaro noto usa un'approssimazione lineare per descrivere il comportamento del blocco di cifre. Consiste nel confrontare il testo chiaro e il corrispondente testo cifrato. In base ai dati così raccolti ed attentamente esaminati ci si può fare un'idea riguardo la chiave. La probabilità di successo è alta.
Vediamo meglio come funziona.
Per prima cosa abbiamo bisogno di un registro a scorrimento lineare che sia composto di n elementi di memoria binaria, detti stadi, il cui contenuto può essere la cifra 0 o la cifra 1; n è la lunghezza del registro; l'ennupla binaria contenuta nel registro in un dato momento è lo stato del registro in quel momento (dunque gli stati possibili di un registro di lunghezza n sono 2n). Ad intervalli di tempo regolari il contenuto di ciascuno stadio viene trasferito (scorre) nello stadio di sinistra ed il contenuto di S0 "esce" dal registro. Anche il contenuto dello stadio più a sinistra, Sn-1, va aggiornato: ciò viene effettuato mediante la funzione di retroazione, detta "feedback" del registro.
Tale funzione consiste in un addizionatore che è collegato a certi stadi del registro: l'addizionatore somma il contenuto di tali stadi (prima che il registro venga aggiornato) ed il risultato viene appunto trasferito in Sn-1; la somma di cui parliamo è, naturalmente, quella binaria modulo 2 in cui 1+1=0. Le uscite del registro sono costituite dalle cifre binarie pseudocasuali che via via occupano lo stadio S0.
Chiave pseudocasuale è sinonimo di chiave "pseudoperfetta" (con riferimento al cifrario perfetto o di Vernam) e potrebbe sembrare che un simile codice sia inattaccabile ma non è così.
Immaginiamo che un crittanalista possa venire in possesso della coppia messaggio-crittogramma; tale coppia può effettivamente essergli sufficiente per capire qual è la chiave che è stata usata, e dunque per decifrare tutti i crittogrammi futuri che sarà in grado di intercettare: bastano 2n cifre di messaggio e le 2n cifre del crittogramma corrispondente perchè il crittanalista sia in grado di forzare il cifrario in maniera completa.
Supponiamo che il registro in questione abbia lunghezza 5, e che il crittanalista abbia intercettato il messaggio m12 m13 m14...m20 m21, ed il crittogramma c12 c13 c14...c20 c21 (gli istanti di tempo sono t=12, 13, 14,...20, 21). Poichè il crittogramma si calcola sommando la chiave al messaggio cifra per cifra, si ha:
c12=m12+S0(12)Ciò consente al crittanalista di calcolare S0(12), S0(13),...S0(21):
Queste 5 equazioni lineari consentono di trovare i valori di a0, a1, a2, a3 e a4. Il crittanalista è ormai in grado di calcolare anche S0(22), S0(23), e così via all'infinito: il cifrario è ormai forzato.
Tale metodo fu per la prima volta usato da Matsui e Yamagishi in un attacco al FEAL. Successivamente Matsui lo estese e migliorò per forzare il DES , e da allora fu assai studiato.
Langford e Hellman introdussero un attacco chiamato crittanalisi lineare-differenziale, che combina elementi della crittanalisi differenziale con quelli della lineare.
Nello stesso modo sono stati studiati metodi per proteggere i testi cifrati da tali tipi di attacchi, e tra i maggiori esponenti di tale ricerche, hanno voce in capitolo Nyberg, Knudsen e O'Conner.