Στοιχεία Θεωρίας Αριθμών και Εφαρμογές στην Κρυπτογραφία (ΣΗΜΜΥ)
Κρυπτογραφία και Πολυπλοκότητα (ΣΕΜΦΕ, ΜΠΛΑ)
χειμερινό εξάμηνο 2011-2012

● Γενικά ● Ανακοινώσεις ● Υλικό ●

Γενικά

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Άρης Παγουρτζής, Eπίκουρος Καθηγητής ()

Βοηθοί διδασκαλίας

  • Ελένη Μπακάλη, Υ.Δ. ()
  • Δημήτρης Σακαβάλας, Υ.Δ. ()

Ώρες - αίθουσα - ώρες γραφείου

  • Δευτέρα, 10:45-13:30 (Θεωρία)
  • Παρασκευή, 11:45-12:30 (ασκήσεις)
  • αίθουσα 1.1.29 (κτ. Ηλεκτρολόγων)
  • Ώρες γραφείου: Τετάρτη 15:00-17:00, στο CoReLab (1.1.30)

Βαθμολογικό σχήμα

  • Ασκήσεις: 2 μονάδες.
  • Εργασία: 2 μονάδες.
  • Καταγραφή σημειώσεων μαθήματος (μίας εβδομάδας): 1 μονάδα.
  • Τελικό διαγώνισμα: 6 μονάδες. Προϋπόθεση για το "πέντε": 2/6 στο τελικό διαγώνισμα.

Βιβλιογραφία

  1. Σημειώσεις Ε. Ζάχου, ΕΜΠ, 2007.
  2. D. Stinson: Cryptography: Theory and Practice, 3rd edition, CRC Press, 2005.
  3. A. Menezes, P. van Oorschot, and C. Vanstone: Handbook of Applied Cryptography: http://www.cacr.math.uwaterloo.ca/hac.
  4. V. Shoup: A Computational Introduction to Number Theory and Algebra: http://shoup.net/ntb/.
  5. B. Schneier: Applied Cryptography: http://www.schneier.com/book-applied.html.
  6. W.Trappe, L. Washington: Introduction to Cryptography with Coding Theory.
  7. A.Κιαγιάς: Τεχνικές Σύγχρονης Κρυπτογραφίας: σημειώσεις

Ανακοινώσεις

  • 27/9/2012: Η εξέταση της 28/9/2012 θα πραγματοποιηθεί στην αίθουσα όπου διδασκόταν το μάθημα (1.1.29, παλ.κτ. Ηλεκτρολόγων).
  • 4/5/2012: Βαθμολογία κανονικής περιόδου: pdf
  • 19/2/2012: Ενδεικτικό διαγώνισμα (τα θέματα 1-6 ήταν με κλειστά βιβλία, τα υπόλοιπα με ανοιχτά): pdf
  • 18/2/2012: Η εξέταση της 20/2/2012 θα αρχίσει στις 11:00 και θα γίνει στην αίθουσα 1.1.29 (παλιό κτ. Ηλεκτρολόγων ΕΜΠ). Θα περιλαμβάνει ένα μέρος με κλειστά βιβλίά και ένα με ανοιχτά. Ύλη μαθήματος για την εξέταση: (α) Σημ. Ζάχου: κεφ. 1, 2 (συνοπτικά), 3, 6, 7 (AKS συνοπτικά), 8, 9, 11 (συνοπτικά), 12, 13, 14, 15, 16, 17 (συνοπτικά) (β) Σημειώσεις διαλέξεων και αναφορές που θα βρείτε εκεί.
  • 7/2/2012: Ενδεικτικό πρόγραμμα παρουσιάσεων: εδώ.
  • 6/2/2012: Την Τετάρτη 8/2/2012, ώρα 1μμ-4μμ, θα γίνει αναπλήρωση του μαθήματος της 30/1.

Ύλη Διαλέξεων και Σημειώσεις

Ημερο-μηνία Διδαχθείσα Ύλη Σημειώσεις
7/11 Διοικητικά του μαθήματος. Εισαγωγή στην κρυπτογραφία και κρυπτολογία. Κλασικά συστήματα (Καίσαρα, ολίσθησης, αντικατάστασης. Affine cipher, Vigenere cipher). Κρυπτανάλυση συστημάτων αντικατάστασης με στατιστικές συχνότητες. Κρυπτανάλυση Vigenere με Kasiski test, και χρήση δείκτη σύμπτωσης (Coincidence Index). Εισαγωγή σε κρυπτογραφία δημοσίου κλειδιού: το κρυπτοσύστημα Σακιδίου (Merkle). pdf (τελικές, διορθωμένες)
11/11 Ασκήσεις: διανομή κλειδιών μεταξύ πολλών, διαμοιρασμός μυστικού, κρυπτανάλυση του XOR cipher με χρήση δείκτη σύμπτωσης. pdf (draft)
14/11 Κρυπτοσυστήματα ρεύματος (stream ciphers): περίοδος κλειδιού, linear feedback shift registers. Κρυπτοσυστήματα πακέτου (block ciphers): τρόποι χρήσης (ECB mode, CBC mode). Κρυπταναλυτικές επιθέσεις. Μερικά ακόμη κλασικά κρυπτοσυστήματα: affine, permutation, product cryptosystems. Τέλεια μυστικότητα (perfect secrecy - Shannon). Απόδειξη για το one-time pad και για το shift cipher με τυχαίο κλειδί. pdf (ημι-διορθωμένες)
18/11 Ασκήσεις: επίδραση λαθών στην αλυσωτή σύνδεση πακέτων (CBC mode), διανομή κλειδιών σε DVD players, αποτυχία τέλειας μυστικότητας σε επανάληψη χρήσης κλειδιών. pdf (ημι-διορθωμένες)
21/11 Δίκτυα Feistel, αποκρυπτογράφηση με αντιστροφή κλειδιών. Το κρυπτοσύστημα DES: S-boxes, διαφορική κρυπτανάλυση. Εισαγωγή στη Θεωρία Αριθμών. Διαιρετότητα, πρώτοι αριθμοί. Το Θεμελιώδες Θεώρημα της Αριθμητικής. - DES: pdf (draft)
- Θεωρία αριθμών: pdf (draft)
25/11 Ασκήσεις: ιδιότητα συμπληρωματικότητας του DES (CPA attack), 2-πλό DES ('meet in the middle' attack). pdf (draft)
28/11 Αποδοτικοί αριθμητικοί αλγόριθμοι: αλγόριθμος Ευκλείδη (απλός και επεκτεταμένος), υπολογισμός αντιστρόφου modulo n, επαναλαμβανόμενος τετραγωνισμός. Η συνάρτηση φ του Euler. Ομάδες, δακτύλιοι, ισοτιμίες modulo n. Θεωρήματα Fermat, Euler, Lagrange. Κινέζικο θεώρημα υπολοίπων. pdf (draft)
2/12 Ασκήσεις: επίλυση γραμμικής ισοτιμίας, επίλυση τετραγωνικής ισοτιμίας (εύρεση τετραγωνικών ριζών modulo n). pdf (draft)
5/12 Αποδείξεις Θεωρήματος Fermat και Κινέζικου θεωρήματος υπολοίπων. Τετραγωνικά υπόλοιπα. Σύμβολα Legendre και Jacobi: αποδοτικός υπολογισμός (κριτήριο Euler, νόμος τετραγωνικής αντιστροφής). Το κρυπτοσύστημα RSA: ορισμός, ορθότητα, επίθεση κοινού γινομένου. pdf (draft)
9/12 Ασκήσεις: επιθέσεις στο RSA, τάξη γινομένου στοιχείων ομάδας. pdf (ημι-διορθωμένες)
12/12 RSA: αποκάλυψη ιδιωτικού κλειδιού => πιθανοτικός αλγόριθμος παραγοντοποίησης του modulus. Έλεγχοι πρώτων αριθμών: Fermat test, Miller-Rabin test. Aπόδειξη ορθότητας του ελέγχου Miller-Rabin. pdf (ημι-διορθωμένες)
16/12 Ασκήσεις: ασφάλεια των bits του κρυπτοκειμένου στο RSA. Hard-core predicates. Απόδειξη Θεωρήματος Wilson. Χρήση του Θ. Wilson για διαφορετική απόδειξη κριτηρίου Euler. pdf (draft)
19/12 Το κρυπτοσύστημα Rabin, ισοδυναμία με παραγοντοποίηση. Το πρόβλημα του Διακριτού Λογαρίθμου (DLP). Αλγόριθμος Shanks για το DLP. Το πρόβλημα Diffie-Hellman (DHP). Το πρωτόκολλο ανταλλαγής κλειδιού Diffie-Hellman. Το κρυπτοσύστημα El Gamal. Η σχετική δυσκολία του σπασίματος του El Gamal, του DHP, και του DLP. Το κρυπτοσύστημα Massey-Omura, και το σχήμα 3 περασμάτων του Shamir. Man-in-the-middle attack. Κρυπτοσυστήματα βασισμένα σε ελλειπτικές καμπύλες (συνοπτική αναφορά). (Σημ. Ζάχου: κεφ. 8.4, 9)
23/12 Ασκήσεις: ασφάλεια των bits του Διακριτού Λογαρίθμου. Προβλήματα ασφάλειας στο σχήμα 3 περασμάτων του Shamir. Απόδειξη ότι οι πρώτοι της μορφής $4k+1$ είναι άπειροι. (υπό προετοιμασία)
9/1 Πολυπλοκότητα του προβλήματος της Παραγοντοποίησης (Factoring). Η τομή των κλάσεων NP και co-NP, η κλάση BQP, υποεκθετικοί αλγόριθμοι. Αλγόριθμοι παραγοντοποίησης: μέθοδος ρ του Pollard (ανάλυση πολυπλοκότητας με παράδοξο γενεθλίων), μέθοδος βάσεων παραγόντων (Dixon). (Σημ. Ζάχου: κεφ. 7.3)
13/1 Ασκήσεις: Παράδοξο Γενεθλίων (εύρεση πλήθους δοκιμών ώστε πιθανότητα σύγκρουσης > 1/2). Επίθεση σε υπογραφές RSA που υπολογίζονται ξεχωριστά modulo p και modulo q, και συνδυάζονται με CRT. Εύρεση διακριτού λογαρίθμου σε ομάδα τάξης 2^m. pdf (draft)
16/1 Ψηφιακές υπογραφές: σχήματα RSA, El Gamal, DSS (Digital Signature Standard). Ζητήματα ασφάλειας: δυνατότητα παραγωγής υπογραφής για τυχαίο κείμενο. Συναρτήσεις πλεονάζουσας πληροφορίας. Μείωση του μεγέθους υπογραφής στο DSS: η χρήση υποομάδας με τάξη q|(p-1). Υπογραφές μιας χρήσης: το σχήμα υπογραφής Lamport, και η βελτίωση Bos-Chaum. (Σημ. Ζάχου: κεφ. 12)
20/1 Ασκήσεις: η υποομάδα του Zp* τάξης d|(p-1). Συνεργατικές υπογραφές RSA. pdf (draft)
23/1 Ψηφιακές υπογραφές επιπρόσθετης λειτουργικότητας: τυφλές υπογραφές, αδιαμφισβήτητες υπογραφές. Σχήμα Chaum-van Antwerpen: απόδειξη ασφάλειας χωρίς προϋποθέσεις (unconditional security), πρωτόκολλο αποκήρυξης. Συναρτήσεις κατακερματισμού (hash functions): ορισμοί, επιθυμητές ιδιότητες (ισχυρή/ασθενής ελευθερία συγκρούσεων, ιδιότητα μονής κατεύθυνσης, αντίσταση 1ου και 2ου ορίσματος). Ιεράρχηση επιθυμητών ιδιοτήτων. pdf (draft)
27/1 Ειδικά θέματα. Εισαγωγή στη θεωρία πολυπλοκότητας. Πιθανοτικοί και μη ντετερμινιστικοί υπολογισμοί. Εισαγωγή στην ομομορφική κρυπτογράφηση. (Σημ. Ζάχου: κεφ. 16)
3/2 Συνάρτηση κατακερματισμού Chaum-van Heisjt-Pfitzmann: ελευθερία συγκρούσεων ανν ισχύει η υπόθεση Διακριτού Λογαρίθμου. Μέθοδος Merkle-Damgard για επέκταση συναρτήσεων κατακερματισμού. Identification schemes: μέθοδος κατασκευής από κρυπτοσυστήματα (κλασσικά και δημοσίου κλειδιού). Εφαρμογή με κρυπτοσύστημα Rabin: πιθανή διαρροή ιδιωτικού κλειδιού. pdf (draft)
6/2 Θεωρία υπολογιστικής πολυπλοκότητας. Μη-ντετερμινιστικοί και πιθανοτικοί αλγόριθμοι. Κλάσεις P, NP, BPP, RP, ZPP. Ενιαία αναπαράσταση με δένδρα υπολογισμού. Τεχνικές ενίσχυσης της πιθανότητας σωστής απάντησης στους πιθανοτικούς αλγόριθμους. Πλειοψηφικοί ποσοδείκτες. Παίγνια Arthur-Merlin και συστήματα διαλογικών αποδείξεων. Αποδείξεις μηδενικής γνώσης. (Σημ. Ζάχου: κεφ. 16, 17)
8/2 Σχήματα αναγνώρισης / ταυτοποίησης. Μέθοδος κατασκευής από κρυπτοσυστήματα κλασικά ή δημοσίου κλειδιού. Πρόκληση-ανταπόκριση. Το σχήμα Fiat-Shamir και το σχήμα Feige-Fiat-Shamir. Το σχήμα αναγνώρισης Schnorr και το σχήμα Okamoto: αποδείξεις ασφάλειας. Πιθανοτική κρυπτογράφηση: μέθοδοι Goldwasser-Micali και Blum-Goldwasser. Γεννήτρια ψευδοτυχαίων Blum-Blum-Shub. (Σημ. Ζάχου: κεφ. 14, 15, Σύγχρονη Κρυπτογραφία: κεφ. 13.4)
13/2 Παρουσιάσεις εργασιών. slides
17/2 Παρουσιάσεις εργασιών. slides

Ασκήσεις

Εργασία

Κείμενα για συμπληρωματική μελέτη

  • Ε. Ζάχος, Α. Παγουρτζής, Δ. Φωτάκης: "Σύντομη Εισαγωγή στη Θεωρία Πολυπλοκότητας":pdf
  • Ε. Ζάχος: "Computational Complexity Notes (in English)":pdf
  • V. Shoup: "A Primer on Algebra and Number Theory for Computer Scientists":pdf
  • R. Rivest, A. Shamir, L. Adleman: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems": ps (gzipped), pdf.
  • W. Diffie, M. Hellman: "New Directions in Cryptography": ps (gzipped), pdf.
  • S. Goldwasser, M. Belare: Lecture Notes on Cryptography: pdf.
  • M. Agrawal, N. Kayal, N. Saxena: Primality is in P: pdf.

Links

Τελευταία ανανέωση: 4/5/2012