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

Η κρυπτογραφία, πριν μόλις μία τριακονταετία, είχε ως μοναδικά πεδία εφαρμογής της το στρατό και τη διπλωματία. Οι τεχνικές οι οποίες χρησιμοποιούσε ήταν αρκετά απλές. Σήμερα, το πεδίο εφαρμογής της έχει επεκταθεί σημαντικά και περιλαμβάνει όλους τους τομείς στους οποίους η ασφαλής μετάδοση μηνυμάτων παίζει πρωτεύοντα ρόλο. Η ανάπτυξη της κοινωνίας της πληροφορίας και των δικτύων επικοινωνίας δημιούργησαν καινούργιες ανάγκες τις οποίες η κρυπτογραφία καλείται να καλύψει. Η σύγχρονη κρυπτογραφία δεν ασχολείται μόνο με την ασφαλή μετάδοση μηνυμάτων αλλά και με άλλα θέματα εξ ίσου σημαντικά, όπως η ακεραιότητα, αυθεντικότητα και αδυναμίας αποκήρυξη των μηνυμάτων. Η ανάπτυξη που γνωρίζει σήμερα η κρυπτογραφία οφείλεται κατά ένα μεγάλο μέρος στη χρήση της Θεωρίας Αριθμών, της Αλγεβρας και τη Θεωρίας Αλγορίθμων. Ειδικότερα, οι πρώτοι αριθμοί, τα πεπερασμένα σώματα και οι ελλειπτικές καμπύλες βρήκαν ένα πολύ ενδιαφέρον πεδίο εφαρμογής τους. Επίσης, η μεγάλη αύξηση των δυνατοτήτων των ηλεκτρονικών υπολογιστών έπαιξε καθοριστικό ρόλο. Χωρίς αυτή, η αποτελεσματικότητα πολλών αλγορίθμων ή πρωτοκόλλων δε θα ήταν δυνατόν να δοκιμαστεί.
Το παρόν σύγγραμμα απευθύνεται κυρίως σε φοιτητές και απόφοιτους τμημάτων Μαθηματικών και Πληροφορικής, αλλά και σ΄ οποιονδήποτε ενδιαφέρεται για την ασφαλή επικοινωνία. Βασίζεται κατά μεγάλο μέρος σ΄ ένα μάθημα που δίδαξα το χειμερινό εξάμηνο του πανεπιστημιακού έτους 2003-4 στην κατεύθυνση “Θεωρητική Πληροφορική και Θεωρία Συστημάτων” του Μεταπτυχιακού Προγράμματος του Τμήματος Μαθηματικών του ΑΠΘ. Απαραίτητες γνώσεις για την κατανόησή του είναι η βασική Θεωρία Αριθμών και Αλγεβρα.
Περιέχει 9 κεφάλαια. Στο πρώτο κεφάλαιο περιγράφονται μερικά απλά κλασικά κρυπτοσυστήματα έτσι, ώστε ο αναγνώστης να εξοικειωθεί με τις πρώτες έννοιες της κρυπτογραφίας. Το δεύτερο κεφάλαιο είναι αφιερωμένο στην ασφάλεια ενός κρυπτοσυστήματος κατά τον C. Shannon και στους καταγραφείς μετατόπισης με ανάδραση.
Στο τρίτο κεφάλαιο παρουσιάζονται βασικά θέματα από την Υπολογιστική Θεωρία Αριθμών. Το αντικείμενο του τέταρτου κεφαλαίου είναι το διάσημο πλέον κρυπτοσύστημα RSA και το κρυπτοσύστημα του Rabin. Στο πέμπτο κεφάλαιο περιγράφονται μερικές κλασικές μέθοδοι πιστοποίησης πρώτου και δίνεται μία εκδοχή του αλγόριθμου AKS. Το έκτο κεφάλαιο ασχολείται με την παραγοντοποίηση των ακεραίων. Το έβδομο κεφάλαιο είναι αφιερωμένο σε κρυπτοσυστήματα που βασίζονται στο πρόβλημα του διακριτού λογάριθμου και παρουσιάζονται μερικοί αλγόριθμοι για την επίλυσή του. Οι ψηφιακές υπογραφές είναι το θέμα του όγδοου κεφαλαίου. Τέλος, στο ένατο κεφάλαιο περιγράφονται μερικά κρυπτογραφικά πρωτόκολλα. Επίσης, για την ευκολία του αναγνώστη, μερικές στοιχειώδεις έννοιες από τη Θεωρία των Πιθανοτήτων περιλαμβάνονται σ΄ ένα παράρτημα.

Περιεχόμενα

1. Κλασική Κρυπτογραφία

1. Κρυπτογράφηση
2. Κρυπτανάλυση
3. Κυπτοσύστημα Μετατόπισης
4. Ομοπαραλληλικό Κρυπτοσύστημα
5. Κρυπτοσύστημα του Hill
6. Κρυπτοσύστημα Μετάθεσης
7. Κρυπτοσύστημα Αντικατάστασης
8. Κρυπτοσύστημα του Vigénere
9. Ασκήσεις

2. Τέλεια Ασφάλεια

1. Θεώρημα του Shannon
2. Κρυπτοσύστημα του Verman
3. Συστήματα Καταγραφής Μετατόπισης
4. Ακολουθίες Καταγραφής Μετατόπισης
5. Κρυπτανάλυση
6. Ασκήσεις

3. Βασική Υπολογιστική Θεωρία Αριθμών

1. Παράσταση Ακεραίου σε Κλίμακα
2. Δυαδικές Πράξεις
3. Αλγόριθμοι
4. Εκτεταμένος Ευκλείδειος Αλγόριθμος
5. Συνεχές Κλάσμα Ρητού
6. Συνάρτηση π(n)
7. Ισοτιμίες
8. Ασκήσεις

4. Τα κρυπτοσυστήματα RSA και Rabin

1. Κρυπτοσύστημα RSA
2. Παραγοντοποίηση Ακεραίων και RSA
3. Ασφάλεια του RSA
4. Ταχύτερη Αποκρυπτογράφηση
5. Κρυπτοσύστημα του Rabin
6. Τετραγωνικές ρίζες
7. Αποκρυπτογράφηση
8. Ασφάλεια του Κρυπτοσυστήματος Rabin
9. Ασκήσεις

5. Πιστοποίηση Πρώτου

1. Μέθοδος των Διαδοχικών Διαιρέσεων
2. Θεώρημα του Lucas
3. Κριτήριο του Fermat
4. Κριτήριο των Miller –Rabin
5. Μερικά Λήμματα
6. Αλγόριθμος AKS
7. Ασκήσεις

6. Παραγοντοποίηση Ακεραίων

1. Μέθοδος των Διαδοχικών Διαιρέσεων
2. Μέθοδος του Fermat
3. Αλγόριθμος του Dixon
4. Αλγόριθμος p – 1 του Pollard
5. Αλγόριθμος Po του Pollard
6. Ασκήσεις

7. Διακριτός Λογάριθμος

1. Πρόβλημα του Διακριτού Λογάριθμου
2. Πρωτόκολλο των Diffie – Hellman
3. Κρυπτοσύστημα του El Gamal
4. Ασφάλεια του Συστήματος El Gamal
5. Κρυπτοσύστημα των Okamoto – Uchiyama
6. Παραγοντοποίηση του n και Ασφάλεια
7. Αλγόριθμος του Shanks
8. Αλγόριθμος Po του Pollard
9. Αλγόριθμος των Polling – Hellman
10. Αλγόριθμος του Adleman
11. Ασκήσεις

8. Ψηφιακές Υπογραφές

1. Σχήμα Ψηφιακής Υπογραφής
2. Συναρτήσεις Συμπύκνωσης
3. Υπογραφή RSA
4. Υπογραφή El Gamal
5. Αλγόριθμος Ψηφιακής Υπογραφής
6. Ασκήσεις

9. Κρυπτογραφικά Πρωτόκολλα

1. Πρωτόκολλα
2. Κορώνα ή Γράμματα
3. Ανώνυμο Ψηφιακό Χρήμα
4. Πρόσβαση σε Σύστημα
5. Ψηφιακές Εκλογές
6. Ασκήσεις