Section outline

  • Collapse Expand

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

    Collapse all Expand all

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


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

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

  • Collapse Expand

    Εβδομάδα 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).

  • Collapse Expand

    Εβδομάδα 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

  • Collapse Expand

    Εβδομάδα 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

  • Collapse Expand

    Εβδομάδα 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η σειρά ασκήσεων
    • Σύντομη επανάληψη θεωρίας αριθμών

  • Collapse Expand

    Εβδομάδα 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)

  • Collapse Expand

    Εβδομάδα 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]
  • Collapse Expand

    Εβδομάδα 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 

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

  • Collapse Expand

    Εβδομάδα 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

  • Collapse Expand

    Εβδομάδα 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

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


  • Collapse Expand

    Εβδομάδα 10η

    ΤΡΙΤΗ 3/12/24

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

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

    Διαφάνειες Διάλεξης (26-44) 

    ΠΑΡΑΣΚΕΥΗ 6/12/24

    Αναβολή μαθήματος.

  • Collapse Expand

    Εβδομάδα 11η

    ΤΡΙΤΗ 10/12/2024

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

    • Padding RSA
    • Η επίθεση του Bleichenbacher
    • RSA - OAEP

    Διαφάνειες (45-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)


    ΠΑΡΑΣΚΕΥΗ 13/12/2024

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

    • Το κρυπτοσύστημα El Gamal (Ιδιότητες Ασφάλειας - Malleability)
    • Σχήματα δέσμευσης με βάση το DLP
    • Secret Sharing

    Διαφάνειες: DLP (16-30 και 36-55)

  • Collapse Expand

    Εβδομάδα 12η

    ΤΡΙΤΗ 17/12/2024

    • Αποδείξεις μηδενικής γνώσης: Διαισθητικά Παραδείγματα - Ορισμός
    • Παραδείγματα από Θ. Πολυπλοκότητας
    • Πρωτόκολλο Schnorr

    Slides: ZK  (1-45)

    Μελέτη [ΖΠΓ] 10.1 - 10.3 [BoSh] 19.1, 19.4, 19.6

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


    ΠΑΡΑΣΚΕΥΗ 20/12/2024

    • Το Σ-πρωτόκολλο Chaum - Pedersen
    • Σύνθεση Σ-πρωτοκόλλων (AND, EQ, OR)

    Slides: ZK  (46-51)

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

    Ψηφιακές Υπογραφές

    • Μοντέλα Ασφάλειας
    • Υπογραφές RSA - FDH
    • To μοντέλο του τυχαίου μαντείου

    Slides: DS (1-32)

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

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

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


  • Collapse Expand

    Εβδομάδα 13η

    Ψηφιακές Υπογραφές (Μέρος 2ο)

    • Ψηφιακές Υπογραφές Διακριτού Λογαρίθμου (ElGamal, Schnorr, ECDSA)
    • Ψηφιακές Υπογραφές με ιδιωτικότητα
    Διαφάνειες


    Μελέτη: [LK2] 10.4, 12.5

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


    Blockchain (εκτός ύλης)

    • Ορισμός μοντέλου bitcoin.
    • Ορισμός ιδιοτήτων: common prefix, chain quality, chain growth.
    • Ορισμός τυχαίων μεταβλητών και απόδειξη λήμματος common prefix.

    Διαφάνειες