Υπογραφή ElGamal

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

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

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

Το δημόσιο κλειδί του A είναι το E_A = (p, g, y) και το ιδιωτικό του κλειδί είναι
το D_A = x.

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

E_B και εκτελεί τον παρακάτω αλγόριθμο:

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

# Αναπαράστησε το m με ένα σύνολο απο τμήματα m_i, το καθένα στο διάστημα [0, p-1].
# Διάλεξε έναν τυχαίο ακέραιο k, τέτοιον ώστε 1 \le k \le p - 2.
# Υπολόγισε το a = g^k \ mod \ p και b = m_i y^k \ mod \ p.
 
Το κρυπτογράφημα για τη B είναι τα (a, b). Η B αποκρυπτογραφεί κάθε ένα από τα (a, b), το οποίο είναι δυο φορές το μέγεθος του αρχικού μηνύματος, χρησιμοποιώντας το D_B και εκτελώντας:

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

# Υπολόγισε το a^{p - 1 - x} \ mod \ p.
# Υπολόγισε το m_i = a^{-x} b \ mod \ p.

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

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

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

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

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

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

# Επιβεβαίωσε ότι 1 \le r \le p - 1, αλλιώς απόρριψε την υπογραφή.
# Υπολόγισε u_1 = y^r r^s \ mod \ p.
# Υπολόγισε h(m).
# Υπολόγισε u_2 = g^h(m) \ mod \ p.
# Έλεγξε αν 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

Κατηγορία:Κρυπτογραφικοί αλγόριθμοι