Θέλουμε να δούμε γιατί απειλεί ο κβαντικός υπολογιστής να αχρηστεύσει τον τρόπο που κρυπτογραφούμε σήμερα τις διάφορες συναλλαγές μέσω υπολογιστών (π.χ. με τη μέθοδο RSA). Από τα προηγούμενα γνωρίζουμε πως η εκκίνηση γίνεται από δύο πολύ μεγάλους πρώτους αριθμούς (να καταλαμβάνουν ο καθένας τουλάχιστον 2.048 μπιτ ή και περισσότερα), έστω τους p,q.

Υπολογίζουμε το γινόμενό τους n=pxq. Από κοντά και το φ(n)=(p-1)(q-1). Το τρίτο στοιχείο που πρέπει να έχουμε ξεκινώντας για την κατασκευή του δημόσιου κλειδιού συνήθως είναι ο 65.537 – εκτός και αν διαιρεί τον φ(n), οπότε θα πάρουμε τον αμέσως μεγαλύτερο πρώτο αριθμό. Με βάση τους n και 65.537 (τον είχαμε συμβολίσει στο προηγούμενο με ε) όπως δείξαμε προκύπτει η κρυπτογράφηση (μετατρέπεται σε έναν άλλον αριθμό) ενός στοιχείου. Για την αντίστροφη διαδικασία, της αποκρυπτογράφησης, χρειαζόμαστε ένα άλλο κλειδί, το ιδιωτικό, που δεν είναι δημόσια γνωστό. Το ιδιωτικό (που έχει και αυτό εκατοντάδες ψηφία) προκύπτει με μια διαδικασία που απαιτεί την παρουσία και τη γνώση του φ(n)=(p-1)(q-1). Και εδώ πλέον αρχίζουν τα πράγματα και γίνονται πια καθαρά. Αφού η αποκρυπτογράφηση εξαρτάται από την παρουσία και τον χειρισμό με κάποιον μαθηματικό τρόπο του ιδιωτικού κλειδιού και αυτό εξαρτάται από το φ(n), άρα και από τη γνώση των p,q είναι αδύνατον να επιστρέψουμε στο μη κρυπτογραφημένο μήνυμα χωρίς τη γνώση του πώς αναλύεται ο n στους δύο αυτούς πρώτους αριθμούς.

Σημερινές δυνατότητες

Τα μέσα που διαθέτουμε δουλεύοντας ακόμη και με τους πιο ισχυρούς σημερινούς υπολογιστές χρειάζονται ίσως και περισσότερο χρόνο από μια ζωή για να κάνουν αυτή την ανάλυση του n στους δύο συγκεκριμένους πρώτους αριθμούς. Με έναν αλγόριθμο όπως αυτός του Σορ όμως (με το συστηματικό του ψάξιμο που απαιτεί πολλές χρονοβόρες δοκιμές και υψώσεις σε δυνάμεις επειδή γίνονται πολλές ταυτόχρονα, σε έναν κβαντικό υπολογιστή) μπορεί αυτό, όπως δείξαμε κάπως στοιχειωδώς σε προηγούμενη συνέχεια, να το κάνει σε πολύ μικρό χρόνο. Αρκεί να διαθέτει αρκετά (κοντά στο 1 εκατομμύριο υπολογίστηκε) qbits. Σήμερα ο πιο «μπιτάτος», αν δανειστούμε κάτι από τη μουσική αργκό, κβαντικός υπολογιστής στον κόσμο, ο ονομαζόμενος Osprey (=ψαραετός), που αναγγέλθηκε από την ΙΒΜ τον Νοέμβριο του 2022, διαθέτει μόλις 443 qbits. Μπορούμε όμως να κοιμόμαστε ήσυχοι γνωρίζοντας αυτό;

Ανησυχητική πρόοδος

Πολύ-πολύ πρόσφατα δημοσιοποιήθηκε μια εργασία Κινέζων που εργάζονται επάνω στο θέμα και εκεί αναγγέλλεται ότι μπορούν να παραβιάσουν την οσοδήποτε δύσκολη μέθοδο κρυπτογράφησης διαθέτουμε σήμερα με τα λίγα αυτά qbits που προσφέρονται σήμερα. Συγκεκριμένα, λένε, τους αρκούν 372 qbits ώστε να χειριστούν κλειδιά με πάνω από 600 ψηφία.

Χρησιμοποιούν έναν άλλον αλγόριθμο, αυτόν του Γερμανού Κλάους Σνορ (προσοχή: άλλο Σνορ κι άλλο Σορ!) και όπως λένε κατάφεραν να αναλύσουν τον αριθμό: 261.980.999.226.229 σε γινόμενο δύο πρώτων, που είναι οι 15.538.213 και 16.860.433. Αν είναι έτσι πρόκειται για κορυφαία επίδοση στον κόσμο αλλά αριθμός πολύ μακριά από το μήκος αυτών που χρησιμοποιούνται σήμερα.

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

Η σειρά για τους κβαντικούς υπολογιστές κλείνει εδώ. Αλλά το ΒΗΜΑ-Science θα παρακολουθεί προσεκτικά και θα ενημερώνει κάθε φορά που κάποιο νέο επίτευγμα θα μας φέρνει πιο κοντά στην τελειοποίησή τους.

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

Πνευματική Γυμναστική

1. Ο Α και ο Β λένε ψέματα αλλά όχι τις ίδιες ημέρες. Ο ένας εκ των δύο, χωρίς να ξέρουμε ποιος, λέει ψέματα Δευτέρες, Τρίτες, Τετάρτες και αλήθειες τις άλλες 4 ημέρες της εβδομάδας. Ο άλλος ψέματα Πέμπτες, Παρασκευές και Σάββατα και αλήθειες τις άλλες 4 ημέρες. Μια ημέρα της εβδομάδας μίλησαν και είπαν κατά σειρά τα εξής: Α: Λέω ψέματα τα Σάββατα, Β: Αύριο θα πω ψέματα, μετά πάλι ο Α: Λέω ψέματα τις Κυριακές. Ποια ημέρα της εβδομάδας ειπώθηκαν αυτά;

2. Σε ένα πλοίο συμβαίνει εισροή νερού και όταν το κατάλαβαν και άρχισαν την άντληση υπήρχε μια ποσότητα. Ο καπετάνιος ξέρει ότι με 12 άνδρες του πληρώματος θα βγάλει όλο το νερό σε 3 ώρες, με 5 άνδρες σε 10 ώρες. Αν πρέπει όμως να βγει όλο το νερό σε 2 ώρες πόσοι πρέπει να απασχοληθούν;

Οι απαντήσεις στα προηγούμενα κουίζ

1. Αν ο αριθμός x ισούται με το x% του αριθμού y και ο αριθμός y ισούται με το y% του αριθμού z, ποια μπορεί να είναι η τιμή του z; Εξετάζουμε την περίπτωση που το z=100, διότι τότε το y μπορεί να έχει τιμές 10 ή 100. Ας συνεχίσουμε τότε με το y. Θα μπορούσε να έχει τιμή 100 αλλά και 10. Αν υποθέσουμε ότι η τιμή του είναι 10, ναι μεν το 10% του 100 είναι 10 (δηλαδή πληρούται το ότι y% του z είναι ίσο με y). Αλλά το x% του y=10 να είναι x δεν βγαίνει. Αν όμως y=100 και αυτό τότε όλα έρχονται στη θέση τους με x=10, y=100, z=100.

2. Αν η ώρα που διαβάζετε αυτές τις γραμμές είναι, ας υποθέσουμε, 10.45 το πρωί (η συγκεκριμένη ώρα δεν έχει σημασία), τότε τι ώρα θα είναι αφού περάσουν 143.999.999.995 λεπτά; Εδώ χρειάζεται να τρέξουμε λίγο πιο μπροστά στον χρόνο. Οχι πολύ, μόλις 5 λεπτά. Δηλαδή να δούμε τι γίνεται αν περάσουν 143.999.999.995 λεπτά + 5 λεπτά = 144.000.000.000 λεπτά. Επειδή η ημέρα έχει 24×60 = 1.440 λεπτά, η διαίρεση των δύο αριθμών μας δείχνει ότι θα έχουν περάσει 100.000.000 ακέραιες ημέρες. Επειδή όμως «κλέψαμε», δηλαδή πήγαμε πέντε λεπτά πιο μπροστά, τώρα που τα γυρίζουμε πίσω σημαίνει ότι η ώρα θα είναι 10.40. Βέβαια υπάρχουν οι ενστάσεις ότι μετά από όλο αυτό το χρονικό διάστημα η τροχιά της Γης θα είναι κάπως διαφορετική, οι μικρές αποκλίσεις της διάρκειας κάθε ημέρας από το 24ωρο θα έχουν ρίξει έξω ημέρες ολόκληρες αυτούς τους υπολογισμούς.

3. Σε ένα κουτί έχουν τοποθετηθεί τέσσερα φύλλα χαρτιού. Στο ένα είναι γραμμένος ο αριθμός 3, στο δεύτερο ο αριθμός 5, στο τρίτο ο αριθμός 7 και στο τέταρτο ο αριθμός 9. Τα τοποθετούμε μέσα στο κουτί κάθε φορά στην τύχη, τα βγάζουμε ένα-ένα και καταγράφουμε τα ψηφία όπως βγήκαν τοποθετώντας τα από αριστερά προς τα δεξιά, οπότε φτιάχνεται κάθε φορά ένας τετραψήφιος αριθμός. Ποια η πιθανότητα από όλους αυτούς τους τετραψήφιους αριθμούς που μπορούν να προκύψουν κάποιος ή κάποιοι να είναι πρώτοι; Επειδή 3+5+7+9=24 έπεται ότι ο κάθε συνδυασμός των τεσσάρων αυτών αριθμών θα δίνει πάντα τετραψήφιο διαιρετό τουλάχιστον με τον 3 και ποτέ πρώτο αριθμό. Αρα η απάντηση είναι πως η πιθανότητα θα είναι ίση με μηδέν.

Έντυπη έκδοση Το Βήμα