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

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

Ας δούμε αρχικά έναν απλό τρόπο κωδικοποίησης. ’Έστω ότι έχουμε ένα αλφάβητο με 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.

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

• Επιλέγουμε 2 πρώτους αριθμούς p,q και υπολογίζουμε το γινόμενό τους m=pq και εδώ θέλουμε το m να είναι μεγαλύτερο από το πλήθος των γραμμάτων που έχουμε (για το ίδιο παράδειγμα επιλέγουμε p=3, q=5)

• Μετά βρίσκουμε 2 αριθμούς c,d τέτοιους ώστε το γινόμενο τους να αφήνει υπόλοιπο 1 όταν διαιρεθεί με τον (p-1)(q-1)

{εδώ (p-1)(q-1)=(3-1)(5-1)=8 άρα αν c=d=3 τότε cd= q= 8+1= (p-1)(q-1)+1}

Τώρα μπορούμε να ανακοινώσουμε τους αριθμούς m και c . Όποιος θέλει να κωδικοποιήσει ένα μήνυμα αρκεί να το μετατρέψει σε μαι ακολουθία αριθμών , κάθε όρο της να τον υψώσει στην c και να πάρει το υπόλοιπο του ως προς m.

Για το συγκεκριμένο παράδειγμα έχουμε την ακολουθία: 2,1,3,1

υψώνοντας κάθε φορά στην 3 παίρνουμε: 8,1,27,1

και άρα τα υπόλοιπα ως προς 15 είναι η ακολουθία: 8,1,12,1

• Για την αποκωδικοποίηση αρκεί να υψώσουμε κάθε όρο της κωδικοποιημένης ακολουθίας στην d=3 και αν πάρουμε το υπόλοιπο του ως προς n=15 έτσι έχουμε διαδοχικά :

512, 1, 1758, 1 αν υψώσουμε στην 3 και

2, 1, 3, 1 αν πάρουμε το υπόλοιπο ως προς 15.

Το σημαντικό στην παραπάνω διαδικασία είναι ότι αν τα p,q είναι μεγάλα τότε είναι πολύ δύσκολο να βρεθούν αν γνωρίζουμε μόνο το n και επομένως είναι πολύ δύσκολο να υπολογιστεί και ο αριθμός d που είναι απαραίτητος για την αποκωδικοποίηση. Ο Rivest υπολόγισε ότι αν ο n είναι ένας αριθμός με 125 ή 126 ψηφία ο οποίος προέκυψε από 2 πρώτους με 63 ψηφία τότε για να αναλυθεί ο n σε γινόμενο πρώτων παραγόντων θα χρειαζόντουσαν περίπου 10 τετράκις εκατομμύρια χρόνια.

Σχεδιάγραμα κρυπτογράφησης δημοσίου κλειδειού. Εικόνα από το wikimedia commons.

Παράρτημα

Ορισμός: γράφοντας a =b modn εννοούμε ότι ο a όταν διαιρεθεί με το n αφήνει το ίδιο υπόλοιπο με τον b

Ισχύει ότι αν (r,n)=1 δηλαδή είναι σχετικά πρώτοι τότε υπάρχει k ώστε : rk=1 modn

Άρα αν a είναι ένας αριθμός που αντιστοιχεί σ’ ένα γράμμα μιας λέξης για να τον κωδικοποιήσουμε τον πολλαπλασιάζουμε μ’ έναν αριθμό r τέτοιο ώστε (r,n)=1. Για να κάνουμε την αποκωδικοποίηση αρκεί να πολλαπλασιάσουμε με τον αντίστοιχο αριθμό k έτσι έχουμε:

(ar) k=a(rk)=a1=amodn 

Επίσης από το θ.Fermat έχουμε ότι αν (a,n)=1 τότε a^φ(n)=1modn, όπου φ(n) η συνάρτηση του Euler (αν n=pq όπου p,q πρώτοι τότε φ(n)= (p-1)(q-1))

Επομένως αν n=pq και cd=λφ(n)+1 τότε για να κωδικοποιήσουμε τον όρο a τον υψώνουμε στην c και παίρνουμε b=a^cmod, ενώ για να τον αποκωδικοποιήσουμε υψώνουμε τον b στην d:

 b^d=(a^c)^d= a^cd =a^λφ(n)+1=a^λφ(n) a=(a^φ(n))^λa=1^λa=1a=amodn