Section outline

  • Collapse Expand

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

    Collapse all Expand all

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


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

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


    Επικοινωνία: crypto@corelab.ntua.gr


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

    • Τρίτη 15:30-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

    Εβδομάδα 2/10-6/10


    ΤΡΙΤΗ 3/10

    • Διαδικαστικά Μαθήματος
    • Επισκόπηση αρχών και εφαρμογών της σύγχρονης κρυπτογραφίας.

    Διαφάνειες διάλεξης


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

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

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

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

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

  • Collapse Expand

    Εβδομάδα 9/10-13/10

    ΤΡΙΤΗ 10/10

    • Τέλεια Μυστικότητα
    • Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
    • Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.
     Διαφάνειες Διάλεξης (σελ. 20-45)

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

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

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

    • Russell Impagliazzo, A Personal View of Average-Case Complexity, (pdf).


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

    Εισαγωγή στη Θεωρία Αριθμών

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


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

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

  • Collapse Expand

    Εβδομάδα 16/10-20/10

    ΤΡΙΤΗ 17/10

    • Σύμπλοκα, ομάδα πηλίκο, θεώρημα Lagrange
    • Έλεγχος πρώτων με θεώρημα του Fermat
    • Κινέζικο Θεώρημα Υπολοίπων
    • Η δομή των ομάδων Z*p και U(Zpq)

      Διαφάνειες διάλεξης (21-32)

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


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

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


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

  • Collapse Expand

    Εβδομάδα 23/10-27/10

    ΤΡΙΤΗ 24/10

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


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


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

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

  • Collapse Expand

    Εβδομάδα 30/10 - 03/11

    ΤΡΙΤΗ 31/10

    • Τρόποι λειτουργίας των blockciphers
    • Το κρυπτοσύστημα AES
    • Αλγεβρική περιγραφή του AES


    Διαφάνειες διάλεξης (14-25)

    Συμπληρωματικά: Raj Jain, Washington University in Saint Louis, και περιγραφή του AES στο επίσημο site του NIST.

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

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

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



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

  • Collapse Expand

    Εβδομάδα 6/11 - 10/11


    ΤΡΙΤΗ 7/11

    • Γεννήτρια Blum-Blum-Shub (επανάληψη)
    • Καταχωρητές Ολίσθησης Γραμμικής Ανάδρασης
    • eStream
    • Συναρτήσεις μονής κατεύθυνσης
    • Συναρτήσεις σύνοψης
    • Ασφάλεια συνάρτησης Chaum-van Heijst-Pfitzman

    Διαφάνειες διάλεξης: Stream Ciphers (37-42), Hash Functions (1-13)

    Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3), [ΖΠΓ] 6.1, 8.1- 8.2, [LK2] 7.1, 5.1


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

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


    Διαφάνειες διάλεξης: Hash Functions (14-32)

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






  • Collapse Expand

    Εβδομάδα 13/11 - 17/11


    ΤΡΙΤΗ 14/11 - Εφαρμογές Συναρτήσεων Σύνοψης

    • Σχήματα δέσμευσης
    • Ασφαλής αποθήκευση κωδικών
    • Timestamping
    • Proof-of-Work, δένδρα Merkle


    Διαφάνειες: Hash Applications

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


    • Message Authentication Codes
    • MAC με hash functions (HMAC)


    Διαφάνειες: MAC

    Προτεινόμενη μελέτη: [BoSh] 8.7, 9.1-9.4 (συνοπτικά)


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

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

  • Collapse Expand

    Εβδομάδα 21/11 - 24/11

    ΤΡΙΤΗ 21/11

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

    Διαφάνειες Διάλεξης

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

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

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

    Διαφάνειες Διάλεξης (1-37) - Κώδικας Sage

    [ΖΠΓ] 6.4, [LK2] 11.5.1, 11.5.2, 11.5.4, 11.5.6, [BoSh] 10.3

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


  • Collapse Expand

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

    ΤΡΙΤΗ 28/11/23

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

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

    Διαφάνειες Διάλεξης (38-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)

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

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

    Slides DLP (1-20)

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

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

    • The Decision Diffie-Hellman Problem (pdf)

     

    ΠΑΡΑΣΚΕΥΗ 01/12/23

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

    • Ευκολία DDHP στο Z_p^* (διευκρινίσεις)
    • Ελλειπτικές Καμπύλες
    • Pairings
    • Τριμερής Ανταλλαγή Κλειδιού

    Slides DLP (21-56)

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

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



  • Collapse Expand

    Εβδομάδα 5/12-8/12

    ΤΡΙΤΗ 05/12/2023

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

    Slides: DLP (57-96)

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

    ΠΑΡΑΣΚΕΥΗ 08/12/2023

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

    Slides: ΖΚ (1-43)

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

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




  • Collapse Expand

    Εβδομάδα 12/12-15/12

    ΤΡΙΤΗ 12/12/2023

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

    Διαφάνειες: ZK (44-53)

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

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

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

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

    Διαφάνειες

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

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


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

    Δεν έγινε μάθημα.


  • Collapse Expand

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


    ΤΡΙΤΗ 19.12.2023

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

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

    Διαφάνειες

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

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

    ΠΑΡΑΣΚΕΥΗ 22.12.2023

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

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

    Διαφάνειες

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

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





  • Collapse Expand

    Εβδομάδα 8/1-12/1

    ΤΡΙΤΗ 9/1/2024

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

    Διαφάνειες

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

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