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

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

Γενικά

Διδάσκοντες

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

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

  • Δημήτρης Σακαβάλας, Υ.Δ. ()
  • Παναγιώτης Γροντάς, Υ.Δ. ()

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

  • ΠΡΟΣΟΧΗ: ΝΕΑ αλλαγή στις ώρες!
  • Δευτέρα, 10:45-12:30 (θεωρία)
  • Παρασκευή, 12:45-14:30 (θεωρία - ασκήσεις)
  • Αίθουσα 1.1.29 (παλιό κτ. Ηλεκτρολόγων ΕΜΠ) -- ΠΡΟΣΟΧΗ: προσωρινά ενδέχεται να χρησιμοποιηθεί η αίθουσα 1.1.31 (επίσης στο παλ. κτ. Ηλεκτρολόγων)
  • Ώρες γραφείου: Τετάρτη 15:00-17:00, στο CoReLab (1.1.30)

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

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

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

  • [25/6/2014]: Βαθμολογία κανονικής περιόδου ακαδ. έτους 2013-14: pdf.
  • [22/3/2014]: Αναρτήθηκε η τρίτη σειρά ασκήσεων (δείτε παρακάτω).
  • 11/3/2014]: η εξέταση του μαθήματος μεταφέρεται στις 10/4, ώρα 3μμ-6μμ, στην ίδια αίθουσα (1.1.29, παλ.κτ. Ηλεκτρολόγων).
  • [6/3/2014]: Αναρτήθηκε το πρόγραμμα παρουσιάσεων της 7/3 (δείτε παρακάτω).
  • [13/2/2014]: Αναρτήθηκε η δεύτερη σειρά ασκήσεων (δείτε παρακάτω).
  • 27/12/2013: Αναρτήθηκε η πρώτη σειρά ασκήσεων (δείτε παρακάτω).
  • [27/11/2013]: Πρώτη συνάντηση και σύντομη εισαγωγή: στις 29/11/2013. Πρώτο μάθημα: 2/12/2013

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

    Η ύλη θα ενημερώνεται τακτικά. Για ενδεικτική ύλη και σημειώσεις του μαθήματος δείτε και την σελίδα του ακ. έτους 2012-2013.
Ημερομηνία Περιεχόμενο διάλεξης Διαφάνειες
29/11 Διοικητικά του μαθήματος. Εισαγωγή στην κρυπτογραφία και κρυπτολογία. Συμμετρική κρυπτογραφία vs κρυπτογραφία Δημοσίου Κλειδιού: μια πρώτη ματιά. pdf
2/12 Κλασικά συστήματα (Καίσαρα, ολίσθησης, αντικατάστασης. Vigenere cipher). Κρυπτανάλυση συστημάτων αντικατάστασης με στατιστικές συχνότητες. Κρυπτανάλυση Vigenere με Kasiski test, και χρήση δείκτη σύμπτωσης (Coincidence Index). Τέλεια μυστικότητα (perfect secrecy). pdf (1-18)
6/12 Random Shift cipher. Ισοδύναμες συνθήκες τέλειας μυστικότητας. Μήκος κλειδιού. One-time pad. Κρυπτοσυστήματα γινομένου. Ασκήσεις. pdf (19-28)
9/12 Κρυπτοσυστήματα ροής. Κρυπτοσύστημα σακιδίου. Κρυπτοσυστήματα τμήματος. Τα δίκτυα Feistel. Aποκρυπτογράφηση με αντιστροφή κλειδιών. Εισαγωγή στο κρυπτοσύστημα DES. pdf (29-37) pdf (1-4)
13/12 Το κρυπτοσύστημα DES: ο ρόλος των S-boxes. Σύγχυση και διάχυση. Κριτήρια σχεδιασμού. Το πρόγραμμα παραγωγής κλειδιών. Επιθέσεις στο DES, MITM attack. Βελτιώσεις: 3-DES, DES-X. pdf (5-13)
16/12 Κρυπτοσυστήματα τμήματος (block ciphers): τρόποι λειτουργίας ECB, CBC, CFB, OFB, CTR. Επίδραση λαθών μετάδοσης, self-recovery. Χρήση CBC και CFB για ακεραιότητα, αυθεντικοποίηση (MAC). Authenticated encryption. Παραγωγή key stream από CFB/OFB/CTR.
Εισαγωγή στη Θεωρία Αριθμών. Διαιρετότητα, βασικές ιδιότητες. 		pdf (14-18) pdf (1-4)
20/12 Ασκήσεις σε κλασικά και συμμετρικά κρυπτοσυστήματα.
23/12 Μέγιστος κοινός διαιρέτης. Το Θεμελιώδες Θεώρημα της Αριθμητικής. Αλγόριθμος Ευκλείδη (απλός και επεκτεταμένος), υπολογισμός αντιστρόφου modulo n. Η συνάρτηση φ του Euler. pdf (5-11)
10/1 Αριθμητική modulo. Ο δακτύλιος Ζm. Επαναλαμβανόμενος τετραγωνισμός. Στοιχεία αφηρημένης άλγεβρας: ομάδες, υποομάδες, κλειστότητα, units του Zm, κυκλικές ομάδες, γεννήτορας, τάξη ομάδας, δακτύλιοι, σώματα. Μικρό Θεώρημα Fermat, Θεώρημα Euler. Σύμπλοκα, τάξη υποομάδας, Θεώρημα Lagrange. Έλεγχος πρώτων αριθμών Fermat. pdf (6-24)
13/1 Κινέζικο Θεώρημα Υπολοίπων. Ο ισομορφισμός του Zm x Zn με το Ζmn. Ο ισομορφισμός του U(Zm) x U(Zn) με το U(Ζmn). Η δομή της ομάδας Zp*. pdf (25-31)
17/1 Η δομή της ομάδας U(Zn). Τετραγωνικά υπόλοιπα. Επίλυση τετραγωνικής ισοτιμίας. Σύμβολα Legendre και Jacobi: αποδοτικός υπολογισμός (κριτήριο Euler, νόμος τετραγωνικής αντιστροφής). pdf (32-42)
20/1 Ο έλεγχος πρώτων αριθμών Miller-Rabin. Το κρυπτοσύστημα RSA: ορισμός, ορθότητα, σχέση με παραγοντοποίηση. pdf (43-46)
pdf (1-4)
24/1 Κρυπτοσύστημα RSA: επίθεση κοινού γινομένου, ανάκτηση πληροφοριών. Κριτήρια επιλογής παραμέτρων RSA. pdf (5-13)
27/1 Το κρυπτοσύστημα Rabin. Το πρόβλημα του διακριτού λογαρίθμου (DLP). Αλγόριθμος Shanks. Ανταλλαγή κλειδιού Diffie-Hellman. pdf (14-24)
31/1 Το κρυπτοσύστημα δημοσίου κλειδιού ElGamal. Επιθέσεις. Ασκήσεις στον διακριτό λογάριθμο. pdf (25-27)
3/2 Θεωρία υπολογιστικής πολυπλοκότητας. Μη-ντετερμινιστικοί και πιθανοτικοί αλγόριθμοι. Κλάσεις P, NP, BPP, RP, ZPP. Δένδρα υπολογισμού. Τεχνικές ενίσχυσης της πιθανότητας σωστής απάντησης στους πιθανοτικούς αλγόριθμους. Πλειοψηφικοί ποσοδείκτες. (Σημ. E.Ζάχου: κεφ. 16)
7/2 Θεωρία υπολογιστικής πολυπλοκότητας. Η κλάση UP, και η σχέση της με την κρυπτανάλυση. Η απόδειξη ότι P <> UP ισοδυναμεί με ύπαρξη συναρτήσεων μονής κατεύθυνσης.
(Σημ. E.Ζάχου: κεφ. 16)
10/2 Αλγόριθμοι παραγοντοποίησης: μέθοδος rho, μέθοδος Dixon, B-smoothness. Το παράδοξο των γενεθλίων. (Σημ. E.Ζάχου: κεφ. 7.3, 13.5)
14/2 Το πρόβλημα απόφασης Diffie-Hellman (DDH). Το υπολογιστικό πρόβλημα Diffie-Hellman (CDH). Η σχέση των προβλημάτων DDH, CDH και DLP. Κρυπτογραφικές αναγωγές και υποθέσεις. Είδη ασφάλειας: IND-CPA, IND-CCA, IND-CCA2. Ισοδυναμία διακρισιμότητας κρυπτοκειμένων ElGamal και DDH. Malleability. pdf
17/2 Ψηφιακές υπογραφές. Το σχήμα υπογραφής RSA. Το σχήμα υπογραφής ElGamal, σενάρια πλαστογράφησης. To Πρότυπο Ψηφιακής Υπογραφής (Digital Signature Standard). pdf (διαφ. 1-18)
21/2 Υπογραφές μιας χρήσης: Lamport scheme, βελτίωση Bos-Chaum. Τυφλές υπογραφές (blind signatures): Chaum's scheme. Αδιαμφισβήτητες υπογραφές (undeniable signatures): Chaum-van Antwerpen scheme. Ασφάλεια έναντι πλαστογράφησης και αποποίησης: unconditional security. pdf (διαφ. 19-24)
24/2 Υπογραφές Fail-Stop: van Heyst-Pedersen scheme. Απόδειξη πλαστογράφησης: unconditional security.
Hash functions: ορισμός, επιθυμητές ιδιότητες (ελευθερία συγκρούσεων, μονής κατεύθυνσης). Ιεράρχηση επιθυμητών ιδιοτήτων. Συνάρτηση Chaum-van Heijst-Pfitzman. 		pdf (διαφ. 25-33)
28/2 Συναρτήσεις σύνοψης: μέθοδος επέκτασης Merkle-Damgard. Χρήσεις συναρτήσεων σύνοψης. Κρυπτογραφικά πρωτόκολλα. Πρωτόκολλα ταυτοποίησης Schnorr, Fiat-Shamir, και Feige-Fiat-Shamir. Αποδείξεις γνώσης και αποδείξεις μηδενικής γνώσης. Επισκόπηση μαθήματος. pdf (διαφ. 34-43)

Ασκήσεις

Μεγάλη εργασία (project)

Μικρή εργασία

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

  1. Σημειώσεις Ε. Ζάχου, ΕΜΠ, 2012.
  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. J. Katz and Y. Lindell: Introduction to Modern Cryptography, Chapman & Hall/CRC Press, 2007.
  5. V. Shoup: A Computational Introduction to Number Theory and Algebra: http://shoup.net/ntb/.
  6. B. Schneier: Applied Cryptography: http://www.schneier.com/book-applied.html.
  7. W.Trappe, L. Washington: Introduction to Cryptography with Coding Theory.
  8. A.Κιαγιάς: Τεχνικές Σύγχρονης Κρυπτογραφίας: σημειώσεις

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

  • Ε. Ζάχος, Α. Παγουρτζής, Δ. Φωτάκης: "Σύντομη Εισαγωγή στη Θεωρία Πολυπλοκότητας":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