Υπογραφή ElGamal

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

Δημιουργία κλειδιών ElGamal[Επεξεργασία | επεξεργασία κώδικα]

  1. Επέλεξε ένα μεγάλου μεγέθους πρώτο αριθμό p και ένα γεννήτορα g για μια ομάδα \mathbb{Z}_p^*.
  2. Επέλεξε έναν τυχαίο αριθμό x, τέτοιον ώστε 1 \le x \le 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 \le k \le p - 2.
  3. Υπολόγισε το a = g^k \ mod \ p και b = m_i y^k \ mod \ p.

Το κρυπτογράφημα για τη B είναι τα (a, b). Η B αποκρυπτογραφεί κάθε ένα από τα (a, b), το οποίο είναι δυο φορές το μέγεθος του αρχικού μηνύματος,[2] χρησιμοποιώντας το 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 \le k \le 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. [3]Οποιαδήποτε άλλη οντότητα που έχει το E_A μπορεί να επιβεβαιώσει την υπογραφή με τα παρακάτω βήματα:

Επιβεβαίωση Υπογραφής ElGamal[Επεξεργασία | επεξεργασία κώδικα]

  1. Επιβεβαίωσε ότι 1 \le r \le 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 ή μεγαλύτερου.

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

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

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

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