Υπολογιστική Κρυπτογραφία
Section outline
-
Χειμερινό Εξάμηνο 2018-2019
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Αν. Καθηγητής (pagour@cs.ntua.gr)
- Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Παναγιώτης Γροντάς, Υ.Δ. (pgrontas@gmail.com)
- Γιάννης Παπαϊωάννου, Υ.Δ. (ipap@corelab.ntua.gr)
Διαλέξεις:
- Τρίτη 17:45-19:30 (αίθουσα 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων)
- Παρασκευή 16:15-18:00 (αίθουσα 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων)
Έναρξη: Τρίτη, 2 Οκτωβρίου 2018
-
ΤΡΙΤΗ 2/10
- Διαδικαστικά.
- Εισαγωγή.
- Στόχοι της Κρυπτογραφίας.
- Επισκόπηση βασικών λειτουργιών και πρωτοκόλλων.
ΠΑΡΑΣΚΕΥΗ 5/10
- Κλασικά συστήματα (αντικατάστασης, Καίσαρα, Vigenere cipher) και κρυπτανάλυσή τους.
- Δείκτης σύμπτωσης (Coincidence Index).
- Τέλεια μυστικότητα (perfect secrecy). Ισοδύναμες συνθήκες. Random Shift cipher.
Προτεινόμενη μελέτη:
- [ΖΠΓ]: κεφ. 1 (έως και 1.4.3)
- [BoSh]: κεφ. 2.2
[ΖΠΓ]: Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς: Υπολογιστική Κρυπτογραφία, Κάλλιπος, 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, κατεβάστε την τελευταία έκδοση) -
ΤΡΙΤΗ 9/10
- One-time pad. Μήκος κλειδιού για perfect secrecy.
- Unicity distance
- Ορισμοί ασφάλειας, υπολογιστική ασφάλεια.
- Κρυπτοσυστήματα ρεύματος (εισαγωγή). Κρυπτοσυστήματα μετάθεσης και γινομένου.
- Ασύμμετρη κρυπτογραφία: κρυπτοσύστημα Merkle-Hellman, επίθεση Shamir.
Προτεινόμενη μελέτη: [ΖΠΓ] 1.4, 5.7 (έως 5.7.3, συνοπτικά), 6.3
ΠΑΡΑΣΚΕΥΗ 12/10
- Εισαγωγή στη Θεωρία Αριθμών. Διαιρετότητα, ιδιότητες ΜΚΔ.
- Ευκλείδειος αλγόριθμος, υπολογισμός αντιστρόφου modulo n.
- Αριθμητική υπολοίπων, ο δακτύλιος Zm. Πρώτοι και σχετικά πρώτοι αριθμοί.
- Συνάρτηση φ του Euler. Θεωρήματα Fermat (μικρό) και Euler.
Προτεινόμενη μελέτη: [ΖΠΓ] 2.1
- One-time pad. Μήκος κλειδιού για perfect secrecy.
-
ΤΡΙΤΗ 16/10
- Κινέζικο θεώρημα υπολοίπων
- Θεωρία ομάδων, τάξη στοιχείου και ομάδας, κυκλικές ομάδες, γεννήτορες
- Σύμπλοκα, ομάδα πηλίκο, Θεώρημα Lagrange
- Έλεγχος πρώτων με θεώρημα του Fermat
Προτεινόμενη μελέτη: [ΖΠΓ] 2.2, 2.3ΠΑΡΑΣΚΕΥΗ 19/10- Η δομή της ομάδας Z*p
- Η δομή της ομάδας U(Zpq)
- Τετραγωνικά Υπόλοιπα, τετραγωνικές ισοτιμίες, κριτήριο Euler
- Σύμβολα Legendre και Jacobi
- Ευεπίλυτα και δυσεπίλυτα αριθμοθεωρητικά προβλήματα
Προτεινόμενη μελέτη: [ΖΠΓ] 2.4, [LK2] 7.1-7.3 (συμπληρωματικά)
- Κινέζικο θεώρημα υπολοίπων
-
ΤΡΙΤΗ 23/10
- Κρυπτοσυστήματα τμήματος.
- Δίκτυα Feistel.
- Κρυπτοσύστημα DES, S-boxes, MITM attack.
- Βελτιώσεις: 3-DES, DES-X.
- Τρόποι λειτουργίας block ciphers: ECB, CBC, CFB, OFB, CTR.
Προτεινόμενη μελέτη: [ΖΠΓ] 5.1-5.3
ΠΑΡΑΣΚΕΥΗ 26/10
- Κρυπτοσύστημα AES.
Προτεινόμενη μελέτη: [ΖΠΓ] 5.4-5.6
- Εισαγωγή στην ψευδοτυχαιότητα.
Προτεινόμενη μελέτη: [LK2] 3.3
- Κρυπτοσυστήματα τμήματος.
-
ΤΡΙΤΗ 30/10
- Ορισμός κρυπτοσυστήματος
- Δυνατότητες αντιπάλου - Επιθέσεις
- Εμπειρική ασφάλεια (Kerckhoffs) - Σημασιολογική ασφάλεια - Μη διακρισιμότητα
- Γενική μορφή κρυπτογραφικών αναγωγών
- Ανταλλαγή κλειδιού Diffie - Hellman
Slides: Lec 5
Προτεινόμενη μελέτη:
[ΖΠΓ]: Ενότητες 1.3, 1.4, 6.5.1
[LK2]: Ενότητες 1.4, 3.1, 3.2, 3.4, 3.7 8.3.2, 10.3, 10.4
ΠΑΡΑΣΚΕΥΗ 2/11
- Ψευδοτυχαιότητα
- Η γεννήτρια Blum-Blum-Shub
- Κρυπτοσυστήματα ροής
- Η γεννήτρια RC4
- Καταχωρητές γραμμικής ανάδρασης (LFSR)
Προτεινόμενη μελέτη: [LK2] 3.3, [BoSh] 3.1, 3.2, 3.9, 3.10, [ΖΠΓ] 5.7
-
ΤΡΙΤΗ 6/11
- Παραγοντοποίηση, πρώτοι αριθμοί, πυκνότητα πρώτων
- Έλεγχοι πρώτων αριθμών Fermat & Miller-Rabin, αριθμοί Carmichael
Προτεινόμενη μελέτη: [ΖΠΓ] 4.5 (όχι AKS)
ΠΑΡΑΣΚΕΥΗ 9/11
- Το πρόβλημα της παραγοντοποίησης
- Μέθοδος rho, μέθοδος Dixon
Προτεινόμενη μελέτη: [ΖΠΓ] 4.6
- Μονόδρομες συναρτήσεις
- Συναρτήσεις σύνοψης
Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.1-8.3
-
ΤΡΙΤΗ 20/11 - RSA
- Κρυπτογραφία Δημοσίου Κλειδιού
- Ορισμός RSA
- Αριθμοθεωρητικές επιθέσεις
- Μοντελοποίηση - Ιδιότητες Ασφάλειας
- Παραλλαγές για IND-CPA, IND-CCA
Προτεινόμενη μελέτη:
[ΖΠΓ]: Ενότητες 6.1, 6.2, 6.4
[LK2]: Ενότητες 11.1, 11.2, 11.5.1, 11.5.2, 11.5.4, 11.5.6
ΠΑΡΑΣΚΕΥΗ 23/11 - MAC
- Ακεραιότητα / γνησιότητα μηνύματος (MAC)
- HMAC
- Authenticated encryption
Προτεινόμενη μελέτη: [BoSh] 8.7, 9.1-9.4 (συνοπτικά)
-
ΤΡΙΤΗ 27/11 - ΚΡΥΠΤΟΣΥΣΤΗΜΑΤΑ ΔΙΑΚΡΙΤΟΥ ΛΟΓΑΡΙΘΜΟΥ
- Διακριτός Λογάριθμος: Προβλήματα και Αλγόριθμοι
- Το κρυπτοσύστημα ElGamal (Ορισμός, Ασφάλεια,
- Παραλλαγές)
- Σχήματα Δέσμευσης με βάση το DLP
- Διαμοιρασμός απορρήτων - Shamir Secret Sharing -
- Threshold ElGamal
Προτεινόμενη μελέτη:
[ΖΠΓ]: Ενότητες 6.5, 9.2, 9.3
[LK2]: Ενότητες 9.2.1, 9.2.2, 11.4.1, 11.4.2, 11.4.4, 13.3
ΠΑΡΑΣΚΕΥΗ 30/11 - Επίλυση-Συζήτηση 1ης, 2ης σειράς ασκήσεων
- Διακριτός Λογάριθμος: Προβλήματα και Αλγόριθμοι
-
ΤΡΙΤΗ 04/12 - ΑΠΟΔΕΙΞΕΙΣ ΜΗΔΕΝΙΚΗΣ ΓΝΩΣΗΣ
- Εισαγωγή - Διαισθητικά παραδείγματα
- Ορισμός - Εφαρμογές στην Θ. Πολυπλοκότητας - Παραλλαγές
- Σ-πρωτόκολλα
- Witness Indistinguishable & Witness Hiding Πρωτόκολλα
Προτεινόμενη μελέτη:
[ΖΠΓ]: Κεφάλαιο 10
ΠΑΡΑΣΚΕΥΗ 7/12 - ΨΗΦΙΑΚΕΣ ΥΠΟΓΡΑΦΕΣ
- Ορισμός - Μοντελοποίηση Ασφάλειας
- Ψηφιακές Υπογραφές RSA και ElGamal-DSA
- Υπογραφές μιας χρήσης
- Τυφλές υπογραφές
- Αδιαμφισβήτητες υπογραφές, υπογραφές Fail-Stop (σύντομη αναφορά)
Προτεινόμενη μελέτη:
[ΖΠΓ]: Κεφ. 7 (έως και 7.6.2)
-
ΤΡΙΤΗ 11/12 - ΕΛΛΕΙΠΤΙΚΕΣ ΚΑΜΠΥΛΕΣ & PAIRINGS
- Ελλεπτικές καμπύλες - Μαθηματικό υπόβαθρο
- Κρυπτογραφικά πρωτόκολλα
- Pairings
- Εφαρμογές Pairings στην κρυπτογραφία
Προτεινόμενη μελέτη:
[ΖΠΓ]: Ενότητες 12.2, 12.3
[LK2]: 8.3.4
ΠΑΡΑΣΚΕΥΗ 14/12 - ΕΦΑΡΜΟΓΕΣ HASH FUNCTIONS- Δέσμευση, απόκρυψη
- Ρίψη νομίσματος
- Χρονοσήμανση
- Αποθήκευση password, αλάτι
- Proof-of-Work
- Δέντρα Merkle
Slides
Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 8.4-8.6 -
ΤΡΙΤΗ 18/12 - CRYPTOGRAPHIC VOTING
- Απαιτήσεις ηλεκτρονικών ψηφοφοριών
- Ομομορφικά συστήματα
- (Επαληθεύσιμα) Δίκτυα Μίξης
- Ψηφοφορίες με τυφλές υπογραφές
- Ανοιχτά Θέματα
ΠΑΡΑΣΚΕΥΗ 21/12 - BLOCKCHAIN & ΚΡΥΠΤΟΝΟΜΙΣΜΑΤΑ
- Εισαγωγή σε Blockchain & Consensus
- Εισαγωγή στο Bitcoin (transactions, blocks, proof-of-work)
Slides (δείτε και www.blockchain-course.org)
- Απαιτήσεις ηλεκτρονικών ψηφοφοριών