Weekly outline

  • General

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

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


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

    • Παναγιώτης Γροντάς, Υ.Δ. (pgrontas@gmail.com)
    • Γιάννης Παπαϊωάννου, Υ.Δ. (ipap@corelab.ntua.gr)
    • Θωμάς Σουλιώτης, Υ.Δ.
    • Ιάσων Μηλιώνης (jasonmili DOT cs AT gmail DOT com)


    Διαλέξεις:

    • Τρίτη 12:00-14:30  [ΑΛΜΑ: 12:00-14:00]
    • Παρασκευή 18:00-19:15  [ΑΛΜΑ: 17:45-19:45]
      (ΠΡΟΣΟΧΗ: οι ώρες έχουν τροποποιηθεί)

    Έναρξη: Τρίτη, 6 Οκτωβρίου 2020

    Σύνδεσμος webex: δείτε τις ανακοινώσεις

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

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

  • 5 October - 11 October

    ΤΡΙΤΗ 6/10

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

      Slides: Lec0
      (ΠΡΟΣΟΧΗ: Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)

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

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

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

         Βίντεο της διάλεξης (password: θα σταλεί με email)

         [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]

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

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

    • 12 October - 18 October

      ΤΡΙΤΗ 13/10

      • Τέλεια μυστικότητα (perfect secrecy). Ισοδύναμες συνθήκες. Random Shift cipher. One-time pad. Unicity distance.
      • Ορισμοί ασφάλειας, υπολογιστική ασφάλεια.
      • Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
      • Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.

      Slides: Lec1 (20-42) (προσωρινά)

      Βίντεο της διάλεξης (password: θα σταλεί με email)

      [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]

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

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


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

      • Εισαγωγή στη θεωρία αριθμών, διαιρετότητα, ΜΚΔ, αλγόριθμος Ευκλείδη
      • Εύρεση αντιστρόφου σε αριθμητική υπολοίπων
      • Συζήτηση 1ης σειράς ασκήσεων

      Slides: Lec2 (1-10)

      Βίντεο της διάλεξης  [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]

      • 19 October - 25 October

        ΤΡΙΤΗ 20/10

        • Αριθμητική υπολοίπων. Θεώρημα Fermat και Euler.
        • Κινέζικο Θεώρημα Υπολοίπων (CRT).
        • Θεωρία ομάδων, τάξη στοιχείου και ομάδας, κυκλικές ομάδες, γεννήτορες.
        • Σύμπλοκα, ομάδα πηλίκο, Θεώρημα Lagrange.

        Slides: Lec2 (11-28)

        Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]

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


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

        • Έλεγχος πρώτων με θεώρημα του Fermat
        • Η δομή των ομάδων Z*p και U(Zpq)
        • Τετραγωνικά Υπόλοιπα, τετραγωνικές ισοτιμίες, κριτήριο Euler

        Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]

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

        • 26 October - 1 November

          ΤΡΙΤΗ 27/10

          • Σύμβολα Legendre και Jacobi
          • Ευεπίλυτα και δυσεπίλυτα αριθμοθεωρητικά προβλήματα

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

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

            Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]

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

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

            Βίντεο της διάλεξης [Ισχύουν οι περιορισμοί χρήσης που αναφέρονται παραπάνω]

          • 2 November - 8 November

            ΤΡΙΤΗ 03/11

            • Καταχωρητές γραμμικής ανάδρασης (LFSR)

              Slides: Lec3 (33-38)

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

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

            Βίντεο της διάλεξης [ισχύουν περιορισμοί - δείτε παραπάνω]


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

            Συζήτηση για την 2η σειρά ασκήσεων

            Βίντεο της διάλεξης [ισχύουν περιορισμοί - δείτε παραπάνω]



            • 9 November - 15 November

              ΤΡΙΤΗ 10/11

              • Τρόποι λειτουργίας block ciphers: ECB, CBC, CFB, OFB, CTR.
              Slides: Lec4 (15-21)

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


              • AES
              Slides: Lec4 (22-25)

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

                • Block ciphers: σύνοψη
                Slides: Lec4 (26)

                Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω]

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


                • Συναρτήσεις μονή κατεύθυνσης (one-way functions)
                Slides: Lec5 (1-6)
                Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 6.1

                Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω]

                • 16 November - 22 November

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

                  • Συναρτήσεις κατακερματισμού
                  Slides: Lec5 (7-17)
                  Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.1


                  Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω]
                  • 23 November - 29 November

                    ΤΡΙΤΗ 24/11
                    • Επιθέσεις γενεθλίων
                    • Επέκταση συναρτήσεων κατακερματισμού Merkle-Damgard
                    • Δέντρα Merkle
                    Slides: Lec5 (18-32)
                    Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.2-8.3


                    Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω]

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

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

                    Βίντεο της διάλεξης [Ισχύουν περιορισμοί - δείτε παραπάνω]

                    • 30 November - 6 December

                      ΤΡΙΤΗ 1/12 - RSA

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


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

                      • RSA: επίθεση μικρού ιδιωτικού εκθέτη
                      • RSA: ισοδυναμία αποκάλυψης ιδιωτικού εκθέτη με παραγοντοποίηση
                      • Συζήτηση για την 3η σειρά ασκήσεων
                      Διαφάνειες (18-29)

                      Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]


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

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

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


                      • 7 December - 13 December

                        ΤΡΙΤΗ 8/12

                        • RSA: ασφάλεια ιδ. εκθέτη σε σχέση με παραγοντοποίηση (επανάληψη),
                          oμοιότητες με έλεγχο πρώτων αριθμών Miller-Rabin
                        • Επίθεση κοινού γινομένου
                        • Μοντελοποίηση ασφάλειας
                        • Έλλειψη ασφάλειας IND-CPA, IND-CCA, malleability στο κλασικό RSA
                        • Παραλλαγές για IND-CPA, IND-CCA. Padded RSA, RSA-OAEP
                        Διαφάνειες (21-22, 30-35, 41-51)

                        Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]


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

                        • RSA: δυσκολία διαρροής ενός bit (location, parity)

                        • Εισαγωγή στον Διακριτό Λογάριθμο: ανταλλαγή κλειδιού Diffie-Hellman.
                        • Αλγόριθμος Shanks

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

                        Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]


                        • 14 December - 20 December

                          ΤΡΙΤΗ 15/12

                          • Διακριτός Λογάριθμος: αλγόριθμος Pohlig-Hellman
                          • Το κρυπτοσύστημα ElGamal (ορισμός, ασφάλεια, σχέση με CDHP)

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

                          Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]


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

                          • Κρυπτοσύστημα ElGamal: Ασφάλεια IND-CPA, malleability
                          • Εκθετικό ElGamal 
                          • Σχήμα Δέσμευσης Pedersen

                          Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]


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

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

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


                          • 21 December - 27 December

                            ΤΡΙΤΗ 22/12

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

                            Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]

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




                            • 4 January - 10 January

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

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

                                Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]


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

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

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



                                • 11 January - 17 January

                                  ΤΡΙΤΗ 12/1

                                  • Εισαγωγή σε Blockchain & Consensus

                                  Διαφάνειες

                                  • Εισαγωγή στο Bitcoin (transactions, blocks, proof-of-work)

                                  Διαφάνειες

                                  Βίντεο της διάλεξης [ισχύουν περιορισμοί, βλ. παραπάνω]


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

                                  • Τυφλές Υπογραφές και εφαρμογές

                                  Διαφάνειες

                                  Υπογραφές μιας χρήσης. Αδιαμφισβήτητες υπογραφές, υπογραφές Fail-Stop

                                  Διαφάνειες (19-20, 23-31)