Πρότυπο ElGamal

Ορισμός - Πρότυπο ψηφιακών υπογραφών ElGamal

Η ασφάλεια του συστήµατος των ψηφιακών υπογραφών ElGamal βασίζεται στη δυσκολία του υπολογισµού του διακριτού λογάριθµου από τον αντίπαλο. Για την υλοποίηση του συστήµατος ψηφιακών υπογραφών ElGamal απαιτείται κρυπτογραφική µονόδροµη hash, της οποίας η σύνοψη είναι στοιχείο του συνόλου Ζp*, όπου p πρώτος αριθµός.
Η υποδοµή ενός συστήµατος ψηφιακών υπογραφών ElGamal απαιτεί την ακόλουθη διαδικασία δηµιουργίας ζεύγους κλειδιών από τα µέλη. Αρχικά επιλέγεταιένας µεγάλος πρώτος αριθµός p και ένας ακέραιος a ο οποίος είναι γεννήτορας του συνόλου Ζp*. Στη συνέχεια επιλέγεται ένας ακέραιος b τέτοιος ώστε 0 < b < p–1, και υπολογίζεται το:

y ≡ aᵇ (mod p)
Το δηµόσιο κλειδί αποτελείται από τους τρεις ακέραιους (p, a, y) ενώ το ιδιωτικό κλειδί είναι ο εκθέτης b. Η παραπάνω διαδικασία εκτελείται από κάθε µέλος. Κατά τη διαδικασία υπογραφής, εκτελείται το ακόλουθο πρωτόκολλο:
1. Επιλογή µυστικού ακεραίου k, µε 0 < k < p–1, και gcd(k, p–1) = 1

2. Υπολογισµός του r ≡ aᵇ (mod p)

3. Υπολογισµός του k⁻¹ mod p

4. Υπολογισµός του s ≡ k⁻¹ (h(m) – br) (mod p–1)

5. Η υπογραφή για το µήνυµα m είναι το ζεύγος (r, s), το οποίο αποστέλλεται µαζί µε το µήνυµα στον παραλήπτη.
Η διαδικασία επαλήθευσης πραγµατοποιείται µε το ακόλουθο πρωτόκολλο:

1. Έλεγχος ότι 0 < r < p–1. Στην περίπτωση που το r δε βρίσκεται µεταξύ των ενδεδειγµένων ορίων, απορρίπτεται η ψηφιακή υπογραφή.

2.Υπολογισµός του v ≡ yʳrˢ (mod p).

3.Υπολογισµός της σύνοψης h(m) και υπολογισµός του v' ≡ a (mod p).

4.Η υπογραφή θεωρείται έγκυρη αν και µόνο αν v = v΄.

Μπορούµε να επαληθεύσουµε την εγκυρότητα της υπογραφής µε την ισοδυναµία του τελευταίου βήµατος του πρωτοκόλλου επαλήθευσης ως εξής:

s ≡ k⁻¹(h(m)-br) (mod p-1)⇒

ks ≡ h(m)-br (mod p-1)⇒

h(m) ≡ ks + br (mod p-1)⇒

a ≡ aᵏˢ ⁺ ᵇʳ(mod p)⇒

a ≡ (aᵇ)ʳ(aᵏ)ˢ (mod p)⇒

a ≡ yʳrˢ (mod p)

ή ισοδύναµα v΄ = v

Ασφάλεια του συστήµατος ψηφιακών υπογραφών ElGamal

Αν θεωρήσουµε ότι το πρόβληµα του διακριτού λογάριθµου είναι υπολογιστικά αδύνατο, τότε αν ο αντίπαλος επιλέξει στην τύχη έναν ακέραιο για υποψήφιο ιδιωτικό κλειδί, η πιθανότητα να επιλέξει το σωστό κλειδί είναι ίση µε 1/(p–1), εφόσον οι επιτρεπτές τιµές του ιδιωτικού κλειδιού βρίσκονται στο διάστηµα 0 < b < p–1. Εποµένως, το p θα πρέπει να είναι αρκετά µεγάλο ώστε η πιθανότητα εύρεσης του ιδιωτικού κλειδιού να είναι µικρή.

Ένα άλλο σηµείο το οποίο θέτει σε κίνδυνο το σύστηµα δίνοντας πλεονέκτηµα για επιτυχή πλαστογραφία, είναι η επιλογή του τυχαίου ακέραιου k, κατά τη διαδικασία δηµιουργίας της ψηφιακής υπογραφής. Πιο συγκεκριµένα, ο υπογεγραµµένος θα πρέπει να διατηρεί ιστορικό όλων των τυχαίων αριθµών που έχει επιλέξει, ώστε σε κάθε υπογραφή να χρησιµοποιείται διαφορετικός ακέραιος k.

Πρότυπο ElGamal

Το πρότυπο ηλεκτρονικής υπογραφής ElGamal δημιουργήθηκε το 1984 από τον Taher ElGamal παράλληλα με τον αντίστοιχο αλγόριθμο δημοσίου κλειδιού.

Για την περιγραφή του αλγορίθμου, υποθέτουμε πως διαθέτουμε μια ¨καλή¨ συνάρτηση κατακερματισμού Η. Έστω τώρα ένας αρκετά μεγάλος αριθμός p και έστω g ένα στοιχείο γεννήτορας της πολλαπλασιαστικής ομάδας των ακεραίων modulo p, την Z*ₚ.Επιλέγουμε ένα τυχαίο αριθμό x, με 1 < x < p - 1 και υπολογίζουμε τον

y = gˣ mod p.
Ο x θα είναι το ιδιωτικό κλειδί, ενώ η τριάδα (p, g, y) είναι το δημόσιο κλειδί.

Για να υπογραφεί ένα μήνυμα m, ο υπογράφων επιλέγει αρχικά έναν τυχαίο k, 1 < k < p - 1 και (k, p - 1) = 1. Στη συνέχεια υπολογίζονται οι αριθμοί

r ≡ gᵏ mod p

s ≡ (H(m) - xr)k⁻¹ mod (p-1)

Στην περίπτωση που s = 0, επιλέγεται νέο k και υπολογίζονται εκ νέου οι r και s. Το ζεύγος (r, s) είναι η ψηφιακή υπογραφή του μηνύματος m.

Για την επικύρωση της υπογραφής κάποιος ο οποίος λαμβάνει το μήνυμα m και την ψηφιακή υπογραφή (r, s), αρκεί να υπολογήσει την ποσότητα g mod p και να ελέγξει αν είναι ίση με yʳrˢ mod p.

Το H(m) μπορεί να εκφραστεί ως:

H(m) ≡ xr + sk mod (p - 1)

Η ποσότητα g θα είναι ίση

g ≡ gˣʳ ⁺ ˢᵏ mod p

≡ gˣʳgˢᵏ mod p

≡(gˣ)ʳ(gᵏ)ˢ mod p

≡ yʳrˢ mod p

Συνεπώς ο αλγόριθμος είναι επιτυχής.