Weekly outline

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

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


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

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


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

    • Τρίτη 15:30-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, κατεβάστε την τελευταία έκδοση)

  • Εβδομάδα 2/10-6/10


    ΤΡΙΤΗ 3/10

    • Διαδικαστικά Μαθήματος
    • Επισκόπηση αρχών και εφαρμογών της σύγχρονης κρυπτογραφίας.

    Διαφάνειες διάλεξης


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

    • Κλασικά συστήματα (αντικατάστασης, Καίσαρα, Vigenere cipher) και κρυπτανάλυσή τους.
    • Δείκτης σύμπτωσης (Coincidence Index).
    • Τέλεια μυστικότητα κατά Shannon.

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

    Προτεινόμενη μελέτη: 

    • [ΖΠΓ]: κεφ. 1.4.3 
    • [LK2]: κεφ. 2

    • Εβδομάδα 9/10-13/10

      ΤΡΙΤΗ 10/10

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

       Προτεινόμενη μελέτη: 

      •   [ΖΠΓ] κεφ 1.4.3, 6.3 
      •   [LK2] κεφ. 2

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

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


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

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

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


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

      Προτεινόμενη μελέτη: [ΖΠΓ] 2.1, 4.1, 4.2, 4.3

      • Εβδομάδα 16/10-20/10

        ΤΡΙΤΗ 17/10

        • Σύμπλοκα, ομάδα πηλίκο, θεώρημα Lagrange
        • Έλεγχος πρώτων με θεώρημα του Fermat
        • Κινέζικο Θεώρημα Υπολοίπων
        • Η δομή των ομάδων Z*p και U(Zpq)

          Διαφάνειες διάλεξης (21-32)

          Προτεινόμενη μελέτη: [ΖΠΓ] 2.2, 2.3, 4.5 [LK2] 8.1-8.3 (συμπληρωματικά)


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

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


          Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, 4.5, 4.6, 4.7 [LK2] 8.2.2 (συμπληρωματικά)

        • Εβδομάδα 23/10-27/10

          ΤΡΙΤΗ 24/10

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


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


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

          Επέτειος 28ης ΟΚΤΩΒΡΙΟΥ - Δεν έγινε μάθημα

          • Εβδομάδα 30/10 - 03/11

            ΤΡΙΤΗ 31/10

            • Τρόποι λειτουργίας των blockciphers
            • Το κρυπτοσύστημα AES
            • Αλγεβρική περιγραφή του AES


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

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

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

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

            • Γεννήτριες Ψευδοτυχαιότητας
            • Ψευδοτυχαίες συναρτήσεις και μεταθέσεις
            • Γεννήτρια Blum-Blum-Shub
            • Κρυπτοσυστήματα ροής
            • Γεννήτρια RC4



            Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3)

            • Εβδομάδα 6/11 - 10/11


              ΤΡΙΤΗ 7/11

              • Γεννήτρια Blum-Blum-Shub (επανάληψη)
              • Καταχωρητές Ολίσθησης Γραμμικής Ανάδρασης
              • eStream
              • Συναρτήσεις μονής κατεύθυνσης
              • Συναρτήσεις σύνοψης
              • Ασφάλεια συνάρτησης Chaum-van Heijst-Pfitzman

              Διαφάνειες διάλεξης: Stream Ciphers (37-42), Hash Functions (1-13)

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


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

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


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

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






              • Εβδομάδα 13/11 - 17/11


                ΤΡΙΤΗ 14/11 - Εφαρμογές Συναρτήσεων Σύνοψης

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


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

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


                • Message Authentication Codes
                • MAC με hash functions (HMAC)


                Διαφάνειες: MAC

                Προτεινόμενη μελέτη: [BoSh] 8.7, 9.1-9.4 (συνοπτικά)


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

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

                • Εβδομάδα 21/11 - 24/11

                  ΤΡΙΤΗ 21/11

                  • Μοντέλα και ορισμοί ασφάλειας
                  • Τύποι επιθέσεων
                  • Παίγνια Μη Διακρισιμότητας
                  • Γενική μορφή κρυπτογραφικών αναγωγών
                  • Ανάλυση ασφάλειας ανταλλαγής κλειδιού Diffie-Hellman
                  • Εισαγωγή στο RSA

                  Διαφάνειες Διάλεξης

                  Προτεινόμενη μελέτη: [ΖΠΓ] 1.4, 6.2, 6.3 [LK2] 1.4 

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

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

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

                  • Κρυπτογραφία Δημοσίου Κλειδιού
                  • Ορισμός RSA
                  • Παρατηρήσεις Λειτουργίας
                  • Αριθμοθεωρητικές Επιθέσεις

                  Διαφάνειες Διάλεξης (1-37) - Κώδικας Sage

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

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


                  • Εβδομάδα 28/11 - 01/12

                    ΤΡΙΤΗ 28/11/23

                    Το κρυπτοσύστημα RSA (ολοκλήρωση)

                    • Μοντελοποίηση - Ιδιότητες IND-CPA, IND - CCA
                    • Malleability
                    • Διαρροή parity - location bits και 'σπάσιμο' RSA
                    • Επιθέσεις Padding Oracle (Bleichenbacher)
                    • RSA - OAEP

                    Διαφάνειες Διάλεξης (38-56) 

                    Συνολική Μελέτη RSA: [ΖΠΓ] 6.4, [LK2] 11.5.1, 11.5.2, 11.5.4, 11.5.6, [BoSh] 10.3

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

                    • Daniel Bleichenbacher. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1 (pdf)

                    Κρυπτοσυστήματα Διακριτού Λογαρίθμου

                    • Προβλήματα DLP, CDHP, DDHP (επανάληψη)
                    • Random Self-Reducibility
                    • Αλγόριθμοι Διακριτού Λογαρίθμου (Shanks, Pohlig-Hellman, Index Calculus)
                    • Ευκολία DDHP στο Z_p^*
                    • Επιλογή Ομάδας, Μέγεθος παραμέτρων

                    Slides DLP (*προσωρινή έκδοση*)

                    Μελέτη: [ΖΠΓ] 4.8, [LK2] 8.3.2, 8.3.3, 9.2.1, 9.2.2, 9.3, 9.4 [BoSh] 10.5

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

                    • The Decision Diffie-Hellman Problem (pdf)

                     

                    ΠΑΡΑΣΚΕΥΗ 01/12/23

                    Κρυπτοσυστήματα Διακριτού Λογαρίθμου

                    • Ευκολία DDHP στο Z_p^* (διευκρινίσεις)
                    • Ελλειπτικές Καμπύλες
                    • Pairings
                    • Τριμερής Ανταλλαγή Κλειδιού

                    Slides DLP (*προσωρινή έκδοση*)

                    Μελέτη: [ΖΠΓ] 12.2, 12.3 [LK2] 8.3.4

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