Η μαθηματική σχέση μεταξύ δημοσίων και ιδιωτικών κλειδιών

Πορτοφόλια κρυπτονομισμάτων, αποστολή και λήψη e-mails, «έξυπνα τηλέφωνα» που τρέχουν μόνο πιστοποιημένες εφαρμογές, πληρωμές με πιστωτικές κάρτες [1] ακόμα και βιομετρικά δεδομένα σε διαβατήρια [2]. Τα συστήματα κρυπτογράφησης δημοσίου κλειδιού χρησιμοποιούνται σε ένα ευρύ φάσμα εφαρμογών.

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

Οι εφευρέτες των συστημάτων κρυπτογραφίας δημοσίου κλειδιού: Martin Hellman (αριστερά) και Whitfield Diffie (δεξιά) το 1977 – η φωτογραφία είναι ιδιοκτησία της Stanford News Service.

Με απλά λόγια, ένα κρυπτοσύστημα δημοσίου κλειδιού είναι μία μέθοδος όπου κάθε τερματική συσκευή έχει το δικό της ζεύγος κλειδιών. Εάν πρόκειται για ένα καλό σύστημα, δεδομένα που έχουν κρυπτογραφηθεί με το δημόσιο κλειδί μίας συσκευής μπορούν να αποκρυπτογραφηθούν μόνο με το αντίστοιχο ιδιωτικό κλειδί και αντίστροφως. Αυτά τα κρυπτογραφικά συστήματα μπορούν να υποδιαιρεθούν στην οικογένεια των μονόδρομων συναρτήσεων καταπακτής. Συγκεκριμένα, οι συναρτήσεις εν γένει επιτρέπουν μόνο την αποκρυπτογράφηση κρυπτογραφημένων δεδομένων, ενώ οι συναρτήσεις “καταπακτής” λειτουργούν αμφίδρομα, τα δεδομένα δηλαδή μπορούν να κρυπτογραφηθούν και με τα δύο κλειδιά και μετά να αποκρυπτογραφηθούν με το άλλο, αντιστοίχως. Καλούνται δε “μονόδρομες” (one-way) συναρτήσεις επειδή είναι εύκολο να υπολογιστούν προς τη μία κατεύθυνση, αλλά πολύ δύσκολο προς την αντίθετη (αντίστροφη συνάρτηση), εκτός και αν είναι γνωστή η ιδιωτική πληροφορία, η λεγόμενη “καταπακτή” [4].

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

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

Ασύμμετρη κρυπτογράφηση ή Κρυπτογράφηση δημοσίου κλειδιού

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

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

Ακόμα και αν υπάρχουν άτομα που κατασκοπεύουν την κίνηση δεδομένων, δεν μπορούν να διαβάσουν το μήνυμα χωρίς το ιδιωτικό κλειδί του παραλήπτη. Όπως τα προγράμματα “hello world” στον προγραμματισμό, έτσι και οι Alice και Bob είναι τα στάνταρ ονόματα για παραδείγματα στην κρυπτογραφία.

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

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

Το μήνυμα μπορεί να αποκρυπτογραφηθεί μόνο με το δημόσιο κλειδί του Bob και το ιδιωτικό κλειδί της Alice. Οποιοσδήποτε μπορεί να πιστοποιήσει την αυθεντικότητα του μηνύματος με το δημόσιο κλειδί του Bob, αλλά μόνο η Alice μπορεί να διαβάσει το πραγματικό μήνυμα.

Υπάρχουν πολλές διαφορετικές υλοποιήσεις τέτοιων συστημάτων ασύμμετρης κρυπτογράφησης, και η σχέση μεταξύ των κλειδιών είναι πάντα βασισμένη σε διαφορετικά μαθηματικά προβλήματα, ώστε να διασφαλίζεται ότι το δημόσιο κλειδί δεν θέτει σε κίνδυνο το ιδιωτικό. Το άρθρο αυτό εστιάζει στον 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 και ο κύκλος επαναλαμβάνεται.

Η πρόσθεση δύο ωρών στις 11 η ώρα “ταυτίζεται με το 1 modulo 12”.

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

Κρυπτογράφηση μηνύματος Μ για τη λήψη του κρυπτογραφημένου μηνύματος C.

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

Αποκρυπτογράφηση του κρυπτογραφημένου μηνύματος C για τη λήψη του μηνύματος Μ.

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

Αφού τα C, M και S βρίσκονται στο ίδιο διάστημα, μπορεί κανείς να τα φανταστεί σε ένα ρολόι όπως αυτό. Όπου S είναι η υπογραφή (το μήνυμα που έχει κρυπτογραφηθεί με το ιδιωτικό κλειδί), C είναι το κρυπτογραφημένο κείμενο (το μήνυμα που έχει κρυπτογραφηθεί με το δημόσιο κλειδί) και Μ είναι το μήνυμα που αποκρυπτογραφείται και με τους δύο τρόπους.

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)):

Όπου k είναι ένας ακέραιος (οποιοσδήποτε ακέραιος λειτουργεί, αφού ο πολλαπλασιασμός οποιουδήποτε ακεραίου με τον παράγοντα φ(n) πάντα έχει ως αποτέλεσμα έναν αριθμό που διαιρείται ακριβώς με το φ(n)).

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

3. Η σχέση μεταξύ δημόσιου και ιδιωτικού κλειδιού

Με την κρυπτογράφηση και την αποκρυπτογράφηση έχουμε:

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

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

Θεώρημα Euler: