Πορτοφόλια κρυπτονομισμάτων, αποστολή και λήψη e-mails, «έξυπνα τηλέφωνα» που τρέχουν μόνο πιστοποιημένες εφαρμογές, πληρωμές με πιστωτικές κάρτες [1] ακόμα και βιομετρικά δεδομένα σε διαβατήρια [2]. Τα συστήματα κρυπτογράφησης δημοσίου κλειδιού χρησιμοποιούνται σε ένα ευρύ φάσμα εφαρμογών.
Δισεκατομμύρια άνθρωποι τα χρησιμοποιούν καθημερινά χωρίς να γνωρίζουν ή να χρειάζεται να γνωρίζουν για όλα τα παραπάνω. Στις εφαρμογές αυτές συγκαταλέγεται και η ασφάλεια της πλοήγησης στον κυβερνοχώρο, που -ειρήσθω εν παρόδω- αφορά και εσάς που διαβάζετε αυτή τη στιγμή το παρόν άρθρο. Σύμφωνα με την αναφορά διαφάνειας της Google, πάνω από το 90% των ιστοσελίδων που φορτώνονται σήμερα στον Chrome σε Windows χρησιμοποιούν πρωτόκολλο HTTPS [3], που περιλαμβάνει μία “χειραψία TLS“, ένα πρωτόκολλο επικοινωνίας δηλαδή που υλοποιεί κρυπτογράφηση δημοσίου κλειδιού για να διασφαλίσει μια ασφαλή επικοινωνία μεταξύ του υπολογιστή σας και του εξυπηρετητή του ιστοτόπου.

Με απλά λόγια, ένα κρυπτοσύστημα δημοσίου κλειδιού είναι μία μέθοδος όπου κάθε τερματική συσκευή έχει το δικό της ζεύγος κλειδιών. Εάν πρόκειται για ένα καλό σύστημα, δεδομένα που έχουν κρυπτογραφηθεί με το δημόσιο κλειδί μίας συσκευής μπορούν να αποκρυπτογραφηθούν μόνο με το αντίστοιχο ιδιωτικό κλειδί και αντίστροφως. Αυτά τα κρυπτογραφικά συστήματα μπορούν να υποδιαιρεθούν στην οικογένεια των μονόδρομων συναρτήσεων καταπακτής. Συγκεκριμένα, οι συναρτήσεις εν γένει επιτρέπουν μόνο την αποκρυπτογράφηση κρυπτογραφημένων δεδομένων, ενώ οι συναρτήσεις “καταπακτής” λειτουργούν αμφίδρομα, τα δεδομένα δηλαδή μπορούν να κρυπτογραφηθούν και με τα δύο κλειδιά και μετά να αποκρυπτογραφηθούν με το άλλο, αντιστοίχως. Καλούνται δε “μονόδρομες” (one-way) συναρτήσεις επειδή είναι εύκολο να υπολογιστούν προς τη μία κατεύθυνση, αλλά πολύ δύσκολο προς την αντίθετη (αντίστροφη συνάρτηση), εκτός και αν είναι γνωστή η ιδιωτική πληροφορία, η λεγόμενη “καταπακτή” [4].
Εργαζόμενοι με δύο διαφορετικά κλειδιά σε μια τέτοια οικογένεια, μπορούμε να λύσουμε ταυτόχρονα δύο προβλήματα κρυπτογραφίας, την ιδιωτικότητα και την αυθεντικότητα, όπως περιγράφεται αργότερα λεπτομερώς, λύνοντας παράλληλα και το πρόβλημα του διαμοιρασμού κλειδιών. Αυτή η κομψή ιδέα παρουσιάστηκε για πρώτη φορά από τους Whitfield Diffie και Martin Hellman τον Νοέμβριο του 1976 στο διάσημο άρθρο τους: “New Directions in Cryptography” [4]. Μολονότι δεν παρουσίασαν μία υλοποίηση της ιδέας αυτής, η κοινοποίησή της ήταν ο θεμέλιος λίθος και η έμπνευση για πολλές υλοποιήσεις που ακολούθησαν μετέπειτα, όπως ο RSA λίγους μήνες μετά, τον Απρίλιο του 1977 [5].
Είναι αναμενόμενο να αναρωτηθεί κανείς, ποια μαθηματική σχέση συνδέει τα κλειδιά μιας “μονόδρομης συνάρτησης καταπακτής”, ούτως ώστε ένα από αυτά τα κλειδιά να παραμένει δημόσιο, αλλά παράλληλα να γίνεται και η ανταλλαγή κλειδιών με έναν ασφαλή τρόπο.
Ασύμμετρη κρυπτογράφηση ή Κρυπτογράφηση δημοσίου κλειδιού
Τα δημόσια και ιδιωτικά κλειδιά είναι ο θεμέλιος λίθος για τα συστήματα ασύμμετρης κρυπτογράφησης. Σε τέτοια συστήματα, η κρυπτογράφηση είναι διαφορετική σε κάθε πλευρά, ενώ και τα δύο τερματικά έχουν το δικό τους ζεύγος κλειδιών. Όπως υπονοεί και το όνομα, το δημόσιο κλειδί παραμένει δημόσιο ώστε οποιοσδήποτε να κρυπτογραφεί μηνύματα προς τον συγκεκριμένο παραλήπτη, ενώ το ιδιωτικό κλειδί κρατείται ιδιωτικό, ώστε μόνο αυτός ο παραλήπτης να μπορεί να αποκρυπτογραφήσει αυτά τα μηνύματα.
Η λήψη μηνυμάτων είναι όπως μία κλειδαριά που κατά κάποιον τρόπο εξαρτάται από το εκάστοτε μήνυμα, και είναι διαθέσιμη για όλους, ενώ το κλειδί είναι προσωπικό. Για την αποστολή ενός μηνύματος, κανείς χρειάζεται απλώς να χρησιμοποιήσει αυτή την “κλειδαριά” του παραλήπτη, ώστε να το ασφαλίσει.

Τα ζεύγη κλειδιών που λειτουργούν και προς τις δύο κατευθύνσεις επιτρέπουν επίσης στον αποστολέα να προστατεύσει το μήνυμα από τροποποιήσεις και να πιστοποιήσει τον εαυτό του ως τον πραγματικό αποστολέα, “υπογράφοντάς” το με κρυπτογραφικό τρόπο. Η υπογραφή του μηνύματος σημαίνει ότι ο αποστολέας το κρυπτογραφεί με το δικό του ιδιωτικό κλειδί πριν την αποστολή του. Εφόσον μόνο ο αποστολέας κατέχει το ιδιωτικό κλειδί, μπορεί κανείς να πιστοποιήσει την αυθεντικότητα του υπογεγραμμένου μηνύματος, αποκρυπτογραφώντας το με το δημόσιο κλειδί του αποστολέα. Το κρυπτογραφημένο κείμενο (ciphertext) που προκύπτει εξαρτάται τόσο από το κλειδί όσο και από το μήνυμα, οπότε η υπογραφή δεν μπορεί να αντιγραφεί για χρήση σε άλλα μηνύματα, και το μήνυμα δεν μπορεί να τροποποιηθεί.
Είναι σαν να κλειδώνουμε ένα μήνυμα με μία κρυφή κλειδαριά, αλλά να έχουμε το κλειδί της διαθέσιμο δημοσίως. Αν το δημόσιο κλειδί ταιριάζει, αυτό σημαίνει ότι η κλειδαριά είναι αυθεντική και άρα το μήνυμα είναι πιστοποιημένα αναλλοίωτο και απεσταλμένο από κάποιον που έχει την ιδιωτική “κλειδαριά”.

Υπάρχουν πολλές διαφορετικές υλοποιήσεις τέτοιων συστημάτων ασύμμετρης κρυπτογράφησης, και η σχέση μεταξύ των κλειδιών είναι πάντα βασισμένη σε διαφορετικά μαθηματικά προβλήματα, ώστε να διασφαλίζεται ότι το δημόσιο κλειδί δεν θέτει σε κίνδυνο το ιδιωτικό. Το άρθρο αυτό εστιάζει στον RSA, το παλαιότερο και πιο χρησιμοποιημένο-ακόμα και σήμερα-σύστημα, που βασίζεται στην μεγάλη δυσκολία παραγοντοποίησης μεγάλων ακεραίων αριθμών.
RSA (Rivest-Shamir-Adleman)
1. Αποκρυπτογράφηση / Κρυπτογράφηση
Η πράξη “αριθμός modulo n” σημαίνει τη διαίρεση του αριθμού δια n και τη χρήση του υπολοίπου ως αποτέλεσμα. Με αυτόν τον τρόπο, το αποτέλεσμα της πράξης θα βρίσκεται πάντα στο διάστημα 0 ≤ αποτέλεσμα ≤ n-1. Μερικές φορές το -1 (mod n) χρησιμοποιείται χωρίς διάκριση με το n-1 (mod n). Στην αριθμητική υπολοίπων συμβολίζουμε: a ≡ b (mod n) και γράφουμε “το a ταυτίζεται με b modulo n”. Μπορείτε να σκεφτείτε το modulo με τον ίδιο τρόπο που διαβάζουμε την ώρα σε ένα ρολόι. Όταν η ώρα φτάνει στον αριθμό 12, γυρίζει ξανά στο 0 και ο κύκλος επαναλαμβάνεται.

Το μήνυμα Μ υψωμένο στη δύναμη δοθέντος αριθμού e modulo έναν άλλο δοθέντα αριθμό n έχει ως αποτέλεσμα ένα κρυπτογραφημένο κείμενο C. Όπως μπορεί κανείς να συμπεράνει, οι δύο αριθμοί e και n σχηματίζουν το δημόσιο κλειδί του παραλήπτη: (e, n). Δηλαδή:

Το μήνυμα πρέπει πρωτίστως να μεταφραστεί σε μία αριθμητική μορφή, όπου πρέπει να ισχύει 0 ≤ Μ ≤ n-1. Με αυτόν τον τρόπο, το μήνυμα και το κρυπτογραφημένο κείμενο θα βρίσκονται στο διάστημα από 0 έως n-1.

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

2. Δημιουργία ζεύγους κλειδιών
Για να υπολογίσουμε το κοινό τμήμα n των δύο κλειδιών, χρειαζόμαστε πρώτα απ’ όλα δύο πολύ μεγάλους τυχαίους πρώτους αριθμούς p και q (σήμερα αυτό γίνεται συνήθως με τη βοήθεια του ελέγχου Miller-Rabin).

Ο επόμενος αριθμός που πρέπει να υπολογίσουμε είναι το d. Για αυτόν τον σκοπό, πρέπει πρώτα να εισάγουμε τη συνάρτηση Euler φ(x), που δίνει το πλήθος όλων των θετικών ακεραίων που είναι μικρότεροι ή ίσοι του x και πρώτοι ως προς αυτόν. Με αυτό εννούμε όλους τους αριθμούς που έχουν τη μονάδα (1) ως τον μέγιστο κοινό διαιρέτη με τον x. Είναι πολύ εύκολο να υπολογίσουμε το φ ενός πρώτου αριθμού, αφού όλοι οι θετικοί ακέραιοι μικρότεροι από έναν πρώτο είναι πρώτοι ως προς αυτόν και έχουν τη μονάδα ως μέγιστο κοινό διαιρέτη: φ(πρώτος) = πρώτος-1. Στη δική μας περίπτωση, χρειαζόμαστε μόνο το φ(n). Αφού οι p και q είναι και οι δύο πρώτοι, είναι πολύ εύκολο να υπολογίσουμε το φ(n) επίσης.

Ο αριθμός d θα πρέπει να είναι πρώτος ως προς το φ(n). Είναι εύκολο να βρούμε έναν τέτοιο αριθμό. Στην πραγματικότητα, οποιοσδήποτε πρώτος αριθμός, μεγαλύτερος του max(p, q) μας κάνει. Ο λόγος που πρέπει το d να είναι πρώτος ως προς το φ(n) είναι επειδή έτσι είναι εγγυημένο ότι υπάρχει ένας άλλος αριθμός e τέτοιος, ώστε e*d ≡ 1 (mod φ(n)). Αυτό είναι το πολλαπλασιαστικό αντίστροφο του d (mod φ(n)):

Έτσι, έχουμε όλους τους απαιτούμενους αριθμούς για να σχηματίσουμε το ζεύγος κλειδιών. Το ιδιωτικό κλειδί θα είναι (d, n) και το δημόσιο κλειδί (e, n).
3. Η σχέση μεταξύ δημόσιου και ιδιωτικού κλειδιού
Με την κρυπτογράφηση και την αποκρυπτογράφηση έχουμε:

Από την αντιμεταθετική ιδιότητα, η σειρά των e και d δεν παίζει ρόλο, επομένως η αποκρυπτογράφηση και η κρυπτογράφηση λειτουργούν και με τα δύο κλειδιά, γι’ αυτό ο RSA είναι μία “μονόδρομη συνάρτηση καταπακτής.” Αποδεικνύοντας ότι το Μ υψωμένο στη δύναμη ed ή de ταυτίζεται με το M modulo n, θα αποδείκνυε την ιδιότητα της αντιμετάθεσης.

Αφού εξ ορισμού ισχύει: e*d ≡ 1 (mod φ(n)) ≡ k*φ(n)+1, μπορούμε επίσης να εκφράσουμε το Μ εις την e*d ως εξής:

Εφαρμόζοντας το θεώρημα Euler στο τελευταίο βήμα, έχουμε:

Και έτσι, η διαδικασία αποκρυπτογράφησης λειτουργεί όταν το e πολλαπλασιάζεται επί d και αντιστρόφως:

Πηγές:
[1] Chip and PIN is broken: Murdoch, S. J., Drimer, S., Anderson, R., Bond, M. IEEE Symposium on Security and Privacy (2010)
[2] Biometric Technology in Machine Readable Documents — the ICAO Blueprint | International Civil Aviation Organization
[3] Google HTTPS Transparency Report | Google
[4] New Directions in Cryptography | Diffie, W., and Hellman, M. IEEE Trans. Inform. Theory IT-22, (Nov. 1976)
[5] A Method for Obtaining Digital Signatures and Public-Key Cryptosystems | Rivest, R., Shamir, A., and Adleman, L.
Επιμέλεια – Μετάφραση : Χρήστος Κ. Λοΐζος, Χρήστος Κατσανδρής