Υπολογιστική Κρυπτογραφία
Section outline
-
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)
- Παναγιώτης Γροντάς, Μεταδιδάκτορας (pgrontas@mail.ntua.gr)
- Νίκος Λεονάρδος, Επ. Καθηγητής (υπό διορισμό) (nleon@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Θωμάς Σουλιώτης, Υ.Δ.
- 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, κατεβάστε την τελευταία έκδοση) -
ΤΡΙΤΗ 3/10
- Διαδικαστικά Μαθήματος
- Επισκόπηση αρχών και εφαρμογών της σύγχρονης κρυπτογραφίας.
ΠΑΡΑΣΚΕΥΗ 6/10
- Κλασικά συστήματα (αντικατάστασης, Καίσαρα, Vigenere cipher) και κρυπτανάλυσή τους.
- Δείκτης σύμπτωσης (Coincidence Index).
- Τέλεια μυστικότητα κατά Shannon.
Διαφάνειες διάλεξης (σελ. 1-20)
Προτεινόμενη μελέτη:
- [ΖΠΓ]: κεφ. 1.4.3
- [LK2]: κεφ. 2
-
ΤΡΙΤΗ 10/10
- Τέλεια Μυστικότητα
- Κρυπτοσυστήματα ρεύματος, μετάθεσης και γινομένου.
- Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα "σακιδίου" Merkle-Hellman, επίθεση Shamir.
Προτεινόμενη μελέτη:
- [ΖΠΓ] κεφ 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
-
ΤΡΙΤΗ 17/10
Διαφάνειες διάλεξης (21-32)- Σύμπλοκα, ομάδα πηλίκο, θεώρημα Lagrange
- Έλεγχος πρώτων με θεώρημα του Fermat
- Κινέζικο Θεώρημα Υπολοίπων
- Η δομή των ομάδων Z*p και U(Zpq)
Προτεινόμενη μελέτη: [ΖΠΓ] 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 (συμπληρωματικά) -
ΤΡΙΤΗ 24/10
- Κρυπτοσυστήματα τμήματος (block ciphers).
- Δίκτυα Feistel.
- Κρυπτοσύστημα DES, S-boxes, MITM attack.
- Βελτιώσεις: 3-DES, DES-X.
Διαφάνειες διάλεξης (1-13)Προτεινόμενη μελέτη: [ΖΠΓ] 5.1-5.3ΠΑΡΑΣΚΕΥΗ 27/10
Επέτειος 28ης ΟΚΤΩΒΡΙΟΥ - Δεν έγινε μάθημα
- Κρυπτοσυστήματα τμήματος (block ciphers).
-
ΤΡΙΤΗ 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
Διαφάνειες διάλεξης (1-36)Προτεινόμενη Μελέτη: [ΖΠΓ] 5.7 (έως και 5.7.3) -
ΤΡΙΤΗ 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
- Γεννήτρια Blum-Blum-Shub (επανάληψη)
-
ΤΡΙΤΗ 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
Επέτειος Πολυτεχνείου.
-
ΤΡΙΤΗ 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
Προαιρετική μελέτη:
- 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)
-
ΤΡΙΤΗ 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
Προαιρετική μελέτη:
- Dan Boneh, 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Προαιρετική μελέτη:
- Pairings For Beginners (Craig Costello)
- Elliptic Curve Cryptography in Practice
Περί των ελλειπτικών Καμπυλών NIST.
https://words.filippo.io/
dispatches/seeds-bounty/
-
ΤΡΙΤΗ 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
Προαιρετική Μελέτη:
-
ΤΡΙΤΗ 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
Δεν έγινε μάθημα.
-
ΤΡΙΤΗ 19.12.2023
Ψηφιακές Υπογραφές (Μέρος 2ο)
- Ψηφιακές Υπογραφές Διακριτού Λογαρίθμου (ElGamal, Schnorr, ECDSA, EdDSA)
- Λύσεις στο πρόβλημα αυθεντικότητας κλειδιών
- Ψηφιακές Υπογραφές με ιδιωτικότητα
Μελέτη: [LK2] 10.4, 12.5,
Προαιρετική Μελέτη
- [PS00] Security Arguments for Digital Signatures and Blind Signatures | Journal of Cryptology
- Multi-signatures in the plain public-Key model and a general forking lemma
- ECDSA Biased Nonces, Χρόνης Σαπουντζάκης
ΠΑΡΑΣΚΕΥΗ 22.12.2023
Κρυπτοψηφοφορίες
- Απαιτήσεις ηλεκτρονικών ψηφοφοριών
- Ομομορφικά συστήματα
- (Επαληθεύσιμα) Δίκτυα Μίξης
- Ψηφοφορίες με τυφλές υπογραφές
- Ανοιχτά Θέματα
Μελέτη: [ΖΠΓ] 11.1 [LK2] 13.3.3
Προαιρετική Μελέτη: [1707.08619] Public Evidence from Secret Ballots
-
ΤΡΙΤΗ 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