Topic outline

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

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


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

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


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

    • Τρίτη 12:45-15:00, Αμφ. 4, Νέο Κτ. Ηλεκτρολόγων ΕΜΠ 
    • Παρασκευή 16:15-18:00, Αμφ. 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, κατεβάστε την τελευταία έκδοση)

  • Εβδομάδα 3/10-7/10


    ΤΡΙΤΗ 4/10

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

         

     Slides: Introduction (1-40) & Classical Cryptosystems (1-19)

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

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

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

    • Επανάληψη κρυπτογράφησης και κρυπτανάλυσης Vigenere.
    • Τέλεια μυστικότητα κατά Shannon. Ισοδύναμες συνθήκες. Random Shift cipher.  

    Slides: Classical Cryptosystems (10-25)

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

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



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

      ΤΡΙΤΗ 11/10

      • Επανάληψη τέλειας μυστικότητας
      • Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
      • Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.
      Slides: Classical Cryptosystems (20-39)

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


      Slides: Formal Models (1-48)

      Προτεινόμενη μελέτη: [ΖΠΓ] 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.
      • Russell Impagliazzo, A Personal View of Average-Case Complexity, (pdf).
      • Neil Koblitz, Alfred Menezes, Another Look at “Provable Security”, (pdf).
      • Ivan Damgard, A proof reading of some issues in cryptography, (pdf).


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

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


      Slides: Number Theory (1-15)

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

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

        ΤΡΙΤΗ 18/10

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


          Slides: Number Theory (16-24)

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


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

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


          Slides: Number Theory (25-33)

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

        • Εβδομάδα 24/10-28/10

          ΤΡΙΤΗ 25/10

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

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

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

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

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

            ΤΡΙΤΗ 1/11

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


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

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

            • Τρόποι Λειτουργίας του DES
            • Το κρυπτοσύστημα AES


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


            • Εβδομάδα 7/11 - 11/11

              ΤΡΙΤΗ 8/11

              • Αλγεβρική περιγραφή του AES

              Δείτε και στο επίσημο site του NIST.

              Δεν έγινε η 2η ώρα λόγω συνέλευσης των φοιτητών.


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

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

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






              • Εβδομάδα 14/11 - 18/11

                ΤΡΙΤΗ 15/11

                Δεν έγινε μάθημα λόγω των εκδηλώσεων για την επέτειο του Πολυτεχνείου.

                ΠΑΡΑΣΚΕΥΗ 18/11  - Συναρτήσεις Σύνοψης

                • Μονόδρομες Συναρτήσεις
                • Συναρτήσεις Σύνοψης
                • Παράδοξο - Επιθέσεις Γενεθλίων

                Slides:  Hash Functions (1-18)

                Προτεινόμενη Μελέτη: [ΖΠΓ] 6.1, 8.1- 8.2, [LK2] 5.1, 5.4.1


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

                  ΤΡΙΤΗ 22/11 - Συναρτήσεις Σύνοψης

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

                  Slides: Hash Functions (19-32)

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

                  ΠΑΡΑΣΚΕΥΗ 25/11 - Εφαρμογές Συναρτήσεων Σύνοψης - Εισαγωγή στην Κρυπτογραφία Δημοσίου Κλειδιού

                  • Σχήματα Δέσμευσης
                  • Ασφαλής αποθήκευση κωδικών
                  • Timestamping
                  • Εισαγωγή στο Proof Of Work

                  Slides: Hash Applications (Δ. Ζήνδρος)

                  • Κρυπτογραφία δημοσίου κλειδιού
                  • To κρυπτοσύστημα RSA - Απόδειξη ορθότητας
                  • Τιμές Παραμέτρων

                  Slides: RSA 1-16

                  Προαιρετική μελέτη: Factorization of a 768-bit RSA modulus (iacr.org)


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

                    ΤΡΙΤΗ 29/11

                    Το κρυπτοσύστημα RSA

                    • Επανάληψη ορισμού
                    • Παρατηρήσεις (Επιλογή p, q, e) - Επιτάχυνση Αποκρυπτογράφησης
                    • Σχετικά δύσκολα προβλήματα και αναγωγές μεταξύ τους
                    • Αριθμοθεωρητικές Επιθέσεις
                    • Έλλειψη IND-CPA, IND-CCA. Malleability

                    Slides: RSA 17-40,45,46

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


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

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

                    • Διαρροή parity - location bits και 'σπάσιμο' RSA
                    • Επιθέσεις Padding Oracle (Bleichenbacher)
                    • RSA - OAEP

                    Slides: RSA 41-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)


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

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

                    Slides: EG 1-15.

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



                    • Εβδομάδα 5/12 - 9/12

                      ΤΡΙΤΗ 6 / 12

                      Δεν έγινε μάθημα στη σχολή.

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

                      • The Decision Diffie-Hellman Problem (pdf)


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

                      • Το κρυπτοσύστημα ElGamal
                      • Το κρυπτοσύστημα Cramer-Shoup
                      • Σχήματα δέσμευσης με βάση τον διακριτό λογάριθμο
                      • Secret Sharing - Threshold ElGamal

                      Slides: EG (16-59)

                      Μελέτη: [ΖΠΓ] 6.5, 9.2, 9.3 [LK2] 11.4.1, 13.3 [BoSh] 10.6.1, 11.5, 11.6

                      • Εβδομάδα 12/12-16/12

                        ΤΡΙΤΗ 13/12/2022

                        • Ψηφιακές Υπογραφές - Ορισμός
                        • Μοντελοποίηση Ασφάλειας
                        • Ψηφιακές Υπογραφές RSA, RSA-FDH
                        • Το μοντέλου του τυχαίου μαντειου
                        • Μη πλαστογραφησιμότητα RSA-FDH στο μοντέλου του τυχαίου μαντείου
                        • Υπογραφές ElGamal

                        Slides: DS 1-42

                        Μελέτη: [ΖΠΓ] 7.1 - 7.4, [LK2] 12.1 - 12.4. 

                        Προαιρετική Μελέτη: Σημειώσεις Bellare - Rogaway για RSA-FDH και απόδειξη μη πλαστογραφησιμότητας (12.3.5 - pdf)


                        ΠΑΡΑΣΚΕΥΗ 16/12/2022

                        • Ψηφιακές Υπογραφές DSA
                        • Υποδομή Δημοσίου Κλειδιού

                        Slides: DS 43-58

                        • Αποδείξεις μηδενικής γνώσης
                        • Παραδείγματα από Θ. Πολυπλοκότητας
                        • Σ-Πρωτόκολλα
                        • Υπογραφές Schnorr

                        Slides: ZK 1-49

                        Μελέτη: [ΖΠΓ] 10.1 - 10.3.

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

                        How To Simulate It - A Tutorial on the Simulation Proof Technique (iacr.org) (Ch.1, 2, 3, 5).

                        Unifying Zero-knowledge Proofs of Knowledge - Information Security and Cryptography Research Group - ETH Zürich




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

                          ΤΡΙΤΗ 20/12

                          • Blockchain - Consensus
                          • Εισαγωγή στο bitcoin

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

                          Διαφάνειες: Blockchain-Consensus και Bitcoin (Δ.Ζήνδρος)

                          Προαιρετική μελέτη:  Bitcoin's Academic Pedigree, Arvind Narayanan and Jeremy Clark 


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

                            ΤΡΙΤΗ 10.01.2023

                            Κρυπτοψηφοφορίες

                            • Απαιτήσεις ηλεκτρονικών ψηφοφοριών
                            • Ομομορφικά συστήματα 
                            • (Επαληθεύσιμα) Δίκτυα Μίξης 
                            • Ψηφοφορίες με τυφλές υπογραφές
                            • Ανοιχτά Θέματα

                            Διαφάνειες

                            Μελέτη: [ΖΠΓ] 11.1μ [LK2] 13.3.3

                            Προαιρετική Μελέτη: [1707.08619] Public Evidence from Secret Ballots (arxiv.org)

                            ΠΑΡΑΣΚΕΥΗ 13.01.2023

                            Ελλειπτικές Καμπύλες

                            • Μαθηματικό υπόβαθρο
                            • Κρυπτογραφικά πρωτόκολλα βασισμένα σε ελλειπτικές καμπύλες
                            • Pairing-Based Crypto και εφαρμογές

                            Διαφάνειες

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



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

                              ΤΡΙΤΗ 17/1

                              Εξέταση ασκήσεων

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

                              Εξέταση ασκήσεων