Κρυπτογράφηση Rsa. Ένα παράδειγμα του αλγόριθμου κρυπτογράφησης rsa. EDS και δημόσιο κλειδί
Στο δεύτερο μέρος, θα δούμε τον δημοφιλή αλγόριθμο RSA, όπου χρησιμοποιείται ένα δημόσιο κλειδί για κρυπτογράφηση. Αλλά πρώτα θέλω να σας προειδοποιήσω ξανά. Ο κωδικός που παρέχεται σε αυτό το άρθρο είναι μόνο για ενημερωτικούς σκοπούς. Η κρυπτογραφία είναι ένα πολύ τεράστιο και πολύπλοκο πεδίο, και για να μην έχετε προβλήματα, δεν συνιστώ την κρυπτογράφηση πληροφοριών χρησιμοποιώντας τη τέχνη μου.
Στο δεύτερο μέρος, θα δούμε τον δημοφιλή αλγόριθμο RSA, όπου χρησιμοποιείται ένα δημόσιο κλειδί για κρυπτογράφηση. Αλλά πρώτα θέλω να σας προειδοποιήσω ξανά. Ο κωδικός που παρέχεται σε αυτό το άρθρο είναι μόνο για ενημερωτικούς σκοπούς. Η κρυπτογραφία είναι μια πολύ μεγάλη και πολύπλοκη περιοχή, και για να μην έχετε προβλήματα, δεν συνιστώ την κρυπτογράφηση πληροφοριών χρησιμοποιώντας την τέχνη μου.
Αλγόριθμος RSA
Κρυπτογράφηση δημόσιου κλειδιού
Η κρυπτογράφηση δημόσιου κλειδιού χρησιμοποιείται παντού. Εάν έχετε πληρώσει ποτέ για κάτι διαδικτυακά, έχετε ήδη χρησιμοποιήσει αυτήν τη μέθοδο (ελπίζω!). Αμέσως τίθεται το ερώτημα πώς λειτουργεί αυτή η προστασία. Εάν εισάγω τον αριθμό της πιστωτικής μου κάρτας για να αγοράσω κάτι, γιατί δεν μπορεί κανείς άλλος εκτός από τον παραλήπτη να δει αυτές τις πληροφορίες; Θα σας δώσω μια μεταφορά. Για να ανοίξετε το χρηματοκιβώτιο, χρειάζεστε ένα κλειδί (ή ένα σφυρί, αλλά ευτυχώς τα χρηματοκιβώτια και οι κλειδαριές προστατεύονται από τέτοιου είδους πράγματα). Στην κρυπτογράφηση με χρήση δημόσιου κλειδιού, συμβαίνει το ίδιο. Δείχνεις την κλειδαριά για να τη δουν όλοι, αλλά μόνο λίγοι εκλεκτοί έχουν το κλειδί αυτής της κλειδαριάς και είναι σχεδόν αδύνατο να ανοίξεις την πόρτα με άλλες μεθόδους.
Ο RSA είναι ένας από τους αλγόριθμους που υλοποιούν το παραπάνω σχήμα. Επιπλέον, μπορούμε να χρησιμοποιήσουμε αυτόν τον αλγόριθμο για να επαληθεύσουμε την αυθεντικότητα της ταυτότητάς μας. Εάν στείλετε ένα κρυπτογραφημένο μήνυμα σε κάποιον χρησιμοποιώντας το ιδιωτικό σας κλειδί, ο παραλήπτης μπορεί να χρησιμοποιήσει το δημόσιο κλειδί σας για να αποκρυπτογραφήσει το μήνυμά σας. Αυτή η τεχνολογία σάς επιτρέπει να υπογράφετε μηνύματα και έτσι να επιβεβαιώνετε την αυθεντικότητα του αποστολέα.
Πρόγραμμα επίδειξης βασισμένο στον αλγόριθμο RSA
Το σχήμα Rivest-Shamir-Adleman (RSA) είναι επί του παρόντος το μόνο ευρέως αποδεκτό σχήμα κρυπτογράφησης δημόσιου κλειδιού στην πράξη.
Το σχήμα RSA είναι ένας μπλοκ κρυπτογράφησης στον οποίο τόσο το απλό κείμενο όσο και το κρυπτογραφημένο κείμενο είναι ακέραιοι αριθμοί από το 0 έως το Π- 1 για κάποιους Π.
Το απλό κείμενο είναι κρυπτογραφημένο σε μπλοκ, καθένα από τα οποία περιέχει μια δυαδική τιμή μικρότερη από κάποιο δεδομένο αριθμό Π.Αυτό σημαίνει ότι το μήκος του μπλοκ δεν πρέπει να υπερβαίνει το log2(“). Στην πράξη, το μήκος του μπλοκ επιλέγεται ίσο με 2 κκομμάτια όπου 2k Το σχήμα που αναπτύχθηκε από τους Rivest, Shamir και Adleman βασίζεται σε εκφράσεις δύναμης. Η κρυπτογράφηση και η αποκρυπτογράφηση για το μπλοκ απλού κειμένου M και το μπλοκ κρυπτογραφημένου κειμένου C μπορούν να αναπαρασταθούν ως οι ακόλουθοι τύποι:
Τόσο ο αποστολέας όσο και ο παραλήπτης πρέπει να γνωρίζουν την τιμή Π.Ο αποστολέας γνωρίζει το νόημα μι,και μόνο ο δέκτης ξέρει την αξία ρε.Έτσι, αυτό το σχήμα είναι ένας αλγόριθμος κρυπτογράφησης δημόσιου κλειδιού KU= (e, p),και ιδιωτικό κλειδί KR = (d, p).
Για να χρησιμοποιηθεί αυτός ο αλγόριθμος για κρυπτογράφηση δημόσιου κλειδιού, πρέπει να πληρούνται οι ακόλουθες απαιτήσεις:
Πρέπει να υπάρχουν αξίες ε, δΚαι Π,τι M ed = M(mod Π)για όλα τα M n.
Θα πρέπει να είναι σχετικά εύκολο να υπολογιστεί η IVT και Από c1για όλες τις τιμές του M p.
Πρέπει να είναι σχεδόν αδύνατο να προσδιοριστεί ρεδιαθέσιμος της σ.
Θα αναλύσουμε πρώτα την πρώτη απαίτηση και θα εξετάσουμε τις υπόλοιπες αργότερα. Είναι απαραίτητο να βρεθεί μια σχέση της φόρμας
Εδώ, το συμπέρασμα από το θεώρημα του Euler ταιριάζει απόλυτα: για δύο τέτοιους πρώτους αριθμούς RΚαι qκαι τέτοιοι δύο ακέραιοι αριθμοί Πιτ,τι n=pqn0 και έναν αυθαίρετο ακέραιο προς τηνισχύουν οι ακόλουθες σχέσεις:
όπου φ(n) είναι η συνάρτηση Euler της οποίας η τιμή είναι ίση με τον αριθμό των θετικών ακεραίων μικρότερων από Πκαι coprime με Π.
Στην περίπτωση του απλού RΚαι qέχουμε f (pq) - (σελ - 1 )(q -ένας). Επομένως, η απαιτούμενη αναλογία λαμβάνεται υπό την προϋπόθεση
Αυτό ισοδυναμεί με τις ακόλουθες σχέσεις:
εκείνοι. της δείναι αμοιβαία αντίστροφα modulo φ(n). Σημειώστε ότι, σύμφωνα με τους κανόνες της αριθμητικής στις τάξεις υπολειμμάτων, αυτό μπορεί να συμβεί μόνο όταν ρε(και ως εκ τούτου μι)είναι συμπρώτος με το φ(u). Σε ισοδύναμο συμβολισμό (f(/7), δ)=.
Τώρα έχουμε τα πάντα για να αντιπροσωπεύσουμε το σχήμα RSA. Τα εξαρτήματα του κυκλώματος είναι:
RΚαι q- δύο πρώτοι αριθμοί (μυστικοί, επιλεγμένοι).
p-pq(ανοιχτό, υπολογισμένο)
τέτοιος μι, αυτό (f(i), μι)= 1,1 e
ρε = e l(mod f(/?)) (μυστικό, υπολογισμένο).
Το ιδιωτικό κλειδί αποτελείται από (d,n),και ανοιχτό από (ε, ρ).Ας υποθέσουμε ότι ο χρήστης Α έχει δημοσιεύσει το δημόσιο κλειδί του και τώρα ο χρήστης Β πρόκειται να του στείλει ένα μήνυμα M.
Στη συνέχεια, ο χρήστης Β υπολογίζει το κρυπτογραφημένο μήνυμα
Έχοντας λάβει αυτό το κρυπτογραφημένο κείμενο, ο χρήστης Α το αποκρυπτογραφεί με υπολογισμό 
Είναι λογικό να δώσουμε εδώ τη λογική για αυτόν τον αλγόριθμο. Επιλέχθηκαν της δτέτοια που
Έτσι, μοιάζει kc>(n)+.Αλλά από τη συνέπεια του θεωρήματος του Euler, για δύο τέτοιους πρώτους αριθμούς RΚαι quακέραιοι αριθμοί n = pqnΜ ότι O οι σχέσεις εκπληρώνονται
Να γιατί 
Τώρα έχουμε
Ο Πίνακας 10.1 συνοψίζει τον αλγόριθμο RSA και στο Σχ. Το 10.1 δείχνει ένα παράδειγμα εφαρμογής του. Σε αυτό το παράδειγμα, τα κλειδιά υπολογίζονται ως εξής:
- 1. Επιλέγονται δύο πρώτοι αριθμοί: p-7 wq- 17.
- 2. Υπολογίστηκε p = pq= 7 x 17=119.
- 3. Υπολογίστε τη f (n) - (p -) (q - 1) = 96.
- 4. Επιλέξιμο μι, συμπριμς με φ (Π)= 96 και λιγότερο από f(i); σε αυτή την περίπτωση = 5.
- 5. Αυτό ορίζεται ρε,τι de= 1 (mod 96) και δ 96. Η αντίστοιχη τιμή θα ήταν d= 77, επειδή 77 x 5 = 385 = 4 x 96 + 1.
- 6. Το αποτέλεσμα είναι ένα δημόσιο κλειδί KU= (5, 119) και ένα ιδιωτικό κλειδί KR = (77, 119).
Αυτό το παράδειγμα δείχνει τη χρήση αυτών των κλειδιών με την είσοδο απλού κειμένου M = 19. Για κρυπτογράφηση, το 19 αυξάνεται στην πέμπτη ισχύ, με αποτέλεσμα 2.476.099. Διαιρώντας με το 119 προκύπτει ένα υπόλοιπο 66. Επομένως, 19 119) και έτσι το Το κρυπτογραφημένο κείμενο θα είναι 66. Μετά την αποκρυπτογράφηση, αποδεικνύεται ότι 
Ρύζι. 10.1.
Πίνακας 10.1
Η κρυπτογράφηση RSA είναι ένα από τα πρώτα πρακτικά κρυπτοσυστήματα δημόσιου κλειδιού που χρησιμοποιείται ευρέως για ασφαλή μετάδοση δεδομένων. Η κύρια διαφορά του από παρόμοιες υπηρεσίες είναι ότι το κλειδί κρυπτογράφησης είναι δημόσιο και διαφέρει από το κλειδί αποκρυπτογράφησης, το οποίο διατηρείται μυστικό. Στην τεχνολογία, το RSA βασίζεται στην πρακτική δυσκολία της παραγοντοποίησης αναπαραγωγής δύο μεγάλων πρώτων (το πρόβλημα της παραγοντοποίησης).
Ιστορία της δημιουργίας
Το όνομα RSA προέρχεται από τα αρχικά γράμματα των ονομάτων Rivest, Shamir και Adleman, των επιστημόνων που περιέγραψαν για πρώτη φορά δημόσια τα επώνυμα το 1977. Ο Κλίφορντ Κοξ, ένας Άγγλος μαθηματικός που εργαζόταν για τις βρετανικές υπηρεσίες πληροφοριών, ανέπτυξε για πρώτη φορά ένα αντίστοιχο σύστημα το 1973, αλλά αποχαρακτηρίστηκε μέχρι το 1997.
Ο χρήστης RSA δημιουργεί και στη συνέχεια δημοσιεύει ένα δημόσιο κλειδί που βασίζεται σε δύο μεγάλους πρώτους αριθμούς μαζί με μια βοηθητική τιμή. πρέπει να κρατηθεί μυστικό. Οποιοσδήποτε μπορεί να χρησιμοποιήσει το δημόσιο κλειδί για να κρυπτογραφήσει ένα μήνυμα, αλλά αν είναι αρκετά μεγάλο, τότε μόνο κάποιος που γνωρίζει τους πρώτους αριθμούς μπορεί να αποκωδικοποιήσει το μήνυμα. Η αποκάλυψη της κρυπτογράφησης RSA είναι γνωστό ότι είναι ένα σημαντικό πρόβλημα: σήμερα υπάρχει μια ανοιχτή συζήτηση σχετικά με το πόσο αξιόπιστος είναι αυτός ο μηχανισμός.
Ο RSA είναι ένας σχετικά αργός αλγόριθμος, γι' αυτό και δεν χρησιμοποιείται ευρέως για τον άμεσο χρήστη. Η πιο κοινή χρήση αυτής της μεθόδου είναι η μετάδοση σε κρυπτογραφημένη μορφή των δημόσιων κλειδιών για ένα συμμετρικό κλειδί κρυπτογράφησης, το οποίο με τη σειρά του μπορεί να εκτελέσει μαζικές λειτουργίες κρυπτογράφησης και αποκρυπτογράφησης με πολύ υψηλότερη ταχύτητα.
Πότε εμφανίστηκε το κρυπτοσύστημα στη σύγχρονη μορφή του;
Η ιδέα ενός ασύμμετρου κρυπτοσυστήματος κλειδιού αποδίδεται στους Diffie και Hellman, οι οποίοι δημοσίευσαν την ιδέα το 1976, εισάγοντας ψηφιακές υπογραφές και προσπαθώντας να εφαρμόσουν τη θεωρία αριθμών. Η διατύπωσή τους χρησιμοποιεί ένα κοινό μυστικό που δημιουργείται από την εκτίμηση κάποιου αριθμού modulo ενός πρώτου αριθμού. Ωστόσο, άφησαν ανοιχτό το πρόβλημα της εφαρμογής αυτής της δυνατότητας, καθώς οι αρχές του factoring δεν ήταν καλά κατανοητές τότε.
Οι Rivest, Adi Shamir και Adleman στο MIT έκαναν αρκετές προσπάθειες κατά τη διάρκεια ενός έτους να δημιουργήσουν μια μονόδρομη συνάρτηση που είναι δύσκολο να αποκωδικοποιηθεί. Οι Rivest και Shamir (ως επιστήμονες υπολογιστών) πρότειναν πολλά πιθανά χαρακτηριστικά, ενώ ο Adleman (ως μαθηματικός) έψαξε για «αδύνατα σημεία» στον αλγόριθμο. Πήραν πολλές προσεγγίσεις και τελικά ανέπτυξαν το τελικό σύστημα τον Απρίλιο του 1977, σήμερα γνωστό ως RSA.
EDS και δημόσιο κλειδί
Η ηλεκτρονική ψηφιακή υπογραφή ή EDS είναι αναπόσπαστο μέρος των ηλεκτρονικών εγγράφων. Σχηματίζεται με κάποια κρυπτογραφική αλλαγή στα δεδομένα. Χρησιμοποιώντας αυτό το χαρακτηριστικό, είναι δυνατό να ελεγχθεί η ακεραιότητα του εγγράφου, η εμπιστευτικότητά του, καθώς και να προσδιοριστεί σε ποιον ανήκει. Στην πραγματικότητα, αυτή είναι μια εναλλακτική λύση στη συνήθη τυπική υπογραφή.
Αυτό το κρυπτοσύστημα (κρυπτογράφηση RSA) προσφέρει ένα δημόσιο κλειδί, το οποίο είναι διαφορετικό από τα συμμετρικά. Η αρχή της λειτουργίας του είναι ότι χρησιμοποιούνται δύο διαφορετικά κλειδιά - ένα ιδιωτικό (κρυπτογραφημένο) καθώς και ένα δημόσιο. Το πρώτο χρησιμοποιείται για τη δημιουργία ενός EDS και στη συνέχεια για την αποκρυπτογράφηση του κειμένου. Το δεύτερο είναι για την πραγματική κρυπτογράφηση και επαλήθευση της ψηφιακής υπογραφής.
Η χρήση μιας υπογραφής επιτρέπει την καλύτερη κατανόηση της κρυπτογράφησης RSA, ένα παράδειγμα της οποίας μπορεί να δοθεί ως ένα κανονικό μυστικό έγγραφο "κρυμμένο από τα αδιάκριτα μάτια".
Ποια είναι η ουσία του αλγορίθμου;
Ο αλγόριθμος RSA αποτελείται από τέσσερα βήματα: δημιουργία κλειδιού, διανομή κλειδιού, κρυπτογράφηση και αποκρυπτογράφηση. Όπως ήδη αναφέρθηκε, η κρυπτογράφηση RSA περιλαμβάνει ένα δημόσιο κλειδί και ένα ιδιωτικό κλειδί. Το Open μπορεί να είναι γνωστό σε όλους και χρησιμοποιείται για την κρυπτογράφηση μηνυμάτων. Η ουσία του έγκειται στο γεγονός ότι τα μηνύματα που είναι κρυπτογραφημένα με το δημόσιο κλειδί μπορούν να αποκρυπτογραφηθούν μόνο σε μια ορισμένη χρονική περίοδο χρησιμοποιώντας το μυστικό κλειδί.
Για λόγους ασφαλείας, οι ακέραιοι αριθμοί θα πρέπει να επιλέγονται τυχαία και να είναι ίδιοι σε μέγεθος, αλλά να διαφέρουν ως προς το μήκος κατά μερικά ψηφία για να κάνουν πιο δύσκολη την παραγοντοποίηση. Οι ίδιοι αριθμοί μπορούν να βρεθούν αποτελεσματικά χρησιμοποιώντας ένα τεστ για την απλότητά τους, επομένως η κρυπτογράφηση των πληροφοριών πρέπει απαραίτητα να γίνει πιο περίπλοκη.
Το δημόσιο κλειδί αποτελείται από μια ενότητα και έναν δημόσιο εκθέτη. Το Private αποτελείται από μια ενότητα και μια ιδιωτική ένδειξη, η οποία πρέπει να παραμείνει μυστική.
Κρυπτογράφηση αρχείων RSA και αδυναμίες
Ωστόσο, υπάρχει ένας αριθμός μηχανισμών για να σπάσει το απλό RSA. Με κρυπτογράφηση χαμηλής αξίας και μικρούς αριθμούς, ο κρυπτογράφηση μπορεί εύκολα να σπάσει επιλέγοντας τη ρίζα του κρυπτογραφημένου κειμένου από ακέραιους αριθμούς.
Επειδή η κρυπτογράφηση RSA είναι ένας ντετερμινιστικός αλγόριθμος (δηλαδή, δεν έχει τυχαίο στοιχείο), ένας εισβολέας μπορεί να ξεκινήσει επιτυχώς μια επιλεγμένη επίθεση απλού κειμένου σε ένα κρυπτοσύστημα κρυπτογραφώντας πιθανά απλά κείμενα με το δημόσιο κλειδί και ελέγχοντας εάν είναι ίσα με το κρυπτογραφημένο κείμενο. Ένα κρυπτοσύστημα ονομάζεται σημασιολογικά ασφαλές εάν ένας εισβολέας δεν μπορεί να διακρίνει δύο κρυπτογραφήσεις μεταξύ τους, ακόμα κι αν γνωρίζει τα αντίστοιχα κείμενα στην εκτεταμένη μορφή. Όπως περιγράφεται παραπάνω, το RSA χωρίς την προσθήκη άλλων υπηρεσιών δεν είναι σημασιολογικά ασφαλές.
Πρόσθετοι αλγόριθμοι κρυπτογράφησης και προστασίας
Για να αποφευχθούν τα παραπάνω προβλήματα, οι πρακτικές υλοποιήσεις του RSA συνήθως ενσωματώνουν κάποια μορφή δομημένης, τυχαιοποιημένης συμπλήρωσης πριν από την κρυπτογράφηση. Αυτό διασφαλίζει ότι το περιεχόμενο δεν εμπίπτει στο εύρος των μη ασφαλών απλών κειμένων και ότι το μήνυμα δεν μπορεί να εντοπιστεί με τυχαία επιλογή.
Η ασφάλεια του κρυπτοσυστήματος RSA και η κρυπτογράφηση των πληροφοριών βασίζονται σε δύο μαθηματικά προβλήματα: το πρόβλημα της παραγοντοποίησης μεγάλων αριθμών και το ίδιο το πρόβλημα RSA. Η πλήρης αποκάλυψη κρυπτογραφημένου κειμένου και ψηφιακής υπογραφής στο RSA θεωρείται απαράδεκτη με την υπόθεση ότι και τα δύο αυτά προβλήματα δεν μπορούν να επιλυθούν μαζί.
Ωστόσο, λόγω της δυνατότητας ανάκτησης πρωταρχικών παραγόντων, ένας εισβολέας μπορεί να υπολογίσει τη μυστική ένδειξη από το δημόσιο κλειδί και στη συνέχεια να αποκρυπτογραφήσει το κείμενο χρησιμοποιώντας την τυπική διαδικασία. Παρόλο που δεν έχει βρεθεί καμία υπάρχουσα μέθοδος παραγοντοποίησης μεγάλων αριθμών σε έναν κλασικό υπολογιστή σήμερα, δεν έχει αποδειχθεί ότι δεν υπάρχει.
Αυτοματοποίηση
Ένα εργαλείο που ονομάζεται Yafu μπορεί να χρησιμοποιηθεί για τον εξορθολογισμό αυτής της διαδικασίας. Ο αυτοματισμός στο YAFU είναι ένα χαρακτηριστικό αιχμής που συνδυάζει αλγόριθμους παραγοντοποίησης σε μια έξυπνη και προσαρμοστική μεθοδολογία που ελαχιστοποιεί τον χρόνο εύρεσης παραγόντων αυθαίρετων αριθμών εισαγωγής. Οι περισσότερες υλοποιήσεις του αλγορίθμου είναι πολλαπλών νημάτων, επιτρέποντας στον Yafu να εκμεταλλευτεί πλήρως τα πολλαπλά ή πολλά (συμπεριλαμβανομένων των SNFS, SIQS και ECM). Πρώτα απ 'όλα, είναι ένα διαχειριζόμενο εργαλείο γραμμής εντολών. Ο χρόνος που αφιερώνεται στην αναζήτηση ενός παράγοντα κρυπτογράφησης χρησιμοποιώντας το Yafu σε έναν κανονικό υπολογιστή μπορεί να μειωθεί στα 103,1746 δευτερόλεπτα. Το εργαλείο παράγει επεξεργασία με χωρητικότητα 320 bit ή περισσότερο. Είναι ένα πολύ περίπλοκο λογισμικό που απαιτεί ορισμένες τεχνικές δεξιότητες για εγκατάσταση και διαμόρφωση. Επομένως, η κρυπτογράφηση RSA C μπορεί να είναι ευάλωτη.
Απόπειρες hacking στη σύγχρονη εποχή
Το 2009, ο Benjamin Moody, χρησιμοποιώντας ένα κλειδί RSA-512 bit, εργάστηκε στην αποκρυπτογράφηση κρυπτοκειμένου για 73 ημέρες χρησιμοποιώντας μόνο γνωστό λογισμικό (GGNFS) και έναν μέσο επιτραπέζιο υπολογιστή (διπύρηνο Athlon64 στα 1900 MHz). Όπως έδειξε αυτή η εμπειρία, χρειάστηκαν κάτι λιγότερο από 5 gigabyte δίσκου και περίπου 2,5 gigabyte μνήμης RAM για τη διαδικασία «κοσκίνισμα».
Από το 2010, ο μεγαλύτερος παραγοντοποιημένος αριθμός RSA είχε μήκος 768 bit (232 δεκαδικά ψηφία ή RSA-768). Η αποκάλυψή του διήρκεσε δύο χρόνια σε αρκετές εκατοντάδες υπολογιστές ταυτόχρονα.
Στην πράξη, τα κλειδιά RSA είναι μεγαλύτερα, συνήθως μεταξύ 1024 και 4096 bit. Ορισμένοι ειδικοί πιστεύουν ότι τα κλειδιά 1024-bit μπορεί να καταστούν αναξιόπιστα στο εγγύς μέλλον ή ακόμη και να σπάσουν από έναν καλά χρηματοδοτούμενο εισβολέα ήδη. Ωστόσο, λίγοι θα υποστήριζαν ότι τα κλειδιά 4096-bit θα μπορούσαν επίσης να εκτεθούν στο άμεσο μέλλον.
προοπτικές
Επομένως, το RSA θεωρείται γενικά ότι είναι ασφαλές εάν οι αριθμοί είναι αρκετά μεγάλοι. Εάν ο βασικός αριθμός είναι 300 bit ή μικρότερος, το κρυπτογραφημένο κείμενο και η ψηφιακή υπογραφή μπορούν να αποσυντεθούν μέσα σε λίγες ώρες σε έναν προσωπικό υπολογιστή χρησιμοποιώντας λογισμικό που είναι ήδη ελεύθερα διαθέσιμο. Τα κλειδιά 512-bit έχουν αποδειχθεί ότι μπορούν να σπάσουν ήδη από το 1999 χρησιμοποιώντας αρκετές εκατοντάδες υπολογιστές. Αυτές τις μέρες, αυτό είναι δυνατό μέσα σε λίγες εβδομάδες χρησιμοποιώντας συνήθως διαθέσιμο υλικό. Έτσι, είναι πολύ πιθανό η κρυπτογράφηση RSA στα δάχτυλα να αποκαλυφθεί εύκολα στο μέλλον και το σύστημα να γίνει απελπιστικά ξεπερασμένο.
Επίσημα το 2003, αμφισβητήθηκε η ασφάλεια των κλειδιών 1024-bit. Προς το παρόν, συνιστάται να έχει μήκος τουλάχιστον 2048 bit.
RSAχρησιμοποιεί δύο τύπους κλειδιών - e και d , όπου το e είναι δημόσιο και το d είναι μυστικό. Ας υποθέσουμε ότι το P είναι το απλό κείμενο και το C είναι το κρυπτογραφημένο κείμενο. Η Alice χρησιμοποιεί C = P e mod n για να δημιουργήσει το κρυπτοκείμενο C από το απλό κείμενο P . Ο Bob χρησιμοποιεί P = C d mod n για να εξαγάγει το κείμενο προέλευσης (αρχείο) που παρέχεται από την Alice. Ένας πολύ μεγάλος αριθμός μονάδων n δημιουργείται χρησιμοποιώντας τη διαδικασία δημιουργίας κλειδιού, την οποία θα συζητήσουμε αργότερα.
Η εκθετική μονάδα χρησιμοποιείται για κρυπτογράφηση και αποκρυπτογράφηση. Όπως έχουμε ήδη συζητήσει στις Διαλέξεις 12-13, όταν χρησιμοποιείται ο γρήγορος αλγόριθμος, ο συντελεστής εκθέσεως είναι εφικτός σε πολυωνυμικό χρόνο. Ωστόσο, η εύρεση του λογάριθμου modulo είναι εξίσου δύσκολη με την παραγοντοποίηση ενός αριθμητικού modulo. Δεν υπάρχει πολυωνυμικός αλγόριθμος χρόνου για αυτό. Αυτό σημαίνει ότι η Alice μπορεί να κρυπτογραφήσει το μήνυμα με το δημόσιο κλειδί (e) σε πολυωνυμικό χρόνο. Ο Bob μπορεί επίσης να το αποκρυπτογραφήσει σε πολυωνυμικό χρόνο (επειδή ξέρει το d ). Αλλά η Εύα δεν μπορεί να αποκρυπτογραφήσει αυτό το μήνυμα γιατί θα έπρεπε να υπολογίσει την ε-η ρίζα του C χρησιμοποιώντας αρθρωτή αριθμητική. Το σχήμα 14.5 δείχνει την ιδέα πίσω από το RSA.
Ρύζι. 14.5.
Με άλλα λόγια, η Αλίκη χρησιμοποιεί μονόδρομη λειτουργία(modulo εκθέσεως) με ένα κενό γνωστό μόνο στον Bob. Η Εύα δεν γνωρίζει το κενό, επομένως δεν μπορεί να αποκρυπτογραφήσει το μήνυμα. Αν κάποιος βρει ποτέ έναν πολυωνυμικό αλγόριθμο για τον e-ο συντελεστή ρίζας του n , τότε το modulo n εκθέσεως δεν θα είναι πλέον μονόδρομη συνάρτηση.
Διαδικασία
Το σχήμα 14.6 δείχνει τη γενική ιδέα της διαδικασίας που χρησιμοποιείται στο RSA.
Το RSA χρησιμοποιεί modulo εκθέσεως για κρυπτογράφηση/αποκρυπτογράφηση. Για να επιτεθεί στο ιδιωτικό κείμενο, η Εύα πρέπει να υπολογίσει 
Ρύζι. 14.6.
Δύο αλγεβρικές δομές
Το RSA χρησιμοποιεί δύο αλγεβρικές δομές: δακτύλιο και ομάδα.
Δακτύλιοι κρυπτογράφησης/αποκρυπτογράφησης. Η κρυπτογράφηση και η αποκρυπτογράφηση γίνονται με χρήση ενός δακτυλίου αντικατάστασης 
με δύο αριθμητικές πράξεις: πρόσθεση και πολλαπλασιασμό. Στο RSA, αυτός ο δακτύλιος είναι δημόσιος επειδή το modulo n είναι δημόσιο. Οποιοσδήποτε μπορεί να στείλει ένα μήνυμα στον Bob χρησιμοποιώντας αυτό το δαχτυλίδι κρυπτογράφησης.
Ομάδες Βασικών Γενεών. Το RSA χρησιμοποιεί την πολλαπλασιαστική ομάδα 
για τη δημιουργία κλειδιών. Η ομάδα υποστηρίζει μόνο πολλαπλασιασμό και διαίρεση (πολλαπλασιαστική αναστροφή), που απαιτούνται για τη δημιουργία δημόσιων και ιδιωτικών κλειδιών. Αυτή η ομάδα πρέπει να είναι κρυφή επειδή η ενότητα της είναι μυστική. Θα δούμε ότι αν η Εύα βρει αυτήν την ενότητα, μπορεί εύκολα να επιτεθεί στο κρυπτογραφικό σύστημα.
Το RSA χρησιμοποιεί δύο αλγεβρικές δομές: ανοιχτός δακτύλιος R =< Z n , +, x > και μυστική ομάδα G =< Z (n)* , x >.
Δημιουργία κλειδιών
Ο Bob χρησιμοποιεί τα βήματα που φαίνονται στον Αλγόριθμο 14.2 για να δημιουργήσει τα δημόσια και ιδιωτικά κλειδιά του. Αφού δημιουργήσει τα κλειδιά, ο Bob δηλώνει την πλειάδα (e, n) ως δημόσιο κλειδί πρόσβασης: ο Bob αποθηκεύει το d ως το ιδιωτικό του κλειδί. Ο Bob μπορεί να αρνηθεί τα p, q και ; δεν μπορούν να αλλάξουν το ιδιωτικό του κλειδί χωρίς να αλλάξουν τη μονάδα. Για ασφάλεια, το συνιστώμενο μέγεθος για κάθε απλό p ή q είναι 512 bit (σχεδόν 154 δεκαδικά ψηφία). Αυτό καθορίζει το μέγεθος της μονάδας, το n είναι 1024 bit (309 ψηφία).
Στο RSA, μια πλειάδα (e, n) είναι ένα δημόσιο κλειδί πρόσβασης. ακέραιος d - μυστικό κλειδί.
Κρυπτογράφηση
Οποιοσδήποτε μπορεί να στείλει ένα μήνυμα στον Bob χρησιμοποιώντας το δημόσιο κλειδί πρόσβασής του. Η κρυπτογράφηση σε RSA μπορεί να γίνει χρησιμοποιώντας έναν αλγόριθμο πολυωνυμικού χρόνου, όπως φαίνεται στον Αλγόριθμο 14.3. Ο αλγόριθμος γρήγορης εκθέσεως συζητήθηκε στις διαλέξεις 12-13. Το μέγεθος του κειμένου πηγής πρέπει να είναι μικρότερο από n ; εάν το μέγεθος του αρχικού κειμένου είναι μεγαλύτερο, τότε θα πρέπει να χωριστεί σε μπλοκ.
Κάτω από την περικοπή, περιγράφονται παραδείγματα επιλογής "κακών" παραμέτρων κρυπτογράφησης RSA.
«Θα πρέπει να τονιστεί ότι πρέπει να δοθεί προσοχή στην επιλογή του συντελεστή RSA (αριθμοί n) για κάθε ανταποκριτή του δικτύου. Από αυτή την άποψη, μπορούν να ειπωθούν τα ακόλουθα. Ο αναγνώστης μπορεί να το επαληθεύσει ανεξάρτητα, γνωρίζοντας μία από τις τρεις ποσότητες Π, qή φ(n), μπορεί κανείς εύκολα να βρει το μυστικό κλειδί RSA…”.
Ας προσθέσουμε αυτό το κείμενο. Εάν η επιλογή της μονάδας κρυπτογράφησης RSA είναι ανεπιτυχής, όπως γίνεται στο παρακάτω παράδειγμα εκμάθησης, είναι δυνατή η αποκρυπτογράφηση του κειμένου χωρίς την παρουσία μυστικού κλειδιού, π.χ. χωρίς να γνωρίζουμε καμία από τις τρεις ονομαζόμενες ποσότητες.
Για να γίνει αυτό, αρκεί να έχετε το κρυπτογραφημένο κείμενο που δίνεται από τη μονάδα κρυπτογράφησης n, δημόσιο κλειδί μικρυπτογράφηση και εκτελέστε μόλις τρία βήματα μιας επίθεσης "ανάγνωσης χωρίς κλειδί". Μετά το τέταρτο βήμα επίθεσης, διαπιστώνεται ότι το κείμενο πηγής ελήφθη στο προηγούμενο βήμα, μπορεί να διαβαστεί. Ας δείξουμε πόσο εύκολο είναι να γίνει.
Αρχικά, ας δώσουμε το ίδιο το παράδειγμα από τις σελ. 313-315 από το αναφερόμενο εγχειρίδιο.
Παράδειγμα
Κρυπτογράφησησύντομο πρωτότυπο μήνυμα κειμένου: RSA.Ο παραλήπτης ορίζει την κρυπτογράφηση με τα χαρακτηριστικά n=pq=527, όπου p=17, q=31Και φ(n)=(р –1)(q – 1)=480. Ως δημόσιο κλειδί μιεπιλέγεται ένας αριθμός που είναι συμπρώτης με φ(n), e=7. Για αυτόν τον αριθμό, χρησιμοποιώντας τον εκτεταμένο αλγόριθμο Ευκλείδη, βρίσκονται ακέραιοι αριθμοί uΚαι v, ικανοποιώντας τη σχέση e∙u+φ(n)∙v=1:
480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.
Στο βαθμό που –137≡343(mod480), έπειτα d=343.
Εξέταση: 7∙343=2401≡1(mod480).
Ένα μήνυμα κειμένου παρουσιάζεται ως μια ακολουθία αριθμών που περιέχονται στο διάστημα . Για αυτήν την επιστολή R, μικρόΚαι ΕΝΑκωδικοποιημένοι ως δυαδικοί αριθμοί 5-bit. Οι αύξοντες αριθμοί αυτών των γραμμάτων στο αγγλικό αλφάβητο χρησιμοποιούνται στη δυαδική τους αναπαράσταση:
R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.
Επειτα RSA=(100101001100001) 2. Η διάσπαση του κειμένου σε μπλοκ περιορισμένου μήκους δίνει μια αναπαράσταση δύο μπλοκ: RSA=(100101001), (100001)=(M 1 =297, M 2 =33).
Διαδοχικά κρυπτογραφημένα μπλοκ κειμένου προέλευσης M 1 \u003d 297, M 2 \u003d 33:
y 1 \u003d E k (M 1) \u003d M 1 e ≡297 7 (mod527) \u003d 474.
Εδώ χρησιμοποιήσαμε:
297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 \u003d E k (M 2) \u003d M 2 e ≡33 7 (mod527) \u003d 407.
Το κρυπτογραφημένο κείμενο, όπως και το αρχικό, λαμβάνεται με τη μορφή δύο μπλοκ: y 1 =474; y 2 =407.
Αποκρυπτογράφησηφαίνεται να είναι μια ακολουθία ενεργειών D k (y i)=(y i) d =(y i) 343 (mod 527), i=1,2.
Υπολογισμοί εκπτώσεων ρεείναι πιο βολικό να πραγματοποιηθεί, αντιπροσωπεύοντας προκαταρκτικά τον εκθέτη ως το άθροισμα των δυνάμεων ενός αριθμού 2 , και συγκεκριμένα: 343=256+64+16+4+2+1 .
Χρησιμοποιώντας αυτήν την αναπαράσταση εκθέτη d=343, παίρνουμε:
474 2 ≡174 (mod527),
474 4 ≡237 (mod527),
474 8 ≡307 (mod527),
474 16 ≡443 (mod527),
474 32 ≡205 (mod527),
474 64 ≡392 (mod527),
474 128 ≡307 (mod527),
474 256 ≡443 (mod527),
και τελικά 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.
Η τιμή υπολογίζεται με τον ίδιο τρόπο 407 343 (mod527)=33.
Η μετάβαση στην κυριολεκτική αναπαράσταση του αποκρυπτογραφημένου μηνύματος δίνει: RSA.
Αφού εξετάσουμε το παράδειγμα, το εγχειρίδιο εξετάζει την ισχύ του συστήματος RSA. Η ανάγκη για προσοχή στην επιλογή του συντελεστή κρυπτογράφησης RSA (αριθμοί n) για κάθε ανταποκριτή του δικτύου. Επισημαίνεται ότι είναι απαράδεκτο να αγνοούνται οι απαιτήσεις για τα επιλεγμένα χαρακτηριστικά του συστήματος κρυπτογράφησης. Μεταξύ αυτών των απαιτήσεων, δυστυχώς, δεν αναφέρεται αυτή της οποίας η παραβίαση απεικονίζεται στο συγκεκριμένο παράδειγμα.
Επίθεση στον κρυπτογράφηση RSA
Εξετάστε ένα παράδειγμα επίθεσης στον κρυπτογράφηση RSA. Ας χρησιμοποιήσουμε τα δεδομένα του παραδείγματος που δίνεται στις σελίδες 313-315 στο σχολικό βιβλίο «Βασικές αρχές της Κρυπτογραφίας» του Α.Π. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, Μόσχα. "Helios ARV", 2001.Η αποτυχία (απαράδεκτο) των επιλεγμένων παραμέτρων συστήματος σε αυτό το παράδειγμα φαίνεται εύκολα από υπολογισμούς που υλοποιούν την επίθεση της ανάγνωσης χωρίς κλειδί του κειμένου προέλευσης. Η ουσία μιας τέτοιας επίθεσης είναι η εξής. Το δημόσιο κλειδί του κωδικού RSA δίνεται ( e=7, n=527) και κρυπτογραφημένο κείμενο. Στο παράδειγμα, το κρυπτογραφημένο κείμενο αντιπροσωπεύεται από δύο μπλοκ
y \u003d (y 1 \u003d 474, y 2 \u003d 407).
Κάθε κρυπτογραφημένο μπλοκ δέχεται επίθεση μεμονωμένα, πρώτα κάνουμε επίθεση y 1 =474, αφού το αποκρυπτογραφήσουμε, επιτιθέμεθα σε άλλο μπλοκ y 2 =407.
Στη συνέχεια σχηματίζεται με επαναλαμβανόμενη κρυπτογράφηση με αποθήκευση των αποτελεσμάτων δύο διαδοχικών βημάτων του αλγόριθμου επίθεσης και χρησιμοποιώντας το δημόσιο κλειδί μια ακολουθία αριθμητικών τιμών Εγώ, y 1 = yδιαθέσιμο κρυπτογραφημένο κείμενο.
Στον αλγόριθμο επίθεσης κρυπτογραφημένου κειμένου, προσδιορίζεται ο ακόλουθος αριθμός βήματος ι, για το οποίο y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. Από την τελευταία σχέση βλέπουμε ότι κατά την άνοδο σε μια δύναμη μιαξίες (y i e j–1 (mod n))αποδεικνύεται το αρχικό shifortext y i = y 1.
Αλλά αυτό σημαίνει ότι το απλό κείμενο κρυπτογραφήθηκε σε αυτό το βήμα. Με άμεσους υπολογισμούς (υπάρχουν πολύ λίγοι από αυτούς) χρησιμοποιώντας την αριθμομηχανή στην οθόνη, βρίσκουμε αυτήν την τιμή ι, στο οποίο ο κύκλος κρυπτογράφησης τελειώνει με την τιμή y 1από το οποίο ξεκίνησε ο κύκλος.
Επίθεση στο πρώτο μπλοκ y 1 =474κρυπτογραφημένο κείμενο.
Βήμα 1: 474 7 (mod527)=382;
Βήμα 2: 382 7 (mod527)=423;
Βήμα 3: 423 7 (mod527)=297;
Βήμα 4: Αυτό το βήμα κρυπτογραφεί το κείμενο προέλευσης που έχει ήδη βρεθεί, αλλά πρέπει να εκτελεστεί επειδή ο εισβολέας δεν γνωρίζει το κείμενο προέλευσης. Το σημάδι της ολοκλήρωσης της επίθεσης είναι η σύμπτωση της αρχικής τιμής του κρυπτογραφημένου κειμένου ( 474
) και το αποτέλεσμα του 4ου βήματος κρυπτογράφησης. Αυτό ακριβώς το είδος της σύμπτωσης συμβαίνει.
297 7 (mod527)=474έλαβε το αρχικό (πρώτο) μπλοκ κρυπτογραφημένου κειμένου. Η επίθεση στο πρώτο μπλοκ ολοκληρώθηκε με επιτυχία y 1 =474. Το προηγούμενο αποτέλεσμα του βήματος 3 είναι απλό κείμενο M 1 \u003d 297.
n=527 r=297 modulo n=527. Είναι γραμμένο έτσι y i \u003d y 1 \u003d 297. Σχηματίζουμε υπολείμματα ισχύος
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.
Επίθεση στο δεύτερο μπλοκ y 2 =407κρυπτογραφημένο κείμενο.
Βήμα 1: 407 7 (mod527)=16;
Βήμα 2: 16 7 (mod527)=101;
Βήμα 3: 101 7 (mod527)=33;
Βήμα 4: 33 7 (mod527)=407.
Και πάλι, στο τρίτο βήμα, λαμβάνεται το μπλοκ κειμένου προέλευσης ( M 2 \u003d 33), αλλά ο επιτιθέμενος δεν το γνωρίζει αυτό και εκτελεί το επόμενο (τέταρτο βήμα), το αποτέλεσμα του οποίου είναι ( 407 ) ταιριάζει με το αρχικό κρυπτογραφημένο κείμενο y 2 =407.
Ουσιαστικά στον δακτύλιο των υπολειμμάτων modulo n=527εφάρμοσε έναν σύντομο κύκλο επεξεργασίας της έκπτωσης r=33 modulo n=527. Είναι γραμμένο έτσι y i \u003d y 2 \u003d 33.
Σχηματίζουμε υπολείμματα ισχύος ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.
Το αποτέλεσμα της επίθεσης (αρχικό κείμενο M 1 \u003d 297, M 2 \u003d 33) λαμβάνεται με τριπλή κρυπτογράφηση του δεδομένου κρυπτογραφημένου κειμένου. Είναι δύσκολο να φανταστεί κανείς μεγαλύτερη επιτυχία για το επιθετικό κρυπτογραφημένο κείμενο.
Συνεχίζοντας τη συζήτηση σχετικά με την επιλογή της ενότητας και άλλες παραμέτρους κρυπτογράφησης, μπορούμε να προσθέσουμε ότι η ενότητα κρυπτογράφησης ( n=527) ορισμένα κείμενα πηγής δεν επιτρέπουν καθόλου την κρυπτογράφηση. Σε αυτή την περίπτωση, η επιλογή της τιμής του δημόσιου κλειδιού e δεν παίζει μεγάλο ρόλο. Υπάρχουν τιμές απλού κειμένου που δεν μπορούν να κρυπτογραφηθούν καθόλου με τον επιλεγμένο κρυπτογράφηση με το modulo n=527.
Κανένα από τα δεδομένα e δεν μπορεί να κρυπτογραφήσει τα απλά κείμενα που αντιπροσωπεύονται με αριθμούς
187
, 341
, 154
Και 373
.
Παράδειγμα (αδυναμία κρυπτογράφησης των τιμών ορισμένων κειμένων πηγής)
Αφήστε τα κείμενα πηγής να αντιπροσωπεύονται από τέσσερα μπλοκ y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373). Εκθέτης μιτο δημόσιο κλειδί του κρυπτογράφησης μπορεί να είναι οποιοσδήποτε σχετικά πρώτος αριθμός με τη συνάρτηση Euler φ(n)=φ(527)=480. Ωστόσο, για την υπό εξέταση περίπτωση, το δημόσιο κλειδί μιμπορεί να οριστεί αυθαίρετα. Πράγματι, ας e=2, 4, 7, 9, 17, 111έπειτα:154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.
Ένα απλό συμπέρασμα προκύπτει από το υπό εξέταση παράδειγμα. Πράγματι, η επιλογή των παραμέτρων της διαδικασίας κρυπτογράφησης πρέπει να προσεγγιστεί πολύ προσεκτικά και θα πρέπει να πραγματοποιηθεί μια ενδελεχής προκαταρκτική ανάλυση τέτοιων παραμέτρων. Το πώς να γίνει αυτό είναι ένα ξεχωριστό θέμα και δεν εξετάζεται στο πλαίσιο αυτής της εργασίας.