Υπογραφή ElGamal

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
(Ανακατεύθυνση από 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