RSA

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

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

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

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

Επιλογή δυο τυχαίων (μεγάλων) πρώτων αριθμών $p\,$ και $q\,$ έτσι ώστε $p\neq q\,$
Υπολογίζουμε $n=p.q\,$
Υπολογίζουμε την συνάρτηση του Όιλερ, $\phi (n)=(p-1)(q-1)\,$ .
Επιλογή ενός αριθμού $e>1\,$ έτσι ώστε $e^{\phi (n)}\equiv 1{\pmod {n}}$ .
Υπολογίζουμε τον αριθμό $d$ έτσι ώστε $d\equiv e^{-1}{\pmod {\varphi (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]

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

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

Επιθέσεις[Επεξεργασία | επεξεργασία κώδικα]

Επίθεση επαναληπτικής κρυπτογράφησης[Επεξεργασία | επεξεργασία κώδικα]

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

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

Προβλήματα που οφείλονται στην κακή χρήση ή υλοποίηση[Επεξεργασία | επεξεργασία κώδικα]

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

Αν υποθέσουμε πως έχουμε στην κατοχή μας δυο κλειδιά του τύπου $(n,e_{1})\,$ και $(n,e_{2})\,$ (το ίδιο n), και δυο κρυπτογραφήσεις $(c_{1},c_{2})\,$ του ιδίου μηνύματος m με τα κλειδιά αυτά (π.χ. αν "κρυφακούμε" σε ένα δίκτυο):

c_{1}=m^{e_{1}}\mod {n}

και

c_{2}=m^{e_{2}}\mod {n}

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

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.

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

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

↑ ^1,0 ^1,1 ^1,2 ^1,3 Βασίλειος Α. Κάτος, Γεώργιος Χρ. Στεφανίδης, επιμ. (2003). Τεχνικές Κρυπτογραφίας & Κρυπτανάλυσης. Θεσσαλονίκη: Ζυγός. ISBN 960-8065-40-2. (κεφ. 6.5.2.: Ασφάλεια του RSA)
↑ $m^{3}<n_{1}.n_{2}.n_{3}$ που σημαίνει πως η κυβική ρίζα μπορεί να υπολογιστεί στο $\mathbb {N}$ , κάτι που είναι πολύ δύσκολο όταν δουλεύουμε στα $\mathbb {Z} /n_{i}\mathbb {Z} ,i\in (1,2,3)$