Αλγόριθμος RSA

Η Alice δίνει το δημόσιο κλειδί της ( n {\displaystyle n\,} & e {\displaystyle e\,} ) στον Bob και κρατάει το ιδιωτικό της κλειδί μυστικό. Ο Bob θέλει να στείλει το μήνυμα M στην Alice.

Πρώτα μετατρέπει το M σε έναν αριθμό m {\displaystyle m} μικρότερο από το n {\displaystyle n} χρησιμοποιώντας ένα συμφωνημένο αντιστρεπτό πρωτόκολλο γνωστό ως σχήμα συμπλήρωσης. Στη συνέχεια υπολογίζει το κρυπτογράφημα c {\displaystyle c\,} που αντιστοιχεί σε:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

Αυτό μπορεί να γίνει γρήγορα με τη μέθοδο του τετραγωνισμού με εκθετικοποίηση. Στη συνέχεια, ο Bob στέλνει το c {\displaystyle c\,} στην Alice.

Η Alice μπορεί να ανακτήσει το m {\displaystyle m\,} από το c {\displaystyle c\,} χρησιμοποιώντας το ιδιωτικό της κλειδί d {\displaystyle d\,} με την ακόλουθη διαδικασία:

m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}

Με δεδομένο m {\displaystyle m\,} , μπορεί να ανακτήσει τους αρχικούς διακριτούς πρώτους αριθμούς, εφαρμόζοντας το κινεζικό θεώρημα υπολοίπων σε αυτές τις δύο συμπτώσεις προκύπτει

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}}} .

Έτσι,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Ένα παράδειγμα εργασίας

Ακολουθεί ένα παράδειγμα κρυπτογράφησης και αποκρυπτογράφησης RSA. Οι παράμετροι που χρησιμοποιούνται εδώ είναι τεχνητά μικρές, αλλά μπορείτε επίσης να χρησιμοποιήσετε το OpenSSL για να δημιουργήσετε και να εξετάσετε ένα πραγματικό ζεύγος κλειδιών.

1. Επιλέξτε δύο τυχαίους πρώτους αριθμούς.
2.  : p = 61 {\displaystyle p=61} και q = 53 ; {\displaystyle q=53;} Υπολογίστε n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Υπολογίστε την ολική τιμή ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,}
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}
6. Επιλέξτε e > 1 {\displaystyle e>1} coprime to 3120
7.  : e = 17 {\displaystyle e=17}
8. Επιλέξτε d {\displaystyle d\,} ώστε να ικανοποιεί d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}
9.  : d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

Το δημόσιο κλειδί είναι ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Για ένα γεμισμένο μήνυμα m {\displaystyle m\,} η συνάρτηση κρυπτογράφησης c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} γίνεται:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,}

Το ιδιωτικό κλειδί είναι ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Η συνάρτηση αποκρυπτογράφησης m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} γίνεται:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,}

Για παράδειγμα, για την κρυπτογράφηση m = 123 {\displaystyle m=123} , υπολογίζουμε

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}

Για την αποκρυπτογράφηση c = 855 {\displaystyle c=855} , υπολογίζουμε

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Και οι δύο αυτοί υπολογισμοί μπορούν να υπολογιστούν αποτελεσματικά χρησιμοποιώντας τον αλγόριθμο square-and-multiply για τον αρθρωτό πολλαπλασιασμό [en].

Το RSA μπορεί εύκολα να προκύψει χρησιμοποιώντας το θεώρημα του Euler και τη συνάρτηση του Euler.

Ξεκινώντας με το θεώρημα του Euler,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

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

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}

Αντικαθιστώντας στον αλγόριθμο αποκρυπτογράφησης, έχουμε

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}

Θέλουμε να δείξουμε ότι αυτή η τιμή είναι επίσης σύμφωνη με το m. Οι τιμές των e και d επιλέχθηκαν για να ικανοποιήσουν,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

Δηλαδή, υπάρχει κάποιος ακέραιος k, τέτοιος ώστε

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Τώρα αντικαθιστούμε το κρυπτογραφημένο και στη συνέχεια αποκρυπτογραφημένο μήνυμα,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}}

Εφαρμόζουμε το θεώρημα του Euler και επιτυγχάνουμε το αποτέλεσμα.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

Όταν χρησιμοποιείται στην πράξη, το RSA πρέπει να συνδυάζεται με κάποια μορφή σχήματος συμπλήρωσης, έτσι ώστε καμία τιμή του M να μην οδηγεί σε μη ασφαλή κρυπτογραφήματα. Ο RSA που χρησιμοποιείται χωρίς συμπλήρωση μπορεί να έχει κάποια προβλήματα:

• Οι τιμές m = 0 ή m = 1 παράγουν πάντα κρυπτογραφήματα ίσα με 0 ή 1 αντίστοιχα, λόγω των ιδιοτήτων του πολλαπλασιασμού.
• Κατά την κρυπτογράφηση με μικρούς εκθέτες κρυπτογράφησης (π.χ. e = 3) και μικρές τιμές του m, το (μη modulus) αποτέλεσμα του m e {\displaystyle m^{e}} μπορεί να είναι αυστηρά μικρότερο από το modulus n. Σε αυτή την περίπτωση, τα κρυπτογραφημένα κείμενα μπορούν εύκολα να αποκρυπτογραφηθούν παίρνοντας την ηθική ρίζα του κρυπτογραφημένου κειμένου χωρίς να λαμβάνεται υπόψη το modulus.
• Η κρυπτογράφηση RSA είναι ένας ντετερμινιστικός αλγόριθμος κρυπτογράφησης. Δεν έχει κανένα τυχαίο στοιχείο. Ως εκ τούτου, ένας επιτιθέμενος μπορεί να εξαπολύσει με επιτυχία μια επίθεση επιλεγμένου απλού κειμένου κατά του κρυπτοσυστήματος. Μπορούν να δημιουργήσουν ένα λεξικό κρυπτογραφώντας πιθανά πλασματικά κείμενα υπό το δημόσιο κλειδί και αποθηκεύοντας τα προκύπτοντα κρυπτοκείμενα. Ο επιτιθέμενος μπορεί στη συνέχεια να παρατηρήσει το κανάλι επικοινωνίας. Μόλις δουν κρυπτογραφήματα που ταιριάζουν με αυτά του λεξικού τους, οι επιτιθέμενοι μπορούν στη συνέχεια να χρησιμοποιήσουν αυτό το λεξικό προκειμένου να μάθουν το περιεχόμενο του μηνύματος.

Στην πράξη, τα δύο πρώτα προβλήματα μπορεί να προκύψουν όταν αποστέλλονται σύντομα μηνύματα ASCII. Σε τέτοια μηνύματα, το m μπορεί να είναι η συνένωση ενός ή περισσότερων κωδικοποιημένων χαρακτήρων ASCII. Ένα μήνυμα που αποτελείται από έναν μόνο χαρακτήρα ASCII NUL (του οποίου η αριθμητική τιμή είναι 0) θα κωδικοποιούνταν ως m = 0, το οποίο παράγει ένα κρυπτογραφημένο κείμενο 0 ανεξάρτητα από τις τιμές των e και N που χρησιμοποιούνται. Ομοίως, ένα απλό ASCII SOH (του οποίου η αριθμητική τιμή είναι 1) θα παρήγαγε πάντα ένα κρυπτογραφημένο κείμενο 1. Για συστήματα που χρησιμοποιούν συμβατικά μικρές τιμές του e, όπως το 3, όλα τα μηνύματα ASCII με ένα χαρακτήρα που κωδικοποιούνται με αυτό το σχήμα θα ήταν ανασφαλή, δεδομένου ότι το μεγαλύτερο m θα είχε τιμή 255, και 255³ είναι μικρότερο από οποιοδήποτε λογικό modulus. Τέτοια κρυπτογραφήματα θα μπορούσαν να ανακτηθούν απλά παίρνοντας την κυβική ρίζα του κρυπτογραφήματος.

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

Πρότυπα όπως το PKCS έχουν σχεδιαστεί προσεκτικά για να γεμίζουν με ασφάλεια τα μηνύματα πριν από την κρυπτογράφηση RSA. Επειδή αυτά τα συστήματα γεμίζουν το απλό κείμενο m με κάποιο αριθμό πρόσθετων bits, το μέγεθος του μη γεμισμένου μηνύματος M πρέπει να είναι κάπως μικρότερο. Τα σχήµατα συµπλήρωσης RSA πρέπει να σχεδιάζονται προσεκτικά ώστε να αποτρέπονται εξεζητηµένες επιθέσεις. Αυτό μπορεί να διευκολυνθεί με μια προβλέψιμη δομή μηνύματος. Οι πρώτες εκδόσεις του προτύπου PKCS χρησιμοποιούσαν ad-hoc κατασκευές, οι οποίες βρέθηκαν αργότερα ευάλωτες σε μια πρακτική προσαρμοστική επίθεση επιλεγμένου κρυπτοκειμένου. Οι σύγχρονες κατασκευές χρησιμοποιούν ασφαλείς τεχνικές όπως η βέλτιστη ασύμμετρη κρυπτογράφηση (Optimal Asymmetric Encryption Padding - OAEP) για την προστασία των μηνυμάτων, αποτρέποντας ταυτόχρονα αυτές τις επιθέσεις. Το πρότυπο PKCS διαθέτει επίσης σχήματα επεξεργασίας που έχουν σχεδιαστεί για να παρέχουν πρόσθετη ασφάλεια για υπογραφές RSA, π.χ. το Probabilistic Signature Scheme for RSA (RSA-PSS).

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

Ας υποθέσουμε ότι η Alice επιθυμεί να στείλει ένα υπογεγραμμένο μήνυμα στον Bob. Παράγει μια τιμή κατακερματισμού του μηνύματος, την αυξάνει στη δύναμη του d mod n (όπως ακριβώς κατά την αποκρυπτογράφηση ενός μηνύματος) και την επισυνάπτει ως "υπογραφή" στο μήνυμα. Όταν ο Bob λαμβάνει το υπογεγραμμένο μήνυμα, αυξάνει την υπογραφή στη δύναμη του e mod n (όπως ακριβώς συμβαίνει κατά την κρυπτογράφηση ενός μηνύματος) και συγκρίνει την προκύπτουσα τιμή κατακερματισμού με την πραγματική τιμή κατακερματισμού του μηνύματος. Εάν οι δύο συμφωνούν, γνωρίζει ότι ο συντάκτης του μηνύματος είχε στην κατοχή του το μυστικό κλειδί της Alice, και ότι το μήνυμα δεν έχει αλλοιωθεί έκτοτε.

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