Μια από τις μεθόδους κρυπτογράφησης που οι υπολογιστές χρησιμοποιούν για τις όποιες συναλλαγές γίνονται με τη μεσολάβησή τους είναι η κρυπτογράφηση RSA (από τα αρχικά των ονομάτων των εμπνευστών της, Ron Rivest, Adi Shamir, Leonard Adleman). Παρουσιάστηκε με τη μορφή δημοσίευσης και στη συνέχεια καταχωρίστηκε ως πατέντα από το ΜΙΤ το 1978. [Αργότερα έγινε γνωστό πως το ίδιο είχε σκεφτεί από το 1973 κάποιος που εργαζόταν για τις βρετανικές μυστικές υπηρεσίες (Government Communications Headquarters – GCHQ), ο Κλίφορντ Κοκς, αλλά όπως είναι κατανοητό οι προϊστάμενοί του είχαν απαγορεύσει να κοινοποιηθεί η επινόησή του αυτή, αν και διαπιστώθηκε αργότερα ότι δεν παρέλειψαν να τη γνωστοποιήσουν στους αμερικανούς «ομοτέχνους» τους και συνεργάτες].

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

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

Ενα κλειδί που θα βοηθήσει στην κρυπτογράφηση δημιουργείται στον υπολογιστή μας και πρέπει μέσω του δικτύου να σταλεί στην τράπεζα. Αλλά και αυτό θα πρέπει να είναι κρυπτογραφημένο, οπότε εδώ έρχεται σε βοήθεια η μέθοδος που επινόησαν ο Κοκς και οι RSA. Ο… τοκετός για να γεννηθούν τα κλειδιά ξεκινάει με δύο πρώτους αριθμούς (p,q), με αρκετό πλήθος ψηφίων, που μπορούν να επιλέγονται και από το Διαδίκτυο χάρη σε έναν αλγόριθμο (=μηχανισμό συγκεκριμένων βημάτων) φτιαγμένο για αυτόν τον λόγο (π.χ. ένας τέτοιος είναι ο Rabin-Miller primality test). Αυτό δηλαδή δεν είναι κάτι δύσκολο ή δυσεξήγητο.

Το παράδειγμα

Ας υποθέσουμε ότι μας έδωσε το «μηχάνημα» τους αριθμούς 907 και 773. Υπολογίζεται το γινόμενό τους: N=p x q. Στο συγκεκριμένο παράδειγμα θα είναι: Ν=907×773=701.111. Στη συνέχεια θα χρειαστεί να προσδιοριστεί το ελάχιστο κοινό πολλαπλάσιο των αριθμών ( p-1) και (q-1). Στην εποχή του Διαδικτύου αυτό είναι πανεύκολο, διότι υπάρχουν σε επιφυλακή μηχανισμοί έτοιμοι να μας εξυπηρετήσουν. Δίνεις τους δύο αριθμούς, εδώ τον (907-1) και τον (773-1), και παίρνεις σε χρόνο σχεδόν μηδενικό το αποτέλεσμα που εδώ είναι ο αριθμός 349.716.

Εχουμε φθάσει πλέον κοντά στη δημιουργία του λεγόμενου «δημόσιου κλειδιού». Πρώτα όμως πρέπει να γίνει η επιλογή και ενός αριθμού που συνήθως συμβολίζεται με το ε και πρέπει να βρίσκεται στο παράδειγμά μας στο διάστημα μεταξύ 1 και 349.716. Για να μην είναι μακροσκελείς οι υπολογισμοί μας, εδώ επιλέγουμε ε=11. Αν λοιπόν αυτό που θέλουμε να διαβιβάσουμε (είτε είναι αριθμός είτε γράμμα ψηφιακά έχει μετατραπεί σε δυαδικό αριθμό) συμβολίζεται με Μ, θα περάσει από την εξής  διαδικασία: Δ= Μ^ε mod Ν (δηλαδή υψώνεται ο Μ στη δύναμη e, γίνεται η ακέραιη διαίρεση με το Ν και κρατάμε το υπόλοιπο). Οπότε προκύπτει ένας εντελώς νέος αριθμός και δύσκολο να αποκρυπτογραφηθεί. Στο παράδειγμά μας αν είναι ο αριθμός 4 που θέλουμε να στείλουμε κρυπτογραφημένο με ε=11 θα είναι: Δ= 4¹¹ mod 701.111. Και δεν υπάρχει λόγος ανησυχίας για τους υπολογισμούς μας εδώ, διότι μπορούμε από αντίστοιχο μηχανισμό του Διαδικτύου να πάρουμε το πόσο είναι το 4¹¹(=4.194.304) και πόσο είναι το υπόλοιπο της ακέραιας διαίρεσής (το mod-ulo) με τον αριθμό 701.111 (στην πράξη οι υπολογιστές είναι προγραμματισμένοι και τα βγάζουν όλα αυτά μόνοι τους στο δευτερόλεπτο). Στο παράδειγμά μας ο αριθμός 4 διαβιβάστηκε τελικά ως 688.749(!)

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

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

1. Αν ο αριθμός x ισούται με το x% του αριθμού y και ο αριθμός y ισούται με το y% του αριθμού z, ποια μπορεί να είναι η τιμή του z;

2. Αν η ώρα που διαβάζετε αυτές τις γραμμές είναι, ας υποθέσουμε, 10.45 το πρωί (η συγκεκριμένη ώρα δεν έχει σημασία), τότε τι ώρα θα είναι αφού περάσουν 143.999.999.995 λεπτά;

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

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

1. Ζητούμε τον πεντηκοστό όρο της εξής ακολουθίας: 5, 6x, 7² x, 8³ x, 9⁴ x, … Αρκεί να παρατηρήσουμε ότι οι όροι της ακολουθίας προκύπτουν ως εξής: ο πρώτος είναι ο 5x⁰, δεύτερος είναι ο 5+1 στην πρώτη δύναμη του x, ο τρίτος προκύπτει αυξάνοντας κατά δύο τον πρώτο συντελεστή 5+2=7 και κατά ένα τον εκθέτη του x, κ.ο.κ. Αρα ο πεντηκοστός θα έχει συντελεστή 5+49=54 και εκθέτη 49, άρα θα είναι ο 54x⁴⁹.

2. Ενα συνηθισμένο ζάρι με τους αριθμούς 1, 2, 3, 4, 5, 6 στις πλευρές του ρίχνεται διαδοχικές φορές μέχρις ότου το άθροισμα των αποτελεσμάτων που ερχόταν με κάθε ζαριά να υπερβαίνει το 12. Ζητούμε να βρεθεί, αν υποθέσουμε ότι επαναλαμβάνουμε κάποιες φορές τη διαδικασία, ποιο άθροισμα πάνω από το 12 έχει τις περισσότερες πιθανότητες να εμφανίζεται. Θα πρέπει λοιπόν να πάμε πρώτα στην προτελευταία ζαριά (αυτήν όπου ακόμη δεν έχουμε υπερβεί το 12). Εως τότε τα αθροίσματα που θα έχουμε φέρει μπορεί να είναι 7, 8, 9, 10, 11, 12. Αν ήταν το 12, με την επόμενη ζαριά το άθροισμα θα είναι ένας από τους εξής αριθμούς: 13, 14, 15, 16, 17, 18. Με την ίδια πιθανότητα ο καθένας (αφού υποθέτουμε «τίμιο» ζάρι). Αν ήταν 11 το αρχικό άθροισμα, τότε το επόμενο άθροισμα θα είναι ένας από τους 12, 13, 14, 15, 16, 17. Αν συνεχίσουμε έτσι, θα παρατηρήσουμε ότι ο 13 είναι μέσα σε όλους τους συνδυασμούς, άρα αυτός είναι ο πιο πιθανός να προκύψει σε μια σειρά επαναλήψεων. Γενικά σε ζάρι με «Ν» αριθμούς στις πλευρές ο πιο πιθανός είναι ο Ν+1.

Σημείωση: Στη λύση του προβλήματος με τους ομόκεντρους κύκλους της Κυριακής 18.1 θα πρέπει η λέξη «ακτίνα» όπου εμφανίζεται να αντικατασταθεί με τη λέξη «διάμετρος».

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