Πρωτόκολλο Ντίφι-Χέλμαν

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

## Περιγραφή πρωτοκόλλου
Η πρωτότυπη εφαρμογή του πρωτοκόλλου χρησιμοποιεί την πολλαπλασιαστική ομάδα των ακεραίων 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.
Στέλνει λοιπόν στον Β τα 
:g=5, p=563, 59mod563 ≡ 1953125mod563 ≡ 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 πρέπει να είναι πρώτος αριθμός ή να έχει ως παράγοντα ένα πολύ μεγάλο πρώτο αριθμό για να αποφευχθεί η χρήση του αλγορίθμου των Πόλιγκ-Χέλμαν η όποια θα δώσει τους αριθμούς a, b. Έτσι πολύ συχνά αναζητούμε να βρούμε **πρώτους της Σόφι Ζερμαίν**, πρώτους δηλαδή για οποίους ισχύει ότι αν p είναι ο πρώτος μας τότε p = 2q + 1, όπου q επίσης πρώτος. Το g συνήθως το επιλέγουμε να παράγει την πολλαπλασιαστική υποομάδα τάξης q του G, και όχι ολόκληρη την G. Με αυτόν τον τρόπο εξασφαλίζουμε ότι το σύμβολο Λεζέντρ του g δεν πρόκειται να αποκαλύψει ποτέ κανένα ψηφίο του a.
Αν οι δυο οντότητες Α και Β δεν χρησιμοποιούν καλές γεννήτριες τυχαίων αριθμών, τότε τα a και b είναι πιθανόν να μπορούν να προσβληθούν από κάποιον ο οποίος παρακολουθεί τα δεδομένα που περνούν στο κανάλι. Πρέπει να τονίσουμε πως μετά το τέλος του πρωτοκόλλου, οι μυστικοί ακέραιοι a και b εξαφανίζονται και από τις δυο συσκευές των δυο οντοτήτων προκειμένου να μην μείνουν στοιχεία για περαιτέρω μελέτη από κάποιο άλλο πιθανό επιτιθέμενο.

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

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

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

Κατηγορία:Κρυπτογραφία