Οι κρυπτογράφοι αγωνίζονται για να προστατεύσουν το Διαδίκτυο από επιτιθέμενους οπλισμένους με κβαντικούς υπολογιστές
Ένας ολοκληρωμένος κβαντικός υπολογιστής απέχει ακόμη χρόνια, αν όχι δεκαετίες. Ωστόσο, οι προγραμματιστές πιστεύουν εδώ και καιρό ότι η εφαρμογή δολοφόνος θα αποκωδικοποιεί κρυπτογραφημένα μηνύματα στο Διαδίκτυο και αλλού, είτε είναι κρατικά μυστικά είτε προσωπικές πληροφορίες. Αυτή η προοπτική έχει γαλβανίσει τους κρυπτογράφους. Σε μια συνάντηση αυτή την εβδομάδα στη Σάντα Μπάρμπαρα της Καλιφόρνια, θα συζητήσουν σχεδόν δύο δωδεκάδες σχέδια για την κρυπτογράφηση μηνυμάτων με τρόπους που ακόμη και οι κβαντικοί υπολογιστές δεν μπορούν να σπάσουν.
Το εργαστήριο αποτελεί μέρος μιας ώθησης του Εθνικού Ινστιτούτου Προτύπων και Τεχνολογίας (NIST) για τη θέσπιση προτύπων για τη λεγόμενη μετακβαντική κρυπτογραφία. Η πολυετής προσπάθεια μπορεί να ακούγεται πρόωρη και λίγο παρανοϊκή, καθώς ένας τέτοιος κβαντικός υπολογιστής μπορεί να μην υπάρξει ποτέ. Αλλά οι κρυπτογράφοι λένε ότι τώρα είναι η ώρα να προετοιμαστούν, ειδικά επειδή οποιοσδήποτε θα μπορούσε να καταγράψει ευαίσθητες επικοινωνίες τώρα και να τις αποκρυπτογραφήσει αργότερα. «Αν περιμένετε μέχρι να έχουμε έναν κβαντικό υπολογιστή, είναι πολύ αργά», λέει η Tanja Lange, κρυπτογράφος στο Τεχνολογικό Πανεπιστήμιο του Αϊντχόβεν στην Ολλανδία. "Κάθε μέρα που δεν έχουμε μετακβαντική κρυπτογραφία είναι μια μέρα που διαρρέουν τα δεδομένα."
Το ηλεκτρονικό εμπόριο εκατοντάδων δισεκατομμυρίων δολαρίων βασίζεται σε δυνητικά ευάλωτα συστήματα που ονομάζονται κρυπτογραφία δημόσιου κλειδιού. Βασίζονται σε υπολογισμούς «πόρτας παγίδας», που ονομάζονται έτσι επειδή είναι πολύ πιο εύκολο να εργαστούν προς τα εμπρός παρά προς τα πίσω. Ένας δέκτης, η Alice, παρέχει ένα αριθμητικό δημόσιο κλειδί και μια συνταγή που χρησιμοποιεί ο αποστολέας, ο Bob, για να ανακατέψει ένα μήνυμα. Ένας υποκλοπής, η Εύα, δεν μπορεί εύκολα να αντιστρέψει τον υπολογισμό του Μπομπ για να ανακαλύψει το μήνυμα. Ωστόσο, η Alice έχει δημιουργήσει επίσης ένα μυστικό ιδιωτικό κλειδί, μαθηματικά συσχετισμένο με το δημόσιο, που τη βοηθά να ξεμπερδέψει το μήνυμα μέσω υπολογισμών όπως του Bob.
Για παράδειγμα, σε ένα δημοφιλές σχήμα δημόσιου κλειδιού που ονομάζεται RSA, ο Bob ανακατεύει ένα αριθμητικό μήνυμα πολλαπλασιάζοντάς το από τον εαυτό του πολλές φορές που καθορίζει η Alice. Διαιρεί το αποτέλεσμα με το δημόσιο κλειδί, έναν τεράστιο αριθμό που παράγεται πολλαπλασιάζοντας δύο πρώτους αριθμούς, και στέλνει στην Αλίκη τον υπόλοιπο. Για να ανακατασκευάσει το μήνυμα, η Αλίκη πολλαπλασιάζει το υπόλοιπο από τον εαυτό του διαφορετικές φορές - αυτός ο αριθμός είναι το ιδιωτικό της κλειδί - και διαιρείται με το δημόσιο κλειδί. Voila! Το αρχικό μήνυμα του Μπομπ εμφανίζεται στο υπόλοιπο. Είναι σαν να λέει η Αλίκη στον Μπομπ πώς να κρύψει τη ρύθμιση ενός λουκέτου στρέφοντας τον επιλογέα πολλές στροφές προς τα εμπρός, γνωρίζοντας πώς να γυρίσει τον επιλογέα πιο μπροστά για να ανακτήσει την αρχική ρύθμιση. Η Εύα μπορεί μόνο να δυσκολευτεί να καταλάβει πόσο μακριά να γυρίσει το καντράν πίσω.
Το RSA απεικονίζει επίσης την απειλή που θέτει ένας κβαντικός υπολογιστής. Αν η Εύα μπορούσε να συνυπολογίσει το δημόσιο κλειδί στους πρώτους του συστατικού, θα μπορούσε να κλέψει το ιδιωτικό κλειδί και να σπάσει τον κώδικα. Η παραγοντοποίηση μεγάλων αριθμών είναι δύσκολη για έναν κλασικό υπολογιστή, αλλά θα ήταν ευκολότερο για έναν κβαντικό υπολογιστή, όπως έδειξε ο Peter Shor, μαθηματικός στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης στο Κέιμπριτζ, το 1994. Ένας κβαντικός υπολογιστής που εκτελεί τον αλγόριθμο του Shor θα μπορούσε επίσης να νικήσει το νεότερο δημόσιο κλειδί σχημάτων επειδή υπερέχει στην εύρεση μοτίβων σε επαναλαμβανόμενες πράξεις διαίρεσης και λήψης του υπολοίπου.
Για να αντιμετωπίσουν τον κίνδυνο, οι κρυπτογράφοι αναπτύσσουν λιγότερο ευάλωτους αλγόριθμους παγίδας. Πολλοί βασίζονται σε γεωμετρικές κατασκευές που ονομάζονται πλέγματα, συστοιχίες σημείων που μοιάζουν με τα επαναλαμβανόμενα τρισδιάστατα μοτίβα ατόμων σε έναν κρύσταλλο, εκτός από το ότι έχουν εκατοντάδες ή χιλιάδες διαστάσεις. Ένα πλέγμα ορίζεται από ένα σύνολο βελών ή διανυσμάτων που μπορούν να προστεθούν σε διαφορετικούς συνδυασμούς για να δημιουργήσουν το σχέδιο. Για το ίδιο πλέγμα, η βάση μπορεί να αποτελείται από μικρά, σχεδόν κάθετα διανύσματα με τα οποία είναι εύκολο να εργαστεί κανείς ή μακριά, σχεδόν παράλληλα, που είναι πιο δύσκολο να χειριστεί κανείς.
Σε αυτά τα σχήματα, το ιδιωτικό κλειδί της Alice είναι μια απλή βάση πλέγματος και το δημόσιο κλειδί της είναι ένα ακατάστατο που ορίζει το ίδιο μοτίβο. Για να μεταφέρει κάθε κομμάτι πληροφορίας στην Αλίκη, ο Μπομπ μπορεί να της στείλει τις συντεταγμένες ενός σημείου στον πολυδιάστατο χώρο που είναι είτε κοντά σε ένα σημείο του πλέγματος για να δηλώσει μηδέν ή πιο μακριά από ένα σημείο πλέγματος για να δηλώσει ένα. Με το ακατάστατο δημόσιο κλειδί, ακόμη και ένας κβαντικός υπολογιστής δεν μπορούσε να βοηθήσει την Εύα να καταλάβει πόσο κοντά είναι το σημείο στο πλέγμα. Η Αλίκη, ωστόσο, μπορεί εύκολα να το κάνει επειδή κρατά το απλό, ιδιωτικό κλειδί. "Η κρυπτογραφία πλέγματος είναι μια πολύ ενεργή περιοχή επειδή είναι τόσο ευέλικτη", λέει η Nina Bindel, επιστήμονας υπολογιστών στο Τεχνικό Πανεπιστήμιο του Darmstadt στη Γερμανία.
Μερικοί ερευνητές ξεσκονίζουν πολύ παλαιότερους αλγόριθμους. Ας υποθέσουμε ότι θέλετε να μεταδώσετε μια σειρά από bits μέσω του Διαδικτύου, αλλά φοβάστε ότι μερικά μηδενικά και ένα ενδέχεται να αναστραφούν κατά λάθος. Μπορείτε να αποφύγετε αυτό κάνοντας μια μεγαλύτερη συμβολοσειρά με απολύσεις που μπορούν να χρησιμοποιηθούν για τη διόρθωση των σφαλμάτων. Ένας τέτοιος κωδικός διόρθωσης σφαλμάτων μπορεί να αναπαρασταθεί με ένα πλέγμα ή μήτρα μηδενικών και μονάδων, και στη δεκαετία του 1970 οι κρυπτογράφοι έδειξαν ότι μπορούν να κρυπτογραφήσουν μηνύματα.
Σε αυτόν τον τύπο σχήματος, το ιδιωτικό κλειδί της Alice είναι ένας πίνακας διόρθωσης σφαλμάτων και το δημόσιο κλειδί της είναι μια κωδικοποιημένη έκδοση του. Το μήνυμα του Bob είναι η συμβολοσειρά των bit, στα οποία εφαρμόζει τη δημόσια μήτρα για να πάρει μια διαφορετική συμβολοσειρά. Αναποδογυρίζει μερικά τυχαία κομμάτια για καλό μέτρο και στέλνει το αποτέλεσμα στην Αλίκη. Ακόμη και γνωρίζοντας την ακατάστατη μήτρα του Μπομπ, η Εύα δεν μπορεί να αναιρέσει τις κινήσεις του. Αλλά με το πιο καθαρό - που έχει σχεδιαστεί για τη διόρθωση αυτών των αναποδογυρισμένων κομματιών - η Alice μπορεί. Τα σχήματα διόρθωσης σφαλμάτων έχουν δοκιμαστεί περισσότερο από τα πλέγματα, λέει ο Lange, και μπορούν να κοιτούν προς τα κάτω την Eve ακόμα κι αν έχει κβαντικό υπολογιστή.
Οι περισσότεροι μετακβαντικοί αλγόριθμοι απαιτούν μεγαλύτερα κλειδιά ή περισσότερο χρόνο υπολογισμού από τα τρέχοντα πρότυπα. Αλλά η Simona Samardjiska, κρυπτογράφος στο Πανεπιστήμιο Radboud στο Nijmegen, στην Ολλανδία, και οι συνεργάτες της αναπτύσσουν ένα εύστροφο σχήμα μικρών κλειδιών, βασισμένο σε σύνολα τετραγωνικών εξισώσεων, που θα μπορούσαν να είναι καλύτερα προσαρμοσμένες για ψηφιακές υπογραφές—τις γρήγορες χειραψίες που ελέγχουν ταυτότητας ιστοτόπους—από για αποστολή μυστικών μηνυμάτων.
Όπως συμβαίνει με οποιοδήποτε σύστημα δημόσιου κλειδιού, δεν υπάρχει καμία απόδειξη ότι τα μετακβαντικά σχήματα δεν μπορούν να παραβιαστούν, ίσως ακόμη και με έναν συμβατικό υπολογιστή. Έτσι, αντί να αντικαθιστούν τους τρέχοντες αλγόριθμους, οι νέοι πιθανότατα θα εκτελούνται σε συνδυασμό με αυτούς, λέει ο Brian LaMacchia, κρυπτογράφος της Microsoft στο Ρέντμοντ της Ουάσιγκτον.
Το NIST θα μπορούσε να τυποποιήσει δύο ή τρεις αλγόριθμους ο καθένας για κρυπτογράφηση και ψηφιακές υπογραφές ήδη από το 2022, λέει ο Dustin Moody, μαθηματικός στο NIST στο Gaithersburg, Maryland. Το πρακτορείο θέλει επιλογές, λέει. «Αν βρεθεί κάποια νέα επίθεση που σπάει όλα τα πλέγματα, θα έχουμε ακόμα κάτι να υποστούμε». Το NIST θέτει πρότυπα για την ομοσπονδιακή κυβέρνηση, λέει ο Moody, αλλά «μεγάλο μέρος του κόσμου χρησιμοποιεί την κρυπτογράφηση που τυποποιεί το NIST». Η Cloudflare, μια εταιρεία ασφάλειας και απόδοσης Διαδικτύου στο Σαν Φρανσίσκο της Καλιφόρνια, η οποία εξυπηρετεί 20 εκατομμύρια επιχειρήσεις και άλλους πελάτες, έχει ήδη αρχίσει να πειραματίζεται με μερικούς από τους αλγόριθμους σε προγράμματα περιήγησης ιστού. Αλλά μια πλήρης μετανάστευση θα διαρκέσει χρόνια, προειδοποιεί ο Nick Sullivan, εφαρμοσμένος κρυπτογράφος στο Cloudflare.
Ο LaMacchia λέει ότι τα τελευταία 30 χρόνια έχει δει τέσσερις ή πέντε σημαντικές αλλαγές στην κρυπτογραφία, συμπεριλαμβανομένης της ώθησης πριν από μια δεκαετία να μεταβεί από το RSA σε έναν μαθηματικά σχετικό αλλά πιο ασφαλή διάδοχο. "Αυτό είναι ποιοτικά διαφορετικό. Είναι πολύ πιο περίπλοκο." Οι χρήστες της κρυπτογράφησης—δηλαδή σχεδόν όλοι—θα γνωρίζουν ότι η αλλαγή έχει πάει καλά, αν δεν την προσέξουν ποτέ.
