Κβαντικοί υπολογιστές: Το τέλος της κρυπτογραφίας;

Διαφήμιση

Η κβαντική υπολογιστική είναι μία από αυτές τις τεχνολογίες που είναι τόσο αυταρχικές που το όνομα των τηλεοπτικών χαρακτήρων την ρίχνει όταν θέλουν να ακούγονται έξυπνα.

Η κβαντική υπολογιστική ως ιδέα υπήρξε για λίγο - η θεωρητική δυνατότητα είχε αρχικά εισαχθεί από τον Γιούρι Μανίν και τον Richard Feynman το 1982. Τα τελευταία χρόνια, όμως, ο τομέας έχει τραβήξει ανησυχητικά πιο κοντά στην πρακτικότητα.

Εταιρείες όπως η Google και η Microsoft, καθώς και κυβερνητικές υπηρεσίες όπως η NSA έχουν ασχοληθεί πυρετωδώς με κβαντικούς υπολογιστές εδώ και χρόνια. Μια εταιρεία που ονομάζεται D-Wave έχει παράγει και πωλεί συσκευές που (ενώ δεν είναι κατάλληλοι υπολογιστές και μπορούν εκτελούν μόνο μερικούς αλγορίθμους) εκμεταλλεύονται τις κβαντικές ιδιότητες και είναι ένα άλλο βήμα προς την κατεύθυνση του α πλήρως Turing-πλήρης Ποια είναι η δοκιμή Turing και θα ξυλοκοπείται ποτέ;Η δοκιμή Turing έχει σκοπό να καθορίσει αν τα μηχανήματα σκέφτονται. Μήπως το πρόγραμμα Eugene Goostman πέτυχε πραγματικά τη δοκιμή του Turing, ή απλά εξαπατούσαν οι δημιουργοί; Διαβάστε περισσότερα

κβαντική μηχανή.

Δεν φαίνεται παράλογο να πούμε ότι θα μπορούσαν να προκύψουν καινοτομίες που θα επιτρέψουν την κατασκευή του πρώτου κβαντικού υπολογιστή μεγάλης κλίμακας μέσα σε μια δεκαετία.

Γιατί λοιπόν το ενδιαφέρον; Γιατί πρέπει να σας ενδιαφέρει; Οι υπολογιστές γίνονται όλο και πιο γρήγορα Τι είναι ο νόμος του Moore και τι πρέπει να κάνει μαζί σου; [Επεξηγήσεις MakeUseOf]Η κακή τύχη δεν έχει καμία σχέση με το νόμο του Moore. Αν αυτή είναι η συσχέτιση που είχατε, το συγχέετε με το νόμο του Murphy. Ωστόσο, δεν ήσουν μακριά από το νόμο του Moore και το νόμο του Murphy ... Διαβάστε περισσότερα - τι είναι τόσο ξεχωριστό για τους κβαντικούς υπολογιστές;

Για να εξηγήσουμε γιατί αυτά τα μηχανήματα είναι τόσο σημαντικά, θα πρέπει να κάνουμε ένα βήμα πίσω και να διερευνήσουμε ακριβώς ποιοι κβαντικοί υπολογιστές είναι και γιατί λειτουργούν. Για να ξεκινήσετε, ας μιλήσουμε για μια έννοια που ονομάζεται "πολυπλοκότητα χρόνου εκτέλεσης".

Τι είναι η πολυπλοκότητα εκτέλεσης;

Μια από τις μεγάλες εκπλήξεις στις πρώτες μέρες της επιστήμης των υπολογιστών ήταν η ανακάλυψη ότι αν έχετε έναν υπολογιστή που λύνει ένα πρόβλημα ένα ορισμένο μέγεθος σε ένα ορισμένο χρονικό διάστημα, ο διπλασιασμός της ταχύτητας του υπολογιστή δεν αφήνει απαραίτητα να αντιμετωπίσει προβλήματα δύο φορές περισσότερο μεγάλο.

Μερικοί αλγόριθμοι αυξάνουν το συνολικό χρόνο εκτέλεσης πολύ, πολύ γρήγορα καθώς μεγαλώνει το μέγεθος του προβλήματος - ορισμένοι αλγόριθμοι μπορούν να ολοκληρωθούν γρήγορα δεδομένης της ύπαρξης 100 σημείων δεδομένων, αλλά η συμπλήρωση του αλγορίθμου που δόθηκε σε 1000 σημεία δεδομένων θα απαιτούσε έναν υπολογιστή με το μέγεθος της Γης να τρέχει για ένα δισεκατομμύριο χρόνια. Η πολυπλοκότητα του χρόνου εκτέλεσης είναι μια τυποποίηση αυτής της ιδέας: εξετάζει την καμπύλη του πόσο γρήγορα μεγαλώνει η πολυπλοκότητα ενός προβλήματος και χρησιμοποιεί το σχήμα αυτής της καμπύλης για να ταξινομήσει τον αλγόριθμο.

Γενικά, αυτές οι κατηγορίες δυσκολίας εκφράζονται ως λειτουργίες. Ένας αλγόριθμος που γίνεται αναλογικά δυσκολότερος όταν αυξάνεται η τιμή των δεδομένων (όπως μια απλή συνάρτηση μέτρησης) είναι μια λειτουργία με πολυπλοκότητα χρόνου εκτέλεσης "n " (όπως και στο, παίρνει n μονάδες χρόνου για επεξεργασία n σημεία δεδομένων).

Εναλλακτικά, μπορεί να ονομαστεί "γραμμική", επειδή όταν το γράφετε, έχετε μια ευθεία γραμμή. Άλλες λειτουργίες μπορεί να είναι n ^ 2 ή 2 ^ n ή n! (n παράγοντα). Αυτά είναι πολυώνυμα και εκθετικά. Στις τελευταίες δύο περιπτώσεις, οι εκθετικές αναπτύσσονται τόσο γρήγορα που σε όλες σχεδόν τις περιπτώσεις δεν μπορούν να λυθούν για τίποτα εκτός από τα πολύ ασήμαντα παραδείγματα.

Περίοδος πολυπλοκότητας και κρυπτογραφία

Εάν ακούτε αυτά τα πράγματα για πρώτη φορά και ακούγεται χωρίς νόημα και αστεία, ας προσπαθήσουμε να εδραιώσουμε αυτή τη συζήτηση. Η πολυπλοκότητα του χρόνου εκτέλεσης είναι κρίσιμη για την κρυπτογραφία, η οποία βασίζεται στην πολύ πιο εύκολη αποκρυπτογράφηση για άτομα που γνωρίζουν ένα μυστικό κλειδί από ό, τι για εκείνους που δεν το κάνουν. Σε ένα ιδανικό κρυπτογραφικό σχήμα, η αποκρυπτογράφηση θα πρέπει να είναι γραμμική αν έχετε το κλειδί, και 2 ^ k (όπου k είναι ο αριθμός των bits στο κλειδί) αν δεν το κάνετε.

Με άλλα λόγια, ο καλύτερος αλγόριθμος για την αποκρυπτογράφηση του μηνύματος χωρίς το κλειδί θα έπρεπε απλώς να μαντέψει πιθανά κλειδιά, τα οποία είναι δύσκολα για κλειδιά μόνο μερικών εκατοντάδων δυαδικών ψηφίων.

Για την κρυπτογράφηση συμμετρικού κλειδιού (στην οποία τα δύο μέρη έχουν την ευκαιρία να ανταλλάξουν ένα μυστικό με ασφάλεια πριν ξεκινήσουν την επικοινωνία) αυτό είναι πολύ εύκολο. Για ασύμμετρη κρυπτογραφία, είναι πιο δύσκολο.

Η ασύμμετρη κρυπτογραφία, στην οποία τα κλειδιά κρυπτογράφησης και αποκρυπτογράφησης είναι διαφορετικά και δεν μπορούν εύκολα να υπολογιστούν μεταξύ τους, είναι μια πολύ πιο δύσκολη μαθηματική δομή για την εφαρμογή από συμμετρική κρυπτογραφία, αλλά είναι επίσης πολύ πιο ισχυρό: η ασύμμετρη κρυπτογράφηση σας επιτρέπει να έχετε ιδιωτικές συνομιλίες, γραμμές! Σας επιτρέπει επίσης να δημιουργήσετε "ψηφιακές υπογραφές" που θα σας επιτρέψουν να επαληθεύσετε από ποιον ένα μήνυμα προέρχεται και ότι δεν έχει παραβιαστεί.

Αυτά είναι ισχυρά εργαλεία και αποτελούν το θεμέλιο της σύγχρονης ιδιωτικότητας: χωρίς ασύμμετρη κρυπτογραφία, οι χρήστες ηλεκτρονικών συσκευών δεν θα είχαν καμία αξιόπιστη προστασία από τα αδιάκριτα μάτια.

Επειδή η ασύμμετρη κρυπτογραφία είναι πιο δύσκολο να κατασκευαστεί παρά συμμετρική, τα πρότυπα συστήματα κρυπτογράφησης που χρησιμοποιούνται σήμερα δεν είναι τόσο ισχυρά όπως θα μπορούσαν να είναι: το πιο συνηθισμένο πρότυπο κρυπτογράφησης, RSA, μπορεί να σπάσει αν μπορείτε να βρείτε αποτελεσματικά τους πρωταρχικούς παράγοντες μιας πολύ μεγάλης αριθμός. Τα καλά νέα είναι ότι αυτό είναι ένα πολύ δύσκολο πρόβλημα.

Ο πιο γνωστός αλγόριθμος για τον παράγοντα μεγάλων αριθμών στις πρώτες συνιστώσες του στοιχείου ονομάζεται γενικός κόσμος αριθμού πεδίων και έχει μια πολυπλοκότητα εκτέλεσης που αναπτύσσεται λίγο πιο αργά από 2 ^ n. Ως εκ τούτου, τα κλειδιά πρέπει να είναι περίπου δέκα φορές περισσότερο για να παρέχουν παρόμοια ασφάλεια, κάτι που οι άνθρωποι συνήθως ανέχονται ως κόστος επιχειρηματικής δραστηριότητας. Τα κακά νέα είναι ότι ολόκληρο το πεδίο παιχνιδιού αλλάζει όταν οι κβαντικοί υπολογιστές ρίχνονται στο μίγμα.

Κβαντικοί υπολογιστές: Αλλαγή του παιχνιδιού κρυπτογράφησης

Οι κβαντικοί υπολογιστές λειτουργούν επειδή μπορούν να έχουν πολλαπλές εσωτερικές καταστάσεις ταυτόχρονα, μέσω ενός κβαντικού φαινομένου που ονομάζεται "υπέρθεση". Αυτό σημαίνει ότι μπορούν να επιτεθούν ταυτόχρονα σε διάφορα τμήματα ενός προβλήματος, χωρισμένα σε πιθανές εκδόσεις του σύμπαντος. Μπορούν επίσης να διαμορφωθούν έτσι ώστε οι κλάδοι που λύνουν το πρόβλημα να τελειώνουν με το μεγαλύτερο εύρος, έτσι ώστε όταν ανοίγετε το κιβώτιο Η γάτα του Schrodinger, η έκδοση της εσωτερικής κατάστασης με την οποία είναι πιο πιθανό να παρουσιαστεί, είναι μια σκυλάλη που κοιτάζει με στυλ και αποκρυπτογραφεί μήνυμα.

Για περισσότερες πληροφορίες σχετικά με τους κβαντικούς υπολογιστές, ελέγξτε έξω το πρόσφατο άρθρο μας σχετικά με το θέμα Πώς λειτουργούν οι Οπτικοί και οι Κβαντικοί Υπολογιστές;Η εποχή της εξάσκησης έρχεται. Ξέρετε πώς λειτουργούν οι οπτικοί και κβαντικοί υπολογιστές και θα γίνουν αυτές οι νέες τεχνολογίες το μέλλον μας; Διαβάστε περισσότερα !

Το αποτέλεσμα αυτού είναι ότι οι κβαντικοί υπολογιστές δεν είναι μόνο γραμμικώς γρηγορότεροι, όπως οι κανονικοί υπολογιστές είναι: να πάρουν δύο ή δέκα ή εκατό φορές πιο γρήγορα δεν βοηθά πολύ όταν πρόκειται για τη συμβατική κρυπτογραφία ότι είστε εκατοντάδες δισεκατομμύρια φορές πολύ αργά για να επεξεργαστείτε. Οι κβαντικοί υπολογιστές υποστηρίζουν αλγόριθμους που έχουν μικρότερες καλλιεργητικές περιπλοκές χρόνου εκτέλεσης από ό, τι είναι δυνατό αλλιώς. Αυτό κάνει τους κβαντικούς υπολογιστές ουσιαστικά διαφορετικούς από άλλες μελλοντικές υπολογιστικές τεχνολογίες, όπως graphene και memrister υπολογισμού Η Τελευταία Τεχνολογία Υπολογιστών που πρέπει να δείτε για να πιστέψετεΕλέγξτε μερικές από τις τελευταίες τεχνολογίες υπολογιστών που έχουν ρυθμιστεί να μετασχηματίζουν τον κόσμο των ηλεκτρονικών και των υπολογιστών τα επόμενα χρόνια. Διαβάστε περισσότερα .

Για ένα συγκεκριμένο παράδειγμα, ο αλγόριθμος Shor, ο οποίος μπορεί να εκτελεστεί μόνο σε έναν κβαντικό υπολογιστή, μπορεί να παράγει μεγάλους αριθμούς log (n) ^ 3 χρόνο, που είναι δραστικά καλύτερη από την καλύτερη κλασική επίθεση. Η χρήση του γενικού κόσκινου πεδίου για τον παράγοντα ενός αριθμού με 2048 μπιτ διαρκεί περίπου 10 ^ 41 μονάδες χρόνου, οι οποίες υπερβαίνουν τα τρισεκατομμύρια τρισεκατομμύρια τρισεκατομμύρια. Χρησιμοποιώντας τον αλγόριθμο Shor, το ίδιο πρόβλημα απαιτεί περίπου 1000 μονάδες χρόνου.

Το αποτέλεσμα γίνεται πιο έντονο όσο τα κλειδιά είναι μεγαλύτερα. Αυτή είναι η δύναμη των κβαντικών υπολογιστών.

Μην με πάρτε λάθος - οι κβαντικοί υπολογιστές έχουν πολλές πιθανές μη κακές χρήσεις. Οι κβαντικοί υπολογιστές μπορούν να λύσουν αποτελεσματικά το πρόβλημα των μετακινούμενων πωλητών, επιτρέποντας στους ερευνητές να δημιουργήσουν πιο αποτελεσματικά δίκτυα ναυτιλίας και να σχεδιάσουν καλύτερα κυκλώματα. Οι κβαντικοί υπολογιστές έχουν ήδη ισχυρές χρήσεις στην τεχνητή νοημοσύνη.

Τούτου λεχθέντος, ο ρόλος τους στην κρυπτογραφία θα είναι καταστροφικός. Οι τεχνολογίες κρυπτογράφησης που επιτρέπουν στον κόσμο μας να συνεχίσει να λειτουργεί εξαρτώνται από το δύσκολο να λυθεί το πρόβλημα της παραγοντοποίησης ακέραιων αριθμών. Το RSA και τα σχετικά συστήματα κρυπτογράφησης είναι αυτά που σας επιτρέπουν να εμπιστεύεστε ότι βρίσκεστε στη σωστή ιστοσελίδα, ότι τα αρχεία σας οι λήψεις δεν είναι γεμάτες με κακόβουλο λογισμικό και ότι οι άνθρωποι δεν κατασκοπεύουν την περιήγησή σας στο Internet (αν χρησιμοποιείτε Βραχώδης κορυφή).

Η κρυπτογραφία διατηρεί τον τραπεζικό σας λογαριασμό ασφαλή και εξασφαλίζει την παγκόσμια πυρηνική υποδομή. Όταν οι κβαντικοί υπολογιστές γίνουν πρακτικοί, όλη αυτή η τεχνολογία σταματά να λειτουργεί. Η πρώτη οργάνωση για την ανάπτυξη ενός κβαντικού υπολογιστή, αν ο κόσμος εξακολουθεί να εργάζεται πάνω στις τεχνολογίες που χρησιμοποιούμε σήμερα, θα είναι σε μια τρομακτικά ισχυρή θέση.

Έτσι, η κβαντική αποκάλυψη είναι αναπόφευκτη; Υπάρχει κάτι που μπορούμε να κάνουμε γι 'αυτό; Όπως αποδεικνύεται... ναι.

Μετά-κβαντική κρυπτογραφία

Υπάρχουν αρκετές κατηγορίες αλγορίθμων κρυπτογράφησης οι οποίες, από όσο γνωρίζουμε, δεν είναι σημαντικά πιο γρήγορες για την επίλυση σε έναν κβαντικό υπολογιστή. Αυτά είναι γνωστά συλλογικά ως μετα-κβαντική κρυπτογραφία και παρέχουν κάποια ελπίδα ότι ο κόσμος μπορεί να μεταβεί σε κρυπτοσυστήματα που θα παραμείνουν ασφαλή σε έναν κόσμο κβαντικής κρυπτογράφησης.

Οι υποσχόμενοι υποψήφιοι περιλαμβάνουν κρυπτογράφηση βασισμένο σε πλέγματα, όπως το Ring-Learning With Error, το οποίο αποκτά την ασφάλειά του από ένα αποδεδειγμένα πολύπλοκο το πρόβλημα της μηχανικής μάθησης και την πολυπαραγοντική κρυπτογραφία, η οποία αντλεί την ασφάλειά της από τη δυσκολία επίλυσης πολύ μεγάλων συστημάτων απλών εξισώσεις. Μπορείτε να διαβάσετε περισσότερα σχετικά με αυτό το θέμα στο Άρθρο Wikipedia. Προσοχή: πολλά από αυτά τα πράγματα είναι περίπλοκα και μπορεί να διαπιστώσετε ότι το μαθηματικό υπόβαθρο πρέπει να βελτιωθεί σημαντικά, ώστε να μπορέσετε πραγματικά να ανακαλύψετε τις λεπτομέρειες.

Το πάρα πολύ μεγάλο κομμάτι αυτού του γεγονότος είναι ότι τα κβαντικά κρυπτοσμήματα είναι πολύ δροσερά αλλά πολύ νεαρά. Χρειάζονται περισσότερη δουλειά για να είναι αποτελεσματικές και πρακτικές, αλλά και να αποδείξουν ότι είναι ασφαλείς. Ο λόγος για τον οποίο είμαστε σε θέση να εμπιστευτούμε τα κρυπτοσυστήματα είναι επειδή έχουμε ρίξει αρκετές κλινικά παρανοϊκές μεγαλοφυίες σε αυτά για αρκετό καιρό ότι θα είχαν ανακαλυφθεί μέχρι στιγμής προφανείς ελλείψεις και ότι οι ερευνητές έχουν αποδείξει διάφορα χαρακτηριστικά που τα καθιστούν ισχυρός.

Η σύγχρονη κρυπτογραφία εξαρτάται από το φως ως απολυμαντικό και τα περισσότερα από τα κβαντογραφικά σχήματα είναι απλά πάρα πολύ καινούργια για να εμπιστευθεί την παγκόσμια ασφάλεια. Παίρνουν εκεί, όμως, και με λίγη τύχη και κάποια προετοιμασία, οι ειδικοί ασφαλείας μπορούν να ολοκληρώσουν το διακόπτη πριν από την πρώτη σύνδεση του κβαντικού υπολογιστή.

Αν αποτύχουν, ωστόσο, οι συνέπειες μπορεί να είναι κακές. Η σκέψη του καθενός που έχει τέτοια δύναμη είναι ανησυχητική, ακόμα κι αν είστε αισιόδοξος για τις προθέσεις του. Το ερώτημα του ποιος αναπτύσσει πρώτα ένα λειτουργικό κβαντικό υπολογιστή είναι αυτός που όλοι πρέπει να προσέξουν πολύ προσεκτικά καθώς θα προχωρήσουμε στην επόμενη δεκαετία.

Ανησυχείτε για την ανασφάλεια της κρυπτογραφίας σε κβαντικούς υπολογιστές; Τι σας παίρνει; Μοιραστείτε τις σκέψεις σας στα παρακάτω σχόλια!

Συντελεστές εικόνας: Δυαδική σφαίρα Μέσω Shutterstock