Weekly outline

  • Χειμερινό Εξάμηνο 2024-2025

    Διδάσκοντες:


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

    • Pourandokht Behrouz, Υ.Δ.
    • Μαριάννα Σπυράκου, Υ.Δ.
    • Θωμάς Σουλιώτης, Υ.Δ.
    • Ελένη Μακρή, Υ.Δ.
    • Δανάη Μπάλλα, Υ.Δ.
    • Ορέστης Κωνσταντινίδης, Υ.Δ.


    Επικοινωνία: crypto@corelab.ntua.gr


    Διαλέξεις (έναρξη: 1/10)

    • Τρίτη 15:15-18:00, Αιθ. 007, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ 
    • Παρασκευή 18:15-20:00, Αμφ. 3, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ


    Βασική βιβλιογραφία:

    [ΖΠΓ]: Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς: Υπολογιστική Κρυπτογραφία, Κάλλιπος, 2015. 
    [LK2]: Jonathan Katz and Yehuda Lindell: Introduction to Modern Cryptography (2nd edition).
    [BoSh]: D. Boneh and V. Shoup: A Graduate Course in Applied Cryptography (free draft, κατεβάστε την τελευταία έκδοση)

  • Εβδομάδα 1η


    ΤΡΙΤΗ 1/10

    • Διαδικαστικά Μαθήματος

    Διαφάνειες (διαδικαστικά)

    • Επισκόπηση αρχών και εφαρμογών της σύγχρονης κρυπτογραφίας.
    • Κλασικά συστήματα (αντικατάστασης, Καίσαρα, Vigenere cipher) και κρυπτανάλυσή τους.

    Διαφάνειες διάλεξης (1-19)


    ΠΑΡΑΣΚΕΥΗ 4/10

    • Δείκτης σύμπτωσης (Coincidence Index).
    • Τέλεια μυστικότητα κατά Shannon.
    • Κρυπτοσυστήματα μετάθεσης και γινομένου.
    • Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.

    Διαφάνειες διάλεξης (σελ. 20-39)


    Προτεινόμενη μελέτη (εβδομάδας): 

    • [ΖΠΓ]: κεφ. 1 (έως ενότητα 1.4.3), 6.3
    • [LK2]: κεφ. 1, 2
    • [BoSh]: κεφ. 2.1

    Προαιρετική Μελέτη: 

    • Russell Impagliazzo, A Personal View of Average-Case Complexity (pdf).

    • Εβδομάδα 2η

      ΤΡΙΤΗ 8/10

      Εισαγωγή στη Θεωρία Αριθμών

      • Διαιρετότητα, ΜΚΔ: ιδιότητες - αλγόριθμος Ευκλείδη
      • Πρώτοι αριθμοί, συνάρτηση φ του Euler
      • Ισοτιμίες, αριθμητική modulo, ο δακτύλιος Z_m 
      • Μικρό Θεώρημα Fermat 
      • Θεωρία ομάδων: τάξη στοιχείου και ομάδας, κυκλικές ομάδες, γεννήτορες, δακτύλιοι, σώματα
      • Σύμπλοκα, ομάδα πηλίκο, θεώρημα Lagrange
      Διαφάνειες διάλεξης (1-23)


      ΠΑΡΑΣΚΕΥΗ 11/10

      • Έλεγχος πρώτων αριθμών κατά Fermat
      • Κινέζικο Θεώρημα Υπολοίπων (CRT)

      Διαφάνειες διάλεξης (24-29)


      Προτεινόμενη μελέτη (εβδομάδας): [ΖΠΓ] 2.1, 2.2, 4.1, 4.2, 4.3

      Δείτε ακόμη: [LK2] Appendix B, [BoSh] Appendix A

      • Εβδομάδα 3η

        ΤΡΙΤΗ 15/10

        • Η δομή των ομάδων Z*p και U(Zpq)
        • Τετραγωνικά Υπόλοιπα
        • Τετραγωνικές ρίζες modulo n και παραγοντοποίηση

        Διαφάνειες διάλεξης (30-37)


          Προτεινόμενη μελέτη: [ΖΠΓ] 2.2, 2.3, 4.5 

          Συμπληρωματική μελέτη: [LK2] Appendix B
                                               [BoSh] Appendix A


        ΠΑΡΑΣΚΕΥΗ 18/10

        • Σύμβολα Legendre και Jacobi
        • Έλεγχοι πρώτων αριθμών Fermat και Miller-Rabin
        • Ευεπίλυτα και Δυσεπίλυτα αριθμητικά προβλήματα


          Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, 4.5, 4.7 
          Συμπληρωματική μελέτη: [LK2] Appendix B
                                               [BoSh] Appendix A

        • Εβδομάδα 4η

          ΤΡΙΤΗ 22/10

          • Κρυπτοσυστήματα τμήματος (block ciphers). 
          • Δίκτυα Feistel. 
          • Κρυπτοσύστημα DES, S-boxes, MITM attack. 
          • Βελτιώσεις: 3-DES, DES-X. 
            Διαφάνειες διάλεξης (1-13) 

            Προτεινόμενη μελέτη: [ΖΠΓ] 5.1-5.3

            Δείτε ακόμη: The Design of Rijndael (accessible through Heal-Link), ch. 6

          ΠΑΡΑΣΚΕΥΗ 25/10

          • Συζήτηση για την 1η σειρά ασκήσεων
          • Σύντομη επανάληψη θεωρίας αριθμών

          • Εβδομάδα 5η

            ΤΡΙΤΗ 29/10

            • Τρόποι λειτουργίας των blockciphers: ECB, CBC, CFB, OFB, CTR
            • Επιθέσεις αλλοίωσης κρυπτοκειμένου
            • Authenticated encryption
            • Το κρυπτοσύστημα AES


            Διαφάνειες διάλεξης (14-25)

            Συμπληρωματικά: Raj Jain, Washington University in Saint Louis, και περιγραφή του AES στο επίσημο site του NIST.

            Προτεινόμενη μελέτη: [ΖΠΓ] 5.3 - 5.6
            Δείτε ακόμη: The Design of Rijndael (accessible through Heal-Link)

            ΠΑΡΑΣΚΕΥΗ 1/11

            • Αλγεβρικός ορισμός του AES
            Προτεινόμενη μελέτη: [ΖΠΓ] 5.3 - 5.6
            Δείτε ακόμη: The Design of Rijndael (accessible through Heal-Link)

            • Εβδομάδα 6η

              ΤΡΙΤΗ 5/11

              • Γεννήτριες Ψευδοτυχαιότητας
              • Ψευδοτυχαίες συναρτήσεις και μεταθέσεις

              Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3)
              Συμπληρωματική μελέτη: Boaz Barak notes, [LK2, ch3], [BoSh, ch3]

              ΠΑΡΑΣΚΕΥΗ 8/11

              • Γεννήτριες Ψευδοτυχαιότητας (επανάληψη)
              • Κατασκευή κρυπτοσυστήματος από γεννήτρια ψευδοτυχαιότητας
              • Απόδειξη μη διακρισιμότητας

              Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3)
              Συμπληρωματική μελέτη: Boaz Barak notes, [LK2, ch3], [BoSh, ch3]

              • Εβδομάδα 7η

                ΤΡΙΤΗ 12/11 

                • Κατασκευή PRG από PRF και αντίστροφα
                • Γεννήτρια Blum-Blum-Shub
                • Γεννήτρια RC4
                • Kρυπτοσυστήματα ροής
                • Καταχωρητές Ολίσθησης Γραμμικής Ανάδρασης
                • eStream

                Διαφάνειες: Stream Ciphers (25-42)

                • Συναρτήσεις μονής κατεύθυνσης
                • Συναρτήσεις σύνοψης
                • Ασφάλεια συνάρτησης Chaum-van Heijst-Pfitzman
                Διαφάνειες: Hash Functions (1-13)

                Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3), [ΖΠΓ] 6.1, 8.1- 8.2, [LK2] 7.1, 5.1


                ΠΑΡΑΣΚΕΥΗ 15/11 

                Επέτειος Πολυτεχνείου

                • Εβδομάδα 8η

                  ΤΡΙΤΗ 19/11

                  • Ασφάλεια συνάρτησης Chaum-van Heijst-Pfitzman
                  • Παράδοξο Γενεθλίων - Βελτιωμένες Επιθέσεις
                  • Κατασκευή Merkle-Damgård
                  • Δένδρα Merkle
                  • Χρήσεις συναρτήσεων σύνοψης

                  Διαφάνειες διάλεξης: Hash Functions (14-32)

                  Προτεινόμενη Μελέτη: [ΖΠΓ] 8.2-8.3, [LK2]: 5.2, [BoSh]: 8.3, 8.4


                  ΠΑΡΑΣΚΕΥΗ 22/11

                  Εφαρμογές Συναρτήσεων Σύνοψης

                  • Σχήματα δέσμευσης
                  • Ασφαλής αποθήκευση κωδικών
                  • Timestamping
                  • Proof-of-Work, δένδρα Merkle

                  Διαφάνειες: Hash Applications

                  Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.4-8.6

                  • Εβδομάδα 9η

                    ΤΡΙΤΗ 26/11

                    • Το πρόβλημα ανταλλαγής κλειδιού
                    • Προβλήματα σχετιζόμενα με το διακριτό λογάριθμο
                    • Πρωτόκολλο Diffie-Hellman
                    • Ανάλυση ασφάλειας ανταλλαγής κλειδιού Diffie-Hellman
                    • Αλγόριθμοι baby-step/giant-step, Pohlig-Hellman


                    Διαφάνειες: A (σελ. 36-48) και Β (σελ. 1-15)

                    Προτεινόμενη μελέτη: [ΖΠΓ] 4.8, 6.5.1 [LK2] 8.3, 9.2, 10

                    Προαιρετική Μελέτη: 

                    • W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Inf. Theor., 22(6):644-654, September 1976.
                    • Ralph Merkle. Secure communications over insecure channels.
                    • Neil Koblitz, Alfred Menezes, Another Look at “Provable Security”, (pdf).
                    • Ivan Damgard, A proof reading of some issues in cryptography, (pdf).

                    ΠΑΡΑΣΚΕΥΗ 29/11

                    • Κρυπτογραφία Δημοσίου Κλειδιού
                    • Ορισμός RSA
                    • Παρατηρήσεις Λειτουργίας
                    • Ασφάλεια-Σχετικά προβλήματα


                    Διαφάνειες Διάλεξης (1-25)

                    [ΖΠΓ] 6.4, [LK2] 11.5.1, 11.5.2, 11.5.4, 11.5.6, [BoSh] 10.3

                    Προαιρετική μελέτη: