Υπογραφή ElGamal

Οι υπογραφές ElGamal βασίζονται στη μη υπολογισιμότητα του προβλήματος του διακριτού λογαρίθμου σε ένα πεπερασμένο πεδίο: είναι εύκολο να υψωθεί ένας ακέραιος $g$ σε μια δύναμη $x$, αλλά είναι δύσκολο να υπολογιστεί το $x$ απο το $g^{x}$. Για τη δημιουργία κλειδιών, κάθε οντότητα $A$ τρέχει τον παρακάτω βασικό αλγόριθμο για το σχήμα ElGamal:

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

1. Επίλεξε ένα μεγάλου μεγέθους πρώτο αριθμό $p$ και ένα γεννήτορα $g$ για μια ομάδα $\mathbb {Z} _{p}^{*}$.
2. Επίλεξε έναν τυχαίο αριθμό $x$, τέτοιον ώστε $1\leq x\leq p-2$.
3. Υπολόγισε $y=g^{x}\ mod\ p$.

Το δημόσιο κλειδί του $A$ είναι το $E_{A}=(p,g,y)$ και το ιδιωτικό του κλειδί είναι το $D_{A}=x$.

Για την κρυπτογράφηση ενός μηνύματος $m$ για τη $B$, η $A$ αποκτά το

$E_{B}$ και εκτελεί τον παρακάτω αλγόριθμο:

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

1. Αναπαράστησε το $m$ με ένα σύνολο απο τμήματα $m_{i}$, το καθένα στο διάστημα $[0,p-1]$.
2. Διάλεξε έναν τυχαίο ακέραιο $k$, τέτοιον ώστε $1\leq k\leq p-2$.
3. Υπολόγισε το $a=g^{k}\ mod\ p$ και $b=m_{i}y^{k}\ mod\ p$.

Το κρυπτογράφημα για τη $B$ είναι τα $(a,b)$. Η $B$ αποκρυπτογραφεί κάθε ένα από τα $(a,b)$, το οποίο είναι δυο φορές το μέγεθος του αρχικού μηνύματος, χρησιμοποιώντας το $D_{B}$ και εκτελώντας:

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

1. Υπολόγισε το $a^{p-1-x}\ mod\ p$.
2. Υπολόγισε το $m_{i}=a^{-x}b\ mod\ p$.

Το σπάσιμο της κρυπτογράφησης ElGamal είναι ισοδύναμο με το να λυθεί το πρόβλημα του διακριτού λογάριθμου. Παρ'όλα αυτά, ο τυχαίος αριθμός $k$ πρέπει να επιλεχθεί διαφορετικός και ανεξάρτητα για διαφορετικές κρυπτογραφήσεις. Αλλιώς, η πιθανή γνώση του μηνύματος θα μπορούσε να οδηγήσει στην ανάκτηση άλλων μηνυμάτων που κρυπτογραφήθηκαν με το ίδιο $k$.

Η υπογραφή ElGamal είναι ένα τυχαίο σχήμα και δημιουργεί υπογραφές με προσθήκη, χρησιμοποιώντας μια μονόδρομη συνάρτηση σύνοψης $h:\{0,1\}^{*}\to \mathbb {Z} _{p}$. Για να υπογράψει ένα μήνυμα $m$ οποιουδήποτε μήκους, ο $A$ εκτελεί τον παρακάτω αλγόριθμο με το ιδιωτικό του κλειδί $D_{A}$:

Δημιουργία Υπογραφής ElGamal

1. Επέλεξε έναν τυχαίο ακέραιο $k$, τέτοιον ώστε $1\leq k\leq p-2$ και $gcd(k,p-1)=1$. Ο $k$ πρέπει να κρατηθεί μυστικός.
2. Υπολόγισε $r=g^{k}\ mod\ p$.
3. Υπολόγισε $k^{-1}\ mod\ (p-1)$.
4. Υπολόγισε $s=k^{-1}(h(m)-xr)\ mod\ (p-1)$.

To ζεύγος $(r,s)$ είναι η υπογραφή του $A$ στο $m$. Οποιαδήποτε άλλη οντότητα που έχει το $E_{A}$ μπορεί να επιβεβαιώσει την υπογραφή με τα παρακάτω βήματα:

Επιβεβαίωση Υπογραφής ElGamal

1. Επιβεβαίωσε ότι $1\leq r\leq p-1$, αλλιώς απόρριψε την υπογραφή.
2. Υπολόγισε $u_{1}=y^{r}r^{s}\ mod\ p$.
3. Υπολόγισε $h(m)$.
4. Υπολόγισε $u_{2}=g^{h}(m)\ mod\ p$.
5. Έλεγξε αν $u_{1}=u_{2}$. Αν ναι, αποδέξου την υπογραφή.

Η επιβεβαίωση μιας υπογραφής ElGamal είναι πιο αργή απο αυτή μιας υπογραφής RSA με μικρό εκθέτη. Είναι δυνατόν να γίνουν η ύψωση σε δύναμη με υπόλοιπο και ο Ευκλείδειος Αλγόριθμος(Βήματα 2 και 3 της Δημιουργίας Υπογραφής) εκ των προτέρων. Παρ'όλα αυτά η επιβεβαίωση θα παραμείνει σημαντικά πιο αργή απο αυτή του RSA. Συνιστάται η χρήση υπολοίπου $p$ μήκους 1024 bits ή μεγαλύτερου.

Πηγές

• Σύγχρονη κρυπτογραφία θεωρία και εφαρμογές,MIKE BURMESTER, ΣΤΕΦΑΝΟΣ ΓΚΡΙΤΖΑΛΗΣ, ΣΩΚΡΑΤΗΣ ΚΑΤΣΙΚΑΣ, ΒΑΣΙΛΕΙΟΣ ΧΡΥΣΙΚΟΠΟΥΛΟΣ, ΑΘΗΝΑ 2011
• Handbook of Applied Cryptography, A. Menezes, S. Vastone, October 1996