▪ Η χρήση της θεωρίας των πρώτων αριθμών στην κωδικοποίηση

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

Ας δούμε αρχικά έναν απλό τρόπο κωδικοποίησης. ’Έστω ότι έχουμε ένα αλφάβητο με m γράμματα (εδώ για ευκολία θα θεωρήσουμε ότι $m=3$) και μια λέξη π.χ. ΓΑΤΑ. Αντιστοιχούμε σε κάθε γράμμα έναν αριθμό

στο Α τον αριθμό $1$

στο Γ τον αριθμό $2$

στο Τ τον αριθμό $3$

Έτσι η λέξη ΓΑΤΑ μεταφράζεται στην ακολουθία αριθμών $2,1,3,1$.

Επιλέγουμε έναν αριθμό $n$ (με $n>m$) και ένα αριθμό $r$ σχετικά πρώτο με το $n$ (εδώ επιλέγουμε $η=5,r=3$).’Έστω $a$ ένας όρος της ακολουθίας, πολλαπλασιάζουμε τον $a$ με τον $r$  και παίρνουμε το υπόλοιπο του γινομένου $αr$ ως προς $n$. ’Έτσι στο συγκεκριμένο παράδειγμα η ακολουθία γίνεται $6,3,9,3$ αν πολλαπλασιαστεί με το $3$ και αν πάρουμε το υπόλοιπο ως προς $5$ έχουμε $1,3,4,3$.

Αν θέλουμε να αποκωδικοποιήσουμε το μήνυμα αρκεί να βρούμε έναν αριθμό $p$ τέτοιο που το γινόμενο $pr$ να έχει υπόλοιπο ένα όταν διαιρεθεί με το $n$ (επειδή $(n,r)=1$ δηλ. είναι σχετικά πρώτοι ένας τέτοιος αριθμός σίγουρα υπάρχει).

Για το παράδειγμα μας είναι $p=2$ αφού

$pr=23=6=5+1$.

Τώρα αν πολλαπλασιάσουμε κάθε όρο της κωδικοποιημένης ακολουθίας με το p και πάρουμε το υπόλοιπο το γινομένου ως προς $n$ έχουμε την αρχική ακολουθία.

Έτσι η ακολουθία $1,3,4,3$ γίνεται $2,6,8,6$ όταν πολλαπλασιαστεί με το $2$ και παίρνοντας τα υπόλοιπα ως προς $5$ έχουμε $2,1,3,1$ που αντιστοιχεί στη λέξη ΓΑΤΑ.

Το πρόβλημα είναι όμως ότι αυτός που κάνει την κωδικοποίηση ξέρει αυτόματα πως να αποκωδικοποιήσει τα μηνύματα.Το πρόβλημα αυτό αντιμετωπίζεται με τη χρήση μιας μεθόδου χάρη στην οποία είναι πρακτικά αδύνατα σε όποιον κάνει την κωδικοποίηση να κάνει και την αποκωδικοποίηση. Τη μέθοδο αυτή επινόησαν οι Ronald L.Rivest,Adi Shamip,Leonard Adleman και παρουσιάστηκε σε μια εργασία τους το $1977$.

Διαβάστε περισσότερα εδώ.