Τον Ιανουάριο του 1955, ο John Nash, τότε assistant professor μαθηματικών στο MIT, άρχισε να αλληλογραφεί με την αμερικανική National Security Agency για μια μηχανή κρυπτογράφησης που είχε σχεδιάσει.
Όμως μέσα στις χειρόγραφες επιστολές του υπήρχε κάτι ίσως πιο ενδιαφέρον από την ίδια τη μηχανή: μια ιδέα για το τι σημαίνει ένα κρυπτοσύστημα να είναι πρακτικά μη παραβιάσιμο.
Η βασική ιδέα
Ο Nash παρατήρησε ότι ένα μυστικό κλειδί μπορεί θεωρητικά να ανακτηθεί με εξαντλητική αναζήτηση. Αν το κλειδί έχει μήκος \(r\) bits, τότε υπάρχουν
\[ 2^r \]πιθανά κλειδιά.
Η ασφάλεια, λοιπόν, δεν εξαρτάται μόνο από το αν το κλειδί μπορεί να βρεθεί «κατ’ αρχήν», αλλά από το πόσο γρήγορα αυξάνεται ο απαιτούμενος υπολογισμός καθώς μεγαλώνει το μήκος του κλειδιού.
Για απλά κρυπτοσυστήματα μπορεί να υπάρχουν μέθοδοι που απαιτούν χρόνο περίπου πολυωνυμικό ως προς το μήκος του κλειδιού. Για αρκετά σύνθετα συστήματα, ο Nash εικάζει ότι ο απαιτούμενος υπολογισμός μπορεί να αυξάνεται εκθετικά.
Στις επιστολές του γράφει ουσιαστικά ότι, για «αρκετά σύνθετους τύπους κρυπτογράφησης», ο μέσος υπολογιστικός κόπος για την εύρεση του κλειδιού θα μπορούσε να αυξάνεται εκθετικά με το μήκος του κλειδιού. :chatgpt-content-reference{index="1"}
Ασφάλεια μέσω υπολογιστικής δυσκολίας
Αυτή είναι η πιο εντυπωσιακή πλευρά της αλληλογραφίας.
Ο Nash αντιλαμβάνεται ότι ένα σύστημα μπορεί να είναι θεωρητικά παραβιάσιμο, αλλά πρακτικά ασφαλές, αν ο καλύτερος γνωστός τρόπος επίθεσης απαιτεί απαγορευτικά μεγάλο υπολογισμό.
Αυτή η λογική βρίσκεται σήμερα στον πυρήνα μεγάλου μέρους της σύγχρονης κρυπτογραφίας:
δεν απαιτούμε ένα μυστικό να είναι αδύνατο να ανακτηθεί· αρκεί να είναι υπολογιστικά μη ρεαλιστικό να ανακτηθεί.
Ο ίδιος ο Nash ήξερε ότι δεν είχε απόδειξη
Εδώ χρειάζεται ιδιαίτερη προσοχή. Ο Nash δεν παρουσίασε θεώρημα ούτε απέδειξε ότι η εκθετική δυσκολία ισχύει γενικά.
Αντίθετα, έγραψε ρητά ότι δεν μπορούσε να αποδείξει την εικασία του ούτε για έναν ειδικό τύπο κρυπτοσυστήματος και ότι δεν περίμενε απαραίτητα να αποδειχθεί. :chatgpt-content-reference{index="2"}
Άρα οι επιστολές δεν αποτελούν «λύση του \(P\) vs \(NP\) πριν από την εποχή του».
Είναι όμως μια εντυπωσιακά πρώιμη διατύπωση της ιδέας ότι πρέπει να ταξινομούμε προβλήματα και συστήματα ανάλογα με το πώς αυξάνεται ο υπολογιστικός χρόνος που απαιτούν.
«Μην με περάσετε για τρελό»
Ο Nash φαίνεται να ανησυχούσε ότι το χειρόγραφο υλικό του θα μπορούσε να μην αντιμετωπιστεί σοβαρά. Σε μία από τις επιστολές του υπενθύμισε στην NSA ότι ήταν assistant professor στο MIT και ότι το πιο γνωστό έργο του αφορούσε τη θεωρία παιγνίων, ζητώντας ουσιαστικά οι ιδέες του να εξεταστούν προσεκτικά από τους κατάλληλους ειδικούς. :chatgpt-content-reference{index="3"}
Τι απάντησε η NSA;
Η NSA εξέτασε τη μηχανή που πρότεινε ο Nash.
Στις 3 Μαρτίου 1955 του απάντησε ότι οι κρυπτογραφικές αρχές του συστήματος ήταν «ingenious», αλλά ότι το σύστημα δεν κάλυπτε τις απαιτήσεις ασφαλείας για επίσημη κυβερνητική χρήση. :chatgpt-content-reference{index="4"}
Με άλλα λόγια:
Η γενικότερη ιδέα του Nash όμως αποδείχθηκε πολύ πιο ανθεκτική στον χρόνο.
Οι επιστολές χάθηκαν για δεκαετίες
Η αλληλογραφία παρέμεινε στα αρχεία της NSA για δεκαετίες. Το υλικό επανεξετάστηκε και αποχαρακτηρίστηκε το 2011, ενώ τον Ιανουάριο του 2012 το National Cryptologic Museum εγκαινίασε ειδική έκθεση με τίτλο An Inquisitive Mind: John Nash Letters. :chatgpt-content-reference{index="5"}
Η NSA σημειώνει ότι οι επιστολές και η υπηρεσιακή αξιολόγηση είχαν διατηρηθεί σε συλλογή ανεπιθύμητης αλληλογραφίας από το 1955 μέχρι την αποχαρακτηρισμένη δημοσιοποίησή τους. :chatgpt-content-reference{index="6"}
Δεκαετίες μπροστά από την εποχή τους;
Με τη σημερινή ορολογία, ο Nash δεν είχε ακόμη ένα πλήρες μοντέλο computational complexity ούτε τη θεωρία που θα αναπτυσσόταν αργότερα.
Αλλά ήδη μιλούσε για:
- μήκος κλειδιού,
- εκθετική έναντι πολυωνυμικής αύξησης του υπολογισμού,
- brute-force αναζήτηση \(2^r\),
- και πρακτική ασφάλεια βασισμένη στην υπολογιστική δυσκολία.
Γι’ αυτό και μεταγενέστεροι μαθηματικοί και θεωρητικοί της πληροφορικής βλέπουν στις επιστολές του μια εξαιρετικά πρώιμη συγγένεια με έννοιες που αργότερα έγιναν κεντρικές στη θεωρητική πληροφορική και τη σύγχρονη κρυπτογραφία. :chatgpt-content-reference{index="7"}
Είδε όμως πολύ νωρίς ότι η πραγματική ασφάλεια μπορεί να βρίσκεται όχι στην αδυναμία επίθεσης, αλλά στο κόστος της.
Πηγές: National Security Agency, John Nash Letters · National Cryptologic Museum, An Inquisitive Mind: John Nash Letters · Mike Rosulek, Correspondences Regarding Cryptography between John Nash and the NSA.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου