Η κρυπτογράφηση RSA σπάει εύκολα (μερικές φορές)
1 min read
RSA encryption cracked
Είναι αποδεκτό ότι πλέον ένα μεγάλο κομμάτι της παγκόσμιας οικονομίας βασίζεται στην κρυπτογράφηση δημοσίου κλειδιού public key cryptography.
Είναι επίσης αποδεκτό ότι με τα κλειδιά μεγάλου εύρους δεν είναι εφικτό να “σπάσει” κάτι που κωδικοποιείται με αυτόν τον τρόπο…. αλλά μπορεί να μην είναι και έτσι.
Ερευνητές πριν από μερικά χρόνια δημοσίευσαν ένα έγγραφο , στο οποίο εμφανίζεται να έχουνε σπάσει έναν μεγάλο αριθμό κλειδιών σε πολύ μικρό χρονικό διάστημα. Πρακτικά αυτό δεν γίνεται, σε οποιοδήποτε κλειδί, όπως θα δείτε παρακάτω, αλλά εδώ πρέπει να δώσετε προσοχή, χρησιμοποίησαν έναν αλγόριθμο “μη περιγράψιμο” ο οποίος έσπασε τους κώδικες σε πολύ μικρό χρονικό διάστημα σε έναν μονοπύρηνο υπολογιστή!
Αυτό βέβαια κέντρισε το ενδιαφέρον του [William Kuszmul] που μετά από ενδελεχή έρευνα μπόρεσε να βρει μερικά έγγραφα που αποκάλυπταν τους εν λόγω αλγόριθμους. Μπορείτε να διαβάσετε την ανάλυσή του και να αποφασίσετε πόσο άσχημα αυτό εκθέτει τους κοινούς αλγόριθμους.
Η βάση για την κρυπτογραφηση δημόσιου κλειδιού είναι ότι πολλαπλασιάζετε δύο μεγάλους πρώτους αριθμούς για να διαμορφώσετε το τελικό προϊόν και να το δημοσιεύσετε. Eίναι αρκετά επίπονο να υπολογιστεί η εύρεση παραγόντων πρώτων μεγάλων αριθμών και σε αυτό επίκειται και ασφάλεια, επειδή είναι δύσκολο να βρεθούν εκείνοι οι πρώτοι αριθμοί που επιλέγονται τυχαία.
Ωστόσο, η τυχαία επιλογή οδηγεί σε μια ασυνήθιστη επίθεση. Τα δημόσια κλειδιά, από τη φύση τους, είναι διαθέσιμα σε όλο το Διαδίκτυο. Τα περισσότερα από αυτά δημιουργούνται με τον ίδιο αλγόριθμο και έτσι η παραγωγή τυχαίων αριθμών δεν είναι “πραγματικά εντελώς τυχαία”.
Αυτό σημαίνει ότι ορισμένα κλειδιά μοιράζονται παράγοντες πρώτων αριθμών και η εύρεση ενός κοινού παράγοντα μεταξύ δύο αριθμών δεν είναι τόσο δύσκολη.
Στην πραγματικότητα, αυτή είναι και η καρδιά του προβλήματος. Η παραγοντοποίηση ενός 232ψήφιου αριθμού χρειαζόταν περίπου “1.500 χρόνια υπολογιστικού χρόνου“.
Η εύρεση κοινών παραγόντων μεταξύ δύο αριθμών είναι ωστόσο πολύ ευκολότερη. Το αρχικό ερευνητικό έγγραφο ανέφερε ότι βρέθηκαν κοινοί παράγοντες για 36 τρισεκατομμύρια ζεύγη κλειδιών μέσα σε λίγες ώρες, πόλυ σύντομο χρονικό διάστημα από ότι περίμενε ο [William].
Πριν ανησυχήσετε πολύ, σας αναφέρουμε ότι οι ερευνητές εξέτασαν 6,2 εκατομμύρια κλειδιά και κατάφεραν να σπάσουν όχι λιγότερα από 13.000. Χμμμ ένα κενό ασφαλείας?? …, εκτός κι αν είστε ένας από τους 13.000, φυσικά :).
Ωστόσο, ολόκληρη η ανάρτηση υπογραμμίζει δύο πράγματα: πρώτον, ο ρυθμός με τον οποίο οι αλγόριθμοι γίνονται πιο αποτελεσματικοι και πιο αποδοτικοί είναι συνήθως πιο γρήγορος από τη δημιουργία ταχύτερων υπολογιστών και, δεύτερον, ποτέ δεν ξέρετε πότε η κρυπτογράφηση σας θα καταστεί άνευ αξίας από έναν καλύτερο αλγόριθμο.
Πάντως πιστεύεται ότι η κβαντική υπολογιστική θα αλλάξει σημαντικά το τι θα πρέπει να κάνετε για να είστε ασφαλείς. Έχουμε δει σε προηγούμενα άρθρα τις αδυναμίες που εγκυμονεί η υλοποίηση ενός αλγορίθμου.
kirilos2000
πηγή https://hackaday.com/2019/01/16/rsa-encryption-cracked-easily-sometimes/
About The Author
