SP-δίκτυο
Στην κρυπτογραφία, ένα δίκτυο SP-network ή substitution-permutation network (SPN), είναι μια σειρά από συνδεδεμένες μαθηματικές πράξεις που χρησιμοποιούνται σε αλγόριθμους κρυπτογράφησης μπλοκ όπως οι AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK και Square.
Ένα τέτοιο δίκτυο λαμβάνει ένα μπλοκ του απλού κειμένου και το κλειδί ως είσοδο και εφαρμόζει διάφορους εναλλασσόμενους "γύρους" ή "στρώματα" από πλαίσια αντικατάστασης (S-boxes) και πλαίσια μετατροπής (P-boxes) για να παράγει το μπλοκ του κρυπτοκειμένου. Τα κουτιά S και τα κουτιά P μετατρέπουν (υπο)μπλοκ από bits εισόδου σε bits εξόδου. Είναι σύνηθες οι μετασχηματισμοί αυτοί να είναι πράξεις που είναι αποδοτικές για να εκτελεστούν σε υλικό, όπως η αποκλειστική ή (XOR) και η περιστροφή κατά bit. Το κλειδί εισάγεται σε κάθε γύρο, συνήθως με τη μορφή "κλειδιών γύρου" που προέρχονται από αυτό. (Σε ορισμένα σχέδια, τα ίδια τα κουτιά S εξαρτώνται από το κλειδί).
Η αποκρυπτογράφηση γίνεται με απλή αντιστροφή της διαδικασίας (χρησιμοποιώντας τα αντίστροφα των S-κουτιών και των P-κουτιών και εφαρμόζοντας τα κλειδιά γύρου με αντίστροφη σειρά).
Ένα S-box αντικαθιστά ένα μικρό μπλοκ από bits (η είσοδος του S-box) με ένα άλλο μπλοκ από bits (η έξοδος του S-box). Αυτή η αντικατάσταση πρέπει να είναι ένα προς ένα, ώστε να διασφαλίζεται η αντιστρεψιμότητα (άρα και η αποκρυπτογράφηση). Ειδικότερα, το μήκος της εξόδου θα πρέπει να είναι το ίδιο με το μήκος της εισόδου (η εικόνα στα δεξιά έχει S-boxes με 4 bits εισόδου και 4 bits εξόδου), κάτι που διαφέρει από τα S-boxes γενικά που θα μπορούσαν επίσης να αλλάξουν το μήκος, όπως για παράδειγμα στο DES (Data Encryption Standard). Ένα S-box συνήθως δεν είναι απλώς μια μετάθεση των bits. Αντίθετα, ένα καλό S-box θα έχει την ιδιότητα ότι η αλλαγή ενός bit εισόδου θα αλλάξει περίπου τα μισά bit εξόδου (ή ένα φαινόμενο χιονοστιβάδας). Θα έχει επίσης την ιδιότητα ότι κάθε bit εξόδου θα εξαρτάται από κάθε bit εισόδου.
Ένα P-box είναι μια μετάθεση όλων των bits: παίρνει τις εξόδους όλων των S-box ενός γύρου, μετατρέπει τα bits και τα τροφοδοτεί στα S-box του επόμενου γύρου. Ένα καλό P-box έχει την ιδιότητα ότι τα bits εξόδου οποιουδήποτε S-box κατανέμονται σε όσο το δυνατόν περισσότερες εισόδους S-box.
Σε κάθε γύρο, το κλειδί του γύρου (που λαμβάνεται από το κλειδί με κάποιες απλές πράξεις, για παράδειγμα, με τη χρήση S-κουτιών και P-κουτιών) συνδυάζεται με κάποια ομαδική πράξη, συνήθως XOR.
Ένα μόνο τυπικό S-box ή ένα μόνο P-box από μόνο του δεν έχει μεγάλη κρυπτογραφική ισχύ: ένα S-box θα μπορούσε να θεωρηθεί ως κρυπτογράφηση αντικατάστασης, ενώ ένα P-box θα μπορούσε να θεωρηθεί ως κρυπτογράφηση μετατόπισης. Ωστόσο, ένα καλά σχεδιασμένο δίκτυο SP με αρκετούς εναλλασσόμενους γύρους S- και P-κουτιών ικανοποιεί ήδη τις ιδιότητες σύγχυσης και διάχυσης του Shannon:
- Ο λόγος για τη διάχυση είναι ο εξής: Εάν κάποιος αλλάξει ένα bit του απλού κειμένου, τότε αυτό τροφοδοτείται σε ένα S-box, του οποίου η έξοδος θα αλλάξει σε αρκετά bits, τότε όλες αυτές οι αλλαγές κατανέμονται από το P-box σε πολλά S-box, επομένως οι έξοδοι όλων αυτών των S-box αλλάζουν και πάλι σε αρκετά bits, και ούτω καθεξής. Κάνοντας αρκετούς γύρους, κάθε bit αλλάζει αρκετές φορές μπρος-πίσω, επομένως, στο τέλος, το κρυπτογραφημένο κείμενο έχει αλλάξει εντελώς, με ψευδοτυχαίο τρόπο. Συγκεκριμένα, για ένα τυχαία επιλεγμένο μπλοκ εισόδου, αν αντιστραφεί το i-οστό bit, τότε η πιθανότητα να αλλάξει το j-οστό bit εξόδου είναι περίπου το μισό, για οποιοδήποτε i και j, το οποίο είναι το Κριτήριο Αυστηρής Χιονοστιβάδας (Strict Avalanche Criterion). Αντιστρόφως, αν κάποιος αλλάξει ένα bit του κρυπτοκειμένου και στη συνέχεια προσπαθήσει να το αποκρυπτογραφήσει, το αποτέλεσμα είναι ένα μήνυμα εντελώς διαφορετικό από το αρχικό απλό κείμενο - οι κρυπτογράφους SP δεν είναι εύκολα τροποποιήσιμοι.
- Ο λόγος για τη σύγχυση είναι ακριβώς ο ίδιος με αυτόν της διάχυσης: η αλλαγή ενός bit του κλειδιού αλλάζει πολλά από τα κλειδιά του γύρου και κάθε αλλαγή σε κάθε κλειδί του γύρου διαχέεται σε όλα τα bit, αλλάζοντας το κρυπτογραφημένο κείμενο με πολύ περίπλοκο τρόπο.
- Ακόμη και αν ένας επιτιθέμενος αποκτήσει με κάποιο τρόπο ένα απλό κείμενο που αντιστοιχεί σε ένα κρυπτοκείμενο - μια επίθεση γνωστού απλού κειμένου ή, ακόμη χειρότερα, μια επίθεση επιλεγμένου απλού κειμένου ή επιλεγμένου κρυπτοκειμένου - η σύγχυση και η διάχυση καθιστούν δύσκολη την ανάκτηση του κλειδιού από τον επιτιθέμενο.
Παρόλο που ένα δίκτυο Feistel που χρησιμοποιεί S-boxes (όπως το DES) είναι αρκετά παρόμοιο με τα δίκτυα SP, υπάρχουν ορισμένες διαφορές που καθιστούν είτε το ένα είτε το άλλο πιο εφαρμόσιμο σε ορισμένες περιπτώσεις. Για δεδομένη ποσότητα σύγχυσης και διάχυσης, ένα δίκτυο SP έχει περισσότερο "εγγενή παραλληλισμό" και έτσι - δεδομένης μιας CPU με πολλές μονάδες εκτέλεσης - μπορεί να υπολογιστεί ταχύτερα από ένα δίκτυο Feistel. ΚΜΕ με λίγες μονάδες εκτέλεσης - όπως οι περισσότερες έξυπνες κάρτες - δεν μπορούν να επωφεληθούν από αυτόν τον εγγενή παραλληλισμό. Επίσης, τα SP κρυπτογραφήματα απαιτούν τα S-boxes να είναι αντιστρέψιμα (για να εκτελούν αποκρυπτογράφηση)- οι εσωτερικές συναρτήσεις Feistel δεν έχουν τέτοιο περιορισμό και μπορούν να κατασκευαστούν ως μονόδρομες συναρτήσεις.
