Υπογραφή ElGamal

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

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

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

Το δημόσιο κλειδί του $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\le k\le p-2$.
3. Υπολόγισε το $a=g^{k}modp$ και $b=m_i{y}^{k}modp$.

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

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

1. Υπολόγισε το $a^{p-1-x}modp$.
2. Υπολόγισε το $m_i=a^{-x}bmodp$.

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

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

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

1. Επέλεξε έναν τυχαίο ακέραιο $k$, τέτοιον ώστε $1\le k\le p-2$ και $gcd(k,p-1)=1$. Ο $k$ πρέπει να κρατηθεί μυστικός.
2. Υπολόγισε $r=g^{k}modp$.
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\le r\le p-1$, αλλιώς απόρριψε την υπογραφή.
2. Υπολόγισε $u_1=y^r{r}^{s}modp$.
3. Υπολόγισε $h(m)$.
4. Υπολόγισε $u_2=g^h(m)modp$.
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