Υπογραφή ElGamal

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

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

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

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

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

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

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

Κρυπτογράφηση ElGamal[Επεξεργασία | επεξεργασία κώδικα]

  1. Αναπαράστησε το με ένα σύνολο απο τμήματα , το καθένα στο διάστημα .
  2. Διάλεξε έναν τυχαίο ακέραιο , τέτοιον ώστε .
  3. Υπολόγισε το και .

Το κρυπτογράφημα για τη είναι τα . Η αποκρυπτογραφεί κάθε ένα από τα , το οποίο είναι δυο φορές το μέγεθος του αρχικού μηνύματος,[2] χρησιμοποιώντας το και εκτελώντας:

Αποκρυπτογράφηση ElGamal[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

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

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

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

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

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