Feistel cipher

Στην κρυπτογραφία, η κρυπτογράφηση Feistel είναι μια συμμετρική δομή που χρησιμοποιείται στην κατασκευή κρυπτογραφήσεων μπλοκ, η οποία πήρε το όνομά της από τον Γερμανό κρυπτογράφο της IBM Horst Feistel. Ένα μεγάλο σύνολο κρυπτογραφήσεων μπλοκ χρησιμοποιεί το σχήμα, συμπεριλαμβανομένου του Data Encryption Standard

Η δομή Feistel έχει το πλεονέκτημα ότι οι λειτουργίες κρυπτογράφησης και αποκρυπτογράφησης είναι πολύ παρόμοιες, ακόμη και πανομοιότυπες σε ορισμένες περιπτώσεις, απαιτώντας μόνο την αντιστροφή του χρονοδιαγράμματος κλειδιών. Επομένως, το μέγεθος του κώδικα ή του κυκλώματος που απαιτείται για την υλοποίηση μιας τέτοιας κρυπτογράφησης μειώνεται σχεδόν στο μισό.

Η κατασκευή Feistel έχει επαναληπτικό χαρακτήρα, γεγονός που καθιστά ευκολότερη την υλοποίηση του κρυπτοσυστήματος σε υλικό.

Τα δίκτυα Feistel και παρόμοιες κατασκευές είναι κρυπτογραφήσεις προϊόντων, και έτσι συνδυάζουν πολλαπλούς γύρους επαναλαμβανόμενων πράξεων, όπως:

Ανακάτεμα bit (συχνά αποκαλούμενα κουτιά μετατροπής ή P-boxes)
Απλές μη γραμμικές συναρτήσεις (συχνά αποκαλούμενες κουτιά υποκατάστασης ή κουτιά S)
Γραμμική ανάμειξη (με την έννοια της σπονδυλωτής άλγεβρας) με χρήση XOR για την παραγωγή μιας συνάρτησης με μεγάλες ποσότητες αυτού που ο Claude Shannon περιέγραψε ως "σύγχυση και διάχυση".

Το ανακάτεμα των bit δημιουργεί το φαινόμενο της διάχυσης, ενώ η αντικατάσταση χρησιμοποιείται για τη σύγχυση.

Θεωρητική εργασία

Πολλοί σύγχρονοι συμμετρικοί κρυπτογράφοι μπλοκ χρησιμοποιούν δίκτυα Feistel και η δομή και οι ιδιότητες των κρυπτογράφων Feistel έχουν διερευνηθεί εκτενώς από τους κρυπτογράφους. Συγκεκριμένα, οι Michael Luby και Charles Rackoff ανέλυσαν την κατασκευή του κρυπτογραφήματος μπλοκ Feistel και απέδειξαν ότι αν η συνάρτηση γύρου είναι μια κρυπτογραφικά ασφαλής ψευδοτυχαία συνάρτηση, με το Κ_i να χρησιμοποιείται ως σπόρος, τότε 3 γύροι αρκούν για να καταστήσουν το κρυπτογράφημα μπλοκ μια ψευδοτυχαία μεταστοιχείωση, ενώ 4 γύροι αρκούν για να το καταστήσουν μια "ισχυρή" ψευδοτυχαία μεταστοιχείωση (που σημαίνει ότι παραμένει ψευδοτυχαία ακόμη και σε έναν αντίπαλο που αποκτά πρόσβαση στο μαντείο στην αντίστροφη μεταστοιχείωσή του). Εξαιτίας αυτού του πολύ σημαντικού αποτελέσματος των Luby και Rackoff, οι κρυπτογραφήσεις Feistel καλούνται μερικές φορές κρυπτογραφήσεις μπλοκ Luby-Rackoff. Περαιτέρω θεωρητικές μελέτες γενίκευσαν την κατασκευή και καθόρισαν ακριβέστερα όρια για την ασφάλεια.

Κατασκευή

Έστω F {\displaystyle {\rm {F}}} ${\rm F}$ η συνάρτηση γύρου και έστω K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}} $K_1,K_2,\ldots,K_{n}$ τα υπο-κλειδιά για τους γύρους 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} $1,2,\ldots,n$ αντίστοιχα.

Στη συνέχεια, η βασική λειτουργία έχει ως εξής:

Χωρίστε το μπλοκ καθαρού κειμένου σε δύο ίσα κομμάτια, ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 )

Για κάθε γύρο i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , υπολογισμός (calculate)

L i + 1 = R i {\displaystyle L_{i+1}=R_{i}\,} $L_{i+1} = R_i\,$

R i + 1 = L i ⊕ F ( R i , K i ) {\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Τότε το κρυπτογραφημένο κείμενο είναι ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Συνήθως τα δύο κομμάτια R n {\displaystyle R_{n}} R_n και L n {\displaystyle L_{n}} L_n δεν αλλάζουν μετά τον τελευταίο γύρο).

Η αποκρυπτογράφηση ενός κρυπτογραφημένου κειμένου ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) επιτυγχάνεται με τον υπολογισμό για i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1} $i=n,n-1,\ldots,1$

R i = L i + 1 {\displaystyle R_{i}=L_{i+1}\,} $R_{i} = L_{i+1}\,$

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})} $L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$ .

Τότε ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) είναι και πάλι το απλό κείμενο.

Ένα πλεονέκτημα αυτού του μοντέλου είναι ότι η στρογγυλή συνάρτηση F {\displaystyle {\rm {F}}} ${\rm F}$ δεν χρειάζεται να είναι αντιστρέψιμη και μπορεί να είναι πολύ περίπλοκη.

Το διάγραμμα απεικονίζει τη διαδικασία κρυπτογράφησης. Η αποκρυπτογράφηση απαιτεί μόνο την αντιστροφή της σειράς των υποκλειδιών K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ χρησιμοποιώντας την ίδια διαδικασία- αυτή είναι η μόνη διαφορά μεταξύ κρυπτογράφησης και αποκρυπτογράφησης:

Τα μη ισορροπημένα κρυπτογραφήματα Feistel χρησιμοποιούν μια τροποποιημένη δομή όπου τα L 1 {\displaystyle L_{1}} L_1 και R 1 {\displaystyle R_{1}} R_1 δεν έχουν ίσα μήκη. Η κρυπτογράφηση MacGuffin είναι ένα πειραματικό παράδειγμα μιας τέτοιας κρυπτογράφησης.

Η κατασκευή Feistel χρησιμοποιείται και σε άλλους κρυπτογραφικούς αλγορίθμους εκτός από τους block ciphers. Για παράδειγμα, το σχήμα Optimal Asymmetric Encryption Padding (OAEP) χρησιμοποιεί ένα απλό δίκτυο Feistel για να τυχαιοποιήσει τα κρυπτογραφήματα σε ορισμένα σχήματα κρυπτογράφησης ασύμμετρου κλειδιού.

Λειτουργία δικτύου Feistel σε block cipher, όπου P είναι το απλό κείμενο και C είναι το κρυπτογράφημα

Κατάλογος κρυπτογραφήσεων Feistel

Feistel ή τροποποιημένο Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Γενικευμένο Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Ερωτήσεις και απαντήσεις

Q: Τι είναι το κρυπτογράφημα Feistel;

A: Ο κρυπτογράφος Feistel είναι μια συμμετρική δομή που χρησιμοποιείται στην κατασκευή κρυπτογραφήσεων μπλοκ, η οποία πήρε το όνομά της από τον Γερμανό κρυπτογράφο της IBM Horst Feistel. Είναι επίσης ευρέως γνωστό ως δίκτυο Feistel.

Ερ: Ποια είναι μερικά πλεονεκτήματα της χρήσης μιας δομής Feistel;

Α: Το κύριο πλεονέκτημα της χρήσης μιας δομής Feistel είναι ότι οι λειτουργίες κρυπτογράφησης και αποκρυπτογράφησης είναι πολύ παρόμοιες, ακόμη και πανομοιότυπες σε ορισμένες περιπτώσεις, απαιτώντας μόνο την αντιστροφή του προγράμματος κλειδιών. Αυτό μειώνει το μέγεθος του κώδικα ή του κυκλώματος που απαιτείται για την υλοποίηση μιας τέτοιας κρυπτογράφησης σχεδόν κατά το ήμισυ. Επιπλέον, η επαναληπτική φύση του καθιστά ευκολότερη την υλοποίηση του κρυπτοσυστήματος σε υλικό.

Ερ: Πώς περιγράφει ο Κλοντ Σάνον τη "σύγχυση και τη διάχυση";

Α: Ο Claude Shannon περιέγραψε τη "σύγχυση και τη διάχυση" ως την ύπαρξη μεγάλων ποσοτήτων και των δύο στοιχείων προκειμένου να δυσχεραίνεται η αποκρυπτογράφηση ενός κρυπτογραφημένου μηνύματος από έναν επιτιθέμενο.

Ερ: Ποιες τεχνικές χρησιμοποιούνται για τη δημιουργία σύγχυσης και διάχυσης;

Α: Η σύγχυση και η διάχυση δημιουργούνται μέσω του ανακατέματος των bit (που συχνά ονομάζονται κουτιά αντιμετάθεσης ή κουτιά P) και απλές μη γραμμικές συναρτήσεις (που συχνά ονομάζονται κουτιά αντικατάστασης ή κουτιά S), καθώς και γραμμική ανάμειξη (με την έννοια της σπονδυλωτής άλγεβρας) με τη χρήση XOR. Το ανακάτεμα των bit δημιουργεί το φαινόμενο της διάχυσης, ενώ η υποκατάσταση χρησιμοποιείται για τη σύγχυση.

Ερ: Τι είδους κρυπτογράφηση είναι ένα δίκτυο Feistel;

A: Ένα δίκτυο Feistel είναι ένας τύπος κρυπτογράφησης προϊόντος που συνδυάζει πολλαπλούς γύρους επαναλαμβανόμενων πράξεων προκειμένου να κρυπτογραφήσει δεδομένα με ασφάλεια.

Ερ: Ποιος ανέπτυξε αυτό το είδος κρυπτογραφίας;

Α: Η δομή Feistel αναπτύχθηκε από τον Γερμανό κρυπτογράφο της IBM Horst Feistel.

Ερ: Το Data Encryption Standard βασίζεται σε αυτόν τον τύπο κρυπτογραφίας;

Α: Ναι, το Data Encryption Standard χρησιμοποιεί αυτόν τον τύπο κρυπτογραφίας, ο οποίος χρησιμοποιεί τις ίδιες αρχές που περιγράφονται παραπάνω για τη δημιουργία σύγχυσης και διάχυσης μέσα σε ένα κρυπτογραφημένο μήνυμα.