Weekly outline

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

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

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

  • Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
  • Νίκος Λεονάρδος, Επίκ. Καθηγητής (nleon@cs.ntua.gr)
  • Παναγιώτης Γροντάς, Μεταδιδάκτορας (pgrontas@corelab.ntua.gr)

  
  

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

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

  • Ανακοινώσεις Forum
  • Βιβλιογραφία - Υλικό - Σύνδεσμοι Page
  • Ασκήσεις - Assignments Folder
  • Βιβλία - σημειώσεις Folder
  • Υποβολή 1ης σειράς ασκήσεων Assignment
  • Υποβολή 2ης σειράς ασκήσεων Assignment
  • Υποβολή 3ης σειράς ασκήσεων Assignment
• Εβδομάδα 1η
  

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

  
  
• Εβδομάδα 2η
  

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

  Εβδομάδα 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
  • Ευεπίλυτα και Δυσεπίλυτα αριθμητικά προβλήματα

  
  

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

  
  

    Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, 4.5, 4.7 

    Συμπληρωματική μελέτη: [LK2] Appendix B

                                         [BoSh] Appendix A
• Εβδομάδα 4η
  

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

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

  
  
• Εβδομάδα 6η
  

  Εβδομάδα 6η

  ΤΡΙΤΗ 5/11
  

  
  

  • Γεννήτριες Ψευδοτυχαιότητας
  • Ψευδοτυχαίες συναρτήσεις και μεταθέσεις

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

  
  

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

  Συμπληρωματική μελέτη: Boaz Barak notes, [LK2, ch3], [BoSh, ch3]
  

  
  

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

  
  

  • Γεννήτριες Ψευδοτυχαιότητας (επανάληψη)
    
  • Κατασκευή κρυπτοσυστήματος από γεννήτρια ψευδοτυχαιότητας
  • Απόδειξη μη διακρισιμότητας
    

  Διαφάνειες διάλεξης (17-24)

  
  

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

  Συμπληρωματική μελέτη: Boaz Barak notes, [LK2, ch3], [BoSh, ch3]
• Εβδομάδα 7η
  

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

  Επέτειος Πολυτεχνείου
  
• Εβδομάδα 8η
  

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

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

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

  • Factorization of a 768-bit RSA modulus (iacr.org)
    
  • Dan Boneh, Twenty Years of Attacks on the RSA Cryptosystem (nmsu.edu)
    
  • Alexander May, Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring, (pdf)
  • Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter, Ron was wrong, Whit is right, (pdf)

  
  
• Εβδομάδα 10η
  

  Εβδομάδα 10η

  ΤΡΙΤΗ 3/12/24

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

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

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

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

  Αναβολή μαθήματος.
  
• Εβδομάδα 11η
  

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

  Εβδομάδα 12η

  ΤΡΙΤΗ 17/12/2024

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

  Slides: ZK  (1-45)

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

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

  • Zero Knowledge Proofs — A Primer
  • To Schnorr and beyond
  • Zero Knowledge Proofs: An illustrated primer
  • 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

  
  

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

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

  Slides: ZK  (46-51)
  

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

  • Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols | SpringerLink

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

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

  Slides: DS (1-32)
  

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

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

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