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

Η **επίθεση του Βίνερ**, όπως ονομάστηκε από τον κρυπτολόγο Μάικλ Τζ. Βίνερ, είναι ένα είδος κρυπτογραφικής επίθεσης εναντίον του κρυπτοσυστήματος 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.

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

**Επιλογή μεγάλου δημοσίου κλειδιού**:  Αντικαθιστώντας  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  μπορεί να γίνει ακολούθως:

#Αρχικά υπολογίζονται τα M_p\equiv C^{d_p} \bmod\ p  και  M_q\equiv C^{d_q} \bmod\ q .
#Με χρήση του Κινέζικου Θεωρήματος Υπολοίπου υπλογίζεται η μοναδική τιμή του 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 . Ισχύει d . 
Δεδομένου \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\times5 - 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 .

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

Δεδομένου ότι 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, προκύπτει:

:\left \vert p+q-1 \right \vert 
:\left \vert N+1-\varphi (N)-1 \right \vert 

Χρησιμοποιώντας 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 
::::\le \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, ώστε k \varphi (N). Δεδομένου ότι e, ώστε k \varphi (N), η σχέση γίνεται:   
:k \varphi (N)
:::k

Δεδομένου k και d.
Ως εκ τούτου η σχέση γίνεται:

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

Δεδομένου ότι d τότε 2d, προκύπτει:

:2d, ώστε (2) \frac{1}{2d}> \frac{1}{N^{ \frac{1}{4}}}
Από τις σχέσεις (1) και (2), συμπεραίνεται ότι:

:\left \vert \frac{e}{N}- \frac{k}{d} \right \vert \le \frac{3k}{d \sqrt{N}}
:Επομένως από το θεώρημα του Λεζάντρ, το 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.

Κατηγορία:Κρυπτογραφία