Επίθεση του Βίνερ

Η επίθεση του Βίνερ, όπως ονομάστηκε από τον κρυπτολόγο Μάικλ Τζ. Βίνερ, είναι ένα είδος κρυπτογραφικής επίθεσης εναντίον του κρυπτοσυστήματος RSA. Η επίθεση χρησιμοποιεί την μέθοδο των συνεχών κλασμάτων για τον εντοπισμό του ιδιωτικού κλειδιού d, όταν αυτό είναι μικρό.

Μια ματιά στον αλγόριθμο του RSA

Προτού γίνει αναφορά στον τρόπο που λειτουργεί η επίθεση του Βίνερ, θα παρουσιαστεί σύντομα ο τρόπος λειτουργίας του κρυπτοσυστήματος RSA. Για περισσότερες λεπτομέρειες, υπάρχει και το κύριο λήμμα RSA.

Γίνεται η υπόθεση ότι η Άλις και ο Μπομπ είναι δύο άτομα που θέλουν να επικοινωνήσουν με ασφάλεια. Πιο συγκεκριμένα, η Άλις θέλει να στείλει ένα μήνυμα στον Μπομπ, το οποίο μόνον ο Μπομπ θα μπορεί να διαβάσει. Αρχικά, ο Μπομπ επιλέγει δύο πρώτους αριθμούς p και q και υπολογίζει τον αριθμό N = pq. Αυτός ο αριθμός γίνεται γνωστός (δημόσιος) μαζί με τον δείκτη κρυπτογράφησης e, ενώ τα N και e διαμορφώνουν το δημόσιο κλειδί (e,N). Με αυτόν τον τρόπο, οποιοσδήποτε μπορεί να κρυπτογραφήσει κάποιο μήνυμα για τον Μπομπ. Ο δείκτης αποκρυπτογράφησης d ικανοποιεί τη συνθήκη $ed=1{\bmod {\varphi }}(N)$, ὀπου $\varphi (N)=(p-1)(q-1)$, είναι η συνάρτηση $\varphi (N)$ του Όιλερ. (σημείωση: αυτή είναι η τάξη της πολλαπλασιαστικής ομάδας $\mathbb {Z} _{N}^{*}$). Ο δείκτης κρυπτογράφησης e και η τιμή του $\varphi (N)$ πρέπει επίσης να είναι σχετικά πρώτοι (πρώτοι μεταξύ τους) ώστε να υπάρχει αντίστροφη επεκτασιμότητα .

Η παραγοντοποίηση του N και το ιδιωτικό κλειδί d παραμένουν κρυφά, ώστε μόνον ο Μπομπ να μπορεί να αποκρυπτογραφήσει το μήνυμα. Το ιδιωτικό κλειδί ορίζεται ως (d,N). Η κρυπτογράφηση του μηνύματος M δίνεται από τον τύπο $C\equiv M^{e}{\bmod {N}}$ και η αποκρυπτογράφηση του κρυπτογραφημένου μηνύματος $C$ δίνεται από τον τύπο $C^{d}\equiv (M^{e})^{d}\equiv M^{(ed)}\equiv M{\bmod {N}}$ (με χρήση του μικρού θεωρήματος του Φερμά).

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

Χρήση Μικρού Ιδιωτικού Κλειδιού

Στο κρυπτοσύστημα του RSA, ο Μπομπ μπορεί να προτιμήσει να κάνει χρήση μιας μικρής τιμής του d, παρά μιας μεγαλύτερης τυχαίας, με σκοπό να βελτιώσει την απόδοση της αποκρυπτογράφησης του RSA. Ωστόσο, η επίθεση του Βίνερ αναδεικνύει το γεγονός ότι η χρήση μιας μικρής τιμής d έχει ως αποτέλεσμα ένα μη ασφαλές σύστημα, στο οποίο ο επιτιθέμενος μπορεί να ανακτήσει όλες τις κρυφές πληροφορίες και να "σπάσει" το σύστημα RSA. Αυτό είναι κάτι που βασίζεται στο Θεώρημα του Βίνερ, το οποίο ισχύει για μικρές τιμές του d. Ο Βίνερ έχει αποδείξει ότι ο επιτιθέμενος μπορεί να βρει (σε πολυωνυμικό χρόνο) το d όταν ισχύει $d<{\frac {1}{3}}N^{\frac {1}{4}}$.

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

Επιλογή μεγάλου δημοσίου κλειδιού: Αντικαθιστώντας $e$ με $e'$, όπου $e'=e+k.\varphi (N)$ για κάποια μεγάλη τιμή του $k$. Όταν η τιμή του $e'$ είναι αρκετά μεγάλη, για παράδειγμα $e'>N^{\frac {3}{2}}$, τότε η επίθεση του Βίνερ δεν μπορεί να εφαρμοστεί, ανεξαρτήτως με το πόσο μικρή είναι η τιμή του $d$.

Χρήση του Κινέζικου Θεωρήματος Υπολοίπου: Γίνεται η υπόθεση ότι κάποιος επιλέγει d ώστε αμφότερα τα $d_{p}=d{\bmod {\ }}(p-1)$ και $d_{q}=d{\bmod {\ }}(q-1)$ να έχουν μικρές τιμές χωρίς όμως να είναι μικρή και η τιμή του $d$. Με βάση αυτό, μια γρήγορη αποκρυπτογράφηση του $C$ μπορεί να γίνει ακολούθως:

1. Αρχικά υπολογίζονται τα $M_{p}\equiv C^{d_{p}}{\bmod {\ }}p$ και $M_{q}\equiv C^{d_{q}}{\bmod {\ }}q$.
2. Με χρήση του Κινέζικου Θεωρήματος Υπολοίπου υπλογίζεται η μοναδική τιμή του $M\in \mathbb {Z_{N}}$ που ικανοποιεί τις σχέσεις $M\equiv M_{p}{\bmod {\ }}p$ και $M\equiv M_{q}{\bmod {\ }}q$. Το αποτέλεσμα του $M$ ικανοποιεί τη σχέση $M\equiv C^{d}{\bmod {\ }}N$ όπως θα έπρεπε. Το αξιοσημείωτο είναι ότι η επίθεση του Βίνερ δεν εφαρμόζεται εδώ, διότι η τιμή του $d{\bmod {\ }}\varphi (N)$ μπορεί να είναι μεγάλη.

Τρόπος λειτουργίας της επίθεσης του Βίνερ

Δεδομένου ότι:

$ed=1({\bmod {\ }}\operatorname {lcm} (p-1,q-1))$,

υπάρχει ένας ακέραιος K ώστε:

$ed=K\times \operatorname {lcm} (p-1,q-1)+1$

Θέτοντας $G=\gcd(p-1,q-1)$ και αντικαθιστώντας τη σχέση αυτή στην παραπάνω εξίσωση προκύπτει:

$ed={\frac {K}{G}}(p-1)(q-1)+1$

Θέτοντας $k={\frac {K}{\gcd(K,G)}}$ και $g={\frac {G}{\gcd(K,G)}}$, αντικαθιστώντας παραπάνω:

$ed={\frac {k}{g}}(p-1)(q-1)+1$.

Διαιρώντας με $dpq$:

${\frac {e}{pq}}={\frac {k}{dg}}(1-\delta )$, όπου $\delta ={\frac {p+q-1-{\frac {g}{k}}}{pq}}$.

Έτσι, η τιμή του ${\frac {e}{pq}}$ είναι λίγο μικρότερη από αυτή του ${\frac {k}{dg}}$, όπου η τελευταία τιμή αποτελείται εξ ολοκλήρου από δημόσια πληροφορία. Ωστόσο, είναι αναγκαία μία μέθοδος ελέγχου της πρόβλεψης. Υποθέτοντας ότι $ed>pq$ (μία λογική υπόθεση, εκτός αν η τιμή του $G$ είναι μεγάλη) η τελευταία εξίσωση παραπάνω μπορεί να γραφεί ως :

$edg=k.(p-1)(q-1)+g$

Με χρήση απλών αλγεβρικών μεθόδων και ταυτοτήτων, μια πρόβλεψη μπορεί να χρησιμοποιηθεί για την ακρίβεια του αποτελέσματος.

Το θεώρημα του Βίνερ

Ισχύει $\ N=pq$ με $\ q<p<2q$. Ισχύει $d<{\frac {1}{3}}N^{\frac {1}{4}}$.
Δεδομένου $\left\langle N,e\right\rangle$ με $ed=1({\bmod {\ }}\varphi (N))$, ο επιτιθέμενος μπορεί να ανακτήσει αποτελεσματικά $d$.

Παράδειγμα

Έστω το δημόσιο κλειδί $\left\langle N,e\right\rangle =\left\langle 90581,17993\right\rangle$.
Ο επιτιθέμενος πρέπει να αποφασίσει για την τιμή του $d$.
Με χρήση του Θεωρήματος του Βίνερ και των συνεχών κλασμάτων για την προσέγγιση του $d$, πρώτα γίνεται προσπάθεια εύρεσης του συνεχούς κλάσματος ${\frac {e}{N}}$.

Σημειώνεται ότι αυτός ο αλγόριθμος βρίσκει το συνεχές κλάσμα στους χαμηλότερους όρους. Είναι γνωστό ότι:

${\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+\dots +{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]$

Βάση των αποτελεσμάτων από τη χρήση μεθόδου των συνεχών κλασμάτων ${\frac {e}{N}}$, όλες οι συγκλίνουσες τιμές του ${\frac {k}{d}}$ είναι:

${\frac {k}{d}}=0,{\frac {1}{5}},{\frac {29}{146}},{\frac {117}{589}},{\frac {146}{735}},{\frac {555}{2794}},{\frac {1256}{6323}},{\frac {5579}{28086}},{\frac {17993}{90581}}$

Γίνεται επιβεβαίωση πως η πρώτη συγκλίνουσα τιμή δεν παράγει μια παραγοντοποίηση του $N$. Ωστόσο, η σύγκλιση του ${\frac {1}{5}}$ παράγει

$\varphi (N)={\frac {e.d-1}{k}}={\frac {17993\times 5-1}{1}}=89964$

Τώρα, επιλύοντας την εξίσωση

$x^{2}-\left(\left(N-\varphi (N)\right)+1\right)x+N=0$

$x^{2}-\left(\left(90581-89964\right)+1\right)x+90581=0$

$x^{2}-\left(618\right)x+90581=0$

προκύπτουν οι ρίζες οι οποίες είναι $x=379;239$. Άρα, η παραγοντοποίηση είναι πλέον γνωστή.

$N=90581=379\times 239=p\times q$.

Επισημαίνεται ότι για το ακέραιο υπόλοιπο του $N=90581$, το Θεώρημα του Βίνερ θα είναι αποτελεσματικό εάν

$d<{\frac {N^{\frac {1}{4}}}{3}}\approx 5.7828$.

Απόδειξη του Θεωρήματος του Βίνερ

Η απόδειξη βασίζεται σε προσεγγίσεις με χρήση συνεχών κλασμάτων.

Δεδομένου ότι $ed=1{\bmod {\varphi }}(N)$, υπάρχει μία τιμή ${\mathit {k}}$ ούτως ώστε $ed-k\varphi (N)=1$. Επομένως

$\left|{\frac {e}{\varphi (N)}}-{\frac {k}{d}}\right\vert ={\frac {1}{d\varphi (N)}}$.

Ως εκ τούτου, ${\frac {k}{d}}$ αποτελεί μια προσέγγιση του ${\frac {e}{\varphi (N)}}$. Παρόλο που ο επιτιθέμενος δεν γνωρίζει την τιμή του $\varphi (N)$, μπορεί να χρησιμοποιήσει το $N$ για να βρει μια προσέγγισή του. Πράγματι, δεδομένου ότι

$\varphi (N)=N-p-q+1$ και $p+q-1<3{\sqrt {N}}$, προκύπτει:

$\left\vert p+q-1\right\vert <3{\sqrt {N}}$

$\left\vert N+1-\varphi (N)-1\right\vert <3{\sqrt {N}}$

Χρησιμοποιώντας $N$ στην θέση του $\varphi (N)$, η σχέση γίνεται:

$\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert =\left\vert {\frac {ed-kN}{Nd}}\right\vert$

$\qquad =\left\vert {\frac {ed-k\varphi (N)-kN+k\varphi (N)}{Nd}}\right\vert$

$=\left\vert {\frac {1-k(N-\varphi (N))}{Nd}}\right\vert$

$\leq \left\vert {\frac {3k{\sqrt {N}}}{Nd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}d}}={\frac {3k}{d{\sqrt {N}}}}$

Τώρα ισχύει, $k\varphi (N)=ed-1<ed$, ώστε $k\varphi (N)<ed$. Δεδομένου ότι $e<\varphi (N)$, ώστε $k\varphi (N)<ed<\varphi (N)d$, η σχέση γίνεται:

$k\varphi (N)<\varphi (N)d$

$k<d$

Δεδομένου $k<d$ και $d<{\frac {1}{3}}N^{\frac {1}{4}}$. Ως εκ τούτου η σχέση γίνεται:

(1) $\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert \leq {\frac {1}{dN^{\frac {1}{4}}}}$

Δεδομένου ότι $d<{\frac {1}{3}}N^{\frac {1}{4}},2d<3d,$ τότε $2d<3d<N^{\frac {1}{4}}$, προκύπτει:

$2d<N^{\frac {1}{4}},$, ώστε (2) ${\frac {1}{2d}}>{\frac {1}{N^{\frac {1}{4}}}}$

Από τις σχέσεις (1) και (2), συμπεραίνεται ότι:

$\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert \leq {\frac {3k}{d{\sqrt {N}}}}<{\frac {1}{d\cdot 2d}}={\frac {1}{2d^{2}}}$

Επομένως από το θεώρημα του Λεζάντρ, το k/d είναι ένα συγκλίνων κλάσμα του e/n.

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

• Coppersmith, Don (1996). Low-Exponent RSA with Related Messages. Springer-Verlag Berlin Heidelberg.
• Jose, Justin (2010). Study of RSA and Proposed Variant Against Wiener's Attack. International Journal of Computer Applications.
• Dujella, Andrej (2004). Continued Fractions and RSA with Small Secret Exponent.
• Cui, Xiao-lei (2005). Attack On the RSA Cryptosystem.