Η κρυπτογράφηση RSA είναι μία από τις πρώτεςπρακτικά κρυπτοσυστήματα δημόσιου κλειδιού, το οποίο χρησιμοποιείται ευρέως για ασφαλή μετάδοση δεδομένων. Η κύρια διαφορά του από παρόμοιες υπηρεσίες είναι ότι το κλειδί κρυπτογράφησης είναι δημόσιο και διαφέρει από το κλειδί αποκρυπτογράφησης, το οποίο διατηρείται μυστικό. Στην τεχνολογία RSA, αυτή η ασυμμετρία βασίζεται στην πρακτική πολυπλοκότητα του factoring δύο μεγάλων πρώτων (πρόβλημα factoring).
Ιστορία της δημιουργίας
Το όνομα RSA αποτελείται από τα αρχικά γράμματα των επωνύμωνΟι Rivest, Shamir και Adleman είναι οι επιστήμονες που περιέγραψαν για πρώτη φορά αυτούς τους αλγόριθμους κρυπτογράφησης το 1977. Ο Clifford Cox, ένας Άγγλος μαθηματικός που εργάζεται για τις υπηρεσίες πληροφοριών του Ηνωμένου Βασιλείου, ανέπτυξε για πρώτη φορά ένα αντίστοιχο σύστημα το 1973, αλλά δεν αποχαρακτηρίστηκε μέχρι το 1997
Ο χρήστης RSA δημιουργεί και στη συνέχεια δημοσιεύειένα δημόσιο κλειδί που βασίζεται σε δύο μεγάλους πρώτους αριθμούς μαζί με μια βοηθητική τιμή. Οι πρωταρχικοί αριθμοί πρέπει να διατηρούνται μυστικοί. Οποιοσδήποτε μπορεί να χρησιμοποιήσει το δημόσιο κλειδί για την κρυπτογράφηση ενός μηνύματος, αλλά αν είναι αρκετά μεγάλο τότε μόνο κάποιος με γνώση των πρωταρχικών αριθμών μπορεί να αποκωδικοποιήσει το μήνυμα. Η αποκάλυψη της κρυπτογράφησης RSA είναι γνωστό ως το κύριο πρόβλημα: σήμερα υπάρχει μια ανοιχτή συζήτηση σχετικά με το πόσο αξιόπιστος είναι ο μηχανισμός.
Το RSA είναι ένας σχετικά αργός αλγόριθμος,Για το λόγο αυτό, δεν χρησιμοποιείται τόσο ευρέως για την άμεση κρυπτογράφηση των δεδομένων χρήστη. Η πιο συνηθισμένη χρήση αυτής της μεθόδου είναι η κρυπτογράφηση κοινών κλειδιών για ένα συμμετρικό κλειδί κρυπτογράφησης, το οποίο με τη σειρά του μπορεί να εκτελεί εργασίες κρυπτογράφησης και αποκρυπτογράφησης με πολύ μεγαλύτερη ταχύτητα.
Πότε εμφανίστηκε το κρυπτοσύστημα στη σύγχρονη μορφή του;
Η ιδέα ενός ασύμμετρου κρυπτοσυστήματος κλειδιούαποδίδεται στον Diffie και τον Hellman, οι οποίοι δημοσίευσαν την ιδέα το 1976 εισάγοντας ψηφιακές υπογραφές και προσπαθώντας να εφαρμόσουν τη θεωρία αριθμών. Η διατύπωσή τους χρησιμοποιεί ένα κοινό μυστικό κλειδί που δημιουργείται από την εκτόνωση κάποιου αριθμού modulo a prime number. Ωστόσο, άφησαν ανοιχτό το πρόβλημα της εφαρμογής αυτής της λειτουργίας, καθώς οι αρχές του factoring δεν ήταν καλά κατανοητές εκείνη την εποχή.
Rivest, Adi Shamir και Adleman στη ΜασαχουσέτηΤο Ινστιτούτο Τεχνολογίας έκανε πολλές προσπάθειες κατά τη διάρκεια του έτους για να δημιουργήσει μια μονοκατευθυντική λειτουργία που είναι δύσκολο να αποκωδικοποιηθεί. Ο Rivest και ο Shamir (ως επιστήμονες υπολογιστών) πρότειναν πολλές πιθανές συναρτήσεις, ενώ ο Adleman (ως μαθηματικός) έψαχνε αδύνατα σημεία στον αλγόριθμο. Πήραν πολλές προσεγγίσεις και τελικά, τον Απρίλιο του 1977, ανέπτυξαν τελικά το σύστημα που είναι τώρα γνωστό ως RSA.
EDS και δημόσιο κλειδί
Ηλεκτρονική ψηφιακή υπογραφή ή EDS,είναι αναπόσπαστο μέρος των εγγράφων ηλεκτρονικού τύπου. Σχηματίζεται όταν μια συγκεκριμένη κρυπτογραφική αλλαγή στα δεδομένα. Χρησιμοποιώντας αυτό το χαρακτηριστικό, μπορείτε να ελέγξετε την ακεραιότητα ενός εγγράφου, την εμπιστευτικότητα του και επίσης να εξακριβώσετε ποιος είναι ο κάτοχός του. Στην πραγματικότητα, αυτή είναι μια εναλλακτική λύση από τη συνήθη τυπική υπογραφή.
Αυτό το κρυπτοσύστημα (κρυπτογράφηση RSA) προσφέρειδημόσιο κλειδί, πώς διαφέρει από τη συμμετρική. Η αρχή της λειτουργίας του είναι ότι χρησιμοποιούνται δύο διαφορετικά κλειδιά - ιδιωτικά (κρυπτογραφημένα) και επίσης δημόσια. Το πρώτο χρησιμοποιείται για τη δημιουργία ενός EDS και στη συνέχεια για να είναι σε θέση να αποκρυπτογραφήσει το κείμενο. Το δεύτερο αφορά την πραγματική κρυπτογράφηση και επαλήθευση της ψηφιακής υπογραφής.
Η χρήση μιας υπογραφής επιτρέπει την καλύτερη κατανόηση της κρυπτογράφησης RSA, ένα παράδειγμα της οποίας μπορεί να αναφέρεται ως ένα συνηθισμένο διαβαθμισμένο έγγραφο "εκτός θέασης".
Ποια είναι η ουσία του αλγορίθμου;
Ο αλγόριθμος RSA αποτελείται από τέσσερα στάδια:δημιουργία κλειδιών, διανομή, κρυπτογράφηση και αποκρυπτογράφηση. Όπως έχει ήδη αναφερθεί, η κρυπτογράφηση RSA περιλαμβάνει ένα δημόσιο κλειδί και ένα ιδιωτικό κλειδί. Το Open μπορεί να είναι γνωστό σε όλους και χρησιμοποιείται για την κρυπτογράφηση μηνυμάτων. Η ουσία του έγκειται στο γεγονός ότι τα μηνύματα που έχουν κρυπτογραφηθεί χρησιμοποιώντας ένα δημόσιο κλειδί μπορούν να αποκρυπτογραφηθούν μόνο εντός ορισμένης χρονικής περιόδου χρησιμοποιώντας ένα μυστικό κλειδί.
Για λόγους ασφαλείας, οι ακέραιοι αριθμοί πρέπει να είναιεπιλέγονται τυχαία και έχουν το ίδιο μέγεθος, αλλά διαφέρουν σε μήκος κατά αρκετά ψηφία για να καταστήσουν πιο δύσκολη την πρακτορεία. Ίδιοι αριθμοί μπορούν να βρεθούν αποτελεσματικά χρησιμοποιώντας ένα τεστ για την απλότητά τους, οπότε η κρυπτογράφηση πληροφοριών πρέπει απαραίτητα να γίνει πιο περίπλοκη.
Το δημόσιο κλειδί αποτελείται από μια ενότητα και έναν δημόσιο εκθέτη. Το Private αποτελείται από μια ενότητα και μια ιδιωτική ένδειξη, τα οποία πρέπει να διατηρούνται μυστικά.
Κρυπτογράφηση αρχείων και αδυναμίες RSA
Ωστόσο, υπάρχουν διάφοροι μηχανισμοί εισβολής.απλή RSA. Σε κρυπτογράφηση με χαμηλές τιμές και χαμηλές τιμές αριθμών, η κρυπτογράφηση μπορεί εύκολα να σπάσει επιλέγοντας τη ρίζα του κρυπτογραφημένου κειμένου πάνω από ακέραιους.
Δεδομένου ότι η κρυπτογράφηση RSA είναιΜε έναν ντετερμινιστικό αλγόριθμο (δηλ. Χωρίς τυχαίο στοιχείο), ένας εισβολέας μπορεί να ξεκινήσει επιτυχώς μια επιλεγμένη επίθεση απλού κειμένου εναντίον ενός κρυπτοσυστήματος κρυπτογραφώντας το πιθανό απλό κείμενο κάτω από το δημόσιο κλειδί και ελέγχοντας εάν είναι ίσοι με το κρυπτότυπο. Ένα κρυπτοσύστημα ονομάζεται σημασιολογικά ασφαλές εάν ένας εισβολέας δεν μπορεί να διακρίνει μεταξύ δύο κρυπτογράφησης μεταξύ τους, ακόμη και αν γνωρίζει τα αντίστοιχα κείμενα στην αποκαλυπτόμενη μορφή. Όπως περιγράφεται παραπάνω, το RSA δεν είναι σημασιολογικά ασφαλές, εκτός εάν συμπληρώνεται με άλλες υπηρεσίες.
Πρόσθετοι αλγόριθμοι κρυπτογράφησης και προστασίας
Για να αποφύγετε τα παραπάνω προβλήματα, ότανΠρακτικές εφαρμογές RSA ενσωματώνουν συνήθως κάποια μορφή δομημένης, τυχαιοποιημένης επένδυσης πριν από την κρυπτογράφηση. Αυτό διασφαλίζει ότι το περιεχόμενο δεν εμπίπτει στο εύρος των μη ασφαλών απλών κειμένων και ότι το μήνυμα δεν μπορεί να αποκαλυφθεί τυχαία.
RSA Cryptosystem Security και EncryptionΟι πληροφορίες βασίζονται σε δύο μαθηματικά προβλήματα: το πρόβλημα του factoring μεγάλων αριθμών και το ίδιο το πρόβλημα RSA. Η πλήρης αποκάλυψη του ciphertext και του EDS στο RSA θεωρείται απαράδεκτη με την υπόθεση ότι και τα δύο αυτά προβλήματα δεν μπορούν να επιλυθούν μαζί.
Ωστόσο, λόγω της πιθανότητας ανάκαμψηςαπλοί παράγοντες, ένας εισβολέας μπορεί να υπολογίσει μια μυστική φιγούρα από το δημόσιο κλειδί και στη συνέχεια να αποκρυπτογραφήσει το κείμενο χρησιμοποιώντας μια τυπική διαδικασία. Παρά το γεγονός ότι σήμερα δεν έχει βρεθεί καμία υπάρχουσα μέθοδος παραγοντοποίησης μεγάλων αριθμών σε έναν κλασικό υπολογιστή, δεν έχει αποδειχθεί ότι δεν υπάρχει.
Αυτοματισμοί
Ένα εργαλείο που ονομάζεται Yafu μπορεί να είναιχρησιμοποιείται για τη βελτιστοποίηση αυτής της διαδικασίας. Ο αυτοματισμός στο YAFU είναι ένα σύγχρονο χαρακτηριστικό που συνδυάζει αλγόριθμους παραγοντοποίησης σε μια έξυπνη και προσαρμοστική μεθοδολογία που ελαχιστοποιεί το χρόνο για την εύρεση παραγόντων αυθαίρετων αριθμών εισόδου. Οι περισσότερες υλοποιήσεις του αλγορίθμου είναι πολλαπλών νημάτων, επιτρέποντας στο Yafu να εκμεταλλευτεί πλήρως τους πολυ-πολυπύρηνους επεξεργαστές (συμπεριλαμβανομένων των SNFS, SIQS και ECM). Πρώτα απ 'όλα, είναι ένα εργαλείο διαχειριζόμενης γραμμής εντολών. Ο χρόνος που απαιτείται για την εύρεση του συντελεστή κρυπτογράφησης χρησιμοποιώντας το Yafu σε έναν κανονικό υπολογιστή μπορεί να μειωθεί στα 103,1746 δευτερόλεπτα. Το εργαλείο επεξεργάζεται δυαδικά αρχεία χωρητικότητας 320 bit ή περισσότερο. Είναι ένα πολύ περίπλοκο λογισμικό που απαιτεί ορισμένη ποσότητα τεχνικής ικανότητας για εγκατάσταση και διαμόρφωση. Έτσι, η κρυπτογράφηση C RSA θα μπορούσε να είναι ευάλωτη.
Απόπειρες πειρατείας στη σύγχρονη εποχή
Το 2009 ο Benjamin Moody χρησιμοποιεί bitΤο κλειδί RSA-512 εργάστηκε για την αποκρυπτογράφηση του κρυπτογραφικού κειμένου για 73 ημέρες χρησιμοποιώντας μόνο γνωστό λογισμικό (GGNFS) και έναν μέσο επιτραπέζιο υπολογιστή (Athlon64 dual-core στα 1900 MHz). Όπως φαίνεται από αυτήν την εμπειρία, χρειάστηκε λίγο λιγότερο από 5 gigabytes δίσκου και περίπου 2,5 gigabytes RAM για τη διαδικασία "κοσκίνισμα".
Από το 2010, ο μεγαλύτερος παραγοντοποιημένος αριθμός RSA είχε μήκος 768 bit (232 δεκαδικά ψηφία ή RSA-768). Η αποκάλυψή του διήρκεσε δύο χρόνια σε αρκετούς εκατοντάδες υπολογιστές ταυτόχρονα.
Στην πράξη, τα κλειδιά RSA είναι μεγάλα -συνήθως 1024 έως 4096 bits. Ορισμένοι ειδικοί πιστεύουν ότι τα κλειδιά 1024-bit μπορεί να γίνουν αναξιόπιστα στο εγγύς μέλλον, ή ακόμη και να έχουν ήδη τεθεί σε κίνδυνο από έναν αρκετά καλά χρηματοδοτούμενο εισβολέα. Ωστόσο, λίγοι θα υποστήριζαν ότι τα κλειδιά 4096-bit θα μπορούσαν επίσης να αποκαλυφθούν στο άμεσο μέλλον.
Προοπτικές
Επομένως, θεωρείται γενικά ότι το RSAείναι ασφαλές εάν οι αριθμοί είναι αρκετά μεγάλοι. Εάν ο κύριος αριθμός είναι 300 bit ή λιγότερο, το ciphertext και το EDS μπορούν να αποσυντεθούν μέσα σε λίγες ώρες σε έναν προσωπικό υπολογιστή χρησιμοποιώντας λογισμικό που είναι ήδη ελεύθερα διαθέσιμο. Τα πλήκτρα 512-bit αποδείχθηκε ότι ήταν σε θέση να σπάσουν ήδη από το 1999 χρησιμοποιώντας αρκετές εκατοντάδες υπολογιστές. Αυτό είναι δυνατό αυτές τις μέρες για αρκετές εβδομάδες χρησιμοποιώντας υλικό που είναι διαθέσιμο στο κοινό. Έτσι, είναι πολύ πιθανό ότι στο μέλλον η κρυπτογράφηση RSA θα αποκαλυφθεί εύκολα στα δάχτυλα και το σύστημα θα καταστεί απελπιστικά παρωχημένο.
Επισήμως το 2003, αμφισβητήθηκε η ασφάλεια των κλειδιών 1024-bit. Προς το παρόν συνιστάται να έχετε μήκος τουλάχιστον 2048 bit.
