Πως κωδικοποιούνται τα μηνύματα που στέλνουμε μέσω υπολογιστή και τι ρόλο παίζουν τα Μαθηματικά σε αυτό;

Εισαγωγή

Ο σύγχρονος τρόπος ζωής επιβάλλει σε πολλούς από εμάς να χρησιμοποιούμε καθημερινά εφαρμογές όπως το 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. Ο αριθμός αυτός είναι ο 274.207.2811 και είναι ασύλληπτα μεγάλος. Για την ακρίβεια έχει 22.338.618 ψηφία σχεδόν 5 εκατομμύρια ψηφία περισσότερα από τον προηγούμενο μεγαλύτερο πρώτο αριθμό.

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

Ανάλυση σε γινόμενο πρώτων παραγόντων :


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

Η συνάρτηση του Euler συμβολίζεται με φ(n)

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

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

φ(n)=φ(pq)=φ(p)φ(q)=(p1)(q1)

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

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

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

122mod3

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

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

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

Βρίσκουμε το γινόμενο αυτών των δυο πρώτων αριθμών το οποίο θα συμβολίζουμε με n n=pq=1113=143

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

φ(n)=φ(1113)=(111)(131)=120

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

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

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

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

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

να δίνει υπόλοιπο 1. (Ο αριθμός αυτός ονομάζεται αντίστροφος του e). Δηλαδή θέλουμε να ισχύει: ed1mod1207d1mod120

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

. Όντως αν υπολογίσουμε το γινόμενο των δύο αριθμών θα βρούμε ed=7103=721 και αν κάνουμε τη διαίρεση του 721 με το 120 θα βρούμε υπόλοιπο 1 δηλαδή 7211mod120 Για παράδειγμα ας πούμε ότι θέλουμε να στείλουμε τον κωδικό m=123

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

memodn=1237mod143=7=c

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

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

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

cdmodn=7103mod143=123

Το παραπάνω παράδειγμα παρόλο του ότι έχει πολύ απλό τελικά περιέχει αρκετά μεγάλους υπολογισμούς όπως το 7103

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

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

Ας υποθέσουμε ότι θέλουμε να κρυπτογραφήσουμε το μήνυμα «ΕΠΑΝΑΣΤΑΣΗ». Το πρώτο πράγμα που πρέπει να κάνουμε είναι να μετατρέψουμε το μήνυμα σε μια ακολουθία αριθμών. Αυτό μπορεί να γίνει πολύ εύκολα αν για παράδειγμα αντιστοιχίσουμε το Α στο 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=pq

n=37524633682137927643384006809428092248970535919594963918431761220678751467928743370786884566081463315401580247913150472980540804607232056904293306860771732520853697288023673304981074821955667693762083

Και το φ(n)

φ(n)=37524633682137927643384006809428092248970535919594963918431761220678751467928743370786884566081463302986327379631486476401179187225911173965110247747504910470481552408458403633609502520761559668319240

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

d=18244998280075759713695032988730429520933917131969628229257184053236010429613033973329936931781830540758034727740929804088126932892162588437039199909581518411613205784450417806505741761509789871843273

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

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

9179289139259139319329193191965537 mod n

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

119537422567696647546527636138701563622174143698678275294011502792672525551731623761205193567854991665156778701044528312422568872387757142010477951978866186680

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

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

119537422567696647546527636138701563622174143698678275294011502792672525551731623761205193567854991665156778701044528312422568872387757142010477951978866186680d mod n

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

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

Πηγή: maThink

 

 

Posted in Χωρίς κατηγορία

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Translate
January 2018
M T W T F S S
« Dec   Feb »
1234567
891011121314
15161718192021
22232425262728
293031  
Pages
Blog Stats
  • 422,396 hits

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 2,979 other followers

Follow ΖΗΣΕ ΤΑ ΜΑΘΗΜΑΤΙΚΑ ΣΟΥ on WordPress.com
in search of Physics

ένα project για τη διδασκαλία της Φυσικής στη Δευτεροβάθμια εκπαίδευση

Joy of mathematics

Live Your Maths

Ο άγνωστος χ

Live Your Maths

%d bloggers like this: