Rete SP
In crittografia, una rete SP, o rete di sostituzione permutazione (SPN), è una serie di operazioni matematiche collegate utilizzate negli algoritmi di cifratura a blocchi come AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK e Square.
Una rete di questo tipo prende un blocco del testo in chiaro e la chiave come input, e applica diversi "giri" o "strati" alternati di caselle di sostituzione (S-box) e di permutazione (P-box) per produrre il blocco di testo cifrato. Le S-boxes e le P-boxes trasformano (sotto)blocchi di bit di ingresso in bit di uscita. È comune che queste trasformazioni siano operazioni efficienti da eseguire in hardware, come la rotazione esclusiva o (XOR) e bitwise rotation. La chiave viene introdotta in ogni turno, di solito sotto forma di "chiavi rotonde" derivate da essa. (In alcuni progetti, le S-box stesse dipendono dalla chiave).
La decodifica avviene semplicemente invertendo il processo (utilizzando gli inversi delle S-box e delle P-box e applicando le chiavi rotonde in ordine inverso).
Una S-box sostituisce un piccolo blocco di bit (l'ingresso della S-box) con un altro blocco di bit (l'uscita della S-box). Questa sostituzione dovrebbe essere uno a uno, per garantire l'invertibilità (quindi la decodifica). In particolare, la lunghezza dell'uscita dovrebbe essere la stessa della lunghezza dell'ingresso (l'immagine a destra ha S-box con 4 bit di ingresso e 4 bit di uscita), che è diversa dalle S-box in generale che potrebbero anche cambiare la lunghezza, come ad esempio nel DES (Data Encryption Standard). Un S-box non è di solito una semplice permutazione dei bit. Piuttosto, una buona S-box avrà la proprietà che cambiando un bit in ingresso si modifica circa la metà dei bit in uscita (o un effetto valanga). Avrà anche la proprietà che ogni bit in uscita dipenderà da ogni bit in ingresso.
Una P-box è una permutazione di tutti i bit: prende le uscite di tutte le S-box di un turno, permutando i bit, e li alimenta nelle S-box del turno successivo. Un buon P-box ha la proprietà che i bit di uscita di qualsiasi S-box sono distribuiti a quanti più ingressi S-box possibile.
Ad ogni turno, la chiave rotonda (ottenuta dalla chiave con alcune semplici operazioni, per esempio, utilizzando S-boxes e P-boxes) viene combinata utilizzando alcune operazioni di gruppo, tipicamente XOR.
Un singolo tipico S-box o un singolo P-box da solo non ha molta forza crittografica: un S-box potrebbe essere pensato come un cifrario di sostituzione, mentre un P-box potrebbe essere pensato come un cifrario di trasposizione. Tuttavia, una rete SP ben progettata con diversi cicli alternati di S-box e P-box soddisfa già le proprietà di confusione e diffusione di Shannon:
- Il motivo della diffusione è il seguente: Se uno cambia un bit del testo in chiaro, allora viene alimentato in una S-box, il cui output cambierà a diversi bit, allora tutti questi cambiamenti sono distribuiti dalla P-box tra diverse S-box, quindi gli output di tutte queste S-box sono di nuovo cambiati a diversi bit, e così via. Facendo diversi giri, ogni bit cambia più volte avanti e indietro, quindi, alla fine, il testo cifrato è cambiato completamente, in modo pseudorandom. In particolare, per un blocco di input scelto a caso, se si capovolge il bit i-esimo, allora la probabilità che il bit di uscita j-esimo cambierà è di circa la metà, per ogni i e j, che è il Criterio della Valanga Rigorosa. Viceversa, se si cambia un bit del testo cifrato e si tenta di decifrarlo, il risultato è un messaggio completamente diverso dal testo in chiaro originale.
- Il motivo della confusione è esattamente lo stesso della diffusione: cambiando un bit della chiave cambia diverse chiavi rotonde, e ogni cambiamento in ogni chiave rotonda si diffonde su tutti i bit, cambiando il testo cifrato in modo molto complesso.
- Anche se un attaccante ottiene in qualche modo un testo in chiaro corrispondente a un testo cifrato - un attacco in chiaro noto - o peggio, un testo in chiaro scelto o un attacco in chiaro scelto - un attacco in chiaro scelto - la confusione e la diffusione rendono difficile per l'attaccante recuperare la chiave.
Sebbene una rete Feistel che utilizza S-boxes (come DES) sia abbastanza simile alle reti SP, ci sono alcune differenze che rendono questa o quella più applicabile in certe situazioni. Per una data quantità di confusione e diffusione, una rete SP ha più "parallelismo intrinseco" e quindi - data una CPU con molte unità di esecuzione - può essere calcolata più velocemente di una rete Feistel. Le CPU con poche unità di esecuzione - come la maggior parte delle smart card - non possono sfruttare questo parallelismo intrinseco. Anche i cifrari SP richiedono che le S-box siano invertibili (per eseguire la decodifica); le funzioni interne di Feistel non hanno tale restrizione e possono essere costruite come funzioni unidirezionali.
