Χαρίτος Χρυσοβαλάντης
Μαθηματικός

Ο αλγόριθμος RSA

Η σύγχρονη πολυπλοκότητα καθιστά απαραίτητη την ασφαλή μετάδοση πληροφοριών. Ο διεπιστημονικός κλάδος που ονομάζεται Κρυπτογραφία διαθέτει σύνολο μεθόδων για να επιτύχει το σκοπό αυτό ώστε κατά την αποστολή προσωπικών δεδομένων, η πιθανότητα να τα εντοπίσει ένας τρίτος κόμβος και να κατανοήσει το περιεχόμενό τους να είναι σχεδόν αδύνατη. Ιστορικά, οι Σπαρτιάτες, περίπου το 500 π.Χ. είχαν αναπτύξει για στρατιωτικούς σκοπούς έναν τρόπο για να κρυπτογραφούν τα μηνύματα που χρειαζόταν να διαβιβάσουν. Στην παρακάτω φωτογραφία βλέπουμε ένα υπόδειγμα από την περίφημη σκυτάλη των Λακεδαιμονίων.



Η λειτουργία της είναι ιδιαιτέρως απλή. Ο αποστολέας του μηνύματος τύλιγε στη σκυτάλη μια κενή λωρίδα (συνήθως κατασκευασμένη από δέρμα ή περγαμηνή) και έγραφε το μήνυμά του. Ξετυλίγοντάς την, προέκυπτε μια λωρίδα με γράμματα που φαίνονταν διάσπαρτα χωρίς να έχουν κάποια σύνδεση μεταξύ τους. Η λωρίδα θα έπρεπε να αποσταλεί στον παραλήπτη ο οποίος με τη σειρά του τύλιγε τη λωρίδα σε σκυτάλη της ιδίας διαμέτρου, έτσι ήταν σε θέση να διαβάσει το απεσταλμένο μήνυμα.

Στη συνέχεια θα αναπτύξουμε μια κλασική μέθοδο κρυπτογράφησης που λέγεται αλγόριθμος RSA. O αλγόριθμος με το όνομα RSA ήταν αντικείμενο έμπνευσης των Ron Rivest, Adi Shamir και Leonard Adleman οι οποίοι τον παρουσίασαν το 1977. O αλγόριθμος μπορεί να χρησιμοποιηθεί όχι μόνο στην κωδικοποίηση πληροφοριών αλλά και στη λεγόμενη ψηφιακή υπογραφή η οποία αξίζει μια περαιτέρω αναφορά.

Η ψηφιακή υπογραφή είναι ένα μαθηματικό μοντέλο με στόχο την απόδειξη της γνησιότητας ενός ψηφιακού εγγράφου. Μια έγκυρη υπογραφή πιστοποιεί ότι το περιεχόμενο του εγγράφου ανήκει σε εκείνον που το υπέγραψε και ότι δεν έχει τροποποιηθεί κατά την μεταφορά του και κάποιον πιθανό εντοπισμό από τρίτο άτομο. Σε χώρες των Η.Π.Α. και ορισμένες της Ε.Ε., οι ψηφιακές υπογραφές έχουν νομική ισχύ. Όταν αυτές παράγονται με χρήση ισχυρών αλγορίθμων της Κρυπτογραφίας τότε είναι ασύγκριτα δυσκολότερο να πλαστογραφηθούν σε σχέση με τις χειρόγραφες που χρησιμοποιεί ο πληθυσμός μέχρι σήμερα. Επιπλέον, εκείνος που ψηφιακά υπογράφει δεν μπορεί να ισχυριστεί εκ των υστέρων ότι δεν το έπραξε (με την υπόθεση ότι το ιδιωτικό κλειδί που χρησιμοποιήθηκε δεν υπεκλάπη). Σε ορισμένες περιπτώσεις ψηφιακών υπογραφών προστίθεται και η ημερομηνία της υπογραφής, ώστε ακόμη και αν το ιδιωτικό κλειδί (η έννοια του ιδιωτικού κλειδιού θα γίνει κατανοητή αν συνεχεία) υποκλαπεί, η εν λόγω υπογραφή να παραμένει σε ισχύ.

Διαιρετότητα και πρώτοι αριθμοί

Ορισμός Ι$.$ Ακέραιοι ονομάζονται οι αριθμοί $0, 1, 2, 3, 4, ...$ καθώς και οι αντίστοιχοι αρνητικοί: $-1, -2, -3, -4, ...$ (αρνητικοί ακέραιοι).
Το σύνολο των ακεραίων αριθμών συμβολίζεται με το γράμμα $\mathbb{Z}$, συμβολισμός ο οποίος επικράτησε από τη Γερμανική λέξη «zahl» που σημαίνει «αριθμός».

$\mathbb{Z}=\{...,-4, -3, -2, -1, 0, 1, 2, 3, 4, ...\}$

Ορισμός ΙI. Θεωρούμε έναν θετικό ακέραιο $m$. Λέμε ότι ο θετικός ακέραιος $n$ διαιρεί τον $m$ αν υπάρχει ακέραιος $λ$ τέτοιος ώστε $m = λn$. Αν ο $n$ διαιρεί τον $m$ τότε συμβολικά γράφουμε $n|m$. Mπορούμε ισοδύναμα να πούμε ότι ο αριθμός $n$ διαιρεί τον $m$ αν προσθέτοντας τον $n$ με τον εαυτό του, μπορούμε να πάρουμε ως άθροισμα τον αριθμό $m$. Για παράδειγμα, ο αριθμός $4$ διαιρεί το $16$ καθώς $4 + 4 + 4 = 12 = 3\cdot 4$. Συμβολικά γράφουμε $4|12$. Ισοδύναμα, λέμε ότι ο $n$ είναι διαιρέτης του $m$ αν, διαιρώντας τον $m$ με τον $n$, η διαίρεση είναι τέλεια με ακέραιο πηλίκο και μηδενικό υπόλοιπο.

Ορισμός III. Πρώτος ονομάζεται κάθε ακέραιος p, μεγαλύτερος του 1 που διαθέτει ακριβώς δυο θετικούς διαιρέτες: τον αριθμό 1 και τον αριθμό p. Αν ένας θετικός ακέραιος μεγαλύτερος του 1 δεν είναι πρώτος τότε ονομάζεται σύνθετος.

  1. O αριθμός 7 είναι πρώτος αριθμός επειδή οι μοναδικοί του διαιρέτες είναι το 1 και το 7. Προφανώς κανείς εκ των αριθμών 2, 3, 4, 5 και 6 δεν διαιρεί το 7.

  2. Ο αριθμός 12 διαιρείται από τους αριθμούς 1, 2, 3, 4, 6 και 12, δηλαδή εκτός του 1 και του 12, διαθέτει ακόμη τέσσερις διαιρέτες, συνεπώς δεν είναι πρώτος αλλά σύνθετος.

Ορισμός IV. Ο μεγαλύτερος από τους κοινούς διαιρέτες δυο θετικών ακεραίων ονομάζεται μέγιστος κοινός διαιρέτης.

Ας δούμε ένα παράδειγμα. Θεωρώ τον αριθμό 8 και τον αριθμό 12. Οι διαιρέτες του 8 είναι οι αριθμοί 1, 2, 4, 8 και οι διαιρέτες του 12 είναι οι αριθμοί 1, 2, 3, 4, 6, 12. Οι κοινοί διαιρέτες, δηλαδή εκείνοι οι αριθμοί που διαιρόυν τόσο τον αριθμό 8 όσο και τον αριθμό 12 είναι προφανώς οι αριθμοί 1, 2 και 4. Ο μεγαλύτερος από αυτούς είναι ο αριθμός 4, συνεπώς ο μέγιστος κοινός διαιρέτης των αριθμών 8 και 12 είναι ο αριθμός 4. Συμβολικά γράφουμε $\gcd(8,12) = 4$.
To αρκτικόλεξο gcd προέρχεται από τη φράση Greatest Common Divisor που μεταφράζεται ως Μέγιστος Κοινός Διαιρέτης.

Ορισμός V. Δυο θετικοί ακέραιοι ονομάζονται σχετικά πρώτοι αν ο μέγιστος κοινός διαιρέτης τους είναι ο αριθμός 1.
Για παράδειγμα, οι αριθμοί $7$ και $9$ έχουν ως διαιρέτες τους αριθμούς $1, 7$ και $1, 3, 9$ αντιστοίχως. Κοινός διαιρέτης είναι μόνο ο αριθμός $1$ που είναι και ο μέγιστος.
Παρατήρηση Ι. Επειδή ο αριθμός 1 είναι κοινός διαιρέτης δυο οποιωνδήποτε ακεραίων και είναι ο μικρότερος δυνατός διαιρέτης τους τότε (για να είναι σχετικά πρώτοι) θα πρέπει να μη διαθέτουν άλλον κοινό διαιρέτη.
Παρατήρηση ΙΙ. Αν δυο αριθμοί είναι πρώτοι τότε είναι και σχετικά πρώτοι. Πράγματι, εφόσον είναι πρώτοι, δεν μπορούν να έχουν (μέγιστο) κοινό διαιρέτη μεγαλύτερο της μονάδας καθώς τότε θα ήταν σύνθετοι.

Η συνάρτηση $\phi$ του Leonard Euler

Ορισμός VI. Θεωρώ τη συνάρτηση $\phi : \{1, 2, 3, ...\} \rightarrow \{1, 2, 3, ...\}$ η οποία απεικονίζει κάθε θετικό ακέραιο $n$ στο πλήθος των θετικών ακεραίων $p \leq n$ οι οποίοι είναι σχετικά πρώτοι με τον αριθμό $n$, δηλαδή $\gcd(p,n) = 1$. H εν λόγω συνάρτηση καλείται συνάρτηση $\phi$ του Euler.

Για να γίνει πιο κατανοητός, ας θεωρήσουμε τον αριθμό $8$. Η συνάρτηση Euler μας δίνει το πόσοι θετικοί ακέραιοι μικρότεροι του 8, είναι σχετικά πρώτοι με αυτόν. Θα αναζητήσουμε το πλήθος των θετικών ακεραιών στο σύνολο $\{1, 2, 3, ..., 8\}$ οι οποίοι είναι σχετικά πρώτοι με το $8$. Ο ίδιος ο αριθμός $8$ δεν είναι σχετικά πρώτος με τον εαυτό του αφού $\gcd(8,8) = 8$. Ο αριθμός $7$ είναι όμως τέτοιος επειδή $\gcd(7,8)=1$. Ο αριθμός $6$ δεν είναι σχετικά πρώτος με το $8$ αφού $\gcd(6,8) = 2$. Ομοίως o αριθμός $5$ είναι σχετικά πρώτος με το $8$. Ο αριθμός $4$ όμως όχι αφού $\gcd(4,8) = 4$. Συνεχίζοντας, ο αριθμός 3 και ο αριθμός 1 είναι σχετικά πρώτοι με το 8 ενώ ο αριθμός 2 όχι. Συνεπώς οι αριθμοί μεταξύ 1 και 8 που είναι σχετικά πρώτοι με το $8$ είναι οι αριθμοί $1, 3, 5, 7$ δηλαδή τέσσερις το πλήθος, επομένως $φ(8) = 4$.

Θεώρημα I. Αν ο θετικός ακέραιος $n$ είναι πρώτος αριθμός τότε $φ(n) = n-1$

Θεώρημα ΙI. Aν $m, n$ δυο θετικοί ακέραιοι και σχετικά πρώτοι ($\gcd(m, n) = 1$) τότε $φ(m\cdot n) = φ(m)\cdot φ(n)$

Η συνάρτηση Euler μετρά τους σχετικά πρώτους με τον $n$ που είναι μικρότεροι του $n$, ωστόσο μπορούμε να επεκταθούμε σε ολόκληρο το σύνολο των ακεραίων αριθμών.

Στην παρακάτω διάταξη, εμφανίζονται οι σχετικά πρώτοι με το 12, από 1 έως 100.
Παρατηρούμε ότι οι σχετικά πρώτοι με το 12 που είναι μικρότεροι από αυτόν, είναι τέσσερις, δηλαδή $φ(12)=4$.



Στην παρακάτω διάταξη, εμφανίζονται οι σχετικά πρώτοι με το 11 που είναι πρώτος αριθμός.
Παρατηρήστε ότι όλοι είναι σχετικά πρώτοι με το 11 εκτός από τα ακέραια πολλαπλάσιά του.
Όμοια, οι σχετικά πρώτοι με το 11 που είναι μικρότεροι από αυτόν, είναι 10, δηλαδή $φ(11)=10$ σε συμφωνία με το θεώρημα Ι.



Ευκλείδεια διαίρεση

Θεώρημα ΙΙΙ. Για κάθε δυο θετικούς ακεραίους $m$ και $n$ υπάρχουν μοναδικοί ακέραιοι $q$ και $r$ τέτοιοι ώστε $m = qn + r$ με $0 \leq r$ και $r \lt n$.
Οι αριθμοί $q$ και $r$ ονομάζονται αντιστοίχως πηλίκο και υπόλοιπο της Ευκλείδειας διαίρεσης.

Για παράδειγμα, θεωρώντας τους ακεραίους $13$ και $4$ τότε έχουμε $13 = 3\cdot 4 + 1$ με πηλίκο $3$ και υπόλοιπο $1$.
Σε ορισμένα βήματα του αλγορίθμου RSA θα χρειαστούμε τα υπόλοιπα Ευκλειδείων διαιρέσεων ακεραίων. Αναφερόμενοι στο υπόλοιπο της Ευκλείδειας διαίρεσης του $m$ με τον $n$ (δηλαδή στο $r$) γράφουμε συμβολικά: $r = m$ mod n.
Στο προαναφερθέν παράδειγμα, έχουμε 13 mod 4 $= 1$.

Παράδειγμα υλοποίησης του αλγορίθμου RSA

Πρέπει να στείλω σε έναν φερέγγυο παραλήπτη το PIN της πιστωτικής μου κάρτας το οποίο ας υποθέσουμε πως είναι το 6224. Εκείνος θα λάβει τον αριθμό 6224 σε κρυπτογραφημένη μορφή και θα ακολουθήσει μια αντίστροφη διαδικασία (αποκρυπτογράφησης) ώστε να μάθει το πραγματικό. Η κρυπτογράφηση θα πρέπει να είναι ισχυρή έτσι ώστε σε περίπτωση που πέσει στα χέρια τρίτου, να είναι σχεδόν αδύνατον να διενεργήσει αποκρυπτογράφηση και να μάθει το προσωπικό αυτό δεδομένο. Στην πράξη, για την κρυπτογράφηση RSA, χρησιμοποιούνται πρώτοι αριθμοί πολύ μεγάλου πλήθους ψηφίων όμως στο παρακάτω παράδειγμα μας ενδιαφέρει ο τρόπος και όχι η ασφάλεια της κρυπτογράφησης.

  1. Επιλέγουμε δυο πρώτους αριθμούς, για παράδειγμα $p = 101$ και $q = 127$ και υπολογίζουμε το γινόμενό τους: $pq = 12827$.

  2. Υπολογίζουμε την τιμή της συνάρτησης Euler (xρησιμοποιώντας το θεώρημα ΙΙΙ καθώς ως πρώτοι θα είναι και σχετικά πρώτοι (βλέπε Παρατήρηση ΙΙ)) για $n = 12827$, έτσι θα έχω $φ(12827) = φ(101)φ(127) \Rightarrow$
    $φ(12827) = 100\cdot 126 = 12600$ (βλέπε και Θεώρημα Ι).

  3. Επιλέγουμε έναν οποιονδήποτε ακέραιο μεγαλύτερο του 1 και μικρότερο του $φ(n)$, έστω $e$, έτσι ώστε να είναι σχετικά πρώτος με τον $φ(n)$. O αριθμός $e$ θα ονομάζεται δημόσιο κλειδί και η επιλογή του δεν επηρεάζει την ασφάλεια της κρυπτογράφησης. Εν προκειμένω ας επιλέξουμε $e = 4463$. Mπορεί σχετικά εύκολα να ελεγχθεί ότι ο μέγιστος κοινός διαιρέτης των αριθμών $e = 4463$ και $φ(n) = 12600$ είναι ο αριθμός 1 (σχετικά πρώτοι).

  4. Eπιλέγουμε έναν θετικό ακέραιο $d$ τέτοιον ώστε η Ευκλείδεια διαίρεση του $de$ με τον $φ(n)$ να έχει υπόλοιπο 1. O αριθμός $d$ θα ονομάζεται ιδιωτικό κλειδί. Eν προκειμένω επιλέγω $d = 8927$. Το ιδιωτικό αυτό κλειδί, $d$, το γνωρίζει μόνο ο αποστολέας και ο παραλήπτης.
    Το ιδιωτικό μας, λοιπόν, κλειδί είναι ο αριθμός $d = 8927$.

  5. Συνοπτικά μέχρι στιγμής:
    Πρώτοι αριθμοί: $p=101$ και $q=127$ με $φ(12827) = 12600$
    Δημόσιο κλειδί: $e = 4463$
    Ιδιωτικό κλειδί: $d = 8927$
    K = 6224 ο αριθμός για τον οποίο χρειάζομαι μια ισχυρή κρυπτογράφηση.

  6. Υπολογίζω την παράσταση $Κ^e$ mod n $=6224^{4463}$ mod 12827 = 12193. Ο αριθμός 12193 αποστέλλεται στον ενδιαφερόμενο και αποτελεί τον αριθμό PIN 6224 σε κρυπτογράφηση RSA.

    6224 $\rightarrow$ 12193


  7. O παραλήπτης, γνωρίζοντας το ιδιωτικό κλειδί $d$ και τον αριθμό $n$, δηλαδή το γινόμενο των δυο πρώτων παραγόντων, πραγματοποιεί αποκρυπτογράφηση υπολογίζοντας την παράσταση $12193^d$ mod 12827 $= 6224$ που είναι και ο αρχικός αριθμός ο οποίος κρυπτογραφήθηκε.

    12193 $\rightarrow$ 6224


Σχόλια και παρατηρήσεις

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

  2. O παραλήπτης δεν χρειάστηκε το δημόσιο κλειδί ώστε να αποκρυπτογραφήσει τον αριθμό 12193.

  3. Η ισχύς του αλγορίθμου RSA βασίζεται στη δυσκολία ανάλυσης μεγάλων αριθμών σε πρώτους παράγοντες. Στο απλό παράδειγμά μας χρησιμοποιήσαμε τους πρώτους αριθμούς 101 και 127 οι οποίοι είναι άνγωστοι τόσο στον παραλήπτη (δεν τους χρειάζεται καν για να αποκρυπτογραφήσει το μήνυμα, του αρκεί το γινόμενό τους) όσο και στον πιθανά κακόβουλο άνθρωπο ο οποίος μαθαίνει το δημόσιο κλειδί, δηλαδή τον αριθμό e και το γινόμενο των δυο πρώτων αριθμών (όχι όμως τους δυο πρώτους που το συγκροτούν). Στις πραγματικές εφαρμογές, ο RSA υλοποιείται με τη βοήθεια τεραστίων πρώτων αριθμών και η διαδικασία κρυπτογράφησης - αποκρυπτογράφησης διενεργείται σε υπολογιστικά συστήματα.

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

  5. Το παράδειγμά μας αφορούσε την RSA κρυπτογράφηση ενός αριθμού PIN. Σε περίπτωση που θέλουμε να στείλουμε ένα κρυπτογραφημένο μήνυμα της Ελληνικής ή άλλης γλώσσας τότε θα πρέπει αρχικά να χρησιμοποιήσουμε κάποια προσυμφωνημένη αντιστοίχηση γραμμάτων και αριθμών, ώστε να μετατρέψουμε τη λέξη ή φράση σε έναν αριθμό. Για παράδειγμα, μπορούμε να αντιστοιχίσουμε το γράμμα Α στο 01, το Β στο 02, το Γ στο 03 και ούτω καθεξής, έως το Ω στο 24. Έτσι, η λέξη «ΚΑΛΗΜΕΡΑ» γράφεται ως 1001110512051701 και έπειτα αναλαμβάνει ο αλγόριθμος RSA. Ο παραλήπτης λαμβάνει κρυπτογραφημένο τον παραπάνω αριθμό, πραγματοποιεί αποκρυπτογράφηση και τέλος, με βάση την αντιστοίχηση γραμμάτων και αριθμών καταλήγει στο αρχικό μήνυμα.

Κώδικας Wolfram Mathematica για την υλοποίηση του RSA

Μέσω του Wolfram cloud (σε περίπτωση που δεν έχετε εγκατεστημένη τη Mathematica) μπορείτε να τρέξετε κώδικα Wolfram.
Το μόνο που απαιτείται είναι η δημιουργία λογαριασμού μέσω της επιλογής sign up.

p = 101; q = 127;
n = p*q; phi = (p - 1)*(q - 1);
e = RandomChoice[Pick[Range[2, phi], CoprimeQ[phi, Range[2, phi]]]];
Do[If[Mod[e*ind, phi] == 1, d = ind], {ind, 2, phi}];
code = Input["Give a password:"]; Print["Given password: ", code];
encrypt = Mod[code^e, n]; Print["Encrypted password: ", encrypt];
decrypt = Mod[encrypt^d, n]; Print["Decrypted password: ", decrypt];




Ο παραπάνω κώδικας θα τρέξει με επιλεγμένους πρώτους αριθμούς το 101 και το 127. Μπορείτε να μεταβάλλετε τις δυο αρχικές συνθήκες καταχωρώντας δυο οποιουσδήποτε πρώτους αριθμούς στις μεταβλητές $p, q$.

Εδώ θα βρείτε όλους τους πρώτους αριθμούς έως το ένα εκατομμύριο.



web counter