RSA

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Το RSA είναι ένας κρυπταλγόριθμος ασύμμετρου κλειδίου, το όνομα του οποίου προέρχεται από τους δημιουργούς του, Ron Rivest, Adi Shamir and Len Adleman. Επιτρέπει όχι μόνο την κωδικοποίηση μηνυμάτων αλλά μπορεί επίσης να χρησιμοποιηθεί για ψηφιακή υπογραφή.

[Επεξεργασία] Λειτουργία

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

[Επεξεργασία] Δημιουργία των κλειδιών

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

Για την εύρεση πρώτων αριθμών χρησιμοποιούνται πιθανολογικοί αλγόριθμοι.
Συνηθισμένες επιλογές για το $e \,$ είναι το 3, 7 και 2¹⁶ + 1. Μικροί αριθμοί οδηγούν σε ταχύτερους υπολογισμούς αλλά και σε πιο αδύνατη ασφάλεια.

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

δημόσιο: $(n, e) \,$
κρυφό: $(n, d) \,$

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

[Επεξεργασία] Κρυπτογράφηση

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

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

[Επεξεργασία] Αποκρυπτογράφηση

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

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

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

$m^{e.d} \equiv m^1 \equiv m\mod{p-1}$

και

$m^{e.d} \equiv m^1 \equiv m\mod{q-1}$

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

$m^{e.d} \equiv m\mod{n}$

[Επεξεργασία] Ψηφιακή υπογραφή

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

$s = m^d\mod{n}$

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

$s = H(m)^d\mod{n}$

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

[Επεξεργασία] Ασφάλεια

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

[Επεξεργασία] Κοινό n

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

$c_1 = m^{e_1}\mod{n}$

και

$c_2 = m^{e_2}\mod{n}$

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

$e_1 \wedge e_2 = 1$

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

$\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 m\mod{n}$

[Επεξεργασία] Μικρό 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}$

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

[Επεξεργασία] Τυφλή υπογραφή

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

$m'^d \equiv (r^e.c)^d \equiv (r^e.m^e) \equiv r^{e.d}.m^{e.d} \equiv r.m\mod{n}$

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

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

[Επεξεργασία] Σημειώσεις

↑ Στην θεωρία, ένας μόνος κρυπταλγόριθμος παρέχει πλήρης ασφάλεια, το one-time-pad. Το RSA είναι ασφαλές διότι η σημερινή υπολογιστική ισχύ καθιστά το πρόβλημα της παραγοντοποίησης του n, για μεγάλα n, δύσκολο, δηλαδή πάρα πολύ χρονοβόρο (μετριέται σε χρόνια)
↑ $m 3 < n 1 . n 2 . n 3$ που σημαίνει πως η κυβική ρίζα μπορεί να υπολογιστεί στο $\mathbb{N}$ , κάτι που είναι πολύ δύσκολο όταν δουλεύουμε στα $\mathbb{Z}/n_i\mathbb{Z}, i \in (1,2,3)$