Υπογραφή ElGamal

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

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

 Επίλεξε ένα μεγάλου μεγέθους πρώτο αριθμό  και ένα γεννήτορα  για μια ομάδα .
 Επίλεξε έναν τυχαίο αριθμό , τέτοιον ώστε  .
 Υπολόγισε .

Το δημόσιο κλειδί του  είναι το  και το ιδιωτικό του κλειδί είναι
το .

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

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

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

 Αναπαράστησε το  με ένα σύνολο απο τμήματα , το καθένα στο διάστημα .
 Διάλεξε έναν τυχαίο ακέραιο , τέτοιον ώστε .
 Υπολόγισε το  και .
 
Το κρυπτογράφημα για τη  είναι τα . Η  αποκρυπτογραφεί κάθε ένα από τα , το οποίο είναι δυο φορές το μέγεθος του αρχικού μηνύματος, χρησιμοποιώντας το  και εκτελώντας:

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

 Υπολόγισε το .
 Υπολόγισε το .

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

Η υπογραφή ElGamal είναι ένα τυχαίο σχήμα και δημιουργεί υπογραφές με προσθήκη, χρησιμοποιώντας μια μονόδρομη συνάρτηση σύνοψης .
Για να υπογράψει ένα μήνυμα  οποιουδήποτε μήκους, ο  εκτελεί τον παρακάτω αλγόριθμο με το ιδιωτικό του κλειδί :

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

 Επέλεξε έναν τυχαίο ακέραιο , τέτοιον ώστε  και . Ο  πρέπει να κρατηθεί μυστικός.
 Υπολόγισε .
 Υπολόγισε .
 Υπολόγισε .

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

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

 Επιβεβαίωσε ότι , αλλιώς απόρριψε την υπογραφή.
 Υπολόγισε .
 Υπολόγισε .
 Υπολόγισε .
 Έλεγξε αν . Αν ναι, αποδέξου την υπογραφή.

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

Παραπομπές

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

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