Υπολογιστική Κρυπτογραφία
Section outline
-
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)
- Παναγιώτης Γροντάς, Μεταδιδάκτορας (pgrontas@mail.ntua.gr)
Βοηθοί Διδασκαλίας:
- Θωμάς Σουλιώτης, Υ.Δ.
- 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, κατεβάστε την τελευταία έκδοση) -
ΤΡΙΤΗ 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
-
ΤΡΙΤΗ 11/10
- Επανάληψη τέλειας μυστικότητας
- Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
- Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.
- Μοντέλα και ορισμοί ασφάλειας
- Τύποι επιθέσεων
- Παίγνια Μη Διακρισιμότητας
- Γενική μορφή κρυπτογραφικών αναγωγών
- Ανάλυση ασφάλειας ανταλλαγής κλειδιού 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
-
ΤΡΙΤΗ 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).
- Κινέζικο Θεώρημα Υπολοίπων
- Τετραγωνικά Υπόλοιπα
Προτεινόμενη μελέτη: [ΖΠΓ] 2.3, 2.4, [LK2] 8.1-8.3 (συμπληρωματικά)
- Θεωρία ομάδων, τάξη στοιχείου και ομάδας, κυκλικές ομάδες, γεννήτορες.
-
ΤΡΙΤΗ 25/10
- Tετραγωνικές ρίζες modulo n και παραγοντοποίηση
- Σύμβολο Legendre
- Σύμβολο Jacobi
- Έλεγχος πρώτων αριθμών Miller-Rabin
- Ευεπίλυτα και Δυσεπίλυτα αριθμητικά προβλήματα
Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, 4.5, 4.6, 4.7 [LK2] 8.2.2 (συμπληρωματικά)ΠΑΡΑΣΚΕΥΗ 28/10
Επέτειος 28ης ΟΚΤΩΒΡΙΟΥ - Δεν έγινε μάθημα
-
ΤΡΙΤΗ 1/11
- Κρυπτοσυστήματα τμήματος.
- Δίκτυα Feistel.
- Κρυπτοσύστημα DES, S-boxes, MITM attack.
- Βελτιώσεις: 3-DES, DES-X.
Προτεινόμενη μελέτη: [ΖΠΓ] 5.1-5.3ΠΑΡΑΣΚΕΥΗ 4/11
- Τρόποι Λειτουργίας του DES
- Το κρυπτοσύστημα AES
Προτεινόμενη μελέτη: [ΖΠΓ] 5.3 - 5.6 - Κρυπτοσυστήματα τμήματος.
-
ΤΡΙΤΗ 8/11
- Αλγεβρική περιγραφή του AES
Δείτε και στο επίσημο site του NIST.
Δεν έγινε η 2η ώρα λόγω συνέλευσης των φοιτητών.ΠΑΡΑΣΚΕΥΗ 11/11- Γεννήτριες Ψευδοτυχαιότητας
- Ψευδοτυχαίες συναρτήσεις και μεταθέσεις
- Blum-Blum-Shub
- Κρυπτοσυστήματα ροής
- RC4
- Καταχωρητές Ολίσθησης Γραμμικής Ανάδρασης
- eStream
Slides: Stream CiphersΠροτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3) -
ΤΡΙΤΗ 15/11Δεν έγινε μάθημα λόγω των εκδηλώσεων για την επέτειο του Πολυτεχνείου.ΠΑΡΑΣΚΕΥΗ 18/11 - Συναρτήσεις Σύνοψης
- Μονόδρομες Συναρτήσεις
- Συναρτήσεις Σύνοψης
- Παράδοξο - Επιθέσεις Γενεθλίων
Slides: Hash Functions (1-18)
Προτεινόμενη Μελέτη: [ΖΠΓ] 6.1, 8.1- 8.2, [LK2] 5.1, 5.4.1
-
ΤΡΙΤΗ 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)
-
ΤΡΙΤΗ 29/11
Το κρυπτοσύστημα RSA
- Επανάληψη ορισμού
- Παρατηρήσεις (Επιλογή p, q, e) - Επιτάχυνση Αποκρυπτογράφησης
- Σχετικά δύσκολα προβλήματα και αναγωγές μεταξύ τους
- Αριθμοθεωρητικές Επιθέσεις
- Έλλειψη IND-CPA, IND-CCA. Malleability
Slides: RSA 17-40,45,46
Προαιρετική μελέτη:
- 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)
ΠΑΡΑΣΚΕΥΗ 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
-
ΤΡΙΤΗ 6 / 12
Δεν έγινε μάθημα στη σχολή.
Προαιρετική μελέτη:
- Dan Boneh, 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
-
ΤΡΙΤΗ 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).
-
ΤΡΙΤΗ 20/12
- Blockchain - Consensus
- Εισαγωγή στο bitcoin
Προτεινόμενη μελέτη: [ΖΠΓ] 11.3 - 11.4
Διαφάνειες: Blockchain-Consensus και Bitcoin (Δ.Ζήνδρος)
Προαιρετική μελέτη: Bitcoin's Academic Pedigree, Arvind Narayanan and Jeremy Clark
-
ΤΡΙΤΗ 10.01.2023
Κρυπτοψηφοφορίες
- Απαιτήσεις ηλεκτρονικών ψηφοφοριών
- Ομομορφικά συστήματα
- (Επαληθεύσιμα) Δίκτυα Μίξης
- Ψηφοφορίες με τυφλές υπογραφές
- Ανοιχτά Θέματα
Μελέτη: [ΖΠΓ] 11.1μ [LK2] 13.3.3
Προαιρετική Μελέτη: [1707.08619] Public Evidence from Secret Ballots (arxiv.org)
ΠΑΡΑΣΚΕΥΗ 13.01.2023
Ελλειπτικές Καμπύλες
- Μαθηματικό υπόβαθρο
- Κρυπτογραφικά πρωτόκολλα βασισμένα σε ελλειπτικές καμπύλες
- Pairing-Based Crypto και εφαρμογές
-
ΤΡΙΤΗ 17/1
Εξέταση ασκήσεωνΠΑΡΑΣΚΕΥΗ 20/1
Εξέταση ασκήσεων