Άνοιγμα κυρίου μενού

Οι υπογραφές 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