Προτείνουν μια μέθοδο για την αποκρυπτογράφηση των κλειδιών RSA-2048
Μια ομάδα από ερευνητές από διάφορα επιστημονικά κέντρα και πανεπιστήμια Κινέζικα πρότειναn έναν νέο τρόπο βελτιστοποίησηςr τη διαδικασία παραγοντοποίησης βασικών παραμέτρων RSA σε κβαντικούς υπολογιστές.
Σύμφωνα με τους ερευνητές, η μέθοδος που ανέπτυξαν επιτρέπει τη χρήση ενός κβαντικού υπολογιστή με 372 qubits για την αποκρυπτογράφηση των κλειδιών RSA-2048. Συγκριτικά, ο IBM Osprey, ο πιο ισχυρός κβαντικός επεξεργαστής που έχει κατασκευαστεί αυτή τη στιγμή, περιέχει 433 qubits και μέχρι το 2026 η IBM σχεδιάζει να κατασκευάσει ένα σύστημα Kookaburra με 4000 qubits.
Αξίζει να το αναφέρουμε η μέθοδος είναι ακόμα μόνο θεωρητική, δεν έχει δοκιμαστεί στην πράξη και προκαλεί σκεπτικισμό σε ορισμένους κρυπτογράφους.
Η κρυπτογράφηση RSA βασίζεται στο modulo της λειτουργίας εκθέσεως σε μεγάλο αριθμό. Το δημόσιο κλειδί περιέχει το συντελεστή και το βαθμό. Η ενότητα σχηματίζεται με βάση δύο τυχαίους πρώτους αριθμούς που μόνο ο κάτοχος του ιδιωτικού κλειδιού γνωρίζει. Οι κβαντικοί υπολογιστές καθιστούν δυνατή την αποτελεσματική επίλυση του προβλήματος της αποσύνθεσης ενός αριθμού σε πρώτους παράγοντες, οι οποίοι μπορούν να χρησιμοποιηθούν για τη σύνθεση ενός ιδιωτικού κλειδιού από ένα δημόσιο.
Μέχρι τώρα πιστευόταν ότι, δεδομένης της τρέχουσας εξέλιξης των κβαντικών υπολογιστών, Τα κλειδιά RSA με μέγεθος 2048 bit δεν μπορούν να σπάσουν για μεγάλο χρονικό διάστημα, δεδομένου ότι χρησιμοποιεί τον κλασικό αλγόριθμο Shor, ένας κβαντικός υπολογιστής με εκατομμύρια qubits απαιτεί πολύ χρόνο για να συνυπολογίσει ένα κλειδί RSA 2048 bit.
Η μέθοδος που προτείνεται από Κινέζους ερευνητές θέτει υπό αμφισβήτηση αυτή την υπόθεση. και, εάν επιβεβαιωθεί, καθιστά δυνατή τη διάσπαση των κλειδιών RSA-2048 όχι σε συστήματα του απώτερου μέλλοντος, αλλά σε ήδη υπάρχοντες κβαντικούς υπολογιστές.
Η μέθοδος βασίζεται στον αλγόριθμο ταχείας παραγοντοποίησης Schnorr. προτάθηκε το 2021, το οποίο επιτρέπει τη δραστική μείωση του αριθμού των επεμβάσεων κατά την επιλογή σε συμβατικούς υπολογιστές. Ωστόσο, στην πράξη, ο αλγόριθμος αποδείχθηκε ότι ήταν ελάχιστα χρήσιμος για το σπάσιμο πραγματικών κλειδιών, καθώς λειτούργησε μόνο για κλειδιά RSA με μικρές τιμές modulo (ένας ακέραιος αριθμός που πρέπει να αποσυντεθεί σε πρώτους αριθμούς). Ο αλγόριθμος βρέθηκε ανεπαρκής για την παραγοντοποίηση μεγάλων αριθμών. Κινέζοι ερευνητές ισχυρίζονται ότι με τη βοήθεια κβαντικών μεθόδων κατάφεραν να παρακάμψουν τον περιορισμό του αλγορίθμου του Schnorr.
Σκεπτικισμός από κάποιους κρυπτογράφους οφείλεται στο γεγονός που καταδεικνύει το άρθρο των Κινέζων ερευνητών εφαρμόζοντας τη μέθοδό σας μόνο σε μικρούς αριθμούς, περίπου την ίδια σειρά για την οποία λειτουργεί ο αλγόριθμος του Schnorr. Παρά τους ισχυρισμούς ότι το όριο μεγέθους έχει ξεπεραστεί, δεν έχουν δοθεί ακόμη αποδείξεις ή λεπτομέρειες. Στην πράξη, η μέθοδος αποδεικνύεται ότι συνυπολογίζει ακέραιους αριθμούς 48 bit χρησιμοποιώντας έναν κβαντικό υπολογιστή 10 qubit.
Ο αλγόριθμος του Shor έχει αμφισβητήσει σοβαρά την ασφάλεια των πληροφοριών που βασίζονται σε κρυπτοσυστήματα δημόσιου κλειδιού. Ωστόσο, για να σπάσει το ευρέως χρησιμοποιούμενο σχήμα RSA-2048 απαιτούνται εκατομμύρια φυσικά qubits, κάτι που υπερβαίνει κατά πολύ τις τρέχουσες τεχνικές δυνατότητες. Εδώ, αναφέρουμε έναν καθολικό κβαντικό αλγόριθμο για παραγοντοποίηση ακεραίων συνδυάζοντας την κλασική μείωση πλέγματος με έναν αλγόριθμο κβαντικής ασαφούς βελτιστοποίησης (QAOA).
Ο αριθμός των qubits που απαιτούνται είναι O(logN/loglogN), ο οποίος είναι υπογραμμικός στο μήκος του ακέραιου bit N, καθιστώντας τον τον αλγόριθμο παραγοντοποίησης που εξοικονομεί περισσότερο qubit μέχρι σήμερα. Επιδεικνύουμε τον αλγόριθμο πειραματικά παραγοντοποιώντας ακέραιους αριθμούς έως και 48 bit με 10 υπεραγώγιμα qubit, τον μεγαλύτερο ακέραιο παράγοντα σε μια κβαντική συσκευή. Υπολογίζουμε ότι χρειάζεται ένα κβαντικό κύκλωμα με 372 φυσικά qubits και βάθος χιλιάδων για την πρόκληση του RSA-2048 χρησιμοποιώντας τον αλγόριθμό μας. Η μελέτη μας δείχνει μεγάλη υπόσχεση να επιταχύνει την εφαρμογή των σημερινών θορυβωδών κβαντικών υπολογιστών και ανοίγει το δρόμο για την παραγοντοποίηση μεγάλων ακεραίων ρεαλιστικής κρυπτογραφικής σημασίας.
Αναφέρεται ότι η υπόθεση ότι 372 φυσικά qubits θα είναι αρκετά για να παραγοντοποιήσουν ένα κλειδί RSA-2048 είναι θεωρητική, επομένως είναι πολύ πιθανό η κβαντική μέθοδος που βασίζεται στον αλγόριθμο του Schnorr να έχει τα ίδια προβλήματα κλιμάκωσης και να μην λειτουργεί κατά την παραγοντοποίηση αριθμών. big .
Εάν το πρόβλημα με την κλιμάκωση λυθεί πραγματικά, τότε η ασφάλεια των κρυπταλγορίθμων που βασίζονται στην πολυπλοκότητα της παραγοντοποίησης μεγάλων πρώτων αριθμών θα υπονομευθεί όχι μακροπρόθεσμα, όπως αναμενόταν, αλλά ήδη σήμερα.
Τέλος, αν ενδιαφέρεστε να μάθετε περισσότερα σχετικά, μπορείτε να συμβουλευτείτε τις λεπτομέρειες στο τον ακόλουθο σύνδεσμο.