Εισαγωγή

Ο σύγχρονος τρόπος ζωής επιβάλλει σε πολλούς από εμάς να χρησιμοποιούμε καθημερινά εφαρμογές όπως το email, το facebook. το online banking και γενικά τις αγορές μέσω internet ή ακόμα να δημιουργούμε λογαριασμούς σε ιστοσελίδες με το προσωπικό μας όνομα και κωδικό. Χωρίς την κρυπτογράφηση δεδομένων όλα τα παραπάνω και πολλά άλλα ακόμη θα ήταν αδύνατα!

Η κρυπτογράφηση είναι σαν το λουκέτο το οποίο κρατάει ασφαλή την ψηφιακή μας ταυτότητα. Η ρίζες της κρυπτογραφίας πάνε πίσω μέχρι το 1900 π.χ. Η πρώτη αναφορά γίνεται σε πολιτισμούς που αναπτύχθηκαν στην Μεσοποταμία και βασιζόταν κυρίως σε απλές αντικαταστάσεις γραμμάτων. Για παράδειγμα κάθε γράμμα της αλφαβήτου αντικαθιστώταν από το μεθεπόμενο του, το Α στο Γ το Β στο Δ το Γ στο Ε κ.ο.κ.

Η πρώτη στρατιωτική χρήση της κρυπτογραφίας αποδίδεται στους Σπαρτιάτες. Γύρω στον 5ο π.Χ. αιώνα εφηύραν την «σκυτάλη», την πρώτη κρυπτογραφική συσκευή, στην οποία χρησιμοποίησαν για την κρυπτογράφηση τη μέθοδο της μετάθεσης. Όπως αναφέρει ο Πλούταρχος, η «Σπαρτιατική Σκυτάλη» Σχήμα (2.1), ήταν μια ξύλινη ράβδος, ορισμένης διαμέτρου, γύρω από την οποία ήταν τυλιγμένη ελικοειδώς μια λωρίδα περγαμηνής. Το κείμενο ήταν γραμμένο σε στήλες, ένα γράμμα σε κάθε έλικα, όταν δε ξετύλιγαν τη λωρίδα, το κείμενο ήταν ακατάληπτο εξαιτίας της αναδιάταξης των γραμμάτων. Το «κλειδί» ήταν η διάμετρος της σκυτάλης. (Wikipedia)

Η σύγχρονη ψηφιακή ζωή απαιτεί νέους τρόπους κρυπτογραφίας τον δεδομένων και ο πιο διαδεδομένος απο αυτούς είναι ο αλγόριθμος RSA το όνομα του οποίου προέρχεται από τους δημιουργούς του Ron Rivest, Adi Shamir και Len Adleman του πανεπιστημίου MIT.

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

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

Το βασικό πρόβλημα με αυτή τη μέθοδο είναι η αποστολή του κλειδιού χωρίς την υποκλοπή του. Ας πούμε λοιπόν ότι η Αλίκη στέλνει ένα μύνημα στον Βαγγέλη μέσω ταχυδρομείου σε ένα κλειδωμένο κουτί. Ο Βαγγέλης θα λάβει το κουτί αλλά χρειάζεται και το κλειδί του λουκέτου για να δει το περιεχόμενο του. Η Αλίκη λοιπόν στέλνει με ένα φάκελο και το κλειδί. Κάποιος κακόβουλος όμως ο οποίος έχει πρόσβαση στην αλληλογραφία σας θα μπορούσε να αντιγράψει το κλειδί και να αποκτήσει και αυτός πρόσβαση. Κάτι αντίστοιχο θα μπορούσε να γίνει μέσω internet με την χρήση κακόβουλων λογισμικών (spyware, malware).

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

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

Όπως και στο προηγούμενο παράδειγμα ας πούμε ότι η Αλίκη θέλει να στείλει ένα μύνημα στον Βαγγέλη. Αυτή τη φορά όμως η Αλίκη και ο Βαγγέλης έχουν ο καθένας από ένα λουκέτο και ένα κλειδί. Η διαδικασία έχει ως εξής:

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

Στη συνέχεια θα παρουσιάσουμε τον τρόπο με τον οποίο εφαρμόζεται στην πραγματικότητα ο αλγόριθμος RSA. Για να γίνει αυτό όμως χρειάζονται (ως συνήθως) πρώτα να γνωρίζουμε κάποια Μαθηματικά.

Μαθηματικό υπόβαθρο

Πρώτοι αριθμοί:

Πρώτοι αριθμοί ονομάζονται οι φυσικοί αριθμοί που διαιρούνται με τον εαυτό τους και την μονάδα. Αν ένας αριθμός δεν είναι πρώτος τότε ονομάζεται σύνθετος. Δυο αριθμοί που δεν έχουν κοινούς διαιρέτες (παρά μόνο το 1) ονομάζονται πρώτοι μεταξύ τους ή σχετικά πρώτοι για παράδειγμα το 4 δεν είναι πρώτος (αφου διαρείται με το 2) ούτε το 9 (αφού διαιρείται με το 3), ωστόσο είναι μεταξύ τους πρώτοι αφου ο μοναδικός αριθμός που διαιρεί και τους δυο είναι το 1.

Οι πρώτοι αριθμοί παίζουν πολύ σημαντικό ρόλο στον αλγόριθμο RSA και αυτός είναι ένας από τους λόγους που οι Μαθηματικοί συνεχώς ψάχνουν όλο και μεγαλύτερους πρώτους αριθμούς. Ο μεγαλύτερος πρώτος αριθμός που γνωρίζουμε, ανακαλύφθηκε το 2016 από το Great Internet Mersenne Prime Search και συγκεκριμένα από τον καθηγητή Curtis Cooper έναν από τους χιλιάδες εθελοντές του GIMPS. Ο αριθμός αυτός είναι ο $2^{\mathrm{74.207.281}}-1$και είναι ασύλληπτα μεγάλος. Για την ακρίβεια έχει 22.338.618 ψηφία σχεδόν 5 εκατομμύρια ψηφία περισσότερα από τον προηγούμενο μεγαλύτερο πρώτο αριθμό.

Προς το παρόν δεν έχει κάποια πρακτική αξία μιας και στην πράξη οι πρώτοι αριθμοί που χρειάζονται στην κρυπτογραφία είναι πολύ μικρότεροι, της τάξης των μερικών εκατοντάδών ψηφίων. Η ασφάλεια του αλγορίθμου RSA έγκειται στο γεγονός ότι η ανάλυση ενός αριθμού σε γινόμενο πρώτων παραγόντων είναι μια ιδιαίτερα χρονοβόρα διαδικασία για τους υπολογιστές. Για παράδειγμα ο RSA-768 έχει πρώτους αριθμούς που αποτελούνται από 232 ψηφία και τον Δεκέμβριο του 2009 ερευνητές κατάφεραν να τον σπάσουν δηλαδή να παραγοντοποιήσουν τον πρώτο αριθμό. Χρειάστηκαν 2 χρόνια για να το καταφέρουν με μια συστοιχία υπερυπολογιστών. Ο αντίστοιχος χρόνος αν το προσπαθούσαν σε έναν απλό υπολογιστή αντιστοιχεί σε 2000 χρόνια. Στην παρακάτω εφαρμογή μπορείτε να εισάγεται έναν αριθμό (με μέγιστο τον $2^{52}$ ) και να δείτε την ανάλυση του σε γινόμενο πρώτων παραγόντων.

Συνάρτηση του Euler

Η συνάρτηση του Euler συμβολίζεται με $\phi \left(n\right)$

και ουσιαστικά μετράει πόσο είναι το πλήθος των αριθμών που είναι μικρότεροι από το n και σχετικά πρώτοι με το n. Για παράδειγμα το $\phi \left(12\right)=4$ γιατί οι αριθμοί που είναι σχετικά πρώτοι με το 12 είναι οι εξής τέσσερις 1, 5, 7 και 11. Για ένα πρώτο αριθμό p όμως ισχύει $\phi \left(p\right)=p-1$ αφού ο p είναι σχετικά πρώτος με τους 1, 2, 3 ,… , p – 1. Επομένως αν έχουμε έναν αριθμό n οποίος ισούται με το γινόμενο δυο πρώτων $n=p\cdot q$

τότε η τιμή της συνάρτησης φ υπολογίζεται πολύ εύκολα ως εξής:

$$\phi \left(n\right)=\phi \left(p\cdot q\right)=\phi \left(p\right)\phi \left(q\right)=\left(p-1\right)\left(q-1\right)$$

Ισοϋπόλοιποι αριθμοί

Αν κάνουμε τη διαίρεση του 8 με το 3 θα δούμε ότι το 3 χωράει 2 φορές στο 8 και περισεύουν 2. Μαθηματικά αυτό συμβολίζεται ως εξής:

Η παραπάνω σχέση διαβάζεται ως «το 8 είναι ισότιμο του 2 μόντουλο 3» και όπως είπαμε δεν είναι τίποτα άλλο από το υπόλοιπο της διαίρεσης του 8 με το 3. Επίσης το 3 χωράει 4 φορές στο 12 και περισσεύουν 2 δηλαδή:

$$12\equiv 2mod3$$

Οπότε οι αριθμοί 8 και 12 αν διαιρεθούν με το 3 δίνουν υπόλοιπο 2. Οι αριθμοί αυτόι λέγονται ισοϋπόλοιποι.

Αριθμητικό παράδειγμα

• Επιλέγουμε 2 πρώτους αριθμούς τους $p=11$και $q=13$

Βρίσκουμε το γινόμενο αυτών των δυο πρώτων αριθμών το οποίο θα συμβολίζουμε με n $n=p\cdot q=11\cdot 13=143$

• Υπολογίζουμε την τιμή της συνάρτησης Euler για τον αριθμό n.

$$\phi \left(n\right)=\phi \left(11\cdot 13\right)=\left(11-1\right)\left(13-1\right)=120$$

• Παράγουμε το δημόσιο κλειδί e

Για το δημόσιο κλειδί επιλέγουμε έναν τυχαίο πρώτο αριθμό ο οποίος όμως είναι σχετικά πρώτος με το $\phi \left(n\right)=120$και μικρότερος του 120. Ένας τέτοιος αριθμός είναι ο $e=7$

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

• Παράγουμε το ιδιωτικό κλειδί d

Ψάχνουμε ένα αριθμό d τέτοιον ώστε όταν τον πολλαπλασιάσουμε με τον e = 7 να προκύπτει ένα νέος αριθμός ο οποίος όταν διαιρεθέι με τον $\phi \left(n\right)=120$

να δίνει υπόλοιπο 1. (Ο αριθμός αυτός ονομάζεται αντίστροφος του e). Δηλαδή θέλουμε να ισχύει: $$e\cdot d\equiv 1mod120\iff 7d\equiv 1mod120$$

Αυτό είναι μια σχετικά απλή διαδικασία για τους υπολογιστές και μπορεί να γίνει πολύ γρήγορα με τη χρήση του διευρυμένου Ευκλείδειου Αλγορίθμου. Εδώ αυτός ο αριθμός είναι ο $d=103$

. Όντως αν υπολογίσουμε το γινόμενο των δύο αριθμών θα βρούμε $e\cdot d=7\cdot 103=721$ και αν κάνουμε τη διαίρεση του 721 με το 120 θα βρούμε υπόλοιπο 1 δηλαδή $721\equiv 1mod120$ Για παράδειγμα ας πούμε ότι θέλουμε να στείλουμε τον κωδικό $m=123$

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

$m^{e}modn={123}^{7}mod143=7=c$

Άρα ο κωδικός μας $m=123$

μετά την κρυπτογράφηση έγινε $c=7$

• Για την αποκωδικοποίηση υπολογίζουμε:

$c^{d}modn=7^{103}mod143=123$

Το παραπάνω παράδειγμα παρόλο του ότι έχει πολύ απλό τελικά περιέχει αρκετά μεγάλους υπολογισμούς όπως το $7^{103}$

, οι οποίοι βέβαια δεν αποτελούν πρόβλημα για τους σύγχρονους υπολογιστές. Στην πραγματικότητα όμως τα πράγματα δεν είναι τόσο απλά.

Ένα πιο ρεαλιστικό παράδειγμα κρυπτογράφησης

Ας υποθέσουμε ότι θέλουμε να κρυπτογραφήσουμε το μήνυμα «ΕΠΑΝΑΣΤΑΣΗ». Το πρώτο πράγμα που πρέπει να κάνουμε είναι να μετατρέψουμε το μήνυμα σε μια ακολουθία αριθμών. Αυτό μπορεί να γίνει πολύ εύκολα αν για παράδειγμα αντιστοιχίσουμε το Α στο 01 το Β στο 02 το Γ στο 03 κ.ο.κ. Για το παράδειγμα μας θα μετατρέψουμε το μήνυμα σε αριθμό χρησιμοποιώντας διεθνές πρότυπο Unicode.Τα ελληνικά γράμματα στο πρότυπο αυτό αντιστοιχούν στους αριθμούς 913, 914 κ.ο.κ. όπως φαίνεται παρακάτω.

Αλφάβητο	Α	Β	Γ	Δ	…	Ψ	Ω
Unicode	913	914	915	916	…	936	937

Επομένως το μήνυμα «ΕΠΑΝΑΣΤΑΣΗ» γίνεται ο αριθμός 91792891392591393193291931919.

Στη συνέχεια επιλέγουμε τους 2 πρώτους αριθμούς που θα χρησιμοποιήσουμε. Στη σελίδα https://primes.utm.edu/ μπορούμε να βρούμε αρκετούς τέτοιους. Στο συγκεκριμένο παράδειγμα έχουμε επιλέξει 2 πρώτους αριθμούς με 100 ψηφία ο καθένας.

p=5202642720986189087034837832337828472969800910926501361967872059486045713145450116712488685004691423

q=7212610147295474909544523785043492409969382148186765460082500085393519556525921455588705423020751421

Στη συνέχεια υπολογίζουμε το $n=p\cdot q$

n=37524633682137927643384006809428092248970535919594963918431761220678751467928743370786884566081463315401580247913150472980540804607232056904293306860771732520853697288023673304981074821955667693762083

Και το $\phi \left(n\right)$

φ(n)=37524633682137927643384006809428092248970535919594963918431761220678751467928743370786884566081463302986327379631486476401179187225911173965110247747504910470481552408458403633609502520761559668319240

Για το δημόσιο κλειδί επιλέγουμε τον αριθμό e = 65537. Για τον υπολογισμό του ιδιωτικού κλειδιού d χρησιμοποιούμε τον διευρυμένο αλγόριθμο του Ευκλείδη και βρίσκουμε ότι:

d=18244998280075759713695032988730429520933917131969628229257184053236010429613033973329936931781830540758034727740929804088126932892162588437039199909581518411613205784450417806505741761509789871843273

Κωδικοποίηση

Για την κωδικοποίηση του μηνύματος υπολογίζουμε το:

91792891392591393193291931919⁶⁵⁵³⁷ mod n

Το οποίο μας δίνει ως αποτέλεσμα το παρακάτω κωδικοποιημένο μήνυμα.

119537422567696647546527636138701563622174143698678275294011502792672525551731623761205193567854991665156778701044528312422568872387757142010477951978866186680

Στο σημείο αυτό να τονίσουμε ότι οι αριθμοί που προκύπτουν είναι εξαιρετικά μεγάλοι. Για παράδειγμα ο υπολογισμός του 91792891392591393193291931919⁶⁵⁵³⁷ δίνει ως αποτέλεσμα έναν αριθμό με 1.898.136 ψηφία. Αν θέλαμε απλά να γράψουμε τον αριθμό αυτό με ρυθμό 1 νούμερο ανά δευτερόλεπτο, θα χρειαζόμασταν περίπου 9 ώρες! Ωστόσο ο παραπάνω υπολογισμός χρείαστηκε λιγότερο από ένα δευτερόλεπτο στο mathematica.

Αποκωδικοποίηση

119537422567696647546527636138701563622174143698678275294011502792672525551731623761205193567854991665156778701044528312422568872387757142010477951978866186680^d mod n

Το οποίο μας δίνει σαν αποτέλεσμα τον αριθμό 91792891392591393193291931919 που αντιστοιχεί στα μήνυμα «ΕΠΑΝΑΣΤΑΣΗ».

Συντάκτης: Π. Γκριμπαβιώτης

Πηγή: maThink