Πρωτόκολλο Diffie-Hellman

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

Το πρωτόκολλο των Diffie-Hellman παρουσιάστηκε το 1976 από τους Whitfield Diffie και Martin Hellman. Πριν από τη δημιουργία αυτού κάθε κρυπτογραφική τεχνική βασιζόταν σε κάποιο προσυμφωνημένο κλειδί. Το συγκεκριμένο πρωτόκολλο είναι το πρώτο που προτάθηκε ώστε να επιτρέπει σε δυο οντότητες, χωρίς προηγούμενη επικοινωνία, να ανταλλάξουν ένα κοινό κλειδί μέσω ενός μη ασφαλούς διαύλου επικοινωνίας.

Περιγραφή πρωτοκόλλου[Επεξεργασία | επεξεργασία κώδικα]

Η πρωτότυπη εφαρμογή του πρωτοκόλλου χρησιμοποιεί την πολλαπλασιαστική ομάδα των ακεραίων modulo p, όπου p είναι πρώτος αριθμός και g είναι γεννήτορας της πολλαπλασιαστικής ομάδας mod p.

Τα βήματα του πρωτοκόλλου για δυο οντότητες Α και Β, οι οποίες θέλουν να ανταλλάξουν ένα μυστικό κλειδί, είναι τα ακόλουθα:

  • Ο Α υπολογίζει ένα μυστικό κλειδί a το οποίο δεν πρόκειται να αποκαλύψει σε κανένα στάδιο του πρωτοκόλλου και τους τυχαίους αριθμούς g, p επιλέγοντας για p έναν πρώτο αριθμό. Στέλνει στον Β το μήνυμα: 'g, p, ga mod p'.
  • Ο Β λαμβάνει το μήνυμα, επιλέγει με τη σειρά του ένα μυστικό κλειδί b, και στέλνει στον Α το μήνυμα: 'gb mod p'.

Μετά το τέλος αυτών των μηνυμάτων και οι δυο οντότητες γνωρίζουν έναν αριθμό ο οποίος δεν είναι γνωστός από κανένα άλλο, τον gab mod p. Παρά το γεγονός ότι μέσα στο μη ασφαλές κανάλι έχουν περάσει οι πληροφορίες: g,p,gamodp, gbmodp, κανένας άλλος, εκτός των Α και Β δεν μπορεί να υπολογίσει το gabmodp, καθώς κάτι τέτοιο θα σημαίνει ουσιαστικά ότι είναι δυνατό σε ρεαλιστικό χρόνο να υπολογιστεί ο διακριτός λογάριθμος.

Παράδειγμα εφαρμογής του πρωτοκόλλου[Επεξεργασία | επεξεργασία κώδικα]

Έστω ότι ο Α διαλέγει τους παρακάτω αριθμούς:

p=563, g=5, a=9.

Στέλνει λοιπόν στον Β:

5,563,59mod563 ≡ 5,563,1953125mod563 ≡ 5,563,78

Ο Β επιλέγει b =14 και στέλνει στον Α:

514mod563 ≡ 6103515625mod563 ≡ 534

Τώρα και οι δυο μπορούν να υπολογίσουν το

(gamod p)bmod p ≡ (gb mod p)amod p ≡ gabmod p ≡ 153312511596308814665178236828300148736 mod 563 = 117

Συνεπώς το μυστικό κλειδί είναι το 117.

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

Η ασφάλεια του πρωτοκόλλου είναι στενά συνδεδεμένη με την επιλογή των στοιχείων p και g. Κάποιος ο οποίος θέλει να επιτεθεί στο πρωτόκολλο πρέπει ουσιαστικά να αποκτήσει τα g,a και b. Προκειμένου να αποφευχθεί κάτι τέτοιο πρέπει να προσέξουμε τις επιλογές των g, a, b, p. Η τάξη G του g πρέπει να είναι πρώτος αριθμός ή να έχει ως παράγοντα ένα πολύ μεγάλο πρώτο αριθμό για να αποφευχθεί η χρήση του αλγορίθμου των Pohlig-Hellman η όποια θα δώσει τους αριθμούς a, b. Έτσι πολύ συχνά αναζητούμε να βρούμε πρώτους της Sophie Germain, πρώτους δηλαδή για οποίους ισχύει ότι αν p είναι ο πρώτος μας τότε p = 2q + 1, όπου q επίσης πρώτος. Το g συνήθως το επιλέγουμε να παράγει την πολλαπλασιαστική υποομάδα τάξης q του G, και όχι ολόκληρη την G. Με αυτόν τον τρόπο εξασφαλίζουμε ότι το σύμβολο Legendre του g δεν πρόκειται να αποκαλύψει ποτέ κανένα ψηφίο του a.
Αν οι δυο οντότητες Α και Β δεν χρησιμοποιούν καλές γεννήτριες τυχαίων αριθμών, τότε τα a και b είναι πιθανόν να μπορούν να προσβληθούν από κάποιον ο οποίος παρακολουθεί τα δεδομένα που περνούν στο κανάλι. Πρέπει να τονίσουμε πως μετά το τέλος του πρωτοκόλλου, οι μυστικοί ακέραιοι a και b εξαφανίζονται και από τις δυο συσκευές των δυο οντοτήτων προκειμένου να μην μείνουν στοιχεία για περαιτέρω μελέτη από κάποιο άλλο πιθανό επιτιθέμενο.

Επίθεση επανάληψης[Επεξεργασία | επεξεργασία κώδικα]

Το πρωτόκολλο έχει ένα βασικό πρόβλημα το οποίο έχει να κάνει με το γεγονός ότι σε κανένα μήνυμα που ανταλλάσσεται μεταξύ των οντοτήτων δεν γίνεται επικύρωση της ώρας κατά της οποία έγινε η επικοινωνία. Αυτό έχει ως αποτέλεσμα ένας επιτιθέμενος να μπορεί να επαναλάβει την όλη επικοινωνία την οποία έχει προηγουμένως καταγράψει μεταξύ δυο οντοτήτων, προκειμένου να εξαπατήσει μια από αυτές. Η λύση του προβλήματος δίνεται μέσω χρονοσφραγίδων (timestamps), φαινομενικά τυχαίων αριθμών οι οποίοι παράγονται από το σύστημα και έχουν αποθηκευμένη μέσα τους την ώρα έκδοσης τους.

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

Κατά τη διάρκεια της αρχικής περιγραφής, το πρωτόκολλο Diffie-Hellman από μόνο του δεν παρέχει πιστοποίηση της ταυτότητας των οντοτήτων της επικοινωνίας και επομένως είναι ευάλωτο σε μία Man-in-the-middle επίθεση. Ένα ενδιάμεσο άτομο μπορεί δηλαδή να συστήσει δύο διακριτές Diffie-Hellman ανταλλαγές κλειδιών, μία με τη μία οντότητα και μία με την άλλη , υποδυόμενος στην κάθε μία οντότητα την άλλη. Συνεπώς, είναι απαραίτητο κατά τη χρήση του πρωτοκόλλου να γίνεται εξακρίβωση της ταυτότητας της κάθε οντότητας για την πρόληψη αυτού του είδους των επιθέσεων

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

  • Ν. Αλεξανδρής, Β. Χρυσικόπουλος, Κ. Πατσάκης, Εισαγωγή στη Θεωρία Πληροφοριών, Κωδικών & Κρυπτογραφίας, Βαρβαρήγου, 2008.
  • Β. Α. Κάτος, Γ. Χ. Στεφανίδης, Τεχνικές Κρυπτογραφίας & Κρυπτοανάλυσης, Ζυγός,2003.
  • http://cgi.di.uoa.gr/~aggelos/crypto/page9/assets/5_diffie_handout_gr.pdf