RSA κρυπτογράφηση. Περιγραφή και εφαρμογή του αλγορίθμου RSA

RSA κρυπτογράφηση είναι ένα από τα πρώτα πρακτικά δημόσιου κλειδιού κρυπτογραφικών που χρησιμοποιείται ευρέως για την ασφαλή μετάδοση των δεδομένων. κύρια διαφορά του από ανάλογες υπηρεσίες είναι ότι το κλειδί κρυπτογράφησης είναι ανοικτή και διαφορετικό από το κλειδί αποκρυπτογράφησης, το οποίο είναι κρυμμένο μυστικό. Η τεχνολογία RSA , αυτή η ασυμμετρία αυτή βασίζεται στην πρακτική δυσκολία του factoring η αναπαραγωγή των δύο μεγάλων πρώτων αριθμών (το πρόβλημα του factoring).

Η ιστορία της δημιουργίας

RSA Το όνομα αποτελείται από τα αρχικά γράμματα των επωνύμων Rivest, Shamir και Adleman - οι επιστήμονες που περιγράφηκε για πρώτη φορά δημοσίως αυτές τις αλγόριθμους κρυπτογράφησης το 1977. Klifford Koks, ένας Άγγλος μαθηματικός, ο οποίος εργαζόταν για τις βρετανικές υπηρεσίες πληροφοριών, η πρώτη για να αναπτύξει ένα ισοδύναμο σύστημα το 1973, αλλά δεν είχε αποχαρακτηριστεί μέχρι το 1997

RSA χρήστης δημιουργεί και στη συνέχεια δημοσιεύει το δημόσιο κλειδί βασίζεται σε δύο μεγάλους πρώτους αριθμούς, μαζί με το βοηθητικό αξία. Πρώτοι αριθμοί θα πρέπει να κρατηθεί μυστικό. Ο καθένας μπορεί να χρησιμοποιήσει το δημόσιο κλειδί για να κρυπτογραφήσει ένα μήνυμα, αλλά αν είναι αρκετά μεγάλο, τότε μόνο κάποιος με γνώση των πρώτων αριθμών μπορεί να αποκωδικοποιήσει το μήνυμα. RSA αποκάλυψη κρυπτογράφησης που είναι γνωστό ως το κύριο πρόβλημα σήμερα είναι μια ανοικτή συζήτηση για το πώς ένα αξιόπιστο μηχανισμό.

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

Όταν υπήρχε ένα κρυπτογραφικό σύστημα στη σημερινή του μορφή;

Η ιδέα των ασύμμετρων κρυπτογραφικό κλειδί που δόθηκε στη Diffie και Hellman, ο οποίος δημοσίευσε την ιδέα το 1976, με την εισαγωγή ψηφιακών υπογραφών, και προσπαθεί να εφαρμόσει τη θεωρία των αριθμών. διατύπωσή τους χρησιμοποιεί ένα κοινό μυστικό κλειδί που δημιουργείται από ένα ορισμένο αριθμό ύψωση σε δύναμη modulo έναν πρώτο αριθμό. Ωστόσο, άφησε ανοικτό το θέμα της πραγματοποίησης αυτής της λειτουργίας, δεδομένου ότι οι αρχές της πρακτορείας επιχειρηματικών απαιτήσεων δεν ήταν πλήρως κατανοητή εκείνη την εποχή.

Rivest, Adi Shamir, και Adleman στο MIT έχουν κάνει αρκετές προσπάθειες όλα αυτά τα χρόνια για να δημιουργήσει μια μονόδρομη συνάρτηση που είναι δύσκολο να αποκωδικοποιήσει. Rivest και Shamir (όπως επιστήμονες πληροφορικής) έχουν προτείνει πολλές πιθανές λειτουργίες, ενώ Adleman (όπως τα μαθηματικά) για να αναζητήσετε «αδύνατα σημεία» του αλγορίθμου. Χρησιμοποίησαν πολλές προσεγγίσεις και τελικά να αναπτύξουν ένα τελικό σύστημα, τώρα γνωστό ως RSA, τον Απρίλιο του 1977.

Ηλεκτρονική υπογραφή και το δημόσιο κλειδί

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

Αυτό το κρυπτοσύστημα (RSA κρυπτογράφηση) προσφέρει το δημόσιο κλειδί, σε αντίθεση με συμμετρική. Η αρχή λειτουργίας είναι ότι τα δύο διαφορετικά κλειδιά που χρησιμοποιούνται - κλειστά (κρυπτογραφημένο) και εξωτερικούς χώρους. Το πρώτο χρησιμοποιείται για να παράγει την ψηφιακή υπογραφή και στη συνέχεια να είναι σε θέση να αποκρυπτογραφήσει το κείμενο. Δεύτερη - για την κρυπτογράφηση και την ηλεκτρονική υπογραφή.

Χρησιμοποιώντας υπογραφές για την καλύτερη κατανόηση της κρυπτογράφησης RSA, ένα παράδειγμα του οποίου μπορεί να μειωθεί ως ένα κανονικό μυστικό «κλειστή από τα αδιάκριτα βλέμματα,» το έγγραφο.

Τι είναι ο αλγόριθμος;

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

Για λόγους ασφαλείας, οι ακέραιοι που θα επιλέγονται τυχαία και είναι ίδια σε μέγεθος, αλλά διαφέρουν σε μήκος από μερικούς αριθμούς για να κάνει factoring πιο δύσκολη. Ίδιο ίδιο αριθμό μπορεί να βρεθεί αποτελεσματικά με δοκιμή στην απλότητά τους, έτσι ώστε η κρυπτογράφηση των πληροφοριών πρέπει κατ 'ανάγκη να είναι περίπλοκη.

Το δημόσιο κλειδί αποτελείται από το μέτρο και δημόσιος εκθέτης. Εσωτερική μονάδα και αποτελείται από ένα ιδιωτικό σχήμα, το οποίο θα πρέπει να κρατηθεί μυστικό.

κρυπτογράφησης RSA των αρχείων και των αδυναμιών

Ωστόσο, υπάρχουν μια σειρά από απλές hacking μηχανισμών RSA. Όταν κρυπτογράφηση με χαμηλή και μικρές τιμές των κωδικών αριθμών μπορεί να ανοίξει εύκολα, εάν η ρίζα επιλογή κρυπτοκείμενο πάνω τους ακέραιους.

Δεδομένου ότι η RSA κρυπτογράφηση είναι ένα ντετερμινιστικό αλγόριθμο (δηλαδή, δεν έχει τυχαία συνιστώσα), ένας εισβολέας μπορεί να ξεκινήσει με επιτυχία το επιλεγμένο κείμενο ανοιχτή επίθεση εναντίον της κρυπτοσύστημα με την κρυπτογράφηση πιθανό plaintexts κάτω από το δημόσιο κλειδί και τους ελέγχους για το αν είναι ίσες κρυπτοκείμενο. Σημασιολογικά ασφαλές κρυπτογραφικό σύστημα καλείται σε περίπτωση που ένας εισβολέας δεν μπορεί να γίνει διάκριση μεταξύ των δύο κρυπτογράφησης από την άλλη, ακόμα κι αν ξέρει τα σχετικά κείμενα στην εκτεταμένη μορφή. Όπως περιγράφεται παραπάνω, RSA άλλες υπηρεσίες χωρίς να γεμίσει δεν είναι σημασιολογικά ασφαλής.

Επιπλέον αλγόριθμους για την κρυπτογράφηση και προστασία

Για να αποφευχθούν τα παραπάνω προβλήματα, στην πρακτική εφαρμογή της RSA είναι συνήθως εισαχθεί σε κάποια μορφή δομημένων, τυχαιοποιημένη γέμιση πριν την κρυπτογράφηση. Αυτό εξασφαλίζει ότι το περιεχόμενο δεν εμπίπτει στο εύρος των ανασφαλής plaintexts, και ότι αυτό το μήνυμα δεν μπορεί να λυθεί με τυχαία επιλογή.

Ασφάλεια RSA κρυπτογραφικού συστήματος και κρυπτογράφηση βασίζεται σε δύο μαθηματικά προβλήματα: το πρόβλημα του factoring μεγάλων αριθμών και το πραγματικό πρόβλημα RSA. Πλήρης αποκάλυψη του ciphertext και την υπογραφή του RSA θεωρείται απαράδεκτη με βάση την υπόθεση ότι τα δύο αυτά προβλήματα δεν μπορούν να επιλυθούν συλλογικά.

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

αυτοματοποίηση

Το εργαλείο, που ονομάζεται Yafu, μπορεί να χρησιμοποιηθεί για τη βελτιστοποίηση της διαδικασίας. Αυτοματοποίηση στην YAFU είναι μια προηγμένη λειτουργία που συνδυάζει αλγόριθμοι παραγοντοποίησης στην πνευματική και προσαρμοστική μέθοδος που ελαχιστοποιεί το χρόνο για να βρει τους παράγοντες των αυθαίρετων αριθμών εισόδου. Οι περισσότερες εφαρμογές πολυνηματική αλγόριθμο που επιτρέπει Yafu πλήρη χρήση των πολυ- ή πολλών multi-core επεξεργαστές (συμπεριλαμβανομένων SNFS, SIQS και ECM). Πρώτα απ 'όλα, να ελέγχεται από το εργαλείο της γραμμής εντολών. Ο χρόνος που δαπανάται ψάχνει για τον παράγοντα Yafu κρυπτογράφηση χρησιμοποιώντας ένα συμβατικό υπολογιστή, μπορεί να μειωθεί σε δευτερόλεπτα 103,1746. Το εργαλείο επεξεργάζεται το δυαδικό χωρητικότητα 320 bit και άνω. Αυτό είναι ένα πολύ περίπλοκο λογισμικό που απαιτεί ένα ορισμένο ποσό των τεχνικών δεξιοτήτων για να εγκαταστήσετε και να ρυθμίσετε. Έτσι, RSA-κρυπτογράφησης μπορεί να είναι ευάλωτες C.

Hacking προσπάθειες τον τελευταίο καιρό

Το 2009, Bendzhamin Mudi χρησιμοποιώντας RSA-512 bit κλειδί εργαζόταν για την αποκρυπτογράφηση kriptoteksta 73 ημέρες, χρησιμοποιώντας μόνο γνωστό λογισμικό (GGNFS) και το μέσο της επιφάνειας εργασίας (dual-core Athlon64 στα 1900 MHz). Όπως φαίνεται από την εμπειρία, απαιτείται ελαφρά μικρότερη από 5 GB του δίσκου και περίπου 2.5 Gb μνήμη για τη διαδικασία της «κοσκίνισμα».

Από το 2010, ο μεγαλύτερος αριθμός ήταν συνυπολογίζονται RSA 768 bits μακρύ (232 δεκαδικά ψηφία, ή RSA-768). δημοσιοποίηση του διήρκεσε δύο χρόνια με αρκετές εκατοντάδες υπολογιστές ταυτόχρονα.

Στην πράξη, τα κλειδιά RSA είναι μακράς - τυπικά από 1024 για να 4096 bits. Ορισμένοι ειδικοί πιστεύουν ότι τα πλήκτρα 1024-bit μπορεί να γίνει αναξιόπιστη στο εγγύς μέλλον ή και περισσότερο μπορεί να είναι ραγισμένα πολύ καλά χρηματοδοτούμενο από εισβολείς. Ωστόσο, λίγοι θα υποστήριζαν ότι τα κλειδιά 4096-bit μπορεί επίσης να γνωστοποιούνται στο εγγύς μέλλον.

προοπτικές

Ως εκ τούτου, κατά κανόνα, θεωρείται ότι RSA είναι ασφαλές αν οι αριθμοί είναι αρκετά μεγάλο. Εάν ο αριθμός βάση των 300 bits ή μικρότερη, και το κρυπτογράφημα ψηφιακή υπογραφή μπορεί να αναλυθεί μέσα σε λίγες ώρες σε έναν προσωπικό υπολογιστή, χρησιμοποιώντας λογισμικό που διατίθεται ήδη στο δημόσιο τομέα. Ένα κλειδί μήκους 512 bits, όπως φαίνεται, μπορεί να ανοίξει ήδη από το 1999, με τη χρήση του μερικές εκατοντάδες υπολογιστές. Σήμερα είναι δυνατόν μέσα σε λίγες εβδομάδες χρησιμοποιεί διαθέσιμη στο κοινό του υλικού. Έτσι, είναι πιθανό ότι σε buduschembudet εύκολα αποκαλύπτονται RSA-κρυπτογραφημένο στα δάχτυλα, και το σύστημα θα γίνει απελπιστικά ξεπερασμένη.

Επισήμως, το 2003, τέθηκε υπό αμφισβήτηση την ασφάλεια των κλειδιών 1024-bit. Επί του παρόντος, συνιστάται να έχουν ελάχιστο μήκος 2048 bits.