Weekly outline

  • Χειμερινό Εξάμηνο 2021-2022

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


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


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

    • Τρίτη 12:00-14:00, Αμφ. 4, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ & διαδικτυακά 
    • Παρασκευή 18:00-19:30, Αμφ. 4, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ & διαδικτυακά


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

    [ΖΠΓ]: Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς: Υπολογιστική Κρυπτογραφία, Κάλλιπος, 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, κατεβάστε την τελευταία έκδοση)

    Τρόπος εξέτασης 

    Η εξέταση του μαθήματος αποτελείται από δύο μέρη: Μέρος Α, με ερωτήσεις θεωρίας, και είναι με κλειστές σημειώσεις και βιβλία και Μέρος Β, ασκήσεις, και είναι με ανοιχτές σημειώσεις και βιβλία.



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

    ΤΡΙΤΗ 12/10

    • Διαδικαστικά.
    • Εισαγωγή.
    • Στόχοι της Κρυπτογραφίας.
    • Επισκόπηση βασικών λειτουργιών και πρωτοκόλλων.

      Slides: Lecture 0

    • Εβδομάδα 18/10-22/10


      ΤΡΙΤΗ 19/10

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

           Slides: Lecture 1 (1-19) (προσωρινά)

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

      • [ΖΠΓ]: κεφ. 1 (1.1 & 1.2)
      • [LK2]: κεφ. 1.2, 1.3

      Παρασκευή 22/10

      • Τέλεια μυστικότητα κατά Shannon. Ισοδύναμες συνθήκες. Random Shift cipher. One-time pad. Unicity distance.
      • Ορισμοί ασφάλειας, υπολογιστική ασφάλεια.

      Slides: Lecture 1 (20-31) (προσωρινά)

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

      • [ΖΠΓ]: κεφ. 1.4, 5.7 (έως 5.7.3, συνοπτικά), 6.3 
      • [BoSh]: κεφ. 2.2
      • [LK2]: κεφ. 2



      • Εβδομάδα 25/10-29/10

        ΤΡΙΤΗ 26/10

        • Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
        • Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.
        Slides: Lecture 1 (32-42) 

        • Εισαγωγή στη θεωρία αριθμών, διαιρετότητα, ΜΚΔ, αλγόριθμος Ευκλείδη
        • Εύρεση αντιστρόφου σε αριθμητική υπολοίπων
        Slides: Lec2 (1-10)


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

        • Αριθμητική υπολοίπων. Θεώρημα Fermat και Euler.
        • Κινέζικο Θεώρημα Υπολοίπων (CRT).

        Slides: Lec2 (11-20)


        Προτεινόμενη μελέτη: [ΖΠΓ] 2.1, 2.2, 2.3 και [LK2] 7.1, 7.3 [7.3.1, 7.3.3] (συμπληρωματικά)

        • Εβδομάδα 1/11-5/11

          ΤΡΙΤΗ 2/11

          • Θεωρία ομάδων, τάξη στοιχείου και ομάδας, κυκλικές ομάδες, γεννήτορες.
          • Σύμπλοκα, ομάδα πηλίκο, Θεώρημα Lagrange.
          • Έλεγχος πρώτων με θεώρημα του Fermat.
            Slides: Lec2 (21-29)

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


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

          • Η δομή των ομάδων Z*p και U(Zpq).
          • Τετραγωνικά Υπόλοιπα, τετραγωνικές ισοτιμίες, κριτήριο Euler.
          • Σύμβολα Legendre και Jacobi.
          • Ευεπίλυτα και δυσεπίλυτα αριθμοθεωρητικά προβλήματα.

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

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

            ΤΡΙΤΗ 9/11

            • Εισαγωγή στην ψευδοτυχαιότητα, γεννήτριες ψευδοτυχαιότητας
                 Προτεινόμενη μελέτη: [LK2] 3.3, [BoSh] 3.1 [ΖΠΓ] 5.7


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

            • Η γεννήτρια ψευδοτυχαιότητας Blum-Blum-Shub
            • Κρυπτοσυστήματα ροής
            • Η γεννήτρια RC4
            • Καταχωρητές ολίσθησης γραμμικής ανάδρασης (LFSR)
                 Προτεινόμενη μελέτη: [LK2] 3.6 [BoSh] 3.2, 3.9, 3.10, [ΖΠΓ] 5.7 (έως και 5.7.3)



            • Εβδομάδα 15/11-19/11

              ΤΡΙΤΗ 16/11

              Δεν έγινε μάθημα (εορτασμός Πολυτεχνείου)


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

              • Κρυπτοσυστήματα τμήματος. 
              • Δίκτυα Feistel. 
              • Κρυπτοσύστημα DES, S-boxes, MITM attack. 
              • Βελτιώσεις: 3-DES, DES-X. 
                Προτεινόμενη μελέτη: [ΖΠΓ] 5.1-5.3


              • Εβδομάδα 22/11-26/11

                ΤΡΙΤΗ 23/11

                • Τρόποι λειτουργίας block ciphers: ECB, CBC, CFB, OFB, CTR.
                • Εισαγωγή στο AES
                • Block ciphers: σύνοψη

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

                Slides: Lec4 (15-26)


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

                • Η λειτουργία του AES

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

                    Συμπληρωματικά δείτε:

                1. https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture8.pdf
                2. https://en.wikipedia.org/wiki/Advanced_Encryption_Standard

                • Συναρτήσεις κατακερματισμού (εισαγωγή)
                Slides: Lec5

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



                • Εβδομάδα 29/11 - 3/12

                  ΤΡΙΤΗ 30/11
                  • Συναρτήσεις μονή κατεύθυνσης (one-way functions)
                  • Επιθέσεις γενεθλίων
                  Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 6.1


                  ΠΑΡΑΣΚΕΥΗ 3/12
                  • Επέκταση συναρτήσεων κατακερματισμού Merkle-Damgard
                  • Δέντρα Merkle
                  Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.2-8.3


                  • Εφαρμογές συναρτήσεων κατακερματισμού
                  Slides: Lec6

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

                    ΤΡΙΤΗ 7/12 - RSA

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

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

                    Επιθέσεις και ασφάλεια στο RSA

                    • επίθεση μικρού ιδιωτικού εκθέτη
                    • ισοδυναμία αποκάλυψης ιδιωτικού εκθέτη με παραγοντοποίηση
                    • επίθεση κοινού γινομένου
                    Διαφάνειες (23-32)

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

                    [ΖΠΓ]Ενότητες 6.1, 6.2, 6.4

                    [LK2]: Ενότητες 11.1, 11.2, 11.5.1, 11.5.2, 11.5.4, 11.5.6


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

                      ΤΡΙΤΗ 14/12

                      Ασφάλεια RSA

                      • Aπόδειξη παραγοντοποίησης μέσω ιδιωτικού εκθέτη,
                        oμοιότητες με έλεγχο πρώτων αριθμών Miller-Rabin
                      • Μοντελοποίηση ασφάλειας
                      • Δυσκολία διαρροής ενός bit στο RSA (location, parity)
                      • Έλλειψη ασφάλειας IND-CPA, IND-CCA, malleability στο κλασικό RSA
                      Διαφάνειες (21-22, 33-40)
                      Σημειώσεις πίνακα για παραγοντοποίηση μέσω ιδιωτικού εκθέτη


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

                      • Παραλλαγές RSA ασφαλείς ως προς IND-CPA, IND-CCA. Padded RSA, RSA-OAEP

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

                      [ΖΠΓ]Ενότητες 6.1, 6.2, 6.4

                      [LK2]: Ενότητες 11.1, 11.2, 11.5.1, 11.5.2, 11.5.4, 11.5.6


                      • Εβδομάδα 20/12 - 23/12

                        ΤΡΙΤΗ 21/12

                        • Εισαγωγή στον Διακριτό Λογάριθμο: ανταλλαγή κλειδιού Diffie-Hellman.
                        • Αλγόριθμος Shanks, αλγόριθμος Pohlig-Hellman
                        • Το κρυπτοσύστημα ElGamal (ορισμός, ασφάλεια, σχέση με CDHP)

                        Διαφάνειες (1-29)


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

                        [ΖΠΓ]: Ενότητες 6.5, 9.2, 9.3

                        [LK2]: Ενότητες 9.2.1, 9.2.2, 11.4.1, 11.4.2, 11.4.4, 13.3


                        • Εβδομάδα 10/1-14/1

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

                            • Διαλογικές αποδείξεις μηδενικής γνώσης
                            • Σ-πρωτόκολλα
                            • Μη διαλογικές αποδείξεις μηδενικής γνώσης
                            • Ηλεκτρονικές ψηφοφορίες


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

                            [ΖΠΓ]Κεφ. 10, 11.1 (11.1.1 έως 11.1.3)

                            [BoSh]: Κεφ. 19.4, 19.7 [προαιρετικά: 19.5, 19.6, 19.8]



                            • Εβδομάδα 17/1-21/1

                              ΤΡΙΤΗ 18/1

                              • Ψηφιακές υπογραφές: ορισμός - μοντελοποίηση ασφάλειας
                              • Ψηφιακές υπογραφές RSA, καθολική πλαστογράφηση
                              • Full Domain Hash RSA, random oracle model
                              • Ψηφιακές υπογραφές ElGamal και DSA
                              Διαφάνειες (1-43)

                              Προτεινόμενη μελέτη: [ΖΠΓ] Κεφ. 7 (έως και 7.6.2)


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

                              • Υποδομή δημοσίου κλειδιού (απλή αναφορά), identity-based cryptography, secret sharing, threshold El Gamal
                                Διαφάνειες (44-71)

                              Προτεινόμενη μελέτη: [ΖΠΓ] Κεφ. 9 (9.1 και 9.3), Κεφ. 11 (11.3 και 11.4)