Εισαγωγή
Το 1994, ο επιστήμονας υπολογιστών Peter Shor ανακάλυψαν ότι αν εφευρίσκονταν ποτέ οι κβαντικοί υπολογιστές, θα αποδεκάτιζαν μεγάλο μέρος της υποδομής που χρησιμοποιείται για την προστασία των πληροφοριών που κοινοποιούνται στο διαδίκτυο. Αυτή η τρομακτική πιθανότητα έκανε τους ερευνητές να προσπαθήσουν να δημιουργήσουν νέα, «μετα-κβαντικά» σχήματα κρυπτογράφησης, για να σώσουν όσες περισσότερες πληροφορίες μπορούσαν από το να πέσουν στα χέρια κβαντικών χάκερ.
Νωρίτερα φέτος, το Εθνικό Ινστιτούτο Προτύπων και Τεχνολογίας αποκάλυψε τέσσερις φιναλίστ στην αναζήτησή της για ένα μετα-κβαντικό πρότυπο κρυπτογραφίας. Τρία από αυτά χρησιμοποιούν «κρυπτογραφία πλέγματος» — ένα σχέδιο εμπνευσμένο από πλέγματα, κανονικές διατάξεις κουκκίδων στο διάστημα.
Η κρυπτογραφία πλέγματος και άλλες μετα-κβαντικές δυνατότητες διαφέρουν από τα τρέχοντα πρότυπα με κρίσιμους τρόπους. Αλλά όλα βασίζονται στη μαθηματική ασυμμετρία. Η ασφάλεια πολλών σημερινών συστημάτων κρυπτογραφίας βασίζεται στον πολλαπλασιασμό και την παραγοντοποίηση: Κάθε υπολογιστής μπορεί να πολλαπλασιάσει γρήγορα δύο αριθμούς, αλλά θα μπορούσαν να χρειαστούν αιώνες για να συνυπολογιστεί ένας κρυπτογραφικά μεγάλος αριθμός στα κύρια συστατικά του. Αυτή η ασυμμετρία καθιστά τα μυστικά εύκολο να κωδικοποιηθούν αλλά δύσκολο να αποκωδικοποιηθούν.
Αυτό που αποκάλυψε ο Shor στον αλγόριθμό του το 1994 ήταν ότι μια ιδιορρυθμία του factoring το καθιστά ευάλωτο σε επιθέσεις από κβαντικούς υπολογιστές. «Είναι ένα πολύ συγκεκριμένο, ιδιαίτερο πράγμα που μπορεί να κάνει ο κβαντικός υπολογιστής», είπε Κάθριν Στάνγκ, μαθηματικός στο Πανεπιστήμιο του Κολοράντο, Boulder. Έτσι, μετά τον Shor, οι κρυπτογράφοι είχαν μια νέα δουλειά: Βρείτε ένα νέο σύνολο μαθηματικών πράξεων που είναι εύκολο να γίνουν αλλά σχεδόν αδύνατο να αναιρεθούν.
Η κρυπτογραφία πλέγματος είναι μια από τις πιο επιτυχημένες προσπάθειες μέχρι στιγμής. Αρχικά αναπτύχθηκε τη δεκαετία του 1990, βασίζεται στη δυσκολία της αντίστροφης μηχανικής αθροίσματος βαθμών.
Εδώ είναι ένας τρόπος για να περιγράψετε την κρυπτογραφία πλέγματος: Φανταστείτε ότι ο φίλος σας έχει ένα πλέγμα, το οποίο είναι απλώς ένα σωρό σημεία σε ένα κανονικό, επαναλαμβανόμενο μοτίβο σε όλο το επίπεδο. Ο φίλος σας θέλει να ονομάσετε 10 από αυτά τα σημεία. Αλλά είναι δύσκολος, και δεν θα τραβήξει ολόκληρο το πλέγμα. Αντίθετα, παραθέτει μόνο δύο σημεία — το πρώτο με ένα x-τιμή 101 και α y-τιμή 19, η άλλη με συντεταγμένες [235, 44].
Ευτυχώς, είναι εύκολο να βρεις νέα σημεία σε ένα πλέγμα, γιατί όταν προσθέτεις και αφαιρείς οποιαδήποτε δύο σημεία σε ένα πλέγμα, λαμβάνεις ένα τρίτο σημείο στο ίδιο πλέγμα. Έτσι, το μόνο που έχετε να κάνετε είναι να αθροίσετε τους πόντους που σας έδωσε ο φίλος σας ή να τους πολλαπλασιάσετε με ακέραιους αριθμούς και στη συνέχεια να τους προσθέσετε ή κάποιον συνδυασμό των δύο. Κάντε αυτό με οκτώ διαφορετικούς τρόπους και θα μπορέσετε να απαντήσετε στην ερώτηση του φίλου σας.
Αλλά ο φίλος σου εξακολουθεί να μην είναι ικανοποιημένος. Σας δίνει τα ίδια δύο σημεία εκκίνησης και μετά σας ρωτά αν το σημείο [2, 1] βρίσκεται στο ίδιο πλέγμα. Για να απαντήσετε σωστά σε αυτήν την ερώτηση, πρέπει να βρείτε τον συνδυασμό των [101, 19] και [235, 44] που παράγει το [2, 1]. Αυτό το πρόβλημα είναι πολύ πιο δύσκολο από το πρώτο και πιθανότατα θα καταλήξετε απλώς να μαντεύετε και να ελέγχετε για να λάβετε την απάντηση.* Αυτή η ασυμμετρία είναι που βρίσκεται κάτω από την κρυπτογραφία πλέγματος.
Εάν θέλετε πραγματικά να χρησιμοποιήσετε κρυπτογραφία πλέγματος για να μοιραστείτε πληροφορίες, θα κάνετε τα εξής. Φανταστείτε ότι ένας φίλος (ο καλύτερος!) θέλει να σας στείλει ένα ασφαλές μήνυμα. Ξεκινάτε με ένα τετράγωνο πλέγμα αριθμών. Ας πούμε ότι έχει δύο σειρές και δύο στήλες και μοιάζει με αυτό:
Τώρα βρίσκετε ένα ιδιωτικό «κλειδί» που μόνο εσείς γνωρίζετε. Σε αυτό το παράδειγμα, ας υποθέσουμε ότι το ιδιωτικό κλειδί σας είναι μόνο δύο μυστικοί αριθμοί: 3 και −2. Πολλαπλασιάζετε τους αριθμούς της πρώτης στήλης με 3 και τους αριθμούς της δεύτερης στήλης με −2. Προσθέστε τα αποτελέσματα σε κάθε σειρά για να λάβετε μια τρίτη στήλη με δύο καταχωρήσεις.
Κολλήστε τη νέα στήλη στο τέλος του πλέγματος σας. Αυτό το νέο πλέγμα τριών στηλών είναι το δημόσιο κλειδί σας. Μοιραστείτε το ελεύθερα!
(Ένα πραγματικό σενάριο θα είναι λίγο πιο περίπλοκο. Για να εμποδίσετε τους χάκερ να αποκωδικοποιήσουν το ιδιωτικό σας κλειδί, πρέπει να προσθέσετε λίγο τυχαίο θόρυβο στην τελευταία στήλη. Αλλά εδώ θα αγνοήσουμε αυτό το βήμα για λόγους απλότητας. )
Τώρα ο φίλος σας θα χρησιμοποιήσει το δημόσιο κλειδί για να σας στείλει ένα μήνυμα. Σκέφτεται δύο δικούς της μυστικούς αριθμούς: το 2 και το 0. Πολλαπλασιάζει τους αριθμούς της πρώτης σειράς επί 2 και τους αριθμούς της δεύτερης σειράς με το 0. Στη συνέχεια, αθροίζει τα αποτελέσματα σε κάθε στήλη για να πάρει μια τρίτη σειρά.
Τώρα προσαρτά τη νέα σειρά στο κάτω μέρος του πλέγματος και σας τη στέλνει πίσω. (Και πάλι, σε ένα πραγματικό σύστημα, θα έπρεπε να προσθέσει λίγο θόρυβο στη σειρά της.)
Τώρα θα διαβάσετε το μήνυμα. Για να το κάνετε αυτό, ελέγξτε αν η τελευταία σειρά του φίλου σας είναι σωστή. Εφαρμόστε το δικό σας ιδιωτικό κλειδί στις δύο πρώτες καταχωρήσεις της σειράς της. Το αποτέλεσμα πρέπει να ταιριάζει με την τελευταία καταχώριση.
Ο φίλος σας μπορεί επίσης να επιλέξει να σας στείλει μια σειρά με λάθος αριθμό στην τελευταία στήλη. Ξέρει ότι αυτός ο αριθμός δεν θα ταιριάζει με τους υπολογισμούς σας.
Εάν η φίλη σας στείλει μια σειρά όπου ο τελευταίος αριθμός είναι σωστός, θα το ερμηνεύσετε ως 0. Εάν στείλει μια σειρά όπου ο αριθμός είναι λάθος, θα την ερμηνεύσετε ως 1. Επομένως, η σειρά κωδικοποιεί ένα μοναδικό bit: είτε 0 είτε 1.
Σημειώστε ότι ένας εξωτερικός εισβολέας δεν θα έχει πρόσβαση ούτε στο ιδιωτικό σας κλειδί ούτε στο κλειδί του φίλου σας. Χωρίς αυτά, ο επιτιθέμενος δεν θα έχει ιδέα αν ο τελικός αριθμός είναι σωστός ή όχι.
Στην πράξη, θα θέλατε να στέλνετε μηνύματα που έχουν μήκος μεγαλύτερο από ένα bit. Έτσι, τα άτομα που θέλουν να λάβουν, ας πούμε, ένα μήνυμα 100-bit θα δημιουργήσουν 100 νέες στήλες αντί για μία. Στη συνέχεια, ο αποστολέας του μηνύματος θα δημιουργήσει μια νέα σειρά, τροποποιώντας τις τελευταίες 100 καταχωρήσεις ώστε να κωδικοποιούν είτε ένα 0 είτε ένα 1 για κάθε καταχώρηση.
Εάν η κρυπτογραφία πλέγματος εφαρμοστεί πραγματικά, θα έχει αμέτρητες αποχρώσεις που δεν καλύπτονται σε αυτό το σενάριο. Για παράδειγμα, εάν θέλετε το μήνυμα να είναι πραγματικά ασφαλές από τα αδιάκριτα βλέμματα, η μήτρα πρέπει να έχει έναν αδιανόητο αριθμό καταχωρίσεων, καθιστώντας το όλο θέμα τόσο δυσκίνητο που δεν αξίζει να το χρησιμοποιήσετε. Για να το ξεπεράσουν αυτό, οι ερευνητές χρησιμοποιούν πίνακες με χρήσιμες συμμετρίες που μπορούν να μειώσουν τον αριθμό των παραμέτρων. Από εκεί και πέρα, υπάρχει μια ολόκληρη σειρά τροποποιήσεων που μπορούν να εφαρμοστούν στο ίδιο το πρόβλημα, στον τρόπο ενσωμάτωσης των σφαλμάτων και πολλά άλλα.
Φυσικά, είναι πάντα πιθανό κάποιος να βρει ένα μοιραίο ελάττωμα στην κρυπτογραφία πλέγματος, όπως έκανε ο Shor για το factoring. Δεν υπάρχει καμία διαβεβαίωση ότι ένα συγκεκριμένο κρυπτογραφικό σχήμα θα λειτουργήσει απέναντι σε οποιαδήποτε πιθανή επίθεση. Η κρυπτογραφία λειτουργεί μέχρι να σπάσει. Πράγματι, νωρίτερα αυτό το καλοκαίρι Ένα πολλά υποσχόμενο σχέδιο μετα-κβαντικής κρυπτογραφίας καταρρίφθηκε χρησιμοποιώντας όχι έναν κβαντικό υπολογιστή, αλλά έναν συνηθισμένο φορητό υπολογιστή. Για τον Stange, ολόκληρο το έργο δημιουργεί ένα άβολο παράδοξο: «Αυτό που βρίσκω τόσο εκπληκτικό σχετικά με την κρυπτογραφία είναι ότι έχουμε δημιουργήσει αυτήν την υποδομή για την ανθρώπινη φυλή με τη σταθερή πεποίθηση ότι οι ικανότητές μας ως άνθρωποι είναι περιορισμένες», είπε. «Είναι τόσο πίσω».
*: Η απάντηση, αν είστε περίεργοι, είναι 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [επιστροφή στο άρθρο]
