RSA

Ο RSA είναι κρυπταλγόριθμος ασύμμετρου κλειδιού, το όνομα του οποίου προέρχεται από τους δημιουργούς του, Ρον Ρίβεστ, Άντι Σαμίρ και Λεν Άντλμαν. Επιτρέπει όχι μόνο την κωδικοποίηση μηνυμάτων αλλά μπορεί επίσης να χρησιμοποιηθεί και ως ψηφιακή υπογραφή.

Λειτουργία

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

Δημιουργία των κλειδιών

1. Επιλογή δυο τυχαίων (μεγάλων) πρώτων αριθμών $p$ και $q$ έτσι ώστε $p\ne q$
2. Υπολογίζουμε $n=p.q$
3. Υπολογίζουμε τη συνάρτηση του Όιλερ, $\varphi (n)=(p-1)(q-1)$.
4. Επιλογή ενός αριθμού $e>1$ έτσι ώστε $e^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.
5. Υπολογίζουμε τον αριθμό $d$ έτσι ώστε $d\equiv e^{-1}(\mathrm{mod}\phi (n))$.

• Για την εύρεση πρώτων αριθμών χρησιμοποιούνται πιθανολογικοί αλγόριθμοι.
• Στην πρωτότυπη δημοσίευση χρησιμοποιείται η συνάρτηση του Όιλερ αλλά η συνάρτηση Charmicael $\lambda (n)$ χρησιμοποιείται πιο συχνά επειδή το $dmod\varphi (n)$ μπορεί να έχει ποιο μεγάλη τιμή από ότι χρειάζεται, δηλαδή $d>\lambda (n)$, ο αλγόριθμος συνεχίζει να δουλεύει γιατί $\varphi (n)$ πάντα διαιρείται από $\lambda (n)$ άρα όποιο d ικανοποιεί τη σχέση $d\cdot e\equiv 1(\mathrm{mod}\varphi (n))$ ικανοποιεί και τη $d\cdot e\equiv 1(\mathrm{mod}\lambda (n))$.
• Συνηθισμένες επιλογές για το $e$ είναι το 3, 7 και 2¹⁶ + 1. Μικροί αριθμοί οδηγούν σε ταχύτερους υπολογισμούς αλλά και σε πιο αδύνατη ασφάλεια.

Τα κλειδιά είναι τα εξής:

• δημόσιο: $(n,e)$
• ιδιωτικό: $(n,d)$

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

Κρυπτογράφηση

Το μήνυμα μπορεί να αντιπροσωπευθεί από έναν αριθμό $m$(π.χ. "RSA" → 0x525341, όπου 0x52 είναι ο δεκαεξαδικός κωδικός ASCII του χαρακτήρα R, 0x53 του S και τέλος 0x41 του A). Το κρυπτογραφημένο μήνυμα $c$ υπολογίζεται με τον εξής τρόπο:

$c=m^{e}modn$

Αποκρυπτογράφηση

Αφού ληφθεί ένα κρυπτογραφημένο μήνυμα $c$, για να διαβάσουμε το αρχικό μήνυμα προβαίνουμε στον ακόλουθο υπολογισμό:

$m=c^{d}modn\equiv (m^e{)}^{d}modn\equiv m^{e.d}modn$

Ξέρουμε πως $e\cdot d\equiv 1mod(p-1)$ και $e\cdot d\equiv 1mod(q-1)$, όποτε με το μικρό θεώρημα του Φερμά, έχουμε:

$m^{e\cdot d}\equiv m^1\equiv mmodp-1$

και

$m^{e\cdot d}\equiv m^1\equiv mmodq-1$

Οι αριθμοί p και q είναι πρώτοι μεταξύ τους, χρησιμοποιώντας λοιπόν το Κινέζικο Θεώρημα Υπολοίπων, έχουμε:

$m^{e\cdot d}\equiv mmodn$

Ψηφιακή υπογραφή

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

$s=m^{d}modn$

Ο παραλήπτης του μηνύματος m και της υπογραφής s, υπολογίζει την τιμή s^e χάρη στο δημόσιο κλειδί (n, e) και τη συγκρίνει με το m. Αυτή η λύση, αν και λειτουργεί, δε χρησιμοποιείται ποτέ, για λόγους ασφαλείας. Αντί να υπογραφεί το μήνυμα ως έχει, προτιμάται η χρήση μιας συνάρτησης κατακερματοποίησης (hash function) Η:

$s=H(m{)}^{d}modn$

Ο παραλήπτης προβαίνει στην ίδια μέθοδο, αρκεί να γνωρίζει και ποία συνάρτηση κατακερματοποίησης χρησιμοποιήθηκε.

Ασφάλεια

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

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

Επίσης, υπάρχει πάντα η πιθανότητα να ανακαλύψει κάποιος έναν αλγόριθμο (ή να έχει ήδη ανακαλύψει) ο οποίος μπορεί να παραγοντοποιεί αριθμούς σε πολυωνυμικό χρόνο.

Επιθέσεις

Επίθεση επαναληπτικής κρυπτογράφησης

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

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

Προβλήματα που οφείλονται στην κακή χρήση ή υλοποίηση

Κοινό n

Αν υποθέσουμε πως έχουμε στην κατοχή μας δυο κλειδιά του τύπου $(n,e_1)$ και $(n,e_2)$ (το ίδιο n), και δυο κρυπτογραφήσεις $(c_1,c_2)$ του ιδίου μηνύματος m με τα κλειδιά αυτά (π.χ. αν "κρυφακούμε" σε ένα δίκτυο):

$c_1=m^{e_1}modn$

και

$c_2=m^{e_2}modn$

μπορούμε να βρούμε το αρχικό μήνυμα m χωρίς να έχουμε πρόσβαση στα κρυφά κλειδιά. Είναι πολύ πιθανόν να έχουμε:

$e_1\wedge e_2=1$

οπότε και με το θεώρημα του Bézout:

$\mathrm{\exists }(u,v),e_1.u+e_2.v=1$

Για να βρούμε το αρχικό μήνυμα m, υπολογίζουμε λοιπόν:

$(c_1{)}^u.(c_2{)}^v\equiv (m^{e_1}{)}^u.(m^{e_2}{)}^v\equiv m^{e_1.u+e_2.v}\equiv m^1\equiv mmodn$

Μικρό e (π.χ. e = 3)

Ένα μήνυμα m κρυπτογραφείται κι αποστέλλεται από τρεις διαφορετικούς χρήστες με χρήση των δημοσίων κλειδιών $(n_1,3)$, $(n_2,3)$ και $(n_3,3)$. Ο κακόβουλος χρήστης έχει λοιπόν στην κατοχή του:

• $m^{3}mod{n}_1$
• $m^{3}mod{n}_2$
• $m^{3}mod{n}_3$

Χάρη στο Κινέζικο Θεώρημα Υπολοίπων, μπορεί να υπολογίσει:

$m^{3}mod{n}_1.n_2.n_3$

και να βρει πια εύκολα το αρχικό μήνυμα m.

Τυφλή υπογραφή

Υποθέτουμε πως ο Γιάννης, το ιδιωτικό (αντ. δημόσιο) κλειδί του οποίου είναι (n, d) (αντ. (n, e)), υπογράφει ότι μήνυμα του δώσουμε χωρίς δεύτερη σκέψη. Αν ένας κακόβουλος χρήστης έχει ένα κρυπτογραφημένο μήνυμα c με τελικό παραλήπτη τον Γιάννη, μπορεί να μπερδέψει τον τελευταίο έτσι ώστε να του το αποκρυπτογραφήσει ο ίδιος ο Γιάννης. Αρκεί να διαλέξει έναν τυχαίο αριθμό r, πρώτο με το n και να ζητήσει από τον Γιάννη να του υπογράψει το μήνυμα m´ = r^e.c. Ο Γιάννης υπολογίζει:

$m{\text{'}}^d\equiv (r^e.c{)}^d\equiv (r^e.m^e)\equiv r^{e.d}.m^{e.d}\equiv r.mmodn$

Το μήνυμα r.m δεν είναι κατανοητό, οπότε ο Γιάννης δεν μπορεί εύκολα να καταλάβει πως πέφτει θύμα απάτης και το στέλνει στον κακόβουλο χρήστη, ο οποίος υπολογίζει τον αριθμό r^-1 mod n και μπορεί πλέον να διαβάσει το μήνυμα m.

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

Δείτε επίσης

• 65537 (αριθμός)

Εξωτερικοί Σύνδεσμοι

• Πρότυπο:En A Method for Obtaining Digital Signatures and Public-Key Cryptosystems: Το πρώτο άρθρο που παρουσιάζει το RSA
• Πρότυπο:En Καινούργιες εκδοχές (χρήση padding για ισχυρότερη ασφάλεια, κλπ.)